Why does std::list have remove and remove_if functions

Question

Why does std::list have remove and remove_if functions? That seems to duplicate behavior with the algorithm functions of the same name. If remove and remove_if make sense, why not find and find_if?

Answer 1

First of all, they have different semantics. std::list::remove_if erases the removed elements, and std::remove_if doesn't. std::remove_if also requires the container elements to be MoveAssignable, while std::list::remove_if only requires them to be Erasable.

There is actually no complexity differences between both (they both are O(n)), but std::remove_if could be about two times slower because of the need to do list traversal using two independent pointers instead of just one - and list traversal on most modern CPUs is a quite expensive operation. If the move operation for the container element type is expensive, this can additionally slow down std::remove_if.