C++ tipo mantener el seguimiento de los índices

Question

¿tiene alguna rutina eficiente para devolver la matriz con los índices de los elementos ordenados en una matriz? Creo que existe una forma conveniente de usar stl vector. ¿Ya ha implementado un algoritmo eficiente sin stl, o tiene un ref referido a pseudocódigo o código C++?

Gracias y saludos

Answer 1

Usando C++ 11, el siguiente debería funcionar bien:

template <typename T> 
std::vector<size_t> ordered(std::vector<T> const& values) { 
    std::vector<size_t> indices(values.size()); 
    std::iota(begin(indices), end(indices), static_cast<size_t>(0)); 

    std::sort(
     begin(indices), end(indices), 
     [&](size_t a, size_t b) { return values[a] < values[b]; } 
    ); 
    return indices; 
} 

Answer 2

para C++ 03, creo que esto guru of the week puede ayudarle a:

namespace Solution3 
{ 
    template<class T> 
    struct CompareDeref 
    { 
    bool operator()(const T& a, const T& b) const 
     { return *a < *b; } 
    }; 


    template<class T, class U> 
    struct Pair2nd 
    { 
    const U& operator()(const std::pair<T,U>& a) const 
     { return a.second; } 
    }; 


    template<class IterIn, class IterOut> 
    void sort_idxtbl(IterIn first, IterIn last, IterOut out) 
    { 
    std::multimap<IterIn, int, CompareDeref<IterIn> > v; 
    for(int i=0; first != last; ++i, ++first) 
     v.insert(std::make_pair(first, i)); 
    std::transform(v.begin(), v.end(), out, 
        Pair2nd<IterIn const,int>()); 
    } 
} 

#include <iostream> 

int main() 
{ 
    int ai[10] = { 15,12,13,14,18,11,10,17,16,19 }; 

    std::cout << "#################" << std::endl; 
    std::vector<int> aidxtbl(10); 


    // use another namespace name to test a different solution 
    Solution3::sort_idxtbl(ai, ai+10, aidxtbl.begin()); 


    for(int i=0; i<10; ++i) 
    std::cout << "i=" << i 
      << ", aidxtbl[i]=" << aidxtbl[i] 
      << ", ai[aidxtbl[i]]=" << ai[aidxtbl[i]] 
      << std::endl; 
    std::cout << "#################" << std::endl; 
} 

El artículo original es here.

Answer 3

Usted podría intentar algo como esto:

template<typename C> 
class index_sorter { 
    public: 
    compare(C const& c) : c(c) {} 
    bool operator()(std::size_t const& lhs, std::size_t const& rhs) const { 
     return c[lhs] < c[rhs]; 
    } 
    private: 
    C const& c; 
}; 

std::sort(index_vector.begin(), index_vector.end(), index_sorter(vector)); 

Answer 4

Agregando a @Konrad respuesta:

Si por alguna razón usted no es capaz de utilizar C++ 11, entonces se puede utilizar para simular boost::phoenix es como

#include <vector> 
    #include <algorithm> 

    #include <boost/spirit/include/phoenix_core.hpp> 
    #include <boost/spirit/include/phoenix_operator.hpp> 

    template <typename T> 
    std::vector<size_t> ordered(std::vector<T> const& values) 
    { 
     using namespace boost::phoenix; 
     using namespace boost::phoenix::arg_names; 

     std::vector<size_t> indices(values.size()); 
     int i = 0; 
     std::transform(values.begin(), values.end(), indices.begin(), ref(i)++); 
     std::sort(indices.begin(), indices.end(), ref(values)[arg1] < ref(values)[arg2]); 
     return indices; 
    }