c++ - 具有 O(1) 插入(分摊)和 O(n) 迭代的容器

Question

我正在寻找具有以下基本属性的类似集合的容器类:

1. 已摊销 O(1) 插入时间，忽略重复插入
2. 有 O(n) 次迭代时间(特别是 O(capacity) 是 Not Acceptable )
3. 重用内存/仅在超出当前容量时分配

用例是我有一个更大的对象容器。在每个循环 期间，我会将这些对象的一个​​子集添加到这个新容器中。此子集可以来自 1-5 个对象或最多占整个集合的 10%。然后我迭代这个新集合中的对象。每个循环对象将被清除并重新开始处理。

我最初的方法是在对象上使用侵入式 bool 值来指示它是否属于这个新集合。因此插入是真正的恒定时间，并且它不使用新的内存。然而，迭代是次优的。

我已经尝试了 boost::unordered_set 并获得比我原来的方法更差的性能。大概是因为，作为 HashMap ，它无法满足第 2 点。

第 3 点是相关的，因为我在内存分配成本非常高的延迟级别进行编码。因此，具有连续分配的容器极不可能表现良好。

Answer 1

使用您的第一种方法来检测元素是否已经在集合( HashMap )中。并将它也放在一个列表中进行迭代..