Why does STL Set overwrite pairs with same value

Question

I can sort an unordered map by value in descending order using this answer.

However, using a set for the same job fails:

#include <set>  
#include <functional>    
#include <iostream>

using namespace std;

typedef pair<string, int> Pair;
typedef function<bool(Pair, Pair)> Comparator;

Comparator DescendingSortComparator = [](Pair pair1, Pair pair2) {
    return pair1.second > pair2.second;
};

void SortHashTableByValueDescending(unordered_map<string, int> hashTable) {
    set<Pair, Comparator> orderedSet(hashTable.begin(), hashTable.end(), DescendingSortComparator);

    for (auto element : orderedSet)
        cout << element.first << ": " << element.second << endl;
}

Running with the following test:

void Test_SortMap()
{
    unordered_map<string, int> CountTable;
    CountTable["word"] = 1;
    CountTable["spark"] = 15;
    CountTable["the"] = 2;
    CountTable["mail"] = 3;
    CountTable["info"] = 3;
    CountTable["sandwich"] = 15;

    SortHashTableByValueDescending(CountTable);
}

yiels the following output:

spark: 15
info: 3
the: 2
word: 1

Can anyone please tell me why set (probably) overwrites pairs with same value? The keys for such pairs are distinct anyways.

You comparator account only values of `unordered_map` but not keys. — ks1322, Jan 09 '17 at 10:32

pergy · Answer 1 · 2017-01-09T19:21:43.023

3

See the definition of Compare function of std::set.

Everywhere the standard library uses the Compare concept, uniqueness is determined by using the equivalence relation. In imprecise terms, two objects a and b are considered equivalent if neither compares less than the other: !comp(a, b) && !comp(b, a).

This means that equal numbers will considered equivalent and not copied into your orderedSet

Use

Comparator DescendingSortComparator = [](Pair pair1, Pair pair2) {
    if (pair1.second == pair2.second)
      return pair1.first > pair2.first;
    else return pair1.second > pair2.second;
};

if you want to keep them

edited Jan 09 '17 at 19:21

answered Jan 09 '17 at 10:36

pergy

5,285
1
22
36

Your answer is wrong, `pair1.second >= pair2.second` is not a valid comparator. – Edgar Rokjān Jan 09 '17 at 10:41
Mathematically? For equal cases it's not.. But I think that's the reason you want to override compare function: to achieve custom behaviour. – pergy Jan 09 '17 at 10:48
@pergy Unfortunately I tried it before and I had runtime error due to same reason as Edgar Rokyan replied. – Ferit Buyukkececi Jan 09 '17 at 10:50
It must be irreflixive at least. – Edgar Rokjān Jan 09 '17 at 10:50
@FeritBuyukkececi strange. i've tried it too ofc. http://coliru.stacked-crooked.com/a/790365fb82913f9c – pergy Jan 09 '17 at 10:52
@pergy I'm even more confused now. Please see this: http://screencast.com/t/GzUcMZcx – Ferit Buyukkececi Jan 09 '17 at 10:55
@pergy Thanks a lot for the explanation of why my pairs were considered equivalent even when they're not. – Ferit Buyukkececi Jan 09 '17 at 10:57
@FeritBuyukkececi what about this?: http://coliru.stacked-crooked.com/a/da3a5f1adb40e89b maybe "less invalid" :) – pergy Jan 09 '17 at 11:05
1

@pergy Thanks. That's actually what I did after all. You can see the comment partially behind the error message :) – Ferit Buyukkececi Jan 09 '17 at 11:07
Yeah, now i see that :) I've edited the answer and removed suggetion for invalid comparator – pergy Jan 09 '17 at 11:09
This solution is still wrong... for two equal pairs `DescendingSortComparator` returns true, but it must return false instead. – Edgar Rokjān Jan 09 '17 at 18:38
Well, it's one of the many workarounds that compiles and successfully tackles the problem. You could either use a string created from key+value and compare them or anything else. I think that's the point of customization. By the way the question is about why it happens, the proposed workaround is just addition, mathematically valid or not. – pergy Jan 09 '17 at 19:15
it's one of the many workarounds - it's just Undefined Behaviour. – Edgar Rokjān Jan 09 '17 at 19:21
Anyway, I changed it to switch back to checking key if value if equal. That's definitely smarter – pergy Jan 09 '17 at 19:23

score 2 · Accepted Answer · answered Jan 09 '17 at 10:33

2

From the cppreference.com:

std::set is an associative container that contains a sorted set of unique objects of type Key.

According to your Comparator only a single std::pair with a fixed second element can be stored in the set.

answered Jan 09 '17 at 10:33

Edgar Rokjān

17,245
4
40
67

Thanks for the reference, I couldn't manage to find this information. Any ideas on how to make it work using set? I know it's possible with sort, but I still want to see if this approach can be an alternative. – Ferit Buyukkececi Jan 09 '17 at 10:35
You can sort additionally by the *first* elements when *second* elements of compared pairs are equal. – Edgar Rokjān Jan 09 '17 at 10:39
Thanks, changing the comparison function to "return pair1.second > pair2.second || (pair1.second == pair2.second && pair1.first > pair2.first)" fixed it. Still, I don't get why this helps, could you please elaborate? – Ferit Buyukkececi Jan 09 '17 at 10:52

Why does STL Set overwrite pairs with same value

2 Answers2