Views, sort_copy, online algorithms...

[Morwenn]

cpp-sort currently only cares about in-place sorting algorithms: algorithms that mutate the passed collection and don't return anything (except when they do), which is pretty much enough for people most of the time. However, I believe that there is some value in having algorithms that actually copy a sorted equivalent of the passed collection into the library. It once again leads to maaaaany design decisions depending on how we want to implement that:

• Have a cppsort::sort_copy function in the library taking a sorter (or defaulting to default_sorter) and an additional OutputIterator parameter?
• Provide an equivalent cppsort::sort_move function?
• Create a cppsort::sorted function that takes an iterable and returns a new instance of the same iterable? Make it work with an OutputIterator instead? Have it take any sorter like cppsort::sort?
• Add a cppsort::sorted_view returning a range with sorted iterators which, when iterated, corresponds to a sorted view of the original collection? It's pretty much what indirect_adapter does in the first place, but decoupling it from the adapter might also be interesting.
• Have first-class support for online sorting algorithm? Adding an is_online property in cppsort::sorter_traits is easy, but how to use it properly?

An interesting algorithm about incremental sort that might provide some idea and/or insights about online/incremental sorting: http://larshagencpp.github.io/blog/2016/04/23/fast-incremental-sort

[Morwenn]

For sort_copy algorithms, one interesting solution would be to take advantage of the fact that sorters are function objects to provide a copy or copy_to method:

cppsort::ska_sort.copy(collection, std::back_inserter(res));

I don't know whether it's a good idea. Like everything else I will have to balance the pros and cons.

[Morwenn]

What I called a sorted "view" in the original post can't be a View according to the standard concept semantics because views are supposed to have O(1) construction and linear traversal. A "sorted view" would either be sorted at construction in O(n log n) time or would use an online algorithm and have O(n log n) traversal. No matter what I do with this issue I should use another terminology.

[Morwenn]

A few updates regarding the concerns discussed in this issue:

• Issue Remove cppsort::sort and cppsort::stable_sort #167 removes cppsort::sort and cppsort::stable_sort, so adding a first-class cppsort::sorted might seem like a poor idea. Though unlike the other two it would provide a feature that can't be covered by a simple sorter or sorter adapter.
• The sorted_view idea is mostly covered by the sorted_iterators utility added as part of issue sorted_indices and apply_permutation #200 (commit 8bd558c).

The other points are still very much open design issues without obvious answers to this day. To keep the genericity of the collection/compare/projection design without getting too complicated, I'd probably need to invent a way to give a separate channel for output range parameters somehow.