set vs unordered_set用于最快的迭代

Question

在我的申请中,我有以下要求 -

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

2. 我将通过上面创建的数据结构的所有元素迭代100次.元素在迭代中出现的顺序并不重要.

约束1表明我将不得不使用set或unordered_set,因为数据不是键值对的形式.

现在set插入比unordered_set插入更昂贵,但数据结构只在我的程序开头填充一次.

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

Answer 1

有几种方法.

1. 对你的问题的评论建议保持一个std::unordered_set具有最快的O(1)查找/插入和O(N)迭代(如每个容器).如果您的数据变化很大,或需要大量随机查找,这可能是最快的.但测试.
2. 如果您需要在没有中间插入的情况下迭代100次,您可以执行一次O(N)复制到a std::vector并从连续的内存布局中获取100次.测试这是否比常规更快std::unordered_set.
3. 如果在迭代之间进行少量中间插入,则可以使用专用向量.如果您可以使用Boost.Container,请尝试boost::flat_set提供std::set具有std::vector存储后端的接口(即,非常缓存和预取友好的连续内存布局).再次,测试这是否能提高其他两个解决方案的速度.

对于最后的解决方案,请参阅Boost文档以获取一些权衡(了解所有其他问题,如迭代器失效,移动语义和异常安全性):

Boost.Container flat_ [multi] map/set容器是基于Austern和Alexandrescu指南的基于有序矢量的关联容器.这些有序的向量容器最近也受益于向C++添加移动语义,大大加快了插入和擦除时间.扁平关联容器具有以下属性:

• 比标准关联容器更快的查找
• 迭代比标准关联容器快得多
• 小对象(如果使用shrink_to_fit,对于大对象)的内存消耗更少
• 改进的缓存性能(数据存储在连续的内存中)
• 非稳定迭代器(插入和擦除元素时迭代器无效)
• 不能存储不可复制和不可移动的值类型
• 比标准关联容器更弱的异常安全性(复制/移动构造函数在擦除和插入时移动值时可以抛出)
• 比标准关联容器更慢的插入和擦除(特别是对于不可移动的类型)

注意:更快的查找,它是指一个flat_set不O(log N)上连续的内存,而不是O(log N)一个普通的指针跟踪std::set.当然,std::unordered_set做一次O(1)查找,对于大型会更快N.

Answer 2

我建议你使用set或unordered_set进行"过滤",当你完成后,将数据移动到固定大小的向量