CODEWITHSUNDEEP
c++setcompareequals
user1788477
user1788477

Reputation: 91

c++ std::set equality

I try to use a std::set in order to have unique elements in my container.

Since I have 3D objects : 

Class Object3D{  
 private:  
  float x;  
  float y;  
  float z;  
}

Those objects are equal when (A.x==B.x && A.y==B.y && A.z==B.z).
In std::set implementation a element A==B if (!(A < B) && !(B>A)).
It's impossible for my comparison... I have tried to overload == operator.
I chose set container for comparing values when I call insert(a). I was doing something like that with std::vector v and his iterator:

if(!(A).inVector()){
 v.push_back(A);
}

With

bool inVector(){
 for(itr = v.begin();itr != v.end();itr++){
  if(this->x==(*itr)->x && this->y==(*itr)->y && this->z==(*itr)->z){
   return true;
  }
 }
 return false;
}

Checking it for each object (10000-100000) is expensive in complexity.
Can someone have an idea ?

Upvotes: 8

Views: 7816

Answers (5)

Benjamin Lindley
Benjamin Lindley

Reputation: 103693

You need to provide a comparator. You don't want to implement operator<, and I agree with that decision. You shouldn't provide meaningless functions for your class just to satisfy the constraints of some container. Thankfully, you don't need operator<. But you do need a function that has behavior similar to operator<. It doesn't have to mean that one object is considered less than another. It just needs to provide a strict-weak ordering. You can give it any name you want. For example:

bool Compare_by_x_then_y_then_z(const Object3D& lhs, const Object3D& rhs)
{
    if (lhs.getX() != rhs.getX()) return lhs.getX() < rhs.getX();
    if (lhs.getY() != rhs.getY()) return lhs.getY() < rhs.getY();
    return lhs.getZ() < rhs.getZ();
}

You then provide this function to the constructor of your set:

typedef bool(*compT)(const Object3D&, const Object3D&);
std::set<Object3D,compT> objects(Compare_by_x_then_y_then_z);

Upvotes: 2

slaphappy
slaphappy

Reputation: 6999

You have to provide a comparison operator, because std::set needs it for its implementation.

A simple less-than operator would look like this:

bool Object3D::operator<(const Object3D& other) const {
    if(x != other.x) return x < other.x;
    if(y != other.y) return y < other.y;
    return z < other.z;
}

Upvotes: 1

Useless
Useless

Reputation: 67723

@OP: std::set is a unique, ordered container. It requires either an operator< or a comparator passed explicitly, which implements a strict weak ordering.

If you don't want to impose an ordering on your elements, don't use an ordered container. You can use std::unordered_set if you just want to detect uniqueness without imposing an ordering.

Upvotes: 5

Kerrek SB
Kerrek SB

Reputation: 476990

You need to implement a strict weak ordering < for your class. The easiest way is to use the lexicographic ordering provided by tuple:

#include <tuple>

class Object3D
{
public:
    bool operator<(Object3D const & rhs) const
    {
        return std::tie(x, y, z) < std::tie(rhs.x, rhs.y, rhs.z);
    }

    // ...
};

Upvotes: 7

john
john

Reputation: 8027

You must declare operator<. You can do it like this

bool operator<(const Object3D& a, const Object3D& b)
{
    if (a.x < b.x) return true;
    if (b.x < a.x) return false;
    if (a.y < b.y) return true;
    if (b.y < a.y) return false;
    if (a.z < b.z) return true;
    if (b.z < a.z) return false;
    return false;
}

It is arbitrary, but it doesn't really matter. As long as operator< gives a consistent ordering you'll be OK.

Upvotes: 1

Related Questions