如何以不改变原向量的方式对向量进行排序？

Question

正如标题所说，我正在寻找一种在不修改原始向量的情况下对其进行排序的方法。 我的第一个想法当然是在排序之前创建向量的副本，例如：

如题所述，我希望找到一种在不修改原始向量的情况下对其进行排序的方法。 我的第一个想法当然是在排序之前创建向量的副本：

std::vector<int> not_in_place_sort(const std::vector<int>& original)
{
   auto copy = original;
   std::sort(copy.begin(), copy.end());
   return copy;
}

然而，也许有一种更高效的方法可以使用C++标准算法来执行排序（或许是sort和transform的组合）？

- Emiliano

---

将向量按值传递，这样它就是函数内部的局部变量，排序并返回结果。这是您能得到的最佳方式。 - DeiDei

请解释一下“排序”的含义。如果您想要一个已排序的向量，那么您不可能避免复制和排序。 - Passer By

@Emiliano -- 一个选项 -- 不要对向量本身进行排序 -- 你可以对索引数组进行排序，并使用它来索引向量。 - PaulMcKenzie

@PaulMcKenzie 聪明 :) - Emiliano

@DeiDei 那不一定是“最好的”。OP的版本更有可能对lvalues更好（只有一个副本）。 - juanchopanza

Answer 1

使用partial_sort_copy。这里有一个例子：

vector<int> v{9,8,6,7,4,5,2,0,3,1};
vector<int> v_sorted(v.size());
partial_sort_copy(begin(v), end(v), begin(v_sorted), end(v_sorted));

现在，v保持不变，但v_sorted 包含{0,1,2,3,4,5,6,7,8,9}。

- Erel Segal-Halevi

---

这个解决方案被低估了。 - Thomas

这个解决方案被高估了：它没有解释为什么partial_sort_copy比最初复制向量并在结果上调用std::sort更好。 只有当两个范围的长度相同时，它才不是“partial”。 它更快吗？ 更易读吗？ 我认为答案对于这两个问题都是否定的。 - Seth Johnson

@SethJohnson 它应该至少比向量的复制传递更快。这正是提问者可能试图实现的，不是复制然后排序，而是直接将排序后的值写入目标。partial 应该真正意味着 general。 - Jan Hošek

Answer 2

这是我的最爱。对索引进行排序，而不是原始的数组/向量本身。

#include <algorithm>

int main() {

    int intarray[4] = { 2, 7, 3, 4 };//Array of values
    //or you can have vector of values as below
    //std::vector<int> intvec = { 2, 7, 3, 4 };//Vector of values
    int indexofarray[4] = { 0, 1, 2, 3 };//Array indices

    std::sort(indexofarray, indexofarray + 4, [intarray](int index_left, int index_right) { return intarray[index_left] < intarray[index_right]; });//Ascending order.
    //have intvec in place of intarray for vector.


}

执行此操作后，indexofarray[] 元素将变为 0, 2, 3, 1，而 intarray[] 不会改变。

- Tryer

Answer 3

正如评论中建议的一样，按值传递函数参数 std::vector<int> original:

#include <iostream>
#include <vector>
#include <algorithm>

std::vector<int> not_in_place_sort(std::vector<int> original) {
    std::sort(original.begin(), original.end());
    return original;
}

int main() {
    std::vector<int> v = { 8, 6, 7, 2, 3, 4, 1, 5, 9 };
    std::vector<int> v2 = not_in_place_sort(v); // pass the vector by value
    std::cout << "v1: " << '\n';
    for (auto el : v) {
        std::cout << el << ' ';
    }
    std::cout << "\nv2: " << '\n';
    for (auto el : v2) {
        std::cout << el << ' ';
    }
}

这将对原向量进行副本排序，使原始向量保持不变。

如下所述，这可能会限制一些优化，例如RVO，但是在return语句中将调用vector的移动构造函数。

- Ron

---

那会抑制RVO。这不是什么大问题，因为返回值会被移动，但根据应用程序的不同，这可能很重要。 - juanchopanza

这如何禁止 RVO？我认为它应该按照描述的那样工作。更好的是，v = not_in_place_sort(std::move(v)) 应该几乎和 std::sort(v.begin(), v.end()) 一样便宜。 - Seth Johnson

