C++ sắp xếp theo dõi các chỉ số

Question

bạn có một số thói quen hiệu quả để trả về mảng với chỉ mục cho các phần tử được sắp xếp trong một mảng không? Tôi nghĩ rằng một số cách thuận tiện tồn tại bằng cách sử dụng vector stl. Bạn đã thực hiện một bản ngã hiệu quả mà không có stl, hoặc bạn có một ref để mã giả hoặc mã C + +?

cảm ơn và liên quan

Answer 1

Sử dụng C++ 11, sau đây nên làm việc tốt:

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

Đối với C++ 03, tôi nghĩ guru of the week này có thể giúp bạn:

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

Bài viết gốc là here.

Answer 3

Bạn có thể thử một cái gì đó như thế này:

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

Thêm vào @ Konrad câu trả lời:

Nếu vì một số lý do bạn không thể sử dụng C++ 11, sau đó bạn có thể sử dụng để mô phỏng boost::phoenix nó giống như

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