为什么STL unordered_map和unordered_set无法按STL算法排序？

Question

我将首先介绍一个简单的用例示例:

• 考虑社会安全ID数据库的问题,其中C++代码被建模std::unordered_map为其关键是人的社会安全ID并且其值是std::string具有该人的全名的(例如,std::unordered_map<int, std::string> DB;).

• 还要考虑,根据人的ID(即,std::unordered_map密钥)按照升序排序打印此数据库的请求.

• 天真地,人们会考虑使用std::sort,以便std::unordered_map根据请求的标准进行排序,然后打印它,如下面的示例代码:

---

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

---

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

问题:

1. 为什么STL的无序容器无法排序std::sort？
2. 是否有合法有效的方法来排序a std::unordered_map或a std::unordered_set？

Answer 1

unordered容器存储内部散列数据,因此在生成散列后无法对它们进行排序.

为了对数据进行排序,您可以使用额外的非散列容器(例如地图或集合),并将它们与无序版本一起使用(这样您就可以使用正常的数据对数据进行排序,而使用无序数据对数据进行快速排序-item access)或者你可以做类似的事情

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

我建议不要经常这样做(无序容器有慢速顺序访问)

/sf/answers/434889661/

Answer 2

排序仅对序列容器有意义,序列容器是容器,其元素由它们添加到容器的顺序确定.标准库中的动态序列容器是vector,deque,list和forward_list.

另一方面,地图和集合是关联容器,其中元素由其值标识.因此,要求"排序"是没有意义的,因为容器元件没有以任何顺序排列.(确实,有序地图可以按照密钥的比较顺序进行迭代,但是该顺序从容器中出现 ;用户不提供.)