C++ 按键排序 std::unordered_map

Sorting std::unordered_map by key

提问by devnull

How can I sort an unordered_mapby key? I need to print an unordered_mapsorted by key.

如何unordered_map按键排序？我需要打印一个unordered_map按键排序。

回答by ronag

std::unordered_map<int, int> unordered;

std::map<int, int> ordered(unordered.begin(), unordered.end());
for(auto it = ordered.begin(); it != ordered.end(); ++it)
     std::cout << it->second;

回答by David Hammen

An alternate solution is to construct a vector of the keys, sort the vector, and print per that sorted vector. This will be considerably faster than the approaches that constructed a map from the ordered map, but will also involve more code.

另一种解决方案是构造一个键向量，对向量进行排序，然后按排序后的向量打印。这将比从有序映射构建映射的方法快得多，但也会涉及更多代码。

std::unordered_map<KeyType, MapType> unordered;
std::vector<KeyType> keys;

keys.reserve (unordered.size());
for (auto& it : unordered) {
    keys.push_back(it.first);
}
std::sort (keys.begin(), keys.end());
for (auto& it : keys) {
    std::cout << unordered[it] << ' ';
}

回答by Xeo

Are you sureyou need this? Because that is not possible. An unordered_mapis a hash container, that is, the keys are hashed. Inside of the container, they don't have the same representation as on the outside. Even the name implies that you can't sort it. It's one of the criteria to choose a hash container: You do notneed a specific order.

你确定你需要这个吗？因为那是不可能的。Anunordered_map是散列容器，即键是散列的。在容器内部，它们的表示与外部不同。甚至名称也暗示您无法对其进行排序。它的标准来选择一个哈希容器之一：你不是需要一个特定的顺序。

If you do, get a normal map. The keys are automatically sorted in a strict-weak ordering. If you need another sort, write your own comparator.

如果你这样做，得到一个正常的map. 键以严格弱顺序自动排序。如果您需要另一种排序，请编写自己的比较器。

If you only need to print it sorted, the following may be inefficient, but it's as close as you'll get if you still want to keep the unordered_map.

如果您只需要将其排序打印，以下可能效率低下，但如果您仍想保留unordered_map.

#include <map>
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <functional>

struct map_streamer{
  std::ostream& _os;

  map_streamer(std::ostream& os) : _os(os) {}

  template<class K, class V>
  void operator()(std::pair<K,V> const& val){
    // .first is your key, .second is your value
    _os << val.first << " : " << val.second << "\n";
  }
};

template<class K, class V, class Comp>
void print_sorted(std::unordered_map<K,V> const& um, Comp pred){
  std::map<K,V> m(um.begin(), um.end(), pred);
  std::for_each(m.begin(),m.end(),map_streamer(std::cout));
}

template<class K, class V>
void print_sorted(std::unordered_map<K,V> const& um){
  print_sorted(um, std::less<int>());
}

Example on Ideone.
Note that in C++0x, you can replace the two overloads with one function with a default template argument:

以 Ideone 为例。
请注意，在 C++0x 中，您可以用一个带有默认模板参数的函数替换两个重载：

template<class K, class V, class Comp = std::less<int> >
void print_sorted(std::unordered_map<K,V> const& um, Comp pred = Comp()){
  std::map<K,V> m(um.begin(), um.end(), pred);
  std::for_each(m.begin(),m.end(),map_streamer(std::cout));
}

回答by AhLeung

Similar to David's answer, we can use std::setto sort the key first:

与大卫的回答类似，我们可以先使用std::set对键进行排序：

std::unordered_map<int, int> unordered;
std::set<int> keys;
for (auto& it : unordered) keys.insert(it.first);
for (auto& it : keys) {
    std::cout << unordered[it] << ' ';
}

回答by Jiancong

You can use vector to store your key value pairs, then sort them in vector, put them back at map at last.

您可以使用 vector 来存储您的键值对，然后在 vector 中对它们进行排序，最后将它们放回 map 中。

#include <iostream>                                 
#include <unordered_map>                                 
#include <algorithm>                                 
#include <vector>                                 

using namespace std;                                

int main(){                                
    unordered_map<string, int> sdict = {{"hello", 11 }, {"world", 52}, {"tommy", 3}};               
    unordered_map<string, int> resdict;          

    vector<pair<string, int>> tmp;
    for (auto& i : sdict)                                         
        tmp.push_back(i);                                

    for (auto& i : sdict)       
        cout <<  i.first << " => " << i.second << endl;  

    // sort with descending order.
    sort(tmp.begin(), tmp.end(),                                   
    [&](pair<string, int>& a, pair<string, int>& b) { return a.second < b.second; });

    for (auto& i : tmp)                          
    {                           
        resdict[i.first] = i.second;                   
    }                                

    cout << "After sort." << endl;   
    for (auto& i : resdict)     
        cout <<  i.first << " => " << i.second << endl;           
    return 0;                                              

}                                            

Compile with following commands.

使用以下命令编译。

g++ --std=c++11 test_sort_ordered_map.cpp

The result is:

结果是：

tommy => 3
hello => 11
world => 52
After sort.
world => 52
hello => 11
tommy => 3