C++ sort che tiene traccia degli indici

Question

avete una routine efficiente per restituire array con indici per elementi ordinati in un array? Penso che esista un modo conveniente usando il vettore stl. Avete già implementato un algo efficiente senza stl, oppure avete un riferimento a pseudo codice o codice C++?

Grazie e saluti

Answer 1

con C++ 11, il seguente dovrebbe funzionare bene:

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

per C++ 03, credo che questo guru of the week può aiutare:

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; 
} 

L'articolo originale è here.

Answer 3

Si potrebbe provare qualcosa di simile:

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

Aggiungendo a @Konrad risposta:

Se per qualche motivo non sono in grado di utilizzare C++ 11, quindi è possibile utilizzare per simulare boost::phoenix come

#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; 
    }