복사하지 않고 stable_sort하는 방법은 무엇입니까?

Question

stable_sort에 복사 생성자가 필요한 이유는 무엇입니까? (swap이면 충분합니까?)
아니면 어떤 요소를 복사하지 않고 stable_sort 범위 내에서 어떻게해야합니까?

#include <algorithm> 

class Person 
{ 
    Person(Person const &); // Disable copying 
public: 
    Person() : age(0) { } 
    int age; 
    void swap(Person &other) { using std::swap; swap(this->age, other.age); } 
    friend void swap(Person &a, Person &b) { a.swap(b); } 
    bool operator <(Person const &other) const { return this->age < other.age; } 
}; 

int main() 
{ 
    static size_t const n = 10; 
    Person people[n]; 
    std::stable_sort(people, people + n); 
} 

Answer 1

OP 토론에서 확장하고 흥미로운 점을 발견했기 때문에 인덱스 래퍼를 사용하여 원본 벡터를 정렬하기 위해 스왑을 사용하는 솔루션이 있습니다.

편집 : 이것은 솔루션 v2에서 바뀌어 있습니다.

편집 (OP 기준) : C++을 필요로하지 않는 STL 친화적 인 버전 11.

template<class Pred> 
struct swapping_stable_sort_pred 
{ 
    Pred pred; 
    swapping_stable_sort_pred(Pred const &pred) : pred(pred) { } 

    template<class It> 
    bool operator()(
     std::pair<It, typename std::iterator_traits<It>::difference_type> const &a, 
     std::pair<It, typename std::iterator_traits<It>::difference_type> const &b) const 
    { 
     bool less = this->pred(*a.first, *b.first); 
     if (!less) 
     { 
      bool const greater = this->pred(*b.first, *a.first); 
      if (!greater) { less = a.second < b.second; } 
     } 
     return less; 
    } 
}; 

template<class It, class Pred> 
void swapping_stable_sort(It const begin, It const end, Pred const pred) 
{ 
    typedef std::pair<It, typename std::iterator_traits<It>::difference_type> Pair; 
    std::vector<Pair> vp; 
    vp.reserve(static_cast<size_t>(std::distance(begin, end))); 
    for (It it = begin; it != end; ++it) 
    { vp.push_back(std::make_pair(it, std::distance(begin, it))); } 
    std::sort(vp.begin(), vp.end(), swapping_stable_sort_pred<Pred>(pred)); 
    std::vector<Pair *> vip(vp.size()); 
    for (size_t i = 0; i < vp.size(); i++) 
    { vip[static_cast<size_t>(vp[i].second)] = &vp[i]; } 

    for (size_t i = 0; i + 1 < vp.size(); i++) 
    { 
     typename std::iterator_traits<It>::difference_type &j = vp[i].second; 
     using std::swap; 
     swap(*(begin + static_cast<ptrdiff_t>(i)), *(begin + j)); 
     swap(j, vip[i]->second); 
     swap(vip[j], vip[vip[j]->second]); 
    } 
} 

template<class It> 
void swapping_stable_sort(It const begin, It const end) 
{ return swapping_stable_sort(begin, end, std::less<typename std::iterator_traits<It>::value_type>()); } 

Answer 2

나는 표준 사본을 소유하고 있지 않습니다.

25.4.1.2 stable_sort

[...]

이 필요합니다 : 먼저 스왑 요구 사항을 만족하여야한다 *의 유형 (그것은 가치가 무엇인지를 들어,이 무료로 사용할 수 2,010 초안의 표현입니다 표 37), MoveConstructible 요구 사항 (표 33) 및 MoveAssignable 요구 사항 (표 35).

최신 Visual C++로 테스트하면 이동 생성자가 정의되었지만 복사 생성자가 개인 일 때 정렬이 허용됩니다.

귀하의 질문에 대답하려면 : 당신은 운이 없어. std :: stable_sort 이외의 것을 사용하거나 래퍼 클래스를 사용하십시오.