c++ - 创建 C++ vector 的排序拷贝的最高效方法是什么？

Question

给定一个 C++ vector (假设它是 double 的，我们称它为 unsorted)，创建一个新 vector sorted 的最佳方法是什么？ unsorted 的已排序拷贝？

考虑以下天真的解决方案:

std::vector<double> sorted = unsorted;
std::sort(sorted.begin(), sorted.end());

这个解决方案有两个步骤:

1. 创建 unsorted 的完整拷贝。
2. 对其进行排序。

但是，在第 1 步的初始拷贝中可能会浪费很多精力，特别是对于(例如)已经基本排序的大型 vector 。

如果我手写这段代码，我可以将我的排序算法的第一遍与步骤 1 结合起来，通过让第一遍在编写时从 unsorted vector 中读取值，部分排序根据需要，放入 sorted。根据算法，后续步骤可能只处理 sorted 中的数据。

有没有办法用 C++ 标准库、Boost 或第三方跨平台库来做这样的事情？

重要的一点是确保在排序开始之前，sorted C++ vector 的内存不会被不必要地初始化为零。许多排序算法需要立即对 sorted vector 进行随机写入访问，因此使用 reserve() 和 push_back() 对第一遍，但是 resize() 会浪费时间初始化 vector 。

---

编辑:由于答案和评论不一定能看出为什么“简单的解决方案”效率低下，请考虑 unsorted 数组实际上已经存在的情况排序顺序(或者只需要一次交换就可以排序)。在那种情况下，不管排序算法如何，使用天真的解决方案每个值都需要至少读取两次——一次是在复制时，一次是在排序时。但使用边复制边排序解决方案，读取次数可能会减半，因此性能大约翻倍。当使用比 std::sort 性能更高的排序算法(可能是 O(n) 而不是 O (n log n)).

Answer 1

标准库 - 故意 - 没有复制时排序功能，因为复制是 O(n) 而 std::sort 是 O(n log n)。

因此，对于任何较大的 n 值，排序将完全支配成本。 (如果 n 很小，那也没关系)。