Further std::set woes

Question

I asked this question earlier. I am intrigued by std::set but I have another confusing scenario.

Namely, is the following code legal, portable c++ for T=std::vector and T=std::set:

template <typename T>
void remove_elements(T& collection, int removal_value)
{
    typename T::iterator new_end = 
        std::remove(collection.begin(), collection.end(), removal_value);
    collection.erase(new_end, collection.end());
}

According to the SGI reference, set::iterator and set::const_iterator are the same, so I don't know if this is legit. However, I can't seem to find another way to get the operation I need to work regardless of type. I could resort to template specialization, however it would be nice not to have to specialize in the first place.

Answer 1

No, it won't work for std::set, because one of the requirements of std::remove() is that the iterator be a mutable iterator, and std::set's iterators are not mutable.

I don't have any good alternatives to suggest, unfortunately. One thing you could do is maybe use std::find() to find an iterator to an occurrence of the element, and then use the .erase() method on the iterator (which is present in both std::vector and std::set) to erase it; and keep doing it until there are no more such elements. But this might be very inefficient, O(n^2) instead of O(n).

Answer 2

erase-remove idiom works only for sequence containers. For the standard associative containers it will not work and the solution is not so straightforward.

Two approaches :

1. Use remove_copy_if to copy all the values into another temporary container and then swap the contents of the original container with those of temporary one. [Refer my answer to related Q]
2. The other one would be loop to walk the container elements and post increment the iterator when you pass it to erase.

Refer this Q for more details: remove_if equivalent for std::map

Also, refer Item 9. Choose carefully among erasing options from Effective STL by Scott Meyers.

Answer 3

I think the "right" answer is to overload remove_elements for std::set. Since set is ordered and contains no duplicates, removing elements equal to removal_value is much simpler than for vector or for generic sequences. You don't really want to use the same algorithm for everything, even if you could:

template <typename T>
void remove_elements(T& collection, const typename T::value_type& removal_value)
{
    typename T::iterator new_end = 
        std::remove(collection.begin(), collection.end(), removal_value);
    collection.erase(new_end, collection.end());
}

template<typename T>
void remove_elements(std::set<T>& collection, const T& removal_value)
{
    collection.erase(removal_value);
}

I'm slightly concerned about whether these are ever ambiguous, but in the most obvious use case they seem to work OK for me.

This is a bit of a pain if you have other Unique Sorted Associative Containers than std::set to worry about. You're moving into std::swap territory, where every class you implement has to provide an overload of remove_elements. But since set is the only class you're asking about, I assume it's the only tricky case you're actually using, at least for now. If necessary you can use traits to select the right version of the algorithm based on the properties of the container.