如何獲得矢量的排序索引？

Question

我有一個向量。它沒有排序。現在我想要得到它的索引，它將排序向量。例如vector<int> v{1, 3, 2}，排序的索引是{0, 2, 1}，因爲v[0] <= v[2] <= v[1]。如果兩個平等，哪一個先走並不重要。

Answer 1

你在找什麼叫標籤排序（或索引排序）。下面是使用的lambda最小例子在C++ 11：

#include <algorithm> 
#include <numeric> 
#include <iostream> 
#include <vector> 

template<typename T> 
std::vector<std::size_t> tag_sort(const std::vector<T>& v) 
{ 
    std::vector<std::size_t> result(v.size()); 
    std::iota(std::begin(result), std::end(result), 0); 
    std::sort(std::begin(result), std::end(result), 
      [&v](const auto & lhs, const auto & rhs) 
      { 
       return v[lhs] < v[rhs]; 
      } 
    ); 
    return result; 
} 

int main() 
{ 
    std::vector<char> v{'a', 'd', 'b', 'c'}; 
    auto idxs = tag_sort(v); 
    for (auto && elem : idxs) 
     std::cout << elem << " : " << v[elem] << std::endl; 
} 

Live on Coliru