使用c++(最好是标准库),我想对一个样本序列进行升序排序,但我也想记住新样本的原始索引。

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

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

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

有谁能想到一个好办法吗?


当前回答

lukasz Wiklendt的漂亮解决方案!虽然在我的情况下,我需要一些更通用的东西,所以我修改了一点:

template <class RAIter, class Compare>
vector<size_t> argSort(RAIter first, RAIter last, Compare comp) {

  vector<size_t> idx(last-first);
  iota(idx.begin(), idx.end(), 0);

  auto idxComp = [&first,comp](size_t i1, size_t i2) {
      return comp(first[i1], first[i2]);
  };

  sort(idx.begin(), idx.end(), idxComp);

  return idx;
}

示例:查找按长度排序字符串向量的索引,除第一个元素为假元素外。

vector<string> test = {"dummy", "a", "abc", "ab"};

auto comp = [](const string &a, const string& b) {
    return a.length() > b.length();
};

const auto& beginIt = test.begin() + 1;
vector<size_t> ind = argSort(beginIt, test.end(), comp);

for(auto i : ind)
    cout << beginIt[i] << endl;

打印:

abc
ab
a

其他回答

考虑使用@Ulrich Eckhardt建议的std::multimap。只是代码可以变得更简单。

鉴于

std::vector<int> a = {5, 2, 1, 4, 3};  // a: 5 2 1 4 3

在插入的平均时间内排序

std::multimap<int, std::size_t> mm;
for (std::size_t i = 0; i != a.size(); ++i)
    mm.insert({a[i], i});

检索值和原始索引

std::vector<int> b;
std::vector<std::size_t> c;
for (const auto & kv : mm) {
    b.push_back(kv.first);             // b: 1 2 3 4 5
    c.push_back(kv.second);            // c: 2 1 4 3 0
}

首选std::multimap而不是std::map的原因是允许原始向量的值相等。另外请注意,与std::map不同,操作符[]没有为std::multimap定义。

使用c++ 11 lambdas:

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

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

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

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

向量中的项是唯一的吗?如果是这样,复制向量,排序一个副本与STL排序,然后你可以找到每个项目在原始向量的索引。

如果向量应该处理重复的项,我认为你最好实现自己的排序例程。

vector<pair<int,int> >a;

for (i = 0 ;i < n ; i++) {
    // filling the original array
    cin >> k;
    a.push_back (make_pair (k,i)); // k = value, i = original index
}

sort (a.begin(),a.end());

for (i = 0 ; i < n ; i++){
    cout << a[i].first << " " << a[i].second << "\n";
}

现在a包含了我们的值和它们在排序中的下标。

[我]。First =第i条的值。

[我]。Second =初始数组中的idx。

在函数中创建std::pair,然后对pair进行排序:

通用版本:

template< class RandomAccessIterator,class Compare >
auto sort2(RandomAccessIterator begin,RandomAccessIterator end,Compare cmp) ->
   std::vector<std::pair<std::uint32_t,RandomAccessIterator>>
{
    using valueType=typename std::iterator_traits<RandomAccessIterator>::value_type;
    using Pair=std::pair<std::uint32_t,RandomAccessIterator>;

    std::vector<Pair> index_pair;
    index_pair.reserve(std::distance(begin,end));

    for(uint32_t idx=0;begin!=end;++begin,++idx){
        index_pair.push_back(Pair(idx,begin));
    }

    std::sort( index_pair.begin(),index_pair.end(),[&](const Pair& lhs,const Pair& rhs){
          return cmp(*lhs.second,*rhs.second);
    });

    return index_pair;
}

ideone