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?
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?
That's because given the nature of std::list (or more precisely - the likely implementation forced by the standard), standard algorithms like std::remove and std::remove_if are inefficient when used on it.
std::list's implementation has to meet some requirements, which essentially force it to be node-based, linked with pointers structure.
This very implementation has its cons. For example, it does not allow for random-access iterators, thus std::sort will simply not work for it, since it requires random-access. This is the extreme case. There are efficient algorithms which do work with the specific nature of std::list likely implementation and they are used in the member std::list::sort. While std::sort could use the same implementation, other scenarious would likely suffer a performance loss.
The less extreme case is the remove case. Standard std::remove, paired with erase member function (erase-remove idiom) is a great way of dealing with removing elements... unless the internal implementation makes those operations costly. On std::list, std::remove paired with naive call to erase will require O(n) (where n is equal to the list's size) operations on average. This can be drastically simplified by taking advantage of the internal implementation (in this case - pointer manipulation in the likely implementation). If you have direct access to the element you wish to remove, this operation becomes O(1).
So - what's the thing about std::find and std::find_if? The thing is that there are no alternatives for std::list that would benefit from its internal implementation. There could be a member find and find_if, but they would be pretty much identical to their <algorithm> versions, thus there is no need to introduce them.
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.
The member functions in this case are more efficient and should be preferred over the more generic ones in <algorithm>, even though the generic functions do work on std::list.
The reason is std::list allows O(1) complexity removing and insertion of a single element anywhere, and the member functions take advantage of that.