Skip to content

Make all sorts work with move-only types #15

Closed
@Morwenn

Description

@Morwenn

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. See pdq_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 and std::raw_storage_iterator. The latter has been updated for C++17 to be more move-friendly.

Metadata

Metadata

Assignees

No one assigned

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions