Moving elements out of an associative container
c++, c++11, move-semantics, multiset, sorting
Solution
`std::set` and `std::multiset` only provide `const` access to their elements. This means you cannot move something out of the set. If you could move items out (or modify them at all), you could break the set by changing the sort order of the items. So C++11 forbids it.
So your attempt to use the `std::move` algorithm will just invoke the copy constructor.
Problem
Just for fun, I have implemented the simplest sorting algorithm imaginable: ``` 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); } ``` It's only about 20 times slower than `std::sort` for my test data :) Next, I wanted to improve the performance with move semantics: ``` 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); } ``` But this did not affect the performance in a significant way, even though I am sorting `std::string`s. Then I remembered that associative containers are constant from the outside, that is, `std::move` and `std::copy` will do the same thing here :( Is there any other way to move the data out of the tree?