C++ Logo


Advanced search

Questions + bikeshed for reorderase

From: Matt Bentley <mattreecebentley_at_[hidden]>
Date: Fri, 25 Aug 2023 12:06:49 +1200
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
  * 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.


Received on 2023-08-25 00:07:00