C++ Logo


Advanced search

Re: Questions + bikeshed for reorderase

From: Matt Bentley <mattreecebentley_at_[hidden]>
Date: Wed, 6 Sep 2023 11:03:30 +1200
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

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

Received on 2023-09-05 23:03:41