c++ - 哪种数据结构更适合 - 堆还是排序数组？

Question

我有一个程序:

1. 将一些数据从磁盘加载到内存中的std::map中。 std::map 保持数据排序。

2. 将排序后的数据保存到磁盘

我想知道如果这样做的话堆是否会更快:

1. 将一些数据从磁盘加载到内存中的 std::vector 中。

2. 对 vector 进行排序

3. 将数据保存到磁盘

甚至使用堆:

1. 将一些数据从磁盘加载到内存中的 std::vector 中。

2. 在 vector 中创建一个堆

3. 从堆中弹出并将数据保存到磁盘

什么最快？

Answer 1

渐近地，你的所有方法都是O(n log n):

• 在 std::map 中插入元素与容器大小成对数关系。插入 n 个元素的时间复杂度为 O(n log n)。
• 在 std::vector 上应用 std::sort 的复杂度是O(n log n)。
• 使用 std::make_heap 可以在线性时间内创建堆。然而，从堆中弹出一个元素与堆的大小成对数关系。从堆中弹出 n 个元素的时间复杂度为 O(n log n)。

但是，我希望对 std::vector 和堆进行排序的方法比使用 std::map 的方法更快，因为它们需要更多的时间由于更好的数据局部性，缓存的优势，即，这两种情况下的元素由内存中连续分配的 block 组成，而不是像 std::map< 那样分散在内存中的节点.

另请注意，使用 std::map 的方法比其他两种方法需要更多的空间，因为指针将 map 的节点粘合在一起。