C++ Logo


Advanced search

Re: Questions + bikeshed for reorderase

From: Patrice Roy <patricer_at_[hidden]>
Date: Tue, 5 Sep 2023 19:43:06 -0400
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) 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 listSG14_at_[hidden]://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:43:20