跟踪指数的c ++sorting

你有一些有效的例程返回数组与索引sorting元素在数组中？ 我认为使用stl向量存在一些方便的方法。 你是否已经实现了一个没有stl的高效的algorithm，或者你是否有伪代码或者C ++代码？

感谢致敬

Answer 1

使用C ++ 11，以下应该工作得很好：

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

你可以尝试这样的事情：

 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

添加到@Konrad答案：

如果由于某种原因，你不能使用C ++ 11，那么你可以使用boost::phoenix来模拟它

  #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

对于C ++ 03，我认为这位本周的大师可以帮助你：

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

原文在这里 。