Just as a follow-up,
I refined my benchmarks, and while my partition code works better on
some platforms, it's not consistent.

However, the destructive partitioning (move instead of swap) results are
good vs non-destructive, at (on average across different numbers of
elements up to 1000000) 2% faster for int, 8% faster for double and
40-byte structs, 40% faster for 490-byte structs, ie. scales with type
sizeof and/or non-trivially-copyable status.

On 6/09/2023 11:43 am, Patrice Roy wrote:
> These remarks make SG14 a fun place to be :) Thanks!
>
> Le mar. 5 sept. 2023 à 19:03, Matt Bentley via SG14
> <sg14_at_[hidden]> a écrit :
>
> Thanks for that-
>
> it led me down a rabbithole where I realised I can improve upon
> the existing strategies used in std::partition across all of the 3
> major vendors.
> Cheers-
>
> On 4/09/2023 2:17 pm, Edward Catmur via SG14 wrote:
>> This is a pretty vague thought, but have you noticed the
>> correspondence to the partition / stable_partition algorithms?
>> partition is essentially a way to accomplish the swap part of a
>> swap-and-pop, and stable_partition is more or less identical to
>> remove_if, so it feels like maybe there should be an equivalent
>> using move instead of swap that operates on iterators/ranges
>> instead of containers, leaving two consecutive ranges where the
>> first part contains the desired elements and the second is
>> moved-from.
>>
>> Anyway, great work and thanks.
>>
>> On Sun, Sep 3, 2023, 18:06 Matt Bentley via SG14
>> <sg14_at_[hidden]> wrote:
>>
>> Yeah there's a few issues, such as whether to support deques,
>> but I figured one thing at a time. Given lack of response,
>> might be best to discuss at next meeting.
>> Can't use swap in the name as mentioned - as no swaps occur.
>>
>> Cheers for getting back to me.
>>
>> On 4/09/2023 10:16 am, Patrice Roy wrote:
>>> In PXXX, I put « Move-With-Last-Swap / Reorderase » for the
>>> moment and we'll find a better name if needed (it's a bit
>>> early for that). I'd focus on the technical issues
>>> initially, and feel LEWG's mood for the name.
>>>
>>> Thanks!
>>>
>>> Le jeu. 24 août 2023 à 20:07, Matt Bentley via SG14
>>> <sg14_at_[hidden]> a écrit :
>>>
>>> Hi all-
>>>
>>> as per the last meeting there was some support for
>>> putting forward a proposal for what I call reorderase
>>> (plflib.org/reorderase.htm
>>> <http://plflib.org/reorderase.htm>) but is really just
>>> an iteration of the swap-and-pop idiom, optimized (no
>>> swap, just move) and extended to range-erase and
>>> std::erase_if/std::erase. See the page for more information.
>>>
>>> There was some discussion of this back in 2015 by Brent
>>> Freidman but he was focused on the erase_if equivalents
>>> - which're the worse-performing of the set.
>>>
>>> I have a few questions before putting a paper together,
>>> the first of which is bikeshedding. I'm pretty settled
>>> on the name 'move_pop', for reasons which will become
>>> clear, but I am open to suggestions. Please let me know
>>> what you think:
>>>
>>>
>>> Names which aren't appropriate:
>>>
>>> * I like portmanteau's but the standard doesn't, so
>>> I'm guessing 'reorderase' is out of the question;
>>> possibly unfair on non-english speakers.
>>> * Anything with 'swap' in it. Implies operations which
>>> do not occur, also implies allocation.
>>> * Anything with 'unstable' in it - in the case of the
>>> standard library the term 'unstable' is not defined
>>> or used, only the term 'stable' is defined. In
>>> addition the word has a bad connotation in terms of
>>> programs, and algorithms are assumed to be unstable
>>> by-default where 'stable' is not used in functions.
>>> * Anything long like 'unstable', 'disordered',
>>> 'unordered', 'reordering', etc; at least for the
>>> singular/range reorderase equivalents. They are
>>> expected to be commonly-used functions, so long is
>>> Bad. I don't mind a longer title on the
>>> erase_if/remove_if equivalent as this is expected to
>>> be less-frequently used.
>>> * Anything involving 'back' or 'front'. A deque would
>>> want to pop from the front if |location == begin()|
>>> or |first == begin()| |(in reorderase(first,
>>> last))|, and we would want the name to be consistent
>>> between deques and vectors/inplace_vectors (if we
>>> want to support deques).
>>>
>>> Potential names:
>>>
>>> * move_pop/move_and_pop (the standard currently has
>>> about 1 other function which uses _and_ but it seems
>>> an unnecessary elongation) - this is good enough,
>>> and short, and brings in the 'pop' association with
>>> being quick/O(1).
>>> * ...? Suggestions?
>>> * For an std::erase_if/std::erase equivalent, using
>>> the 'pop' thing won't work, as erase_if already does
>>> this (moves the stuff to the back, erases it). If we
>>> go with a remove_if-equivalent implementation
>>> instead of erase_if, pop also doesn't work because
>>> remove_if doesn't erase/pop anything. I'm leaning
>>> towards (assuming a remove_if equivalent member
>>> function instead of erase_if)
>>> 'unordered_remove_if'/'unordered_remove', or
>>> 'disordered_remove_if'/'disordered_remove'. I prefer
>>> the latter is it clearly implies that there /will
>>> be/ a disruption of order in the use of this function.
>>>
>>>
>>> M@
>>>
>>> _______________________________________________
>>> SG14 mailing list
>>> SG14_at_[hidden]
>>> https://lists.isocpp.org/mailman/listinfo.cgi/sg14
>>>
>> _______________________________________________
>> SG14 mailing list
>> SG14_at_[hidden]
>> https://lists.isocpp.org/mailman/listinfo.cgi/sg14
>>
>>
>> _______________________________________________
>> SG14 mailing list
>> SG14_at_[hidden]
>> https://lists.isocpp.org/mailman/listinfo.cgi/sg14
> _______________________________________________
> SG14 mailing list
> SG14_at_[hidden]
> https://lists.isocpp.org/mailman/listinfo.cgi/sg14
>