[boost] Alternative remove, erase, and partition algorithms

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

Hello,

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

*semistable_partition*
   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.

*unstable_erase*
   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:
https://groups.google.com/a/isocpp.org/forum/#!topic/sg14/2uwOmXWqa2E
(unstable_erase, unstable_remove)

https://iterator.wordpress.com/2016/01/31/algorithms_0/
(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