Skip to content

Handling the Ranges TS once merged into the standard #130

Open
@Morwenn

Description

@Morwenn

There are currently several papers in flight related to merging (parts of) the Ranges TS into the C++ IS. Those changes might come soon enough and will have a deep impact on several parts of cpp-sort, opening the way for a 2.0.0 breaking release. The following papers should be reviewed during the committee meetings to come:

  • P0896 - Merging the Ranges TS
  • P0898 - Standard Library Concepts
  • P0970 - Better, Safer Range Access Customization Points
  • P1037 - Deep Integration of the Ranges TS
  • P1522 - Iterator Difference Type and Integer Overflow

cpp-sort 2.0.0 will have to take all those changes into account in order to modernize itself. The following changes will be needed to fully adapt:

  • Conceptify the library (we explicitly handle iterators that don't implement postfix operator++ and operator--, so we might have to reimplement a few concepts).
  • std::identity should be used instead of cppsort::utility::identity (we could conditionally make it an alias in cpp-sort 1.x.y).
  • Keep std::less<> and std::greater<> as the main comparison functions (vocabulary types), but add support for std::ranges::less and std::ranges::greater where it makes sense.
  • Algorithms support sentinels, we will need to implement that too (issue Handle sentinel parameters #20).
  • Sorting algorithms in std::ranges:: return the past-the-end iterator, we will have to update every sorting algorithm to reflect that, and also to make sure that sorter adapters correctly return it too. I'm still not sure what to do with sorter adapters and Return type of sorter adapters #134.
  • Replace calls to std::swap, std::size, std::begin and std::end by calls to std::ranges::swap, std::ranges::size, std::ranges::begin, std::ranges::end which should do exactly the right thing.
  • We need to audit the library to check what needs be done to smoothly adapt to the iterator traits overhaul proposed in P1037, we may rename the equivalent traits to match in cpp-sort 1.x.y to make the terminology consistent.
  • cppsort::utility::iter_move and cppsort::utility::iter_swap can be replaced by the equivalent functions in std::ranges::, and since they automate the lookup we can stop explicitly using the corresponding using in some algorithms (do they?).
  • Handling user-defined difference types might prove tricky (we sometimes assume that those are built-in integer types) but might be worth trying.
  • std::projected can most likely be used to replace detail::projected_t (tried, didn't work).
  • std::contiguous_iterator_tag or the new ContiguousIterator concept can be used to optimize a few internal algorithms, but it's unlikely that sorting algorithms specific to that tag exist; we still need to check that nothing breaks when it is used.

Some of the issues described here are tracked in specific issues too, but an exhaustive list of the changes made by the Ranges TS is valuable enough. My main concern currently is that some of the things we do with our custom proxy iterator support are actually beyond the scopes of Ranges: I fear that associate_iterator will break.

Metadata

Metadata

Assignees

No one assigned

    Projects

    Status

    In Progress

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions