Перемещение элементов из ассоциативного контейнера
Просто для забавы я реализовал самый простой алгоритм сортировки:
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);
}
Это всего в 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);
}
Но это не сильно повлияло на производительность, хотя я сортирую std::strings.
Тогда я вспомнил, что ассоциативные контейнеры являются постоянными извне, то есть std::move а также std::copy будет делать то же самое здесь 🙁 Есть ли другой способ переместить данные из дерева?
Решение
std::set а также std::multiset только обеспечить const доступ к своим элементам. Это означает, что вы не можете переместить что-то из набора. Если бы вы могли перемещать элементы (или изменять их вообще), вы могли бы разбить набор, изменив порядок сортировки элементов. Так что C ++ 11 запрещает это.
Итак, ваша попытка использовать std::move алгоритм просто вызовет конструктор копирования.
Другие решения
Я считаю, что вы могли бы сделать собственный распределитель для multiset использовать (3-й аргумент шаблона), который на самом деле перемещает элементы в его destroy метод обратно в контейнер пользователя. Затем сотрите каждый элемент в наборе, и во время его уничтожения он должен переместить вашу строку обратно в исходный контейнер. Я думаю, что пользовательский распределитель должен иметь двухфазное построение (передайте его, итератор начала передается вашему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);
}
Это сортирует multiset ссылок, поэтому их не нужно перемещать из дерева.
Однако при возврате в исходный диапазон назначения перемещений не обязательно безопасны для самостоятельного назначения, поэтому я сначала переместил их в вектор, чтобы при повторном назначении их обратно в исходный диапазон не было самостоятельных назначений.
Это минимально быстрее, чем ваша оригинальная версия в моих тестах. Вероятно, он теряет эффективность, потому что он должен выделить вектор, а также все узлы дерева. Это и тот факт, что мой компилятор использует строки COW, поэтому перемещение не намного быстрее, чем копирование в любом случае.