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

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

4

c++c++03 copy-constructor stable-sort

Решение

Другие решения

Я не владею копией стандарта. Для чего это стоит, это формулировка из свободно доступного проекта 2010 года:

25.4.1.2 stable_sort

[…]

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

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

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

1

Источник

Accepted Answer

Продолжая обсуждение в 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>()); }

1