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

Question

我有一个程序：

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

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

我想知道如果我这样做堆是否会更快：

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

2. 对向量进行排序

3. 将数据保存到磁盘

甚至使用堆：

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

2. 在向量中堆

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

什么会最快？

标签： c++algorithmdata-structuresstl

Answer 1

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

• 在 an 中插入元素std::map是容器大小的对数。插入n 个元素将是O(n log n)。
• 应用于std::sortanstd::vector是O(n log n)。
• 创建堆可以在线性时间内完成std::make_heap。但是，从堆中弹出一个元素是堆大小的对数。从堆中弹出n 个元素是O(n log n)。

但是，我希望由排序std::vector和堆组成的方法比使用 的方法更快，std::map因为由于更好的数据局部性，它们可以更多地利用缓存，即这两种情况下的元素由内存中连续分配的块组成而不是像std::map.

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