Why can't I remove a string from a std::set with std::remove_if?

Question

Possible Duplicate:
remove_if equivalent for std::map

I have a set of strings:

set <wstring> strings;
// ...

I wish to remove strings according to a predicate, e.g.:

std::remove_if ( strings.begin(), strings.end(), []( const wstring &s ) -> bool { return s == L"matching"; });

When I attempt this, I get the following compiler error:

c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\algorithm(1840): error C2678: binary '=' : no operator found which takes a left-hand operand of type 'const std::basic_string<_Elem,_Traits,_Ax>' 

The error appears to suggest that std::string doesn't have a by-value copy constructor ( which would be illegal). Is it somehow bad to use std::remove_if with std::set ? Should I be doing something else instead such as several iterations of set::find() followed by set::erase() ?

Answer 1

std::remove_if (or std::erase) works by reassigning the values of the members of the range. It doesn't understand how std::set organizes data, or how to remove a node from its internal tree data structure. Indeed, it's impossible to do so using only references to nodes, without having the set object itself.

The standard algorithms are designed to have transparent (or at least consistently easy-to-remember) computational complexities. A function to selectively remove elements from a set would be O(N log N), due to the need to rebalance the tree, which is no better than a loop calling my_set.remove() . So, the standard doesn't provide it, and that is what you need to write.

On the other hand, a naively hand-coded loop to remove items from a vector one-by-one would be O(N^2), whereas std::remove_if is O(N). So the library does provide a tangible benefit in that case.

A typical loop (C++03 style):

for ( set_t::iterator i = my_set.begin(); i != my_set.end(); ) {
    if ( condition ) {
        my_set.erase( i ++ ); // strict C++03
        // i = my_set.erase( i ); // more modern, typically accepted as C++03
    } else {
        ++ i; // do not include ++ i inside for ( )
    }
}

Edit (4 years later!): i ++ looks suspicious there. What if erase invalidates i before the post-increment operator can update it? This is fine, though, because it's an overloaded operator++ rather than the built-in operator. The function safely updates i in-place and then returns a copy of its original value.

Answer 2

The error message says

no operator found which takes a left-hand operand of type 'const std::basic_string<_Elem,_Traits,_Ax>'

Note the const. The compiler is correct that std::wstring doesn't have an operator= which can be called on a const object.

Why is the string const? The answer is that the values in a std::set are immutable, because values in a set are ordered, and changing a value could change its ordering in the set, invalidating the set.

Why is the compiler trying to copy a value of the set?

std::remove_if (and std::remove) don't actually erase anything (nor can they, because they don't have the container, only iterators). What they do is to copy all values in the range which don't match the criterion to the beginning of the range, and return an iterator to the next element after the matching elements. You are then supposed to manually erase from the returned iterator to the end of the range. Since a set keeps its elements in order, it would be wrong to move any elements around, so remove_if cannot be used on a set (or any other associative container).

In short, you do have to use a loop of std::find_if and set::erase, like so:

template<class V, class P>
void erase_if(std::set<V>& s, P p)
{
  std::set<V>::iterator e = s.begin();
  for (;;)
  {
    e = std::find_if(e, s.end(), p);
    if (e == s.end())
      break;
    e = s.erase(e);
  }
}