2

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++.

2

3 Answers 3

2

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 &);
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.

4
  • 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, 2013 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. Apr 17, 2013 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! Apr 17, 2013 at 15:08
  • 1
    @DrewDormann: there was a question about that just the other day. stackoverflow.com/questions/16013545/… Apr 17, 2013 at 15:14
0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.