When using std::map should I overload operator== for the key type?

Question

The std::map should not have duplicated keys so how does it knows I have a duplicated key when I have a custom type, do I need do overload overload operator==? Or it will be implicitly created?

According to the documentation I only need the operator< but this is not enough to maintain the keys' unicity.

Consider this example:

class MyType{
public:
  MyType(int newId){
    id = new int;
    *id = newId;
  };
  ~MyType{
    delete id;
  }
private:
  int* id;
};

int main(){
  std::map<MyType,int> myMap;

  std::pair<std::map<MyType,int>::iterator,bool> ret;
  ret = myMap.insert ( std::pair<MyType,int>(myType(2),100) );

  if (!ret.second) {//now how can he knows that?
    std::cout << "element already existed" << endl;
  }
}

Answer 1

std::map does not care about literal unicity of the keys. It cares about keys equivalence. The keys a and b are equivalent by definition when neither a < b nor b < a is true.

Note also that std::map does not directly use operator <. std::map does not know anything about operator <. Instead std::map uses the comparison predicate, whose type is specified as the third parameter of std::map template. The default value of that parameter is std::less. Implementation of std::less delegates the comparison to operator < (unless specialized differently). This is how operator < comes into play. But you can always supply your own predicate which will not necessarily use operator <.

But in any case the key moment here is that std::map uses an ordering "less" comparison and only "less" comparison. It does not need and does not care about any "equality" comparisons.

Meanwhile, std::unordered_map would be a different story. It relies on non-ordering "equality" comparison specified by a predicate. By default it is std::equal_to. Implementation of std::equal_to delegates the call to operator == (unless specialized differently).

Answer 2

operator < is enough. Equality can be checked by testing a < b and b < a both returning false.