使用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
有谁能想到一个好办法吗?
当前回答
假设给定向量为
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];} );
其他回答
你可以对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。
使用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。
对于这类问题 将原始数组数据存储到一个新数据中，然后将排序数组的第一个元素二进制搜索到复制的数组中，该索引应存储到一个矢量或数组中。
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是一个函数，它接受数组，数组大小，搜索项，并返回被搜索项的位置
向量中的项是唯一的吗?如果是这样，复制向量，排序一个副本与STL排序，然后你可以找到每个项目在原始向量的索引。
如果向量应该处理重复的项，我认为你最好实现自己的排序例程。
lukasz Wiklendt的漂亮解决方案!虽然在我的情况下，我需要一些更通用的东西，所以我修改了一点:
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;
}
示例:查找按长度排序字符串向量的索引，除第一个元素为假元素外。
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
