我该如何按值对STL映射进行排序？

Question

如何按照值对STL map进行排序？

例如，我有一个map m:

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

我想按照 m 的值对该映射表进行排序。因此，如果我打印映射表，我希望得到以下结果：

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

我该如何以这种方式对地图进行排序？有没有办法在处理值排序的同时处理键和值？

- Charlie Epps

---

看看 boost::bimap。 - Alexandre C.

有一个类似的Java问题。 - Raedwald

使用比较器的概念来使用自定义排序函数 - code_10

Answer 1

首先，将所有的键值对转储到一个 set<pair<K, V>> 中，其中 set 是使用仅比较键值对第二个值的小于函数构建的。这样即使您的值不都是不同的，您的代码仍然可以正常工作。

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

- C. K. Young

---

一个问题，你现在不会使用双倍的内存吗？ - atoMerz

@AtoMerZ 如果这是个问题，你可以让集合持有引用。如果它们已经是引用或小类型，那就没关系了。 - David Schwartz

对于对由pair构成的向量进行排序：https://dev59.com/fXVC5IYBdhLWcg3wfhGL - juanmirocks

将地图“dump”到向量中： vector<pair<K,V>> v(m.begin(), m.end());。 - juanmirocks

在我看来，如果值不都是唯一的，那么“set”这个想法就行不通。如果你执行了myset.insert(make_pair(1, 1));和myset.insert(make_pair(2, 1))，那么第二个pair将不会被插入，因为对于该集合，如果函数对象只比较pair的第二个值，那么这两个项是相同的。 - honk

Answer 2

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

只有在所有值都不相同时才能使用此方法。如果无法假定这一点，则需要构建 multimap 而不是 map。

- swegi

---

如果所有的值都是唯一的，那没问题。但如果有多个键具有相同的值，该怎么处理？因此这个解决方案不好！ - diwatu

这甚至不是一个解决方案。如果所有的值都相同怎么办？那么你的第二个映射只会有1个元素！ - derek

Answer 3

我想知道如何按值对STL map进行排序。

你不能，根据定义。map是一种按键排序其元素的数据结构。

- Konrad Rudolph

---

我该如何实现这个函数？我需要这个函数。 - Charlie Epps

@Charlie Epps：使用另一个映射表吗？每次向第一个映射表添加键/值对时，您都需要向第二个映射表添加值/键对。 - paercebal

Answer 4

在这种情况下，您应该使用 Boost.Bimap。

- rlbond

---

只要您的映射是一对一的，就可以提供。 - Vlad

Boost.Bimap实际上支持非一对一操作。例如，bimap<multiset_of<int>, set_of<double>>。 - rlbond

Answer 5

根据 @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.

在Ideone上的代码

我还根据@Chris的想法使用了一个pair向量来实现基于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;

在 Ideone 上的代码

第一种解决方案更加紧凑，但两种解决方案的性能应该差不多。将元素插入到 multimap 中的时间复杂度为 O(log n)，但是需要对 n 个元素进行操作，因此总时间复杂度为 O(n log n)。而对于第二种解决方案，对向量进行排序也会产生 O(n log n) 的时间复杂度。

我还尝试过 @Chris 的想法，即使用一组成对的集合。然而，如果值不都是不同的，则无法使用。使用一个只比较成对元素的第二个元素的函数对象是没有帮助的。如果你先将 make_pair(1, 1) 插入到集合中，然后再尝试插入 make_pair(2, 1)，那么第二个成对元素就不会被插入，因为该集合认为这两个成对元素是相同的。你可以在 Ideone 上看到这种效果。

- honk

---

第二种解决方案的优点在于它可以推广到对映射值进行非平凡数据类型排序。 - j b

Answer 6

我刚在我的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;
}

- hatethisgarbage

Answer 7

在某些情况下，可以使用 vector<pair<int, int>> 而不是使用 maps<int, int>。这样做的好处是你可以直接使用带有比较器函数的 vector<pair<int, int>>，虽然你会失去使用 map 的一些优点，例如更少的查找时间。

bool compare(pair<int, int> a, pair<int, int> b)
{
    return (a.second < b.second);
}

- Saurabh Mahra

Answer 8

我在thispointer发现了这个。 这个例子通过所有int值对std :: map 进行排序。

#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;
}

- Pat. ANDRIA

Answer 9

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

- Hua Zhong

Answer 10

地图已根据第一个键排序，如果你想根据第二个值进行排序，请将第二个值作为键。否则使用另一个容器，例如vector>。

- Vishal choudhary