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&nbsp;<iostream>#include&nbsp;<vector>#include&nbsp;<numeric>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;std::iota #include&nbsp;<algorithm>&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;std::sorttemplate&nbsp;<typename&nbsp;T>vector<size_t>&nbsp;sort_indexes(const&nbsp;vector<T>&nbsp;&v)&nbsp;{ &nbsp;&nbsp;//&nbsp;initialize&nbsp;original&nbsp;index&nbsp;locations &nbsp;&nbsp;vector<size_t>&nbsp;idx(v.size()); &nbsp;&nbsp;iota(idx.begin(),&nbsp;idx.end(),&nbsp;0); &nbsp;&nbsp;//&nbsp;sort&nbsp;indexes&nbsp;based&nbsp;on&nbsp;comparing&nbsp;values&nbsp;in&nbsp;v &nbsp;&nbsp;sort(idx.begin(),&nbsp;idx.end(), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;[&v](size_t&nbsp;i1,&nbsp;size_t&nbsp;i2)&nbsp;{return&nbsp;v[i1]&nbsp;<&nbsp;v[i2];}); &nbsp;&nbsp;return&nbsp;idx;}现在，您可以在迭代中使用返回的索引向量，例如for&nbsp;(auto&nbsp;i:&nbsp;sort_indexes(v))&nbsp;{ &nbsp;&nbsp;cout&nbsp;<<&nbsp;v[i]&nbsp;<<&nbsp;endl;}显然，您还可以选择提供自己的原始索引向量，排序函数，比较器，或使用额外的向量在sort_indexes函数中自动重新排序v。

Answer 2

您可以对std :: pair进行排序，而不仅仅是整数 - 第一个int是原始数据，第二个int是原始索引。然后提供一个只对第一个int进行排序的比较器。例：Your&nbsp;problem&nbsp;instance:&nbsp;v&nbsp;=&nbsp;[5&nbsp;7&nbsp;8]New&nbsp;problem&nbsp;instance:&nbsp;v_prime&nbsp;=&nbsp;[<5,0>,&nbsp;<8,1>,&nbsp;<7,2>]使用比较器对新问题实例进行排序：typedef&nbsp;std::pair<int,int>&nbsp;mypair;bool&nbsp;comparator&nbsp;(&nbsp;const&nbsp;mypair&&nbsp;l,&nbsp;const&nbsp;mypair&&nbsp;r) &nbsp;&nbsp;&nbsp;{&nbsp;return&nbsp;l.first&nbsp;<&nbsp;r.first;&nbsp;}//&nbsp;forgetting&nbsp;the&nbsp;syntax&nbsp;here&nbsp;but&nbsp;intent&nbsp;is&nbsp;clear&nbsp;enough使用该比较器的st_ :: sort on v_prime的结果应该是：v_prime&nbsp;=&nbsp;[<5,0>,&nbsp;<7,2>,&nbsp;<8,1>]你可以通过遍历向量来剥离索引，从每个std :: pair中获取.second。

Answer 3

我写了索引排序的通用版本。template&nbsp;<class&nbsp;RAIter,&nbsp;class&nbsp;Compare>void&nbsp;argsort(RAIter&nbsp;iterBegin,&nbsp;RAIter&nbsp;iterEnd,&nbsp;Compare&nbsp;comp,&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;std::vector<size_t>&&nbsp;indexes)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;std::vector<&nbsp;std::pair<size_t,RAIter>&nbsp;>&nbsp;pv&nbsp;; &nbsp;&nbsp;&nbsp;&nbsp;pv.reserve(iterEnd&nbsp;-&nbsp;iterBegin)&nbsp;; &nbsp;&nbsp;&nbsp;&nbsp;RAIter&nbsp;iter&nbsp;; &nbsp;&nbsp;&nbsp;&nbsp;size_t&nbsp;k&nbsp;; &nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(iter&nbsp;=&nbsp;iterBegin,&nbsp;k&nbsp;=&nbsp;0&nbsp;;&nbsp;iter&nbsp;!=&nbsp;iterEnd&nbsp;;&nbsp;iter++,&nbsp;k++)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;pv.push_back(&nbsp;std::pair<int,RAIter>(k,iter)&nbsp;)&nbsp;; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;std::sort(pv.begin(),&nbsp;pv.end(),&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;[&comp](const&nbsp;std::pair<size_t,RAIter>&&nbsp;a,&nbsp;const&nbsp;std::pair<size_t,RAIter>&&nbsp;b)&nbsp;->&nbsp;bool&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{&nbsp;return&nbsp;comp(*a.second,&nbsp;*b.second)&nbsp;;&nbsp;})&nbsp;; &nbsp;&nbsp;&nbsp;&nbsp;indexes.resize(pv.size())&nbsp;; &nbsp;&nbsp;&nbsp;&nbsp;std::transform(pv.begin(),&nbsp;pv.end(),&nbsp;indexes.begin(),&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;[](const&nbsp;std::pair<size_t,RAIter>&&nbsp;a)&nbsp;->&nbsp;size_t&nbsp;{&nbsp;return&nbsp;a.first&nbsp;;&nbsp;})&nbsp;;}除了用于接收已排序索引的索引容器之外，用法与std :: sort的用法相同。测试：int&nbsp;a[]&nbsp;=&nbsp;{&nbsp;3,&nbsp;1,&nbsp;0,&nbsp;4&nbsp;}&nbsp;;std::vector<size_t>&nbsp;indexes&nbsp;;argsort(a,&nbsp;a&nbsp;+&nbsp;sizeof(a)&nbsp;/&nbsp;sizeof(a[0]),&nbsp;std::less<int>(),&nbsp;indexes)&nbsp;;for&nbsp;(size_t&nbsp;i&nbsp;:&nbsp;indexes)&nbsp;printf("%d\n",&nbsp;int(i))&nbsp;;对于没有c ++ 0x支持的编译器，你应该得到2 1 0 3.将lamba表达式替换为类模板：template&nbsp;<class&nbsp;RAIter,&nbsp;class&nbsp;Compare>&nbsp;class&nbsp;PairComp&nbsp;{public: &nbsp;&nbsp;Compare&nbsp;comp&nbsp;; &nbsp;&nbsp;PairComp(Compare&nbsp;comp_)&nbsp;:&nbsp;comp(comp_)&nbsp;{} &nbsp;&nbsp;bool&nbsp;operator()&nbsp;(const&nbsp;std::pair<size_t,RAIter>&&nbsp;a,&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;const&nbsp;std::pair<size_t,RAIter>&&nbsp;b)&nbsp;const&nbsp;{&nbsp;return&nbsp;comp(*a.second,&nbsp;*b.second)&nbsp;;&nbsp;}&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;;并重写std :: sort asstd::sort(pv.begin(),&nbsp;pv.end(),&nbsp;PairComp(comp)())&nbsp;;