为什么不能通过STL算法对STL unordered_map和unordered_set进行排序? [英] Why STL unordered_map and unordered_set cannot be sorted by STL algorithms?

问题描述

我将首先说明一个简单的用例:

I'll start by illustrating a simple use case example:

• 考虑一个社会保障ID数据库的问题，其中在C ++代码中将其建模为std::unordered_map，其键是一个人的社会保障ID，其值是一个std::string，其中包含完整的-该人的姓名(例如std::unordered_map<int, std::string> DB;).

• Consider the problem of a social security ID database, where in C++ code is modelled as a std::unordered_map where its key is the social security ID of a person and its value is a std::string with the full-name of that person (e.g., std::unordered_map<int, std::string> DB;).

还请考虑根据该用户的ID(即std::unordered_map的密钥)以升序打印此数据库的请求.

Consider also, that there's a request for printing this database sorted in ascending order based on the person's ID (i.e., std::unordered_map's key).

天真的，人们会考虑使用std::sort以便根据请求的条件对std::unordered_map进行排序，然后将其打印出来，例如下面的示例代码:

Naively, one would think to use std::sort in order to sort the std::unordered_map according to the requested criteria and then print it, like the example code below:

   std::sort(DB.begin(), DB.end());
   for(auto p : DB) std::cout << "ID(" << p.first
                              << ") - " 
                              << p.second 
                              << std::endl;

---

• 但是，情况并非如此，因为使用范围为std::unordered_map或std::unordered_set的std::sort会引发编译器错误.

---

• However, this is not the case, because use of std::sort with a range of either a std::unordered_map or a std::unordered_set will raise a compiler error.
1. 为什么STL的无序容器不能按std::sort排序?
2. 是否有合法有效的方法对std::unordered_map或std::unordered_set进行排序?
1. Why STL's unordered containers cannot be sorted by std::sort?
2. Is there a legitimate and efficient way to sort either a std::unordered_map or a std::unordered_set?

推荐答案

容器在内部存储散列数据，因此在生成哈希后就无法对其进行排序.

unordered containers store internally hashed data and thus it's not possible to order them after the hash has been generated.

为了对数据进行排序，您可以使用其他非哈希容器(例如，地图或集合)，也可以将它们与无序版本一起使用(因此，您可以使用普通的容器对数据进行排序，而对无序的容器进行排序)具有快速的逐项访问权限)，或者您可以执行

In order to sort the data you can use an additional non-hashed container (e.g. map or set) and either use them along with the unordered version (so you can use the normal one to sort the data and the unordered one to have fast per-item access) or you can do something like

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

我建议您不要经常执行上述操作(无序容器的顺序访问速度很慢)

I recommend not to do the above often (unordered containers have slow sequential access)

https://stackoverflow.com/a/6212709/1938163

这篇关于为什么不能通过STL算法对STL unordered_map和unordered_set进行排序?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！