Movendo elementos de um contêiner associativo
Apenas por diversão, eu implementei o algoritmo de ordenação mais simples que se possa imaginar:
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);
}
É apenas cerca de 20 vezes mais lento questd::sort
para meus dados de teste :)
Em seguida, eu queria melhorar o desempenho com a semântica de movimento:
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);
}
Mas isso não afetou o desempenho de maneira significativa, embora eu esteja classificandostd::string
s.
Então lembrei que recipientes associativos são constantes do lado de fora, isto é,std::move
estd::copy
vai fazer a mesma coisa aqui :( Existe alguma outra maneira de mover os dados para fora da árvore?