6

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?

honk
  • 9,137
  • 11
  • 75
  • 83
EMiller
  • 2,792
  • 4
  • 34
  • 55
  • what are you using, `map` or `set`? it's rather confusing. please give a self-contained example – TemplateRex Aug 22 '13 at 20:24
  • I am using sets to sort maps by value. – EMiller Aug 22 '13 at 20:25
  • Is this an on-demand thing or a continual pairing of both structures (which I strongly advise against)? If on-demand, have you considered simply throwing `std::ref>` into a vector and firing `std::sort()` with your own comparator ? – WhozCraig Aug 22 '13 at 20:27
  • Sounds like standard C++ pitfalls. But why does insert invalidate the loop iterator? The iterator is over the elements of the map. Isn't that remaining unmodified? – EMiller Aug 22 '13 at 20:28
  • @User7391 yes to your question in-comment. I would advise using a `const_iterator` on the map-walk regardless, but it doesn't immediately explain your fault with the code as-presented. – WhozCraig Aug 22 '13 at 20:30
  • 1
    To answer your updated question, see Praetorians answer (which is the correct one). your decl tells it the *type* of the comparator (a bool-returning function taking two const `std::pair<>` references), but you never actually *gave* it a comparator to use. one of the many reasons I fallback to using functors in cases like this. – WhozCraig Aug 22 '13 at 21:13

1 Answers1

6
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;
Praetorian
  • 106,671
  • 19
  • 240
  • 328
  • Ah! And I just realized that this was my question! – EMiller Aug 22 '13 at 21:10
  • 2
    @User7391 I.e. you told it the *type* of the comparator, but never actually *gave* it one. – WhozCraig Aug 22 '13 at 21:11
  • @User7391 Note in Praetorians additional sample, by telling it the type (a functor) it can (and does) use an instance of that type for eval through `operator()`. It is also usually preferred for performance since it is *highly* likely to inline. Were I you, I would use his functor example. – WhozCraig Aug 22 '13 at 21:15
  • I have not heard of functors before. I'll need to look into these. – EMiller Aug 22 '13 at 21:16
  • @User7391 Well you have a concrete example of one right there. =P – WhozCraig Aug 22 '13 at 21:17
  • @balki: I am not sure about that, in the general case. You can make it work with enough effort (by creating a factory function) but in general the lambda expression generates an object, not a type, so you would have to use the `decltype` trick on the type declaration: `std::set s(???)`. Now the question is what to pass in `???`. If you retype the lambda expression that will generate a different unrelated (although with the exact behavior) type, so that is not an option. 5.1.2/19 states that the default constructor is deleted... – David Rodríguez - dribeas Aug 22 '13 at 22:38
  • [...] now, you the workaround to make it work (just 'cos we can, not that we want!) would be a factory function `template std::set createSet(T cmp) { return std::set(cmp); }` and the use would have to be through `auto` again: `auto myset = createSet([](int l, int r) { return l < r; });`... put that in production code, wait until someone hits a bug and needs to read the code and start running... – David Rodríguez - dribeas Aug 22 '13 at 22:41
  • 2
    @David What about `auto comp = [](...) {return ...;}; std::set s(comp);`? (I still prefer the functor version over that) – Praetorian Aug 22 '13 at 22:44
  • @Praetorian: lol... I was so focused on the problem of getting the type before the object that I did not see the obvious :) At any rate this allows you to create the set in the stack (or heap), but you cannot use this mechanism to create a member of a type unless you template the class and use either trick, then that cannot become a member of a larger type unless... – David Rodríguez - dribeas Aug 23 '13 at 01:56