创建C ++向量的排序副本最有效的方法是什么？

Question

给定一个C ++向量（假设它是双精度数，我们称它为unsorted），最有效的方法是创建一个新的向量sorted，该向量包含一个排序的副本unsorted？

考虑以下简单的解决方案：

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

此解决方案有两个步骤：

1. 创建的完整副本unsorted。
2. 把它分类。

但是，在步骤1的初始副本中可能会浪费很多精力，尤其是对于（例如）已经被大量排序的大型矢量而言。

如果我用手编写此代码，则可以通过将第一遍读取unsorted向量中的值，同时将它们（根据需要进行部分排序）写入向量中，从而将排序算法的第一遍与步骤1结合起来sorted。根据算法，随后的步骤可能仅适用于中的数据sorted。

有没有办法使用C ++标准库，Boost或第三方跨平台库来执行此操作？

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

---

编辑：由于答案和评论不一定了解为什么“单纯的解决方案”效率低下，请考虑以下情况：unsorted数组实际上已经按排序顺序排序（或者只需要一次交换就可以排序）。在那种情况下，无论采用哪种排序算法，使用朴素的解决方案，每个值都至少需要读取两次-复制时一次，排序时一次。但是使用分时复制解决方案，读取次数可能减半，因此性能大约翻倍。unsorted当使用性能更高的排序算法std::sort（可能是O（n）而不是O（n log n））时，不管中的数据如何，都会出现类似的情况。

Answer 1

标准库（故意）没有复制时排序功能，因为副本是O（n），而副本std::sort是O（n log n）。

因此，对于任何较大的n值，排序将完全控制成本。（如果n小，那也没关系）。