有序列表的最佳数据结构（性能）

Question

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

• 读取源代码并将其放入 std::map，使用排序元素作为键和信息作为内容。
• 使用迭代器读取地图并执行算法。

我看到地图可能不是最好的数据结构，因为我只需要将数据添加到一个排序列表中，然后完全“刻录”列表（此外，移动设备上的内存分配成本很高，所以我更愿意这样做我自己）。

我做了一些研究，我正在阅读诸如 B 树和黑红树之类的东西。它们可能是我正在寻找的东西，但我会在这里问是否有人知道适合该任务的数据结构。

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

• 快速插入。
• 快速迭代（从开始到结束）。
• 其他一切都不重要（无论是删除还是搜索）。

此外，快速插入比快速迭代更重要（我的分析器是这样说的：D）。

谢谢大家。

Answer 1

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

1. 将元素附加到向量；对向量进行排序；扫描向量。
2. 将元素插入到priority_queue中；将其沥干。

该向量的优点是加载时间为 O(N)（相对于priority_queue 为 O(N log N)）。（请注意，由于排序的原因，总体上仍然需要 O(N log N)）。

Priority_queue 的优点是可以在耗尽内存时释放内存。这不会减少最大内存占用，并且可能带来的好处可以忽略不计，但无论如何都值得尝试。