时间戳

首页 > 解决方案 > 为什么 std::set 遍历所有元素的速度较慢？

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

问题描述

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

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

标签： c++stlset

解决方案

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

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

另一个问题是，使用迭代器遍历树需要在迭代器中编码状态机——推进迭代器需要知道是移动到左子节点还是右子节点，从而导致分支预测。

推荐阅读