c – 如何在不复制的情况下进行stable_sort？

发布时间：2020-12-16 07:34:04 所属栏目：百科来源：网络整理

导读：为什么stable_sort需要复制构造函数？ (交换应该就够了,对吧？) 或者更确切地说,我如何在不复制任何元素的情况下stable_sort一个范围？ #include algorithmclass Person{ Person(Person const ); // Disable copyingpublic: Person() : age(0) { } int age;

为什么stable_sort需要复制构造函数？ (交换应该就够了,对吧？)
或者更确切地说,我如何在不复制任何元素的情况下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);
}

解决方法

扩展了OP中的讨论,并且因为我发现它很有趣,这里是一个解决方案,它只使用swap来对原始向量进行排序(通过使用指针包装器对索引进行排序).

编辑：这是解决方案v2,它就地交换.

编辑(通过OP)：STL友好版本,不需要C 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>()); }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!