C++ map not behaving properly

Question

I have defined my class SumClass and trying to use it in a map as shown in the code below. I have defined the required <, = and == operator.

#include <iostream>
#include <vector>
#include <map>

using namespace std;

class SumClass {
    public:
    int id;
    int sum;
    SumClass() { id = sum = 0;}
    bool operator<(const SumClass& rhs) const{
        if( (id < rhs.id) && (sum< rhs.sum)) return true;
        else return false;
    }
    bool operator==(const SumClass& rhs) const{
        //if(this == &rhs) return true;
        if( (id == rhs.id) && (sum == rhs.sum) ) return true;
        else return false;
    }
    void set(int idd, int summ) { id = idd; sum = summ; }
    SumClass& operator=(const SumClass& rhs){
        id = rhs.id;
        sum = rhs.sum;
        return *this;
    }
};

void test(){
    map<SumClass, int> m;
    SumClass temp;
    temp.set(0,3);
    m[temp] = -1;
    temp.set(-1, 3);
    m[temp] = -1;
    temp.set(-1, 2);
    m[temp] = -1;
    temp.set(0, 1);
    cout << "Test: " << m[temp] << endl;
}


int main(){
    test();
}

The output of the code above is: "Test: -1". But the expected output is "Test: 0" as the SumClass element I am trying to find is not present in the map. Can anyone please point what am I doing wrong ?

You shouldn't need `operator==`. Equality is checked in there using `operator<`. — chris, Nov 29 '12 at 17:40
@chris. I guess it will figure out "a == b" if both 'a < b' and 'b < a' returns false. Isn't it ? — Deepak Garg, Nov 29 '12 at 18:05

Robᵩ · Accepted Answer · 2012-11-29T19:00:34.293

5

Your operator< does not provide a strict weak ordering.

Try this:

bool operator<(const SumClass& rhs) const{
  return std::tie(id, sum) < std::tie(rhs.id, rhs.sum);
}

Or, if you cannot use C++11 features:

bool operator<(const SumClass& rhs) const{
  return std::make_pair(id, sum) < std::make_pair(rhs.id, rhs.sum);
}

edited Nov 29 '12 at 19:00

answered Nov 29 '12 at 17:42

Robᵩ

163,533
20
239
308

It's fine for a strict weak ordering to have distinct incomparable values; the relevant requirement is that incomparability model an equivalence relation. – ecatmur Nov 29 '12 at 17:48
@ecatmur - Thanks! I've deleted the part where I obviously didn't know what I was talking about. – Robᵩ Nov 29 '12 at 17:51
Thanks Rob, I compiled the code with make_pair and it worked fine. However I couldn't compile the code with std:tie even when I used the c++0x compiler of g++ – Deepak Garg Nov 29 '12 at 18:00
This answer is very useful, but it is not the complete solution for the problem. – Werner Henze Nov 30 '12 at 14:47

score 2 · Answer 2 · edited May 23 '17 at 12:18

2

You haven't defined the required operators; your operator< is not a strict weak ordering.

For example, (0, 0) < (1, 1), but neither (0, 0) < (0, 1) nor (0, 1) < (1, 1) holds, violating transitivity of equivalence.

See Operator< and strict weak ordering for how to write a strict weak ordering.

edited May 23 '17 at 12:18

Community

1
1

answered Nov 29 '12 at 17:43

ecatmur

152,476
27
293
366

score 0 · Answer 3 · answered Nov 29 '12 at 17:43

0

I suspect this is wrong:

 bool operator<(const SumClass& rhs) const{
        if( (id < rhs.id) && (sum< rhs.sum)) return true;
        else return false;
    }

Are they really both always going to have this relation?

answered Nov 29 '12 at 17:43

John Dibling

99,718
31
186
324

Thanks John, my understanding of strict weak ordering wasn't clear. – Deepak Garg Nov 29 '12 at 18:02

score 0 · Answer 4 · answered Nov 29 '12 at 17:45

0

map::operator[] is trying to find the value in the map. If it finds it, it returns a reference to it. If it does not find it, then it creates it. You might consider using map::find.

answered Nov 29 '12 at 17:45

Werner Henze

16,404
12
44
69

I don't understand why would it create it and even if it does, what would it do with the value ? – Deepak Garg Nov 29 '12 at 17:57
The value will be created with a standard ctor. In your case it seems to be 0 :-). It's defined this way in the C++ standard. The idea behind it is that you can insert values with 'map[key] = value', which BTW you are using in your code. The insertion into the map is done during `map[key]`, not during the `operator =`. – Werner Henze Nov 30 '12 at 12:07

C++ map not behaving properly

4 Answers4