Why Does C++ Map Say That Struct Exists When Doesn't?

Question

I have a struct called foo, and also a map called mp, but for some reason, when I insert {5, 0, 3} and query for {5, 3, 0}, the map says that it contains {5, 3, 0} when it actually doesn't:

#include <bits/stdc++.h>

using namespace std;

struct foo {
    int v1, v2, v3;
    friend bool operator<(const foo &a, const foo &b) {
        return a.v1 < b.v1;
    }
    friend bool operator==(const foo &a, const foo &b) {
        return (a.v1 == b.v1) && (a.v2 == b.v2) && (a.v3 == b.v3);
    }
};

int main() {    
    map<foo, int> mp;
    mp[{5, 0, 3}] = 1;
    if(mp[{5, 3, 0}]) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }

    return 0;
}

Output:

YES

Does anyone know why my code is doing this? If so, what do I need to change?

Answer 1

Your comparison operator does not match your equality operator. A std::map does not use the equality operator; it uses "less than". If neither a < b nor b < a then the map considers a and b equivalent. In your case:

• foo{5, 0, 3} < foo{5, 3, 0} is false because 5 < 5 is false.
• foo{5, 3, 0} < foo{5, 0, 3} is false because 5 < 5 is false.

So the map considers these objects equivalent. So mp[{5, 3, 0}] finds the map element you just set to 1, hence it is a true value.

To get the result you want, your operator< needs to account for all three members, not just v1.

For example:

    friend bool operator<(const foo &a, const foo &b) {
        if (a.v1 != b.v1)
            return a.v1 < b.v1;
        if (a.v2 != b.v2)
            return a.v2 < b.v2;
        return a.v3 < b.v3;
    }

or (as PaulMcKenzie suggested) more simply:

    friend bool operator<(const foo &a, const foo &b) {
        return std::tie(a.v1, a.v2, a.v3) < std::tie (b.v1, b.v2, b.v3);
    }

Answer 2

int v1, v2, v3;
friend bool operator<(const foo &a, const foo &b) {
    return a.v1 < b.v1;
}

firstly, this only checks the first value. So 5,0,0 will be considered the same a 5,9,9, etc.

   if(mp[{5, 3, 0}])

This doesn't work the way you think. Operator[] will create a new entry if one doesn't exist. However as it is inserting a value of 0, your if statement is giving the result you expect, but it is not doing it in the way you expect. This kind of "side effect" is bad, this is where bugs creep in. You shoudl use methods like map.find() instead