Alternative remove, erase, and partition algorithms
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
participants (1)
-
Brent Friedman