5

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

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

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

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

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

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

快速插入也比快速迭代更重要（我的分析器这么说：D）。

谢谢大家。

4

4 回答 4

3

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

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

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

于 2013-06-25T12:15:57.610 回答
3

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

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

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

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

于 2013-06-25T11:59:41.923 回答
2

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

于 2013-06-25T14:24:20.743 回答
0

我建议写一个跳过列表。这正是您所要求的 - 带有O(log(n))插入的排序列表。它也相对容易实现。

于 2013-06-25T12:33:11.063 回答