How to overload std::remove for std::list?

Question

I once learnt that the general way to erase elements from a container is via the erase-remove-idiom. But I was surprised to find out that at least g++'s STL implementation does not overload std::remove() for std::list, since in this case a lot of object assignments could be saved by doing the reordering via pointer manipulation.

Is there a reason that the C++ standard does not mandate such an optimisation? But my main question is how I can overload std::remove() (it does not have to be portable beyond g++), so I could provide an implementation that use list::splice()/list::merge() instead. I tried a couple of signatures but get an ambiguity error at best, for example:

template <typename T>
typename std::list<T>::iterator
remove(typename std::list<T>::iterator first,
       typename std::list<T>::iterator last, const T &v);

P.S.: I am sorry that I was not clear enough. Please ignore that the functions come from the std namespace and what they do specifically. I just wish to learn more about the template/typetraits/overload rules in C++.

You're supposed to use [`std::list::remove`](http://en.cppreference.com/w/cpp/container/list/remove). — Joseph Mansfield, Apr 17 '13 at 14:43
This may be an [XY Problem](http://meta.stackexchange.com/questions/66377). — Drew Dormann, Apr 17 '13 at 15:12

Steve Jessop · Answer 1 · 2013-04-17T15:30:01.670

It's not mandated because it's not just an optimization, it has different semantics from what you'd expect for a Sequence container:

std::list<int> l;
l.push_back(1);
l.push_back(2);

std::list<int>::iterator one = l.begin();
std::list<int>::iterator two = l.end(); --two;

if (something) {
    l.erase(remove(l.begin(), l.end(), 1), l.end());
    // one is still valid and *one == 2, two has been invalidated
} else {
    l.remove(1);
    // two is still valid and *two == 2, one has been invalidated
}

Regarding the actual question: ISWYM, I'm stuck for the moment how to write a pair of function templates so that one matches arbitrary iterators and the other matches list iterators, without ambiguity.

Do be aware that there isn't actually any guarantee in the standard that list<T>::iterator is a different type from some_other_container<T>::iterator. So although in practice you'd expect each container to have its own iterator, in principle the approach is flawed quite aside from the fact that you suggested putting the overload in std. You can't use iterators alone to make "structural" changes to their corresponding containers.

You can do this without ambiguity:

template <typename Container>
void erase_all(Container &, const typename Container::value_type &);

template <typename T>
void erase_all(std::list<T> &, const T &);

score 1 · Answer 2 · answered Apr 17 '13 at 14:46

1

list::remove or list::erase alone will do what you've seen the erase/remove idiom do for vectors.

remove for values or predicates. erase for single iterators or ranges.

answered Apr 17 '13 at 14:46

Drew Dormann

59,987
13
123
180

Thanks but I do know about the list member functions but it doesn't answer my question. Just assume there are quite a few template functions in my code that use erase-remove to work with generic containers and I don't want to overload all of them for std::list. – antje-m Apr 17 '13 at 14:50
Hi, @antje-m. You may have been misled that the erase/remove idiom is the general approach for all containers. It's not valid for *most* container types. Also, if it *were* used on `std::list`, it would be much slower than the functions I link to. – Drew Dormann Apr 17 '13 at 15:06
@antje-m Perhaps you would benefit more from asking about a "generic remover for containers" instead of asking *how* to make erase/remove the correct approach. Good luck! – Drew Dormann Apr 17 '13 at 15:08
1

@DrewDormann: there was a question about that just the other day. http://stackoverflow.com/questions/16013545/how-do-i-erase-elements-from-stl-containers/16013546#16013546 – Steve Jessop Apr 17 '13 at 15:14

score 0 · Answer 3 · answered Apr 17 '13 at 14:50

The advice you received is good, but not universal. It is good for std::vector, for instance, but completely innecessary for std::list since std::list::erase() and std::list::remove() already do the right thing. They do all the pointer magic you request, something std::vector::erase() cannot do because its internal storage is different. This is the reason why std::remove() is not specialised for std::list: because there is no need to use it in this case.

How to overload std::remove for std::list?

3 Answers3