Counted iterators

[Morwenn]

In one of his blog posts, Eric Nieber introduces generic counted iterators, which might come along with the Ranges TS. These iterators allow to use the same algorithms for usual iterables and counted iterables instead of having to provide counted versions of the algorithms (e.g. copy_n and friends). The proposed mechanism relies on sentinel parameters, so this issue logically comes after issue #20, and would also need a small update on the standard library side in order to work properly, making it a future issue.

Anyway, we should take into account the fact that counting iterables will be proposed for standardization at some point, and think of how it might impact cpp-sort. It shouldn't make things really different, and even things like counted and uncounted should not be a problem since we don't have counted algorithms in the library.

---

A new problem arises: in the new iterations of the work related to the Ranges TS, std::sort is specified to return the end iterator. This is because when passed a normal iterator and a counted sentinel, the actual end iterator of the algorithm is unknown even though it is valuable information that is most probably computed by the sorting algorithm. The first obvious problem is that we will probably have to add that to every sorting algorithm of the library.

The second and most subtle problem has to do with adapters: today counting_adapter returns an integer type. When given a sorter that returns an iterator, should it return the integer type instead, or build a tuple with the integer type and the iterator type? I have currently no elegant solution to this problem.

[Morwenn]

The nomenclature for these features changed a bit in 4 years, but the ideas are still there, interesting and evolving. Several things are now more obvious than they used to be, notably that sized sentinels are great to avoid some O(n) size computations in a few sorters designed to handle forward and/or bidirectional iterators (e.g. quick_sorter, quick_merge_sorter). A few things seem to be possible to improve those:

• Add an operator() overload to these sorters accepting an iterator and a sized sentinel, which allows to avoid having to recompute the size when passed those.
• Tweak some sorter adapters so that they can pass an iterator/sized sentinel pair to the underlying sorter instead of just an iterator pair, which is interesting when said adapters need to compute the size anyway.

I'm not sure exactly how to do that the proper way yet, but there are definitely some possible improvements in this area.

[Morwenn]

Most of the problems this issue is concerned about are about having vocabulary types allowing to pass a pair of non-random-access iterators and a size without having to pay a O(n) cost. This was handled not with std::counted_iterator, not with sized_sentinel stuff, but with an equivalent of std::ranges::subrange which can be constructed with a pair of iterators and a size, and store them all, giving O(1) access to all of the information we care about. This is what verge_adapter passes around nowadays, which enabled a simplification of parts of the library.

Most of the other points mentioned previously such as sentinels or returning the end iterator have already been handled. Truly, all that's left to do before I can close this issue is to add a few tests to make sure that counted_iterator + default_sentinel work correctly.

Last but not least, the issue of "what should counting_adapter return?" has its dedicated issue #134 and should not block this one.