C++ 如何按值对 STL 映射进行排序？

How can I sort an STL map by value?

提问by Charlie Epps

How can I implement STL map sorting by value?

如何按值实现 STL 映射排序？

For example, I have a map m:

例如，我有一张地图m：

map<int, int> m;
m[1] = 10;
m[2] = 5;
m[4] = 6;
m[6] = 1;

I'd like to sort that map by m's value. So, if I print the map, I'd like to get the result as follows:

我想按m的值对该地图进行排序。所以，如果我打印地图，我想得到如下结果：

m[6] = 1
m[2] = 5
m[4] = 6
m[1] = 10

How can I sort the map in this way? Is there any way that I can deal with the key and value with sorted values?

如何以这种方式对地图进行排序？有什么办法可以用排序的值处理键和值？

采纳答案by swegi

You can build a second map, with the first map's values as keys and the first map's keys as values.

您可以构建第二个映射，将第一个映射的值作为键，将第一个映射的键作为值。

This works only if all values are distinct. If you cannot assume this, then you need to build a multimap instead of a map.

这仅在所有值都不同时才有效。如果您不能假设这一点，那么您需要构建一个多地图而不是地图。

回答by Chris Jester-Young

Dump out all the key-value pairs into a set<pair<K, V> >first, where the setis constructed with a less-than functor that compares the pair's second value only. That way, your code still works even if your values aren't all distinct.

将所有键值对转储到set<pair<K, V> >第一个中，其中set用小于函子构造，仅比较该对的第二个值。这样，即使您的值不完全不同，您的代码仍然有效。

Or dump the key-value pairs into a vector<pair<K, V> >, then sort that vector with the same less-than functor afterwards.

或者将键值对转储到 a 中vector<pair<K, V> >，然后使用相同的小于函子对该向量进行排序。

回答by Konrad Rudolph

I wonder how can I implement the STL map sorting by value.

我想知道如何按值实现 STL 映射排序。

You can't, by definition. A map is a data structure that sorts its element by key.

你不能，根据定义。映射是一种按键对其元素进行排序的数据结构。

回答by rlbond

You should use Boost.Bimapfor this sort of thing.

您应该将Boost.Bimap用于此类事情。

回答by hatethisgarbage

I've just done a similar question in my c++ book. The answer I came up with might not be very efficient though:

我刚刚在我的 c++ 书中做了一个类似的问题。我想出的答案可能不是很有效：

int main()
{
    string s;
    map<string, int> counters;

    while(cin >> s)
        ++counters[s];

    //Get the largest and smallest values from map
    int beginPos = smallest_map_value(counters);
    int endPos = largest_map_value(counters);

    //Increment through smallest value to largest values found
    for(int i = beginPos; i <= endPos; ++i)
    {
        //For each increment, go through the map...
        for(map<string, int>::const_iterator it = counters.begin(); it != counters.end(); ++it)
        {
            //...and print out any pairs with matching values
            if(it->second == i)
            {
                cout << it->first << "\t" << it->second << endl;
            }
        }
    }
    return 0;
}

//Find the smallest value for a map<string, int>
int smallest_map_value(const map<string, int>& m)
{
    map<string, int>::const_iterator it = m.begin();
    int lowest = it->second;
    for(map<string, int>::const_iterator it = m.begin(); it != m.end(); ++it)
    {
        if(it->second < lowest)
            lowest = it->second;
    }
    return lowest;
}

//Find the largest value for a map<string, int>
int largest_map_value(const map<string, int>& m)
{
    map<string, int>::const_iterator it = m.begin();
    int highest = it->second;
    for(map<string, int>::const_iterator it = m.begin(); it != m.end(); ++it)
    {
        if(it->second > highest)
            highest = it->second;
    }
    return highest;
}

回答by honk

Based on @swegi's idea, I implemented a solution in c++11using a multimap:

基于@swegi 的想法，我在c++11 中使用了一个解决方案multimap：

map<int, int> m = {{1, 10}, {2, 5}, {4, 6}, {6, 1}};
multimap<int, int> mm;

