使用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
有谁能想到一个好办法吗?
当前回答
我遇到了这个问题，并发现直接对迭代器排序是一种对值排序并跟踪下标的方法;不需要定义一个额外的(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()。
其他回答
你可以对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。
我的解法使用了余数法。我们可以把需要排序的值放在上面2个字节，而把元素的下标放在下面2个字节:
int myints[] = {32,71,12,45,26,80,53,33};
for (int i = 0; i < 8; i++)
myints[i] = myints[i]*(1 << 16) + i;
然后像往常一样对数组myint进行排序:
std::vector<int> myvector(myints, myints+8);
sort(myvector.begin(), myvector.begin()+8, std::less<int>());
在此之后，您可以通过渣滓访问元素的指数。下面的代码输出按升序排序的值的索引:
for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it)
std::cout << ' ' << (*it)%(1 << 16);
当然，这种技术只适用于原始数组myint中相对较小的值(即可以装入int的前2个字节的值)。但是它还有一个额外的好处，可以区分相同的myint值:它们的下标将按正确的顺序打印。
我遇到了这个问题，并发现直接对迭代器排序是一种对值排序并跟踪下标的方法;不需要定义一个额外的(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()。
向量中的项是唯一的吗?如果是这样，复制向量，排序一个副本与STL排序，然后你可以找到每个项目在原始向量的索引。
如果向量应该处理重复的项，我认为你最好实现自己的排序例程。
在函数中创建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
