Closed
Description
std::sort
works with move-only types. Actually, it requires the iterators to be ValueSwappable
, and the type of the dereferenced iterators to be MoveAssignable
and MoveConstructible
. We would realy like all of our algorithms to work with move-only types. The following sorters fail to handle move-only types:
-
quick_sorter
: it makes a copy of the pivot. There is probably a way to move the pivot to the beginning or the end of the partition and make sure it is never moved during this step. Seepdq_sorter
for an equivalent mechanism. -
tim_sorter
: that one is trickier. It would need to make the original code work with move-only types. While adding the moves operations is pretty trivial, I'm not sure that doing it without precautions won't cause reads from moved-from values, which would be bad. -
block_sorter
: trying to trivially convert copy operations to move operations resulted in reads from moved-from objects. I guess that the algorithm actually needs to copy things in the cache; if so, making it work with move-only types will be tricky.
Additionally, std::sort
is also required to work even if the type is not default-constructible. The following sorters currently do not work with such types:
-
block_sorter
: the cache is a fixed-size C array of size 512; initializing it default-initializes every element. We can probably get rid of that by using unitialized memory andstd::raw_storage_iterator
. The latter has been updated for C++17 to be more move-friendly.