在我的应用程序中,我有以下要求 -
数据结构将只用一些值(不是键/值对)填充一次。 这些值可能会重复,但我希望数据结构只存储一次。
我将遍历上面创建的数据结构的所有元素 100 次。元素在迭代中出现的顺序无关紧要。
约束 1 表明我必须使用 set 或 unordered_set,因为数据不是键值对的形式。
现在集合插入比 unordered_set 插入成本更高,但数据结构仅在我的程序开始时填充一次。
我相信决定因素将是我能够以多快的速度迭代数据结构的所有元素。为此,我不确定 set 或 unordered_set 是否会更快。我相信标准没有提到这个事实,因为对于任何一种数据结构,这个操作都是 O(n)。但我想知道哪个数据结构 iterator.next() 会更快。
最佳答案
有几种方法。
- 对您的问题的评论建议保留一个
std::unordered_set
具有最快的O(1)
查找/插入和O(N)
迭代(每个容器都有)。如果您的数据变化很大,或者需要大量随机查找,这可能是最快的。但是测试。 - 如果您需要在没有中间插入的情况下迭代 100 次,您可以将单个
O(N)
复制到std::vector
并从连续内存中获益布局 100 次。 测试这是否比常规的std::unordered_set
更快。 - 如果您在迭代之间有少量中间插入,则使用专用 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
会更快。
关于c++ - set vs unordered_set 最快迭代,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24506789/