P0227 Weakening the iterator categories of some standard algorithms

[jensmaurer]

P0227R0 Weakening the iterator categories of some standard algorithms (Thibaut Le Jehan)

https://issues.isocpp.org/show_bug.cgi?id=169

[jensmaurer]

Jeffrey Yasskin 2016-03-04 00:46:35 UTC
http://wiki.edg.com/bin/view/Wg21jacksonville/P0227

Take this for C++17?
SF F N A SA
1 9 2 2 0
(Some worry that it will be a footgun, where sorting a list is much slower than sorting a vector.)

[jensmaurer]

@mclow, what kind of revision are you looking for here? The paper has wording.

[mclow]

The wording that it is attempting to revise has changed since the paper was written.

[Morwenn]

Hi, author here, I'm surprised that the proposal is still alive considering that I withdrew it quite some time ago. Here is the mail I sent back then to motivate the withdrawal:

To be honest, I don't think the paper was that good an idea to start with: the committee was most likely right in considering the proposed feature to be too easy to use improperly. Let's be honest, unless a sort method is specialized for a specific data structure and takes advantage of it (as it is the case for standard library lists), it is almost always better to simply move the elements to sort in a temporary buffer, sort them with a performant algorithm that works on random-access iterators and move the sorting elements back to the original collection.

The only semi-valid use case where I think sorting algorithms for forward and bidirectional iterators could actually be useful is in memory-constrained environments where there isn't much extra memory available, but as far I know data structures that provide forward or bidirectional iterators tend to also allocate heap memory, and thus aren't probably used in such environments. Moreover std::stable_sort as described can still allocate heap memory which means it still isn't suitable for such environments. std::sort can actually be made to run in O(n log n) with O(log n) extra memory for the stack recursion with a quicksort derivative, making it potentially usable in memory-constrained environments, but I'm unconvinced it is really worth it.

Sorry again for the delay and the eventual waste of time: despite the motivation exposed in the original paper I managed to convince myself it wasn't good enough an idea in the meantime ^^"

Reading my withdrawal motivation again, some things are a bit off (I found an algorithm that works on forward iterators and can run in O(n log n) time and O(1) extra memory), but in the grand scheme of things it still is more or less my point of view. Now, I'm not sure what to do: if people still want the feature I can produce an updated paper provided I know how to tweak the wording, but I haven't seen much interest since 2017 so it's probably not worse pursuing it.