C++ 排序和跟踪索引

Question

使用 C++，希望使用标准库，我想按升序对一系列样本进行排序，但我也想记住新样本的原始索引。

例如，我有一个样本集、 vector 或矩阵A : [5, 2, 1, 4, 3]。我想将这些排序为 B : [1,2,3,4,5]，但我也想记住这些值的原始索引，所以我可以得到另一个集合:C : [2, 1, 4, 3, 0 ] - 对应于原始'A'中'B'中每个元素的索引。

例如，在 Matlab 中你可以这样做:

 [a,b]=sort([5, 8, 7])
 a = 5 7 8
 b = 1 3 2

任何人都可以找到这样做的好方法吗？

Answer 1

使用 C++ 11 个 lambda:

#include <iostream>
#include <vector>
#include <numeric>      // std::iota
#include <algorithm>    // std::sort, std::stable_sort

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
  // using std::stable_sort instead of std::sort
  // to avoid unnecessary index re-orderings
  // when v contains elements of equal values 
  stable_sort(idx.begin(), idx.end(),
       [&v](size_t i1, size_t i2) {return v[i1] < v[i2];});

  return idx;
}

现在您可以在迭代中使用返回的索引 vector ，例如

for (auto i: sort_indexes(v)) {
  cout << v[i] << endl;
}

您还可以选择提供原始索引 vector 、排序函数、比较器，或使用额外 vector 在 sort_indexes 函数中自动重新排序 v。