Come ottenere l'indice ordinato di un vettore?

Question

Ho un vettore. Non è ordinato. Ora voglio ottenere i suoi indici che ordineranno il vettore. Ad esempio vector<int> v{1, 3, 2}, gli indici ordinati sono {0, 2, 1} perché v[0] <= v[2] <= v[1]. Se due sono uguali, non importa quale sia il primo.

Answer 1

Quello che stai cercando si chiama tag sorting (o index sorting). Ecco un esempio minimo utilizzando lambda in 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