Boost logo

Boost :

Subject: [boost] Alternative remove, erase, and partition algorithms
From: Brent Friedman (fourthgeek_at_[hidden])
Date: 2016-02-15 03:19:05


I'd like to propose the following for inclusion in Boost.Algorithm.

   partitions a range into 'good' and 'bad' elements, as partition. 'Good'
elements maintain their order, while 'bad' elements are left in unspecified
order. stable_partition has either linear additional storage or performs
3NlogN move operations, whereas semistable_partition has constant memory
overhead and at most 3N move operations. Requires forward iterators.

*unstable_remove ( _if )*
   removes elements from a range but without maintaining element order.
Performs at most N/2 moves as compared to N for remove. Requires
bidirectional iterators.

   erases an iterator or range from a container ( as vector::erase )
without maintaining element order. Intuitively, this fills in the hole
created by the erase operation by moving elements from the end. Limited to
containers with bidirectional iterators (possibly random-access).

The following documents describe and explore these algorithms:!topic/sg14/2uwOmXWqa2E
(unstable_erase, unstable_remove)
(unstable_remove, semistable_partition)

I have been pursuing standardization, but it seems like there is value in
getting community experience with these algorithms first in order to make
for easier justification.

-Brent Friedman

Boost list run by bdawes at, gregod at, cpdaniel at, john at