Handle sentinel parameters

[Morwenn]

The Ranges TS introduces the notion of sentinels. A sentinel is an end iterator with a different type than the actual iterators; it shall be comparable to the other iterators and may be used to help the compiler generate better code.

We probably want to have such sentinel iterators at some point in cpp-sort. However, it will probably require lots of tricky SFINAE and modifying most of the available algorithms to get things right.

It is worth noting that the Ranges TS makes sort and stable_sort return an iterator to the last element, which makes sense in the context of sentinels: when a couting/size sentinel is passed, the last iterator isn't known beforehand, so the algorithm returns it since it might be useful. This adds a new question: how do we handle adapters such as counting_adapter that already override the return type? Do we still override that return type, or do we return a tuple? The latter solution allows not to throw away information, so it might be preferred.

[Morwenn]

At long last I'm making progress in this issue, now that Ranges-v3 is already history, the Ranges TS is no more, and most iterator and ranges improvements have been merged into C++20 and compiler and standard library support mostly caught up. By now this issue is the oldest still open issue in the library, dating back to the very first year of the project, which is quite something.

Nostalgia aside, I am done adding basic sentinel support and tests for all sorters, sorter adapters and measures of presortedness in the library, modulo unseen bugs and missed components. Philosophically, I can consider that this part is done. However the story doesn't end there! The following points must be treated before I can close the issue:

• Update the documentation to include basic information about sentinels and their support in the library.
• Update tutorials and examples.

Additionally, the following points can be the subject of follow-up development and features:

• I realized that it is "trivial" to add sentinel support to existing sorters that don't explicitly support sentinels: all it takes is computing the last iterator from the passed iterator/sentinel pair and passing that down to the sorter implementation if it doesn't support sentinels out-of-the-box. It is a possible future improvement to sorter_facade provided it doesn't make the class unmaintainable.
• Most sorters and adapters currently implement sentinel support by explicitly computing the end iterator and/or the size of the collection to sort from the iterator/sentinel pair, which adds one or two additional O(n) passes prior to the sorting. When two passes are performed, I believe than one could be enough. Moreover, a bunch of existing components could probably be updated to compute that information on-the-fly if needed to avoid the additional O(n) pass.

If automatic sentinel support is added to sorter_facade, it will be reasonable for sorter adapters to expect the passed sorters to already have sentinel support.