c++ - 在单个排序调用 C++ 中对多个 vector 进行排序

Question

This answer演示了如何使用漂亮的新式 C++11 功能对值 vector 使用 std::sort 有效地获取索引 vector (该问题也有多种重复)。它还暗示您可以通过“使用额外的 vector ”获得已排序 vector 和已排序索引的双重输出。但是，我可以实现此目的的唯一方法是再次调用 std:sort。我正在处理长度为数十，也许数百，数千个元素的数组，试图专注于效率。是否可以通过对 std::sort 的一次调用同时获得排序 vector 和排序索引？

更一般地说，我的问题是:可以通过一次排序调用对多个 vector 进行排序吗？假设排序顺序仅基于提供的 vector 之一。

我在此期间提出的内容如下(对链接答案中的代码进行了轻微修改)。如您所见，它需要为每个正在排序的 vector 调用 std::sort，即使它们都将根据单个 vector 的排序进行排序。我怀疑可能有一种方法可以通过传递对 lambda 比较函数的引用来做到这一点，但我似乎无法让它工作。

#include <numeric>
#include <algorithm>

using std;

void sort_vectors(vector<size_t> idx, vector<double> &v) {

  // sort indexes based on comparing values in v
  sort(idx.begin(), idx.end(),
       [&v](size_t i1, size_t i2) {return v[i1] < v[i2];});

  // Sort the actual vector
  sort(v.begin(), v.end());

  return idx;
}

Answer 1

std::sort 采用迭代器:虽然自定义排序可能会在单个排序步骤中同时采用索引和值，但它不太可能有多大用处(并且可能需要不同的算法，从而使其变慢)。

算法设计

为什么？因为 std::sort 在 O(n*logn) 时间内执行。从排序的索引中移动元素将花费 O(n) 时间，相比之下这相对便宜。

使用上面的示例，在给定的链接中，我们有以下现有代码:

using namespace std;

template <typename T>
vector<size_t> sort_indexes(const vector<T> &v) 
{

  // initialize original index locations
  vector<size_t> idx(v.size());
  iota(idx.begin(), idx.end(), 0);

  // sort indexes based on comparing values in v
  sort(idx.begin(), idx.end(),
       [&v](size_t i1, size_t i2) {return v[i1] < v[i2];});

  return idx;
}

我们现在可以从这些索引创建一个排序数组，这是一个简单的步骤:

template <typename T>
vector<T> sorted_array(const vector<T> &v, const vector<size_t>& i) 
{
    vector<T> out;
    out.reserve(v.size())
    for (auto j: i) {
        out.emplace_back(v[j]);
    }
}

如果无法复制值，您可以使用 std::reference_wrapper 创建一个不可为 null 的包装器。

template <typename T>
vector<reference_wrapper<const T>> sorted_array(const vector<T> &v, const vector<size_t>& i) 
{
    vector<reference_wrapper<const T>> out;
    out.reserve(v.size())
    for (auto j: i) {
        out.emplace_back(std::cref(v[j]));
    }
}

即使对于大型阵列，这也应该非常有效。

注意

不要尝试同时对两个数组进行排序。对索引数组进行排序时，不要尝试移动值数组中的项目。为什么？因为值数组的比较是基于索引的:移动项目会破坏原始数组中的排序。因为一旦有了排序的索引，将项目移动到正确的位置就非常便宜，所以不要担心这里的性能:排序是瓶颈。