c++ - 为什么 std::set 遍历所有元素的速度较慢？

Question

我们有一段代码最初使用双端队列作为容器。不幸的是，对于我们的时间测量来说，它的速度不够快，因为它需要相当长的时间来进行搜索或排序。因此，我最近重构了代码以尝试使用集合。它在搜索和排序方面肯定比双端队列更快。

但我注意到的一件事是，在遍历所有元素时，集合的速度要慢得多。我们有一个测试，基本上只是从头到尾遍历元素，直到它匹配它正在寻找的值，并发现该集合花费的时间几乎是双端队列完成它所花费的时间的 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

Answer 1

集合遍历有两个方面比列表遍历更难。缓存位置，如评论中所述，以及将状态存储到迭代器的必要性。

这些集合通常实现为自平衡树——因为从排序数据生成二叉树会产生退化树，链表，不允许 O(log N) 插入、删除或查找。自平衡属性将导致(可能但不一定)从相邻内存地址分配的节点以任意顺序访问，从而导致更多缓存未命中。

另一个问题是，用迭代器遍历树需要在迭代器中编码一个状态机——推进迭代器需要知道，是移动到左 child 的旁边还是右 child ，导致也分支预测数量增加。