for(auto const &kv : m)
    mm.insert(make_pair(kv.second, kv.first));  // Flip the pairs.

for(auto const &kv : mm)
    cout << "m[" << kv.second << "] = " << kv.first << endl;  // Flip the pairs again.

Code on Ideone

Ideone 上的代码

I also implemented a C++11 solution based on @Chris' idea using a vector of pairs. For correct sorting, I provide a lambda expressionas comparison functor:

我还使用成对向量实现了基于@Chris 的想法的 C++11 解决方案。为了正确排序，我提供了一个lambda 表达式作为比较函子：

map<int, int> m = {{1, 10}, {2, 5}, {4, 6}, {6, 1}};
using mypair = pair<int, int>;

vector<mypair> v(begin(m), end(m));

sort(begin(v), end(v), [](const mypair& a, const mypair& b) { return a.second < b.second; });

for(auto const &p : v)
    cout << "m[" << p.first << "] = " << p.second << endl;

Code on Ideone

Ideone 上的代码

The first solution is more compact, but both solutions should have roughly the same performance. Inserting into a multimapis of O(log n), but this has to be done for nentries, resulting in O(n log n). Sorting the vector in the second solution also results in O(n log n).

第一种解决方案更紧凑，但两种解决方案应该具有大致相同的性能。插入 amultimap是O(log n)，但这必须对n个条目进行，导致O(n log n)。对第二个解决方案中的向量进行排序也会导致O(n log n)。

I also gave a try to @Chris' idea on using a set of pairs. However, it won't work if the values aren't all distinct. Using a functor that compares only the pair's second element doesn't help. If you first insert make_pair(1, 1)into the set and then try to insert make_pair(2, 1), then the second pair won't be inserted, because both pairs are seen as identical by that set. You can see that effect here on Ideone.

我还尝试了@Chris 关于使用一组对的想法。但是，如果这些值不是完全不同的，它将不起作用。使用仅比较该对的第二个元素的函子无济于事。如果您先插入make_pair(1, 1)集合然后尝试插入make_pair(2, 1)，则不会插入第二对，因为该集合将两对视为相同。您可以在 Ideone 上看到这种效果。

回答by Pat. ANDRIA

I have found this in thispointer. The example sorts a std::map< std::string,int> by all the int values.

我在thispointer 中找到了这个。该示例按所有 int 值对 std::map<std::string,int> 进行排序。

#include <map>
#include <set>
#include <algorithm>
#include <functional>

int main() {

    // Creating & Initializing a map of String & Ints
    std::map<std::string, int> mapOfWordCount = { { "aaa", 10 }, { "ddd", 41 },
            { "bbb", 62 }, { "ccc", 13 } };

    // Declaring the type of Predicate that accepts 2 pairs and return a bool
    typedef std::function<bool(std::pair<std::string, int>, std::pair<std::string, int>)> Comparator;

    // Defining a lambda function to compare two pairs. It will compare two pairs using second field
    Comparator compFunctor =
            [](std::pair<std::string, int> elem1 ,std::pair<std::string, int> elem2)
            {
                return elem1.second < elem2.second;
            };

    // Declaring a set that will store the pairs using above comparision logic
    std::set<std::pair<std::string, int>, Comparator> setOfWords(
            mapOfWordCount.begin(), mapOfWordCount.end(), compFunctor);

    // Iterate over a set using range base for loop
    // It will display the items in sorted order of values
    for (std::pair<std::string, int> element : setOfWords)
        std::cout << element.first << " :: " << element.second << std::endl;

    return 0;
}

回答by Hua Zhong

Create another map, provide a less() function based on the value not key, AND the function should return true if the value1 <=value2 (not strictly < ). In this case, elements with non-distinct values can be sorted as well.

创建另一个映射，提供一个基于非键值的 less() 函数，如果 value1 <=value2（不是严格的 < ），该函数应该返回 true 。在这种情况下，也可以对具有非不同值的元素进行排序。