std::map with non-unique key ordering but unique comparison

Question

Consider the following code:

#include <iostream>
#include <map>
#include <utility>


struct Key{
    int attr1, attr2;
    Key(int attr1, int attr2) : attr1(attr1), attr2(attr2) {}

    friend bool operator== (const Key& s1, const Key& s2);
    friend bool operator< (const Key& s1, const Key& s2);
};

bool operator== (const Key& s1, const Key& s2){
    return ((s1.attr1 == s2.attr1) && (s1.attr2 == s2.attr2));
}

bool operator< (const Key& s1, const Key& s2){
    return (s1.attr1 < s2.attr1);
}

int main(void){
    std::map<Key, int> mmap;
    mmap.insert(std::make_pair(Key(10, 10), 5));
    mmap.insert(std::make_pair(Key(10, 20), 5));
    std::cout << mmap.size() << std::endl;
}

The output is 1 where I would expect it to be 2. This seems to be due to only attr1 being compared in the operator<. However if I am correct, the comparison does not have to be a strong ordering, but rather having a weak ordering is sufficient. Is there some other bug here or do I have to define an operator< for which

Key1 !< Key2 && Key2 !< Key1 implies that Key1 == Key2

holds true?

Answer 1

std::map does not use operartor == at all when comparing elements. By default, and in this case, it uses std::less which uses your operator <. Since your operator < only compares attr1, and both objects have the same attr1, the are considered equivalent and thus you only have one object in the map.

To fix this you need to check both members and you can use the std::tie trick to make a tuple that does this for you like

bool operator< (const Key& s1, const Key& s2){
    return std::tie(s1.attr1, s1.attr2) < std::tie(s2.attr1, s2.attr2);
}

---

Another option is to use a std::unordered_map which uses a hashing algorithm and an equality operator. Using that you can hash attr1 only, but have the equality operator check both attr1 and attr2 to make sure a true duplicate is not added.

Answer 2

if I am correct, the comparison does not have to be a strong ordering, but rather having a weak ordering is sufficient.

You're correct.

The output is 1 where I would expect it to be 2.

You would expect wrongly because according to the weak ordering relation that you provided, those keys are considered equal.

Is there some other bug here

No.

do I have to define an operator< for which

Key1 !< Key2 && Key2 !< Key1 implies that Key1 == Key2

holds true?

If you want the operation to produce an ordering where keys are considered equal if and only if Key1 == Key2 then yes, you do need to define such operator.

Or you could use a multi-map which may contain non-unique keys.