Why stl map inserts another value if key already exist, and not just change it?

Question

Why does my program using STL maps insert values when keys already exist instead of changing the existing values?

#include <iostream>
#include <map>

using namespace std;

struct CTest
{
    int a, b, c;
    CTest(int A, int B, int C) : a(A), b(B), c(C) {}
};

bool operator<(const CTest & l, const CTest & r)
{
    if(l.a < r.a) return true;
    else if(l.a > r.a) return false;

    if(l.b < r.b) return true;
    else if(l.b > r.b) return false;

    if(l.c < r.c) return true;
    else if(l.c > r.c) return false;

    return true;
}

struct CTest2
{
    bool operator<(const CTest2 & r) const
    {
        return q < r.q && w < r.w;
    }
    int q,w;
    CTest2() : q(0), w(0) {}
    CTest2(int Q, int W) : q(Q), w(W) {}
};

int main()
{
    // map of maps
    map<CTest, map<string, CTest2> > x;

    x[CTest(1,1,1)]["lol"] = CTest2(1,2); // x[CTest(1,1,1)]["lol"] now stores CTest2(1,2)
    x[CTest(1,1,1)]["lol"] = CTest2(3,4); // CTest2(1,2) must be changed to CTest2(3,4)
    x[CTest(1,1,1)]["lol"] = CTest2(5,6); // now to CTest2(5,6)

    x[CTest(2,1,0)]["ha"] = CTest2(11,12);

    for(map<CTest, map<string, CTest2> >::iterator i = x.begin(); i != x.end(); ++i)
        for(map<string, CTest2>::iterator j = i->second.begin(); j != i->second.end(); ++j)
            cout << j->first << " " << j->second.q << " " << j->second.w << endl;
}

Running this prints:

lol 3 4
lol 1 2
ha 11 12

Why does this happen and how do I fix it?

Answer 1

The comparison function which std::map uses to sort the elements must adhere to strict weak ordering. But your implementation doesn't do it. As per your implementation, when all members (a, b, c) are equal, your operator< returns true. In other words, (1,1,1) < (1,1,1) returns true. Does it make sense? No.

An easy fix is this:

bool operator<(const CTest & l, const CTest & r)
{
    if(l.a < r.a) return true;
    else if(l.a > r.a) return false;

    if(l.b < r.b) return true;
    else if(l.b > r.b) return false;

    return l.c < r.c;
}

That is too verbose. Instead of <, if you use !=, the above will reduce to this:

bool operator<(const CTest & l, const CTest & r)
{
    if(l.a != r.a) return l.a < r.a;
    else if(l.b != r.b) return l.b < r.b;
    return l.c < r.c;
}

Well, that is still verbose, you can implement it as:

bool operator<(const CTest & l, const CTest & r)
{
   return std::tie(l.a,l.b,l.c) < std::tie(r.a,r.b,r.c);
}

The std::tie function returns std::tuple whose operator< implements strick weak ordering, so take advantage of this fact.

Answer 2

Your operator<() returns true for equal elements.

Answer 3

The code you linked has an error in operator <: it returns true when keys are equal. It gives a runtime debug assertion at 'x[CTest(1,1,1)]["lol"] = CTest2(3,4);. If you change return true; to return false; it will work as intended.

Answer 4

Your < operator for CTest is incorrect. You are returning true in cases where l's members are all equal to r's members. If l == r, how is it less than r ? Basically this means the map doesn't see each CTest(1,1,1) as equivalent, so will create a new mapping each time you assign to it.