迭代有序与无序容器

我想知道哪些数据结构更有效地遍历其元素在std::set,std::map和std::unordered_set,std::unordered_map之间。迭代有序与无序容器

我通过SO搜索，我发现这个question。答案要么复制std::vector中的元素，要么使用Boost.Container，恕我直言不回答我的问题。

我的目的是在容器中保留大量独特的元素，大多数时候我想遍历它们。插入和提取更为罕见。我想避免std::vector结合std::unique。

来源

2015-07-21 101010

如果迭代频繁，你确实真的想要一个向量。 –

使用'boost :: flat_ *' – inf

@ T.C。我知道但是让我们假装我不能使用'std :: vector'。在有序和无序之间哪个是最好的选择，为什么？ :) – 101010

让我们考虑set与unordered_set。

这里的主要区别在于迭代的“性质”，即遍历集合会按顺序给出元素，而在无序集合中遍历范围会给你一堆没有特定顺序的值。

假设您想遍历一个范围[it1, it2]。如果我们排除查找元素it1和it2所需的查找时间，则不能从一种情况直接映射到另一种情况，因为即使使用相同的元素构建容器，它们之间的元素也不会保持相同。

然而在某些情况下，如果这样的事情具有含义，例如，你想遍历固定数量的元素（不管它们是什么）或者当你需要遍历整个容器时。在这种情况下，你需要考虑执行机制：

集通常是像红黑树（的二叉搜索树形式）来实现。与所有的二叉搜索树一样，它们允许有效地对它们的元素进行有效的有序遍历（LRR：左边的右边）。那就是遍历你支付指针追逐的代价（就像遍历列表一样）。在另一方面

typical red black tree layout

无序集哈希表和我knowledge的STL实现使用与链接散列。这意味着（在非常高的层次上）结构使用的是一个（连续的）缓冲区，其中每个元素是包含元素的链（列表）的头部。元素在这些链（桶）和缓冲区之间的布局方式会影响遍历时间，但是这次您将再次跳过不同的列表来追逐指针。我不认为它会与树状结构有很大差异，但肯定不会更好。

schematic layout of hashing with chaining

在任何情况下微调，和基准会给你的具体应用问题的答案。

来源

2015-07-21 08:45:22

添加[链接]（http://coliru.stacked-crooked.com/a/732aa1187a99f862）到您之前写的基准....干杯。 –

区别不在于排序或缺少一个，而是在后备容器中。如果它是一个连续的内存，由于迭代器和缓存友好性的简单实现，它应该快速迭代。

无序容器通常作为向量（或类似事物）的向量存储，而有序容器是使用树实现的，但它毕竟是留给实施的。这表明迭代无序版本应该是浪费。然而，这是留给执行毕竟的，并且我看到了具有不同行为的实现（这些实现倾向于公平）。

一般来说，容器性能是一个相当复杂的话题，通常需要在实际应用中进行测试以获得可靠的答案。有很多实施定义的内容可能会影响性能。如果我不得不去盲人，我会和hash_set一起去。复制到vector也可能成为一个不错的选择。

编辑：正如@TonyD在它的评论中说的那样，有一条规则，当max_load_factor()没有被超过时，不允许在添加元素期间使迭代器失效，这实际上排除了支持内存中连续的容器。

因此，将所有内容复制到矢量中似乎更加合理。如果你需要删除重复项，一个可行的选择可能是使用http://en.cppreference.com/w/cpp/algorithm/sort并且容易被忽略。我听说使用vector和sort有一个经过排序的数组（或向量）通常是一个常用的选项，用于需要需要排序的容器，并且被修改的次数更多。

来源

2015-07-21 08:41:30 luk32

*“无序容器通常作为向量（或类似的东西）的向量存储”*仅当您考虑链接列表的向量类似时（我不这样做）：不会将挂接元素的连续向量挂在存储桶上实际上根据标准的要求，保证现有对象在插入过程中不会移动，而这些插入不会增加超出max_load_factor（）的负载因数，从而触发整个表的重新散列。尽管你提到了“'hash_set”“，这是Pre-C++ 11实现的通用名称，并且它们各不相同，所以大多数人都认为实现选择并不多。 –

@TonyD我也不考虑它们与我的第一段相似，记忆“连续性”在这里非常重要。我知道，人们可以想到的移动空间更小，我认为我曾经讨论过一次（甚至认为它与你同在），有一些微妙的规则基本上排除了某些实现。尽管如此，仍然足以影响某些情况下的表现。海事组织是非常脆弱的，真的需要衡量。我会更新答案永远不会少。复制到矢量中可能会成为最佳选择。 – luk32

从最快到最慢的迭代应该是：set> map> unordered_set> unordered_map; 集合比map更轻一点，它们按照二叉树规则排序，因此应该比unordered_容器快。

来源

2015-07-21 08:49:03 hero

迭代有序与无序容器

回答

相关问题