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@lists.isocpp.org> 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@lists.isocpp.org
https://lists.isocpp.org/mailman/listinfo.cgi/sg14