5

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

  • 考虑一个社会保障 ID 数据库的问题,其中 C++ 代码被建模为 a std::unordered_map,它的键是一个人的社会保障 ID,它的值是std::string带有那个人的全名的 a(例如,std::unordered_map<int, std::string> DB;)。

  • 还请考虑,有一个打印此数据库的请求,该数据库根据人的 ID(即std::unordered_map's 键)按升序排序。

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


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

  • 但是,情况并非如此,因为在 a或 astd::sort范围内使用a会引发编译器错误。std::unordered_mapstd::unordered_set

问题:

  1. 为什么 STL 的无序容器不能按 排序std::sort
  2. 是否有一种合法且有效的方法来对 astd::unordered_map或 a进行排序std::unordered_set
4

3 回答 3

6

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

为了对数据进行排序,您可以使用额外的非散列容器(例如 map 或 set),并将它们与无序版本一起使用(因此您可以使用普通容器对数据进行排序,使用无序容器来快速-item access)或者你可以做类似的事情

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

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

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

于 2014-06-13T19:13:27.607 回答
5

排序仅对序列容器有意义,这些容器的元素由它们添加到容器的顺序决定。标准库中的动态序列容器有vector、deque、list和forward_list。

另一方面,映射和集合是关联容器,其中元素由它们的标识。因此,要求“排序”是没有意义的,因为容器元素没有按任何顺序排列。(确实,有序映射可以按键上的比较顺序进行迭代,但该顺序来自容器;它不是由用户提供的。)

于 2014-06-13T19:38:17.653 回答
2

1.为什么STL的无序容器不能排序std::sort

因为无序容器已经“排序”了,尽管不是直接按它们的键,而是按(通常)(也可以作为 访问)。这种“排序”顺序不是装饰性的——它是哈希表能够快速找到元素的整个基础。如果允许通过键重新排序元素,那么容器将不再能够用作哈希表:无法可靠地找到或删除元素,插入可能会将重复项放入容器等。hash_function(key) % bucket_count()bucket(key)std::sort

2.是否有一种合法有效的方法来排序 astd::unordered_map或 a std::unordered_set

在一般情况下,只需首先将元素复制到可排序或已排序的容器中,例如std::vectoror std::set(前者通常会更快,但如果您真的关心的话,可以同时对两者进行基准测试):

std::unordered_set<T> my_set = ...;
std::vector<T> my_vec{my_set.begin(), my_set.end(), my_set.size()};
std::sort(my_vec.begin(), my_vec.end());

在您的情况下std::unordered_map<int, std::string> DB;,我建议仅将int键复制到 avector进行排序,然后在迭代期间查找unordered_map: 中的每个键,这将避免大量string复制。

(有时可以通过键排序来编排无序容器(例如,哈希函数返回键,容器预先调整大小,因此最大存储桶索引> = 最大键值)但任何考虑这种滥用的人最好使用vector.)

于 2015-06-22T03:56:13.637 回答