CODEWITHSUNDEEP
c++c++11
lino
lino

Reputation: 287

Overloading Operator < for std::set

I have a struct called Dist,

struct Dist {
    Point firstPoint, secondPoint;
    double value;
};

struct distCompare {
    bool operator()(const Dist& x, const Dist& y) const {
        return x.value < y.value;
    }
};

and I have a set to store this Object.

std::set<Dist, distCompare> distList;

Two Dists like x and y are equal if x.firstPoint==y.firstPoint and x.secondPoint==y.secondPoint and since distCompare compares the value of two Dists, I cant use set::find like this:

for (auto q:input) {
    Dist tempDist; tempDist.firstPoint = p; tempDist.secondPoint = q;
    auto it = distList.find(tempDist);
    if (it != distList.end()) { //'it' is always distList.end() 
        distList.erase(it); 
    }
}

my Point class looks like this:

class Point {
public:
    Point(double a, double b){ x = a; y = b; }
    Point(){}
    double getX() const { return x; }
    double getY() const { return y; }
    void setX(double item){ x = item; }
    void setY(double item){ y = item; }

private:
    double x, y;
};

how can I overload operator < so that I can use set::find to find equal Dists?

Upvotes: 1

Views: 1867

Answers (1)

Jonathan Wakely
Jonathan Wakely

Reputation: 171303

std::set<T, Cmp>::find does a binary search, relying on the fact that the elements are ordered, and will always use Cmp to decide equivalence (which is not the same as than equality), so if you don't want it to find based on distCompare ... then don't use distCompare in the set!

Since the ordering defined by distCompare is completely unrelated to your definition of equality for Dist objects, there is no way to perform a fast binary search using the distCompare ordering to find objects that are considered equal by an entirely different function. You could have two elements that are "equal" according to your definition of equality, but are ordered at opposite ends of the set according to the ordering defined by distCompare.

Your options are:

  • change the comparison function for the set, so that items that compare equal also compare equivalent using the comparison function.

  • replace the set with a multi-index container, such as Boost.MultiIndex.

  • perform a linear search through the set

Upvotes: 1

Related Questions