使用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
有谁能想到一个好办法吗?
当前回答
使用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。
其他回答
在函数中创建std::pair，然后对pair进行排序:
通用版本:
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
我遇到了这个问题，并发现直接对迭代器排序是一种对值排序并跟踪下标的方法;不需要定义一个额外的(value, index)对容器，这在值是大对象时很有用;迭代器提供了对值和索引的访问:
/*
* 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 > ( ) );
现在，例如，排序向量中第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包含了我们的值和它们在排序中的下标。
[我]。First =第i条的值。
[我]。Second =初始数组中的idx。
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
使用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。
