C ++ sorting tracking indexes

Question

Do you have an efficient procedure to return an array with indices for the sorted elements in the array? I think there is some convenient way to use the stl vector. Have you already implemented an efficient algorithm without stl, or do you have a link to pseudo-code or C ++ code?

thank you and welcome

Answer 1

Using C ++ 11, the following should work fine:

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

You can try something like this:

 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 3

Adding to @Konrad's answer:

If for some reason you cannot use C ++ 11, you can use boost::phoenix to simulate this type

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

Answer 4

For C ++ 03, I think this guru of the week can help you:

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

Original article here .