C ++排序和跟踪索引

Question

C ++排序和跟踪索引使用C ++，希望是标准库，我想按升序对一系列样本进行排序，但我还想记住新样本的原始索引。例如，我有一个集合，矢量或样本矩阵A : [5, 2, 1, 4, 3]。我想对这些进行排序 B : [1,2,3,4,5]，但我也想记住值的原始索引，所以我可以得到另一个集合： C : [2, 1, 4, 3, 0 ]- 它对应于'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::sorttemplate <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;}

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

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

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

Answer 2

您可以对std :: pair进行排序，而不仅仅是整数 - 第一个int是原始数据，第二个int是原始索引。然后提供一个只对第一个int进行排序的比较器。例：

Your problem instance: v = [5 7 8]New problem instance: v_prime = [<5,0>, <8,1>, <7,2>]

使用比较器对新问题实例进行排序：

typedef std::pair<int,int> mypair;bool comparator ( const mypair& l, const mypair& r)
   { return l.first < r.first; }// forgetting the syntax here but intent is clear enough

使用该比较器的st_ :: sort on v_prime的结果应该是：

v_prime = [<5,0>, <7,2>, <8,1>]

你可以通过遍历向量来剥离索引，从每个std :: pair中获取.second。

Answer 3

我写了索引排序的通用版本。

template <class RAIter, class Compare>void argsort(RAIter iterBegin, RAIter iterEnd, Compare comp, 
    std::vector<size_t>& indexes) {
    std::vector< std::pair<size_t,RAIter> > pv ;
    pv.reserve(iterEnd - iterBegin) ;
    RAIter iter ;
    size_t k ;
    for (iter = iterBegin, k = 0 ; iter != iterEnd ; iter++, k++) {
        pv.push_back( std::pair<int,RAIter>(k,iter) ) ;
    }
    std::sort(pv.begin(), pv.end(), 
        [&comp](const std::pair<size_t,RAIter>& a, const std::pair<size_t,RAIter>& b) -> bool 
        { return comp(*a.second, *b.second) ; }) ;
    indexes.resize(pv.size()) ;
    std::transform(pv.begin(), pv.end(), indexes.begin(), 
        [](const std::pair<size_t,RAIter>& a) -> size_t { return a.first ; }) ;}

除了用于接收已排序索引的索引容器之外，用法与std :: sort的用法相同。测试：

int a[] = { 3, 1, 0, 4 } ;std::vector<size_t> indexes ;argsort(a, a + sizeof(a) / sizeof(a[0]), std::less<int>(), indexes) ;for (size_t i : indexes) printf("%d\n", int(i)) ;

对于没有c ++ 0x支持的编译器，你应该得到2 1 0 3.将lamba表达式替换为类模板：

template <class RAIter, class Compare> class PairComp {public:
  Compare comp ;
  PairComp(Compare comp_) : comp(comp_) {}
  bool operator() (const std::pair<size_t,RAIter>& a, 
    const std::pair<size_t,RAIter>& b) const { return comp(*a.second, *b.second) ; }        } ;

并重写std :: sort as

std::sort(pv.begin(), pv.end(), PairComp(comp)()) ;