Why do I need to repeat the sorting subroutine when declaring a std::set?

Question

In my C++ program I am trying to sort my maps by value, rather than by key.

From this question, it seems clear that the way to do this is to create a set whose elements are pairs and which are sorted by my own less-than function.

Here is some sample code where I try to do this:

#include <map>
#include <set>
#include <iostream>
#include <string>

using namespace std;

bool compareCounts(const pair<string, size_t> &lhs, const pair<string, size_t> &rhs);

int main (int argc, char *argv[]) {
        map <string, size_t> counter = { {"A", 1}, {"B", 2}, {"C", 3} };
        set <pair<string, size_t>, decltype(compareCounts) *> sorted_counter;
        for (map<string, size_t>::iterator it = counter.begin(); it != counter.end(); ++it) {
                cout << "About to add: " << it->first << ":" << it->second << endl;
                auto ret = sorted_counter.insert(*it);
                if (! ret.second) {
                        cout << "ERROR adding this element!" << endl;
                } else {
                        cout << "Element added ok" << endl;
                }
                cout << "Set is of size: " << sorted_counter.size() << endl;
        }

        return 0;
}

bool compareCounts(const pair<string, size_t> &lhs, const pair<string, size_t> &rhs) {
        return lhs.second > rhs.second;
}

Here is the output:

About to add: A:1
Element added ok
Set is of size: 1
About to add: B:2
Segmentation fault: 11

I noticed that things come crashing down when I go to add the second element. I found that this is happening because it is now necessary to call my sorting subroutine, compareCounts.

The fix was to change this line:

set <pair<string, size_t>, decltype(compareCounts) *> sorted_counter;

to this:

set <pair<string, size_t>, decltype(compareCounts) *> sorted_counter(compareCounts);

Why do I need to specify the sorting subroutine compareCounts twice? Doesn't the compiler already know it from my type definition?

Answer 1

set <pair<string, size_t>, decltype(compareCounts) *> sorted_counter;

You never specified what comparator the set should actually use. Change the above line to

set <pair<string, size_t>, decltype(compareCounts) *> sorted_counter(compareCounts);

Without the comparator being specified, the set default constructs one (nullptr) and when it tries to use the comparator for inserting the second element, your code crashes.

You should just use a functor instead of a function pointer

struct compareCounts
{
    bool operator()(const pair<string, size_t> &lhs, 
                    const pair<string, size_t> &rhs) const
    {
        return lhs.second > rhs.second;
    }
};

set <pair<string, size_t>, compareCounts> sorted_counter;