c++ - set vs unordered_set 最快迭代

Question

在我的应用程序中，我有以下要求 -

1. 数据结构将只用一些值(不是键/值对)填充一次。这些值可能会重复，但我希望数据结构只存储一次。

2. 我将遍历上面创建的数据结构的所有元素 100 次。元素在迭代中出现的顺序无关紧要。

约束 1 表明我必须使用 set 或 unordered_set，因为数据不是键值对的形式。

现在集合插入比 unordered_set 插入成本更高，但数据结构仅在我的程序开始时填充一次。

我相信决定因素将是我能够以多快的速度迭代数据结构的所有元素。为此，我不确定 set 或 unordered_set 是否会更快。我相信标准没有提到这个事实，因为对于任何一种数据结构，这个操作都是 O(n)。但我想知道哪个数据结构 iterator.next() 会更快。

Answer 1

有几种方法。

1. 对您的问题的评论建议保留一个 std::unordered_set 具有最快的 O(1) 查找/插入和 O(N)迭代(每个容器都有)。如果您的数据变化很大，或者需要大量随机查找，这可能是最快的。但是测试。
2. 如果您需要在没有中间插入的情况下迭代 100 次，您可以将单个 O(N) 复制到 std::vector 并从连续内存中获益布局 100 次。 测试这是否比常规的 std::unordered_set 更快。​​
3. 如果您在迭代之间有少量中间插入，则使用专用 vector 可能会有所帮助。如果可以使用 Boost.Container , 试试 boost::flat_set 它提供了一个 std::set 接口(interface)和一个 std::vector 存储后端(即一个连续的内存非常缓存和预取友好的布局)。同样，测试这是否可以加快其他两种解决方案的速度。

对于最后一个解决方案，请参阅 Boost 文档以了解一些权衡(最好了解所有其他问题，例如迭代器无效、移动语义和异常安全):

Boost.Container flat_[multi]map/set containers are ordered-vector based associative containers based on Austern's and Alexandrescu's guidelines. These ordered vector containers have also benefited recently with the addition of move semantics to C++, speeding up insertion and erasure times considerably. Flat associative containers have the following attributes:

• Faster lookup than standard associative containers
• Much faster iteration than standard associative containers
• Less memory consumption for small objects (and for big objects if shrink_to_fit is used)
• Improved cache performance (data is stored in contiguous memory)
• Non-stable iterators (iterators are invalidated when inserting and erasing elements)
• Non-copyable and non-movable values types can't be stored
• Weaker exception safety than standard associative containers (copy/move constructors can throw when shifting values in erasures and insertions)
• Slower insertion and erasure than standard associative containers (specially for non-movable types)

注意:查找速度更快，这意味着 flat_set 在连续内存上执行 O(log N) 而不是 O(log N) 指针追逐常规 std::set。当然，std::unordered_set 会进行 O(1) 查找，这对于较大的 N 会更快。