好的，这确实可以防止RVO。但是只要容器具有移动构造函数，按值传递和按值返回就会提供最大的灵活性并改善调用代码的清晰度：“sorted(std::move(v))”意味着假设v在函数之后将不再有效，“sorted(v)”则表示它仍然有效。 - Seth Johnson

Answer 4

如果你对代理排序（对索引列表进行排序）感兴趣，你可能需要实现一个更加灵活的算法，以处理不支持随机访问的容器（例如 std::list）。例如：

#include <algorithm>
#include <iostream>
#include <list>
#include <numeric>
#include <vector>

template <typename Container>
auto sorted_indices(const Container& c) {
  std::vector<typename Container::size_type> indices(c.size());
  std::iota(indices.begin(), indices.end(), 0);
  std::sort(indices.begin(), indices.end(), [&c](auto lhs, auto rhs) {
    return (*(std::next(c.begin(), lhs)) < *(std::next(c.begin(), rhs)));
  });
  return indices;
}

template <typename Container, typename Indices>
auto display_sorted(const Container& c, const Indices& indices) {
  std::cout << "sorted: ";
  for (auto&& index : indices) {
    std::cout << *(std::next(c.begin(), index)) << " ";
  }
  std::cout << std::endl;
}

template <typename Container>
auto display_sorted(const Container& c) {
  return display_sorted(c, sorted_indices(c));
}

template <typename Container>
auto display(const Container& c) {
  std::cout << "as provided: ";
  for (auto&& ci : c) std::cout << ci << " ";
  std::cout << std::endl;
}

int main() {
  // random access
  const std::vector<int> a{9, 5, 2, 3, 1, 6, 4};
  display(a);
  display_sorted(a);
  display(a);

  std::cout << "---\n";

  // no random access
  const std::list<int> b{9, 5, 2, 3, 1, 6, 4};
  display(b);
  display_sorted(b);
  display(b);
}

样例运行：

$ clang++ example.cpp -std=c++17 -Wall -Wextra
$ ./a.out
as provided: 9 5 2 3 1 6 4 
sorted: 1 2 3 4 5 6 9 
as provided: 9 5 2 3 1 6 4 
---
as provided: 9 5 2 3 1 6 4 
sorted: 1 2 3 4 5 6 9 
as provided: 9 5 2 3 1 6 4 

正如你所预料的，依赖代理排序可能会对性能产生重要影响。例如：每次想要按顺序遍历时，你可能会遇到缓存未命中。此外，遍历的复杂度将与用于随机访问的底层容器相同：在std::vector的情况下，std::next(v.begin(), n)是O(1)，但在std::list的情况下，std::next(l.begin(), n)是O(n)。

- Escualo

Answer 5

对于int类型，无论是对索引进行排序还是复制并排序副本，差别不大；数据仍然需要初始化，在索引的情况下，这将涉及循环分配值而不是更快的memcpy例程；因此可能会变慢；另外，你将要在内存中跳来跳去；所以现在缓存无法很好地发挥作用。

对于较大的对象，我不会对索引进行排序，而是使用指针向量。指针的副本与复制对象本身相比便宜；容器仍然很明显，因为它们包含你的对象的指针；而且排序不会尝试引用另一个向量。

- UKMonkey

Answer 6

你可以创建另一个向量来存储索引。以下是代码:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
    vector<int> numbers = {50,30,20,10,40};
    vector<int> indexOfNumbers;
    
    for(int i = 0; i < numbers.size(); i++)
    {
        indexOfNumbers.push_back(i); 
    }
    // Now, indexOfNumbers = [0,1,2,3,4]

    std::sort(
        indexOfNumbers.begin(), indexOfNumbers.end(), 
        [numbers](int leftIndex, int rightIndex) 
        { 
            return numbers[leftIndex] < numbers[rightIndex]; // sort in ascending order
        }
    );
    // After sorting, indexOfNumbers = [3, 2, 1, 4, 0]

    // Access the sorted elements
    cout << "Accessing the sorted elements : ";
    for(int i = 0; i < numbers.size(); i++)
    {
        cout << numbers[indexOfNumbers[i]] << " ";
    }
    // prints numbers in sorted order i.e. [10,20,30,40,50]
   return 0;
}

来源：根据Tyrer的回答稍作修改（https://dev59.com/dVYN5IYBdhLWcg3wXnP7#47537314）

- Puneeth G R