Как стабильно_сортировать без копирования?

Зачем 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);
}

c++ stable-sort copy-constructor c++03
person user541686    schedule 09.12.2012    source источник
comment
Честно говоря, я не знаю ни одного алгоритма стабильной сортировки, который был бы основан на операции swap. Все они, похоже, основаны на операции copy или, точнее, move. Конечно, вы можете эмулировать move через swap, но было бы странно ожидать, что стандартная библиотека сделает это внутри своей реализации.   -  person AnT    schedule 10.12.2012
comment
@AndreyT: На самом деле, у меня возникает еще один вопрос ... Я собирался спросить вас, почему они просто не сортировали итераторы на основе их целей, а не самих элементов? но теперь я понятия не имею, как (эффективно) использовать итераторы для ранжирования... отсюда и новый вопрос! См.: stackoverflow.com/questions/13791810/   -  person user541686    schedule 10.12.2012
comment
@AndreyT: Хм, может быть, я задал этот вопрос слишком рано. Вы можете просто использовать sort для изменения порядка, а затем поменять местами и элементы, верно? Таким образом, вы сохраните соответствие между элементами и рейтингом, и вам никогда не придется копировать элементы... это должно работать нормально? Или я что-то упускаю?   -  person user541686    schedule 10.12.2012
comment
Создание дополнительного массива индексов (с указателями или итераторами) и std::sort-инг этого массива вместо этого всегда являются простым и жизнеспособным подходом к выполнению стабильной сортировки (массива индексов). В дополнение к вашим критериям сравнения (например, сравнение age выше) вы также должны сравнить значения итератора, которые стабилизируют сортировку. Однако, чтобы переупорядочить исходный массив в соответствии с вашим отсортированным индексом (если вам это действительно нужно), вам все равно потребуется операция move.   -  person AnT    schedule 10.12.2012
comment
@AndreyT: Да, я ищу сортировку исходного массива - я просто пытался посмотреть, можно ли этого добиться с помощью дополнительного временного массива. Значит, вы говорите, что обмена недостаточно — мне действительно нужно переехать? (Почему?)   -  person user541686    schedule 10.12.2012

Ответы (2)


arrow_upward
1
arrow_downward

В дополнение к обсуждению в ОП и потому, что мне это показалось интересным, вот решение, которое использует только обмен для сортировки исходного вектора (с использованием оболочки указателя для сортировки индексов).

Редактировать: это решение v2, которое заменяется на месте.

Редактировать (от OP): версия для 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>()); }
person Andrei Tita    schedule 10.12.2012
comment
Ха-ха, создание по умолчанию и замена - это обман... Это уклонение от сути вопроса, сложность которого заключается в том, как избежать создания новых объектов! =P Но хорошая попытка. :) - person user541686; 10.12.2012
comment
@Mehrdad Ну, дело в том, что вы не можете избежать создания новых объектов, если хотите использовать стандартные библиотечные сортировки (по крайней мере, вам понадобится контейнер индексов). Если вы хотите развернуть свой собственный алгоритм сортировки, у вас есть 2 варианта: что-то медленное и простое в реализации, например пузырьковая сортировка (я мог бы написать это в двух строках кода), или что-то эффективное, но более сложное. - person Andrei Tita; 10.12.2012
comment
Извините, под новыми объектами я имел в виду объекты типа в массиве - очевидно, индексы в порядке. Я просто имел в виду, что это должно работать, если у типа есть только своп и нет доступных конструкторов. - person user541686; 10.12.2012
comment
@Mehrdad Нашел способ поменять местами, просто потребовалось немного больше учета (см. Улучшенный код). Я не уверен, стоит ли оно того. Я также не уверен, что обострение, которое я испытал, стоило того :) - person Andrei Tita; 10.12.2012
comment
Оооо интересно... Я начал ходить по похожему пути (с pair<size_t, Iterator>), но у меня не получилось :) Попробую, спасибо! - person user541686; 10.12.2012
comment
Кажется, работает отлично! :D Спасибо! (Я также отредактировал ваш ответ, добавив немного более удобную для STL версию, которая также полностью избегает stable_sort, просто чтобы проиллюстрировать это.) - person user541686; 10.12.2012

arrow_upward
1
arrow_downward

У меня нет копии стандарта. Что бы это ни стоило, вот формулировка из свободно доступного черновика 2010 года:

25.4.1.2 стабильная_сортировка

[...]

Требования: Тип *first должен удовлетворять требованиям Swappable (таблица 37), MoveConstructible (таблица 33) и MoveAssignable (таблица 35).

Тестирование с помощью последней версии Visual C++ позволяет выполнять сортировку, когда определен конструктор перемещения, но конструктор копирования является закрытым.

Итак, чтобы ответить на ваш вопрос: вам не повезло. Используйте что-то отличное от std::stable_sort или используйте класс-оболочку.

person Andrei Tita    schedule 09.12.2012
comment
Комитет по стандартам C++ регулярно публикует обновления своего рабочего проекта C++ по адресу open- std.org/Jtc1/sc22/wg21/docs/papers. Самый последний из них от 2 ноября 2012 г. на www.open-std.org/Jtc1/sc22/wg21/docs/papers/2012/n3485.pdf. - person Olaf Dietsche; 10.12.2012
comment
@OlafDietsche Спасибо за эту ссылку. - person Andrei Tita; 10.12.2012