C++排序和跟踪索引

Question

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

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

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

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)()) ;

Answer 4

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包含我们的值和它们在排序中的相应索引.

a[i].first = value在i'th.

a[i].second = idx 在初始数组中.

Answer 5

它似乎比它看起来容易.

假设给定的向量是

A=[2,4,3]

创建一个新的向量

V=[0,1,2] // indicating positions

排序V并在排序时而不是比较V的元素,比较A的相应元素

 //Assume A is a given vector with N elements
 vector<int> V(N);
 int x=0;
 std::iota(V.begin(),V.end(),x++); //Initializing
 sort( V.begin(),V.end(), [&](int i,int j){return A[i]<A[j];} );

Answer 6

我遇到了这个问题,并想出直接对迭代器进行排序将是一种对值进行排序并跟踪索引的方法; 没有必要定义一个额外的pairs(value,index)容器,当值是大对象时这是有用的; 迭代器提供对值和索引的访问:

/*
 * a function object that allows to compare
 * the iterators by the value they point to
 */
template < class RAIter, class Compare >
class IterSortComp
{
    public:
        IterSortComp ( Compare comp ): m_comp ( comp ) { }
        inline bool operator( ) ( const RAIter & i, const RAIter & j ) const
        {
            return m_comp ( * i, * j );
        }
    private:
        const Compare m_comp;
};

template <class INIter, class RAIter, class Compare>
void itersort ( INIter first, INIter last, std::vector < RAIter > & idx, Compare comp )
{ 
    idx.resize ( std::distance ( first, last ) );
    for ( typename std::vector < RAIter >::iterator j = idx.begin( ); first != last; ++ j, ++ first )
        * j = first;

    std::sort ( idx.begin( ), idx.end( ), IterSortComp< RAIter, Compare > ( comp ) );
}

至于用法示例:

std::vector < int > A ( n );

// populate A with some random values
std::generate ( A.begin( ), A.end( ), rand );

std::vector < std::vector < int >::const_iterator > idx;
itersort ( A.begin( ), A.end( ), idx, std::less < int > ( ) );

现在,例如,排序向量中的第五个最小元素将具有值,**idx[ 5 ]并且其在原始向量中的索引将是distance( A.begin( ), *idx[ 5 ] )或简单地*idx[ 5 ] - A.begin( ).

Answer 7

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

或者，也许您可​​以使用一个映射，其中键是元素，值是其在即将到来的数组中的位置列表（A、B 和 C）

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