Просто ради интереса я реализовал самый простой алгоритм сортировки:

template
void treesort(Iterator begin, Iterator end)
{
    typedef typename std::iterator_traits::value_type element_type;

    // copy data into the tree
    std::multiset tree(begin, end);

    // copy data out of the tree
    std::copy(tree.begin(), tree.end(), begin);
}

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

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

template
void treesort(Iterator begin, Iterator end)
{
    typedef typename std::iterator_traits::value_type element_type;

    // move data into the tree
    std::multiset 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 будет делать то же самое здесь :( Есть ли другой способ переместить данные из дерева?