Can't compile std::map sorting, why?

Question

This is my code:

map<string, int> errs;
struct Compare {
    bool operator() (map<string, int>::const_iterator l, 
        map<string, int>::const_iterator r) { 
        return ((*l).second < (*r).second); 
    }
} comp;
sort(errs.begin(), errs.end(), comp);

Can't compile. This is what I'm getting:

no matching function for call to ‘sort(..’

Why so? Can anyone help? Thanks!

Answer 1

You can't sort a map. It has its own sort order, defined at construction time either as the default (use <) or a passed in comparator.

Answer 2

This is probably because a std::map has a non-assignable iterator.

std::map has an invariant that is Strictly ascending order, it is always sorted by key.

Read more about it here: http://www.sgi.com/tech/stl/UniqueSortedAssociativeContainer.html

and note 1 here: http://www.sgi.com/tech/stl/Map.html

Answer 3

I assume you are doing using namespace std;. In that sort method requires the iterators to be random access iterators. But map iterators are bidirectional, so it will not compile.

Answer 4

In addition to Marcelo's answer: The predicate used by std::sort should take values, not iterators as input.

Answer 5

Maps are, by definition, sorted by their keys, so you can't resort a map by its values.

You can provide an alternate comparison function as the third template parameter to a map, if you want to sort the keys by a non-default order.

If you're trying to sort a map by its values, then perhaps you could try using Boost.MultiIndex to make a bidirectional map instead?

Answer 6

As stated Marcelo you can't sort a map with std::sort you need to define the sort method in the constructor i believe is value_compare.

struct Compare
{
bool operator()(const char* a, const char* b) const
{
return strcmp(a,b) < 0;
};
std::map<char, char, Compare> compareMap;

Answer 7

The Compare template parameter takes map keys to compare (or references to keys), not the iterators. Also, the std::map takes that type at instantiation and is sorted automatically by the key (the most common implementation is the red-black tree).

Take a look at boost::multi_index for multi-key access.