有序列表的最佳数据结构(性能)

Question

我有一个关于我的应用程序的关键部分，它包括获取一个数据源(无序)，然后按照顺序对每个元素执行一个算法。实际上，我遵循下一个算法：

• 读取源并将其放到std::map中，使用排序元素作为键，信息作为内容。
• 使用迭代器读取映射并执行算法。

我看到地图可能不是最好的数据结构，因为我只需要将数据添加到排序列表中，然后“烧掉”列表(而且，在移动设备上内存分配成本很高，所以我更愿意自己做)。

我做了一些研究，我正在读一些像B树和黑红树之类的东西。他们可能是我正在寻找的，但我在这里会问，是否有人知道一个数据结构是方便的，为这项任务。

简言之，我想要一个结构，包括：

• 快速插入。
• 快速迭代(从开始到结束)。
• 其他一切都不重要(既不删除也不搜索)。

另外，快速插入比快速迭代更重要(我的分析器这样说:D)。

谢谢大家。

Answer 1

至少有两个有效的解决方案：

1. 将元素附加到向量中；对向量进行排序；扫描向量。
2. 将元素插入到priority_queue中，然后将其耗尽。

该向量具有O(N)加载时间(相对于priority_queue的O( N ) )的优势。(请注意，由于排序，它仍然需要O(N log )整体)。

当您耗尽内存时，priority_queue具有释放内存的优点。这并不能减少最大内存占用，而且可能会带来微不足道的好处，但还是值得一试。

Answer 2

理论上更好的方法是使用堆形。

然而，在实践中，最快的方法是将元素附加到向量中，并使用快速排序对它们进行排序。

在这两种情况下，平均取O( N* log(N) )，但Quick排序的常数因子最低。

Answer 3

如果您的键在有限的值范围内，您可能需要考虑使用桶式。