Why can't I use lambda to sort std::map by value

Question

#include <iostream>
#include <map>
#include <utility>
#include <algorithm>


int main()
{
        std::map<int, std::string> m;
        m[2] = "abc";
        m[1] = "bcd";

        auto cmp = [](std::pair<int, std::string>  a, std::pair<int, std::string>  b)
        {
                return a.second != b.second ? a.second < b.second : a.first < b.first;
        };
        std::sort(m.begin(), m.end(), cmp);
        for (auto it = m.begin(); it != m.end(); ++it)
        {
                std::cout<<it->first<<std::endl;
                std::cout<<it->second<<std::endl;
        }

        return 0;
}

I want to sort a map by its value, instead of its key, so I code as above.

I just read this link and this is why I code like this: std::map, how to sort by value, then by key

But it produced an error:

Severity    Code    Description Project File    Line    Suppression State
Error   C2784   'unknown-type std::operator -(const std::move_iterator<_RanIt> &,const std::move_iterator<_RanIt2> &)': could not deduce template argument for 'const std::move_iterator<_RanIt> &' from 'std::_Tree_unchecked_iterator<_Mytree>'   testcpp c:\program files (x86)\microsoft visual studio\2017\enterprise\vc\tools\msvc\14.10.25017\include\algorithm  2908

Note that the linked question sorts a `vector`, not a `map`. A map is already sorted on the key to support fast lookup and cannot be reordered. (The specific error message comes from `std::sort` requiring a random access iterator, which the map doesn't have). — Bo Persson, Apr 21 '18 at 12:39
`std::map` is a sorted container; and is sorted according the key (the first type of the couple); you can change the sorting function (using the third, defaulted template parameter of `std::map`) but there is no sense in sorting it using `std::sort`. — max66, Apr 21 '18 at 12:46

con ko · Accepted Answer · 2020-12-30T11:27:29.983

3

auto cmp = [](std::pair<int, std::string>  a, std::pair<int, std::string>  b)
    {
            return a.second != b.second ? a.second < b.second : a.first < b.first;
    };

Here's the problem.

The predicate's parameter should have the type that key_type can convert to implicitly

And you shouldn't apply std::sort to std::map. One reason is this operation is redundant(see the reference below), another is the keys have const type.

http://en.cppreference.com/w/cpp/container/map

And another advice:

declare the predicate's parameter type as a reference to const

edited Dec 30 '20 at 11:27

answered Apr 21 '18 at 11:53

con ko

1,368
5
18

2

You could have commented instead. – Aniket Chowdhury Apr 21 '18 at 11:55
@AniketChowdhury Thanks for your advice. But could you tell me why should this be a comment? I think I've answered the question. – con ko Apr 21 '18 at 11:58
That was before you edited it. It is easier to be rude in the comments, than write up an answer, it doesn't create clutter. – Aniket Chowdhury Apr 21 '18 at 12:05
1

You can also use `auto` in lambdas. – Quimby Apr 21 '18 at 19:18

Why can't I use lambda to sort std::map by value

1 Answers1