Перемещение элементов из ассоциативного контейнера

Просто для удовольствия, я реализовал простейший алгоритм сортировки, который можно себе представить:

template<typename iterator="">
void treesort(Iterator begin, Iterator end)
{
 typedef typename std::iterator_traits<iterator>::value_type element_type;
 // copy data into the tree
 std::multiset<element_type> tree(begin, end);
 // copy data out of the tree
 std::copy(tree.begin(), tree.end(), begin);
}
</element_type></iterator></typename>

Это примерно в 20 раз медленнее, чем std::sort для моих тестовых данных:)

Затем я хотел улучшить производительность с помощью семантики перемещения:

template<typename iterator="">
void treesort(Iterator begin, Iterator end)
{
 typedef typename std::iterator_traits<iterator>::value_type element_type;
 // move data into the tree
 std::multiset<element_type> tree(std::make_move_iterator(begin),
 std::make_move_iterator(end));
 // move data out of the tree
 std::move(tree.begin(), tree.end(), begin);
}
</element_type></iterator></typename>

Но это не повлияло на производительность значительным образом, хотя я сортирую std::string s.

Тогда я вспомнил, что ассоциативные контейнеры постоянны снаружи, то есть std::move и std::copy будут делать то же самое здесь:( Есть ли другой способ перемещения данных из дерева?

3 ответа

std::set и std::multiset обеспечивают const доступ к своим элементам. Это означает, что вы не можете вытащить что-то из набора. Если вы можете перемещать элементы (или изменять их вообще), вы можете сломать набор, изменив порядок сортировки элементов. Поэтому С++ 11 запрещает его.

Итак, ваша попытка использовать алгоритм std::move просто вызовет конструктор копирования.


Я полагаю, вы могли бы создать собственный распределитель для multiset для использования (аргумент третьего шаблона), который фактически перемещает в нем элементы destroy обратно в контейнер пользователя. Затем стирайте каждый элемент в наборе и во время его уничтожения он должен переместить вашу строку обратно в исходный контейнер. Я думаю, что у пользовательского распределителя потребуется 2-фазное построение (передайте ему начальный итератор, переданный вашей функции treesort, чтобы удерживать его как член, но не во время построения, потому что он должен быть конструктивным по умолчанию).

Очевидно, это было бы странно и глупо обходным путем для того, чтобы не иметь метода pop в наборе/мультимножестве. Но это должно быть возможно.


Мне нравится идея Дэйва о причудливом распределителе, который помнит источник каждого перемещенного объекта и автоматически возвращается к разрушению, я никогда не думал об этом!

Но вот ответ ближе к вашей первоначальной попытке:

template<typename iterator="">
void treesort_mv(Iterator begin, Iterator end)
{
 typedef typename std::iterator_traits<iterator>::value_type element_type;
 // move the elements to tmp storage
 std::vector<element_type> tmp(std::make_move_iterator(begin),
 std::make_move_iterator(end));
 // fill the tree with sorted references
 typedef std::reference_wrapper<element_type> element_ref;
 std::multiset<element_ref, std::less<element_type="">> tree(tmp.begin(), tmp.end());
 // move data out of the vector, in sorted order
 std::move(tree.begin(), tree.end(), begin);
}
</element_ref,></element_type></element_type></iterator></typename>

Это сортирует a multiset ссылок, поэтому их не нужно выводить из дерева.

Однако, возвращаясь в исходный диапазон, назначения переноса не обязательно безопасны для самоопределения, поэтому я перенесил их в вектор сначала, так что при повторном назначении их обратно в исходный диапазон не будет -assignments.

Это незначительно быстрее, чем исходная версия в моих тестах. Вероятно, он теряет эффективность, потому что он должен выделять вектор, а также все узлы дерева. Это и тот факт, что мой компилятор использует строки COW, поэтому перемещение происходит не намного быстрее, чем копирование.

licensed under cc by-sa 3.0 with attribution.