使用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
有谁能想到一个好办法吗?
当前回答
还有另一种方法来解决这个问题，使用地图:
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;
其他回答
我写了索引排序的通用版本。
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)) ;
你应该得到2 10 0 3。 对于不支持c++0x的编译器，将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)()) ;
一种解决方案是使用二维矢量。
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<vector<double>> val_and_id;
val_and_id.resize(5);
for (int i = 0; i < 5; i++) {
val_and_id[i].resize(2); // one to store value, the other for index.
}
// Store value in dimension 1, and index in the other:
// say values are 5,4,7,1,3.
val_and_id[0][0] = 5.0;
val_and_id[1][0] = 4.0;
val_and_id[2][0] = 7.0;
val_and_id[3][0] = 1.0;
val_and_id[4][0] = 3.0;
val_and_id[0][1] = 0.0;
val_and_id[1][1] = 1.0;
val_and_id[2][1] = 2.0;
val_and_id[3][1] = 3.0;
val_and_id[4][1] = 4.0;
sort(val_and_id.begin(), val_and_id.end());
// display them:
cout << "Index \t" << "Value \n";
for (int i = 0; i < 5; i++) {
cout << val_and_id[i][1] << "\t" << val_and_id[i][0] << "\n";
}
return 0;
}
输出如下:
Index Value
3 1
4 3
1 4
0 5
2 7
如果可能的话，可以使用find函数构建位置数组，然后对数组排序。
或者你可以使用一个映射，其中键是元素，值是它在即将到来的数组(a, B和C)中的位置列表
这取决于以后对这些数组的使用。
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
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包含了我们的值和它们在排序中的下标。
[我]。First =第i条的值。
[我]。Second =初始数组中的idx。
