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
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:
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk