考虑使用@Ulrich Eckhardt建议的std::multimap。只是代码可以变得更简单。

鉴于

std::vector<int> a = {5, 2, 1, 4, 3};  // a: 5 2 1 4 3

在插入的平均时间内排序

std::multimap<int, std::size_t> mm;
for (std::size_t i = 0; i != a.size(); ++i)
    mm.insert({a[i], i});

检索值和原始索引

std::vector<int> b;
std::vector<std::size_t> c;
for (const auto & kv : mm) {
    b.push_back(kv.first);             // b: 1 2 3 4 5
    c.push_back(kv.second);            // c: 2 1 4 3 0
}

首选std::multimap而不是std::map的原因是允许原始向量的值相等。另外请注意，与std::map不同，操作符[]没有为std::multimap定义。

你可以对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。

还有另一种方法来解决这个问题，使用地图:

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;

使用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。

我的解法使用了余数法。我们可以把需要排序的值放在上面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()。