4

なぜ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);
}
4

2 に答える 2

1

私は規格のコピーを所有していません。価値があるのは、これは無料で入手できる2010年ドラフトの文言です。

25.4.1.2安定ソート

[...]

要件：* firstのタイプは、Swappable要件（表37）、MoveConstructible要件（表33）、およびMoveAssignable要件（表35）を満たしている必要があります。

最新のVisualC++でテストすると、移動コンストラクターが定義されているがコピーコンストラクターがプライベートである場合に並べ替えが可能です。

だからあなたの質問に答えるために：あなたは運が悪いです。std :: stable_sort以外のものを使用するか、ラッパークラスを使用します。

于 2012-12-09T20:56:30.687 に答える
1

OPでの議論を拡張し、興味深いと思ったので、スワップのみを使用して元のベクトルをソートする（ポインターラッパーを使用してインデックスをソートする）ソリューションを次に示します。

編集：これは、インプレースでスワップするソリューションv2です。

編集（OPによる）：C++11を必要としないSTL対応バージョン。

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>()); }
于 2012-12-10T00:57:05.533 に答える