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.

Answer 1

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

Answer 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.