Handling the Ranges TS once merged into the standard

[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).
• [x] std::identity should be used instead of cppsort::utility::identity (we could conditionally make it an alias in cpp-sort 1.x.y).
• [x] 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.
• [x] Algorithms support sentinels, we will need to implement that too (issue #20).
• [x] 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 #134.
• [x] 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.
• [x] 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.
• [x] 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.
• [x] ~~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.

[Morwenn]

Replacing cppsort::utility::identity with std::identity in branch 2.0.0-develop was fortunately as much of a no-brainer as I thought: a bit long but no big challenge occurred while doing it.

Instead of using std::identity when available in branch 1.x.y I'd rather make a CPPSORT_USE_STD_IDENTITY switch to conditionally make cppsort::utility::identity an alias of std::identity. There's not that much of a difference between both, but the current version supports operator| unlike std::identity, so it could still be a breaking change. As such I'd rather it be opt-in in branch 1.x.y instead of automatic .

[Morwenn]

Instead of introducing CPPSORT_USE_STD_IDENTITY and having more compile time switchs to test, more documentation to write about options, etc. I made what gives the most value added while being the least disruptive to branch 1.x.y: support for std::identity in places where it matters along the already existing support for utility::identity.

[Morwenn]

After having tried to replace std::less<> with std::ranges::less, a few tests broke because std::ranges::less requires the full zoo of comparison and relational operators for the type to compare through std::totally_ordered, which was immediately noticeable when the tests broke.

Instead I plan to add support for std::ranges::less and std::ranges::greater along the existing support for std::less<> and std::greater<>, conditionally in 1.x.y and unconditionally in 2.0.0-develop. It means a lot of overloads when using branch 1.x.y in C++20 mode, but the old comparison function objects are still more porweful (less restrictive) but users might want to use the next ones for the added security of constraints, so I can't not support them either.

The number of additional overloads to sorter_facade is a good argument for the clean break to C++20 in 2.0.0.

[Morwenn]

The groundwork for the concepts part is advancing slowly, mostly because the concepts used by cpp-sort are slightly different from those used by the standard library, especially in the following areas:

• Unconditional support for __int128_t and __uint128_t when available, affecting all components relying on integer and integer-like concepts.
• Iterators and incrementables don't require postifx operator++/operator-- to exist at all, which affects all of the incremetable, iterator and range concepts.
• iter_move(it) can return a type that's nothing like std::move(*it), leading to all kinds of mayhem.

Support for a more powerful iter_move is kind of non-negotiable for the library, so I had to reimplement lots of standard library concepts (mostly stolen from libc++), and decided that I might as well tackle the other two bullet points. I started working on that, and the truth is that I don't just need to reimplement the standard library concepts, but also lots of the iterators and range utilities based on them. I do that on a as-needed basis, which ensures that all reimplemented components are implicitly tested by being used in the library - it notably avoids having to add lots of additional dedicated tests for stolen code.

The new iterator/sentinel model is more complicated than I expected it to be, so things aren't going quite fast and I need to change more parts of cpp-sort than expected, but I'm pretty confident that the end result makes it worth the cost.