Przenoszenie elementów z kontenera asocjacyjnego
Dla zabawy zaimplementowałem najprostszy algorytm sortowania, jaki można sobie wyobrazić:
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);
}
To tylko około 20 razy wolniej niżstd::sort
dla moich danych testowych :)
Następnie chciałem poprawić wydajność za pomocą semantyki ruchu:
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);
}
Ale to nie wpłynęło na wydajność w znaczący sposób, chociaż sortujęstd::string
s.
Wtedy przypomniałem sobie, że pojemniki asocjacyjne są stałe z zewnątrz, to znaczystd::move
istd::copy
zrobi to samo tutaj :( Czy istnieje inny sposób przeniesienia danych z drzewa?