我们有一个代码，最初使用deque作为容器。不幸的是，对于我们的时间测量来说，它不够快，因为它需要相当长的时间来进行搜索或排序。因此，我最近重构了代码以尝试改用集合。在搜索和排序方面，它绝对比 deque 更快。
不过，我注意到的一件事是，在遍历所有元素时，该集合的速度要慢得多。我们有一个测试，基本上只是从开始到结束遍历元素，直到它与它正在寻找的值匹配，并发现该集合花费的时间几乎是 deque 所需时间的 5 倍。
有人可以解释为什么集合较慢吗？我假设时间大致相同，因为它只是从头到尾遍历所有元素，但事实并非如此。我已经做了很多搜索，但找不到任何关于一个集合在遍历其元素时较慢的信息。
更新：set/deque 包含一个基本上有两个整数成员变量的类。
class Element
{
uint32_t id;
uint32_t time;
};
Compile options:
-g -pipe -funit-at-a-time
-O3 --param inline-unit-growth=10000 --param large-function-growth=10000 --param max-inline-insns-single=10000
-Wall -Wextra -Wno-aggregate-return -Wno-padded -Wno-reorder -Wno-sign-compare -Wno-unused-parameter -Wcast-align -Wcast-qual -Wdisabled-optimization -Wfloat-equal -Wno-inline -Wlarger-than-10000 -Wmissing-format-attribute -Wpointer-arith -Wredundant-decls -Wno-unknown-pragmas
集合遍历中有两个方面比列表遍历更困难。缓存位置，如注释中所述，以及将状态存储到迭代器的必要性。
这些集合通常实现为自平衡树 - 因为从排序的数据生成二叉树将产生退化树，链表，它不允许O(log N(插入，删除或查找。 自平衡属性将导致从相邻内存地址分配的节点(可能但不一定(以任意顺序访问，从而导致更多的缓存未命中。
另一个问题是，使用迭代器遍历树需要在迭代器中编码状态机——推进迭代器需要知道，是移动到左子项旁边还是移动到右子项旁边，从而导致分支预测的数量也增加。
ADD：
二叉树确实是反缓存友好的，但我想这不是主要问题。
.........................
dequeue：：iterator++ 只是 (index++(%size(在数组上实现(，或者取它的下一个指针(在链表上实现(。
set：：iterator++ 是树中的无序遍历。 想象一下，当前位置在根的前身，所以下一个是根。 它应该向上并验证当前节点是否是左子节点，直到它是，并且根是当前节点的父节点。因此，取消队列中的遍历
比集合中的遍历更琐碎。............
...............
std：：set 是基于 RB-Tree(一种 BST(实现的。
find(( 是在意识到 BST 的情况下实现的，它是 O(logn(。
如果从最左边遍历到最右边以查找元素，则开销为 O(n(。
从begin((到end((的遍历实际上是RB树的In顺序遍历，而find((只是从根向下并比较两个子键。