按键排序std :: unordered_map

Question

如何按键对unordered_map进行排序？我需要按键排序后打印unordered_map。

- softwarematter

Answer 1

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;

- ronag

---

我已经将unorderedmap声明为std::unordered_map<int, unsigned long> *myunorderedmap;，但是std::map<int, unsigned long> ordered(myunorderedmap->begin, myunorderedmap->end);会出现错误。 - softwarematter

begin和end是函数。使用ordered(myunorderedmap->begin(), myunorderedmap->end())代替你之前使用的内容，一切都会没问题的。 - David Hammen

不要忘记，如果您不关心保留初始容器中的元素，则可以使用make_move_iterator将元素移动到新容器中：std::map<int, int> ordered(std::make_move_iterator(unordered.begin()), std::make_move_iterator(unordered.end())); - ipapadop

Answer 2

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

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] << ' ';
}

- David Hammen

---

如果您使用向量和std::sort而不是列表，速度将更快。 - ltjax

如果必须使用 push_back，那么通过预留所需长度（reserve）可以使向量操作稍微更快一些。 - Steven Lu

@Steven Lu，如果您不关心顺序，您可以使用什么代替push_back，例如在这个例子中？ - Kyle

Answer 3

你确定需要这个吗？因为这是不可能的。 unordered_map 是一个哈希容器，也就是说，键被散列了。 在容器内部，它们与外部的表示方式不同。即使名称表明您不能对其进行排序。这是选择哈希容器的标准之一：您不需要特定顺序。

如果需要排序，请使用普通的 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>());
}

在 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));
}

- Xeo

---

你可以使用 std::ostream_iterator 和 std::copy 代替自己的 streamer。 - ltjax

@Itjax：仔细想想，不用std::for_each，因为它会给我一个std::pair<K,V>，而我仍然需要拆分它。我的第一次实现由于这个原因而失败了，因为std::pair无法流式传输。 - Xeo

Answer 4

与David的答案类似，我们可以使用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] << ' ';
}

- AhLeung

Answer 5

你可以使用向量(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;                                              

}                                            

使用以下命令进行编译。

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

结果是：

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

- Jiancong