problem with using struct as std::map key

Question

my code is like this:

struct Info { string name; int score; bool operator< (const Info &x) const { return score < x.score; } }; int main(int argc, char *argv[]) { Info a, b; a.name = "eric"; a.score = 90; b.name = "cat"; b.score = 85; map<Info, int> m; m[a] = 1; m[b] = 2; map<Info, int>::iterator it; for(it = m.begin(); it != m.end(); it++) { cout << it->first.name << endl; } return 0; }

it prints out "cat" and "eric", as expected. but how ever, when I modify it to （make a.score and b.score the same）

Info a, b; a.name = "eric"; a.score = 90; b.name = "cat"; b.score = 90;

It prints out "eric" only, there's only one element in the whole map.

question: does std::map think they are the same key? how do I make std::map think they are not the same key? I tried operator==, but not working.

john · Accepted Answer · 2020-03-26 12:58:49Z

1

They are the same key because your custom comparator uses the score as the key. Try this instead

bool operator< (const Info &x) const { return name < x.name; }

If you want the name to be the key but the map to be sorted on the score, then I'm afraid you are out of luck, because maps are sorted on the key by definition. You'll have to pick another data structure or another algorithm.

answered Mar 26, 2020 at 12:58

john

88.3k5 gold badges61 silver badges95 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

BunsenBurner Over a year ago

I want to use both name and score as key, I think I've solved it by using “ if (score == x.score) return name < x.name; else return score < x.score;”

john Over a year ago

No, that's an invalid comparison function because it doesn't impose a strict weak ordering. Try this version return score < x.score || (score == x.score && name < x.name); }

BunsenBurner Over a year ago

so what is the mechanics inside std::map? How does std::map decide if they are the same or not? I've only provided operator<(). Does map do a < b and b < a, then found out they are both true, then think a and b are the same key?

john Over a year ago

@BunsenBurner Exactly, NO, correction, if both are false they are the same key.

john Over a year ago

PS boost.org/sgi/stl/StrictWeakOrdering.html, you must have a strict weak ordering or your code will crash (eventually).

Collectives™ on Stack Overflow

problem with using struct as std::map key

1 Answer 1

5 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Related