在单个排序调用 C++ 中对多个向量进行排序 [英] Sorting multiple vectors in single sort call C++

问题描述

这个答案 演示了如何使用 std::sort 有效地获取索引向量使用漂亮的新式 C++11 功能的值向量(该问题也有各种重复).它还暗示您可以通过使用额外的向量"来获得排序向量和排序索引的双重输出.但是，我可以实现这一点的唯一方法是再次调用 std:sort.我正在处理长度为数十、数百、数千个元素的数组，试图专注于效率.是否可以通过对 std::sort 的单个调用同时获得排序向量和排序索引?

This answer demonstrates how to efficiently obtain an indices vector using std::sort on a vector of values using the nice new-ish C++11 functionality (there's also a variety of duplicates of that question as well). It also hints that you can obtain the double output of both the sorted vector and the sorted indices by "using an extra vector." However, the only way I can achieve this is by calling std:sort a second time. I'm working with arrays with lengths of tens, maybe hundreds, of thousands of elements trying to focus on efficiency. Is it possible to obtain both the sorted vector and the indices of the sort from a single call to std::sort?

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

More generally, my question is: can one sort multiple vectors with a single sort call? The assumption is the sorting order is based on only one of the supplied vectors.

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

What I've come up with in the meantime is below (a slight modification to the code in the linked answer). As you can see, it requires a call to std::sort for each vector being sorted, even though they are all to be ordered according to the sorting of a single vector. I suspect there may be a way to do this by passing references to the lambda compare function, but I can't seem to make it work.

#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;
}

推荐答案

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

std::sort takes iterators: Although a custom sort could likely take both indexes and the values in a single sort step, it's unlikely to be of much use (and may require different algorithms, making it slower).

算法设计

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

Why? Because std::sort performs in O(n*logn) time. Moving elements from the sorted indexes will take O(n) time, which is relatively cheap in comparison.

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

Using the example from above, in the link given, we have this existing code:

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;
}

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

We can now create a sorted array from these indexes, a cheap step:

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 的包装器.

If copying the values is too prohibitive, you can use a std::reference_wrapper to create a non-nullable wrapper.

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]));
    }
}

即使对于大型数组，这也应该非常有效.

Even for large arrays, this should be pretty efficient.

注意

不要尝试一次对两个数组进行排序.在对索引数组进行排序时，不要尝试移动值数组中的项目.为什么?因为值数组的比较是基于索引的:移动项目将破坏原始数组中的排序.由于一旦您拥有已排序的索引，将项目移动到正确的位置就非常便宜，因此不必担心这里的性能:排序是瓶颈.

Don't try to sort two arrays at once. Don't try to move items in your value array when sorting the index array. Why? Because the comparison is index-based for the value array: moving items will destroy the sort in the original array. Since moving the items to the correct position is so cheap once you have the sorted indexes, don't worry about performance here: the sort is the bottleneck.

这篇关于在单个排序调用 C++ 中对多个向量进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！