std::map not removing duplicates with custom object

Question

all.

So, I have created a Comparable base class (a la Java) which does the job of overloading comparison operators in C++. Here it is:

template <class T>
class Comparable {
public:
  bool operator== (const T& rhs) const { return this->compare(rhs) == 0; }
  bool operator!= (const T& rhs) const { return !(*this == rhs); }
  bool operator<  (const T& rhs) const { return this->compare(rhs) < 0; }
  bool operator<= (const T& rhs) const { return (*this == rhs) || (*this < rhs); }
  bool operator>  (const T& rhs) const { return this->compare(rhs) > 0; }
  bool operator>= (const T& rhs) const { return (*this == rhs) || (*this > rhs); }
protected:
  virtual int compare (const T& rhs) const = 0;
};

The subclass objects have both an ID, and data that needs to be a key for sorting. I've implemented each so that objects with the same ID return 0, and if they're not the same ID, they sort according to their data. Here's an example:

int Foo::compare(const Foo& rhs) const
{
    if (_id == rhs._id)
        return 0;
    // _value is integer data; comparison should sort on this
    if (_value == rhs._value)
    {
        // OK, same data, now sort on ID's
        return _id.compare(rhs._id);
    }
    // Sort on value
    return _value - rhs._value;
}

So far, so good, I think.

However, when I attempt to store Foo objects in a std::set container, the set will NOT eliminate duplicates. That is, there will still be objects in it that contain the same ID, even though that should be considered equal.

Does anyone have any idea what is going on?

EDIT: There are a lot of questions about why the code is designed this way.

There are two conditions I need to satisfy:

1. Objects with the same ID must be considered the "same" object, regardless of value.
2. Objects that do not have the same ID must be sorted according to their value (what that value is, depends upon the type of the object).

This is because the data that creates these objects is coming from an unverified source. If that source gives data with the same ID but a different value, that's invalid data.

EDIT 2: Regarding strict weak ordering for std::map. Let's say you have two Foo objects, A and B.

If their ID's are equal, then A < B is false, and B < A is false. If their ID's are not equal, then A < B is true or false depending upon their values, and B < A is the opposite of A < B.

Should this not satisfy the strict ordering rules?

In any case, if std::set uses the less-than operator (as it does by default), shouldn't it work as designed?

EDIT 3: std::set, not std::map. That was really stupid of me. Apologies.

Answer 1

std::map does not determine duplicates via operator==. It uses operator<¹, since it needs to use that anyway to determine order. Your operator< is broken. It needs to enforce a strict weak ordering.

The way in which your comparison fails is in the following property (called transitivity). For 3 objects, if A < B and B < C, then it must be the case that A < C.

So, consider three objects, A, B and C. A.id != B.id, but A.value < B.value, so A < B. Now, C.id == B.id (therefore C.id != A.id), but C.value < A.value. So C < A, and A < B. Therefore, C should be < B. But it's not, because C.id == B.id.

One way to do that would be to define your compare function like this:

int Foo::compare(const Foo& rhs) const
{
    if (_id < rhs._id)
        return -1;
    if (rhs._id < _id)
        return 1;

    return _value - rhs._value;
}

If you cannot use that, and you cannot find some other way to enforce a proper ordering, then you simply cannot use your objects as keys in a std::map.

_{1. If rhs is not less than lhs, and lhs is not less than rhs, then it is implied that they are equal. You can also provide an alternative functor as long as it also enforces a strict weak ordering.}

Answer 2

If you don't have a strict weak ordering, you don't get to use map, and you can't complain if you do and it doesn't work. It's a precondition of map.

EDITED:

Your compare does not implement the semantics you specify - you should return 0 if _value == rhs._value in your second test.

But with that fix you still don't have a consistent ordering - see the example given by Benjamin Lindley in the comments. Essentially your ordering doesn't make sense - you either need to fix your semantics, or stop using standard library components that require a consistent ordering.