使用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

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


当前回答

使用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。

其他回答

还有另一种方法来解决这个问题,使用地图:

vector<double> v = {...}; // input data
map<double, unsigned> m; // mapping from value to its index
for (auto it = v.begin(); it != v.end(); ++it)
    m[*it] = it - v.begin();

这将消除非唯一元素。如果不能接受,使用multimap:

vector<double> v = {...}; // input data
multimap<double, unsigned> m; // mapping from value to its index
for (auto it = v.begin(); it != v.end(); ++it)
    m.insert(make_pair(*it, it - v.begin()));

为了输出索引,迭代map或multimap:

for (auto it = m.begin(); it != m.end(); ++it)
    cout << it->second << endl;

你可以对std::pair进行排序,而不仅仅是整型——第一个整型是原始数据,第二个整型是原始索引。然后提供一个只对第一个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

在v_prime上使用比较器std::sort的结果应该是:

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

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

在函数中创建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

我的解法使用了余数法。我们可以把需要排序的值放在上面2个字节,而把元素的下标放在下面2个字节:

int myints[] = {32,71,12,45,26,80,53,33};

for (int i = 0; i < 8; i++)
   myints[i] = myints[i]*(1 << 16) + i;

然后像往常一样对数组myint进行排序:

std::vector<int> myvector(myints, myints+8);
sort(myvector.begin(), myvector.begin()+8, std::less<int>());

在此之后,您可以通过渣滓访问元素的指数。下面的代码输出按升序排序的值的索引:

for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it)
   std::cout << ' ' << (*it)%(1 << 16);

当然,这种技术只适用于原始数组myint中相对较小的值(即可以装入int的前2个字节的值)。但是它还有一个额外的好处,可以区分相同的myint值:它们的下标将按正确的顺序打印。

如果可能的话,可以使用find函数构建位置数组,然后对数组排序。

或者你可以使用一个映射,其中键是元素,值是它在即将到来的数组(a, B和C)中的位置列表

这取决于以后对这些数组的使用。