C++对索引进行排序和跟踪
C++对索引进行排序和跟踪
提问于 2009-10-16 11:18:24
使用C++ (希望还有标准库)，我希望按升序对一系列样本进行排序，但我还希望记住新样本的原始索引。
例如，我有一个集合，或向量，或样本矩阵A : [5, 2, 1, 4, 3]。我想要将这些元素排序为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有没有人能找到一种好的方法呢？
回答 14
Stack Overflow用户
发布于 2012-09-13 12:10:42
使用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。
Stack Overflow用户
发布于 2009-10-16 11:53:11
你可以对std::pair进行排序，而不仅仅是int --第一个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使用该比较器对v_prime执行std::sort的结果应该是：
v_prime = [<5,0>, <7,2>, <8,1>]您可以通过遍历向量，从每个std：：对中抓取.second来剥离索引。
Stack Overflow用户
发布于 2016-10-22 03:06:58
假设给定的向量是
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);
std::iota(V.begin(),V.end(),0); //Initializing
sort( V.begin(),V.end(), [&](int i,int j){return A[i]<A[j];} );页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/1577475
复制相关文章
相似问题
腾讯云开发者
