C ++sorting和跟踪索引
使用C ++，希望是标准库，我想按升序对样本序列进行sorting，但我也想记住新样本的原始索引。
例如，我有一个集合，或向量，或样本matrixA : [5, 2, 1, 4, 3] 。 我想把它们sorting为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
任何人都可以看到一个很好的办法做到这一点
使用C ++ 11 lambdaexpression式
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; }
显然，你也可以select使用额外的向量来提供你自己的原始索引向量，sorting函数，比较器，或者在sort_indexes函数中自动重新sortingv。
你可以sortingstd :: pair，而不是只是整数 – 第一个int是原始数据，第二个int是原始索引。 然后提供一个比较器，只对第一个int进行sorting。 例：
Your problem instance: v = [5 7 8] New problem instance: v_prime = [<5,0>, <8,1>, <7,2>]
使用比较器对新的问题实例进行sorting：
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
使用该比较器的std :: sort在v_prime上的结果应该是：
v_prime = [<5,0>, <7,2>, <8,1>]
您可以通过走向量来剥离索引，从每个std :: pair中抓取.second。
我写了索引sorting的通用版本。
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的用法相同，除了索引容器接收有序索引。 testing：
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)) ;
您应该得到2 1 0 3.对于没有c ++ 0x支持的编译器，将lambaexpression式replace为类模板：
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为
std::sort(pv.begin(), pv.end(), PairComp(comp)()) ;
我遇到了这个问题，并认为直接对迭代器进行sorting将是一种对值进行sorting并跟踪索引的方法; 没有必要定义一个（value，index） pair的额外容器，当这些值是大对象的时候它是有帮助的; 迭代器提供对值和索引的访问：
/* * 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 > ( ) );
现在，例如，sorting向量中的第5个最小元素将具有值**idx[ 5 ]并且其在原始向量中的索引将是distance( A.begin( ), *idx[ 5 ] )或者简单地*idx[ 5 ] - A.begin( ) 。
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包含我们的价值和他们各自的指数在sorting。
a[i].first = value第i个a[i].first = value 。
a[i].second = idx初始数组中的a[i].second = idx 。
在函数中做一个std::pair然后sorting对：
通用版本：
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
@Lukasz Wiklendt的美丽解决scheme！ 虽然在我的情况下，我需要更通用的东西，所以我修改了一下：
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; }
示例：查找按长度sortingstring向量的索引，除了第一个元素是虚拟元素。
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
如果可能，可以使用find函数构build位置数组，然后对数组进行sorting。
或者，也许你可以使用一个地图，其中的关键将是元素，值在即将到来的arrays（A，B和C）中的位置列表，
这取决于该arrays的以后使用。
vector中的项目是唯一的吗？ 如果是这样的话，复制vector，用STL Sortsorting其中一个副本，然后你可以find每个项目在原始vector中的索引。
如果向量应该处理重复的项目，我认为你最好实施自己的sorting程序。
还有另一种方法来解决这个问题，使用地图：
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;
那么，我的解决scheme使用残留技术。 我们可以将sorting中的值放在高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;
然后像往常一样对数组myintssorting：
std::vector<int> myvector(myints, myints+8); sort(myvector.begin(), myvector.begin()+8, std::less<int>());
之后，您可以通过残差访问元素的索引。 以下代码打印按升序sorting的值的索引：
for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it) std::cout << ' ' << (*it)%(1 << 16);
当然，这种技术只适用于原始数组myints相对较小的值（即可以放入int高2字节的那些值）。 但它具有区分相同的myints值的额外好处：它们的索引将以正确的顺序打印。
对于这种types的问题将原始数组数据存储到一个新的数据，然后二进制searchsorting数组的第一个元素到重复的数组，该指数应存储到一个向量或数组。
input array=>a duplicate array=>b vector=>c(Stores the indices(position) of the orignal array Syntax: for(i=0;i<n;i++) c.push_back(binarysearch(b,n,a[i]));`
这里binarysearch是一个函数，它接受数组，数组的大小，search项目并返回search到的项目的位置
它比它似乎更容易。
假设给定的vector是
A=[2,4,3]
创build一个新的vector
V=[0,1,2] // indicating positions
sortingV，同时sorting而不是比较V的元素，比较A的相应元素
//Assume A is a given vector with N elements vector<int> map(N) for(int i=0;i<N;i++) map[i]=i; sort( map.begin(),map.end(), [&](int x,int y){return A[x]<A[y];} );
你也可以使用map或元组来做到这一点！
// Example program #include <iostream> #include <string> #include <vector> #include <tuple> #include <algorithm> #include <random> typedef std::tuple<double, int> mytuple; bool comparator(const mytuple& l, const mytuple& r) { return std::get<0>(l) < std::get<0>(r); } int main() { // declare vector of tuples double and int std::vector<std::tuple<double, int> > vtA; //vector of doubles std::vector<double> vB; //for exemple, fill "vB" with something int j = 0; for(int i = 10; i < 20 ; i++) { j = rand()% i; vB.push_back(j); } for (int k = 0; k < vB.size(); k++) { //make a tuple with double and int (int is a indexis you want to save) vtA.emplace_back(vB[k], k); //print members before ordering std::cout << std::get<0>(vtA[k]) << " - " << std::get<1>(vtA[k]) << std::endl; } std::cout << "\n"; std::cout << "\n"; std::sort(vtA.begin(), vtA.end(), comparator); //call function to increasing order std::cout << "\n"; std::cout << "\n"; //prints vector with the old indices for (int k = 0; k < vB.size(); k++) { std::cout << std::get<0>(vtA[k]) << " - " << std::get<1>(vtA[k]) << std::endl; } return(0); }
