Erase-remove idiom with std::set failing with cons

Question

Can someone help me out here?

Compiling this code:

void test()
{
  std::set<int> test;
  test.insert(42);
  test.erase(std::remove(test.begin(), test.end(), 30), test.end());  // <- Line 33
}

Is generating the following error when compiling:

$ make
g++ -c -Wall -pedantic-errors -Wextra -Wunused -Werror a_star.cpp
/usr/lib/gcc/i686-pc-cygwin/4.3.4/include/c++/bits/stl_algo.h: In function `_FIter std::remove(_FIter, _FIter, const _Tp&) [with _FIter = std::_Rb_tree_const_iterator<int>, _Tp = int]':
a_star.cpp:33:   instantiated from here
/usr/lib/gcc/i686-pc-cygwin/4.3.4/include/c++/bits/stl_algo.h:779: error: assignment of read-only location `__result.std::_Rb_tree_const_iterator<_Tp>::operator* [with _Tp = int]()'
make: *** [a_star.o] Error 1

Answer 1

As already said your code doesn't work because you try to modify a sequence inside an associative container, but you can't do this because this sequence is immutable. Rationale: set holds an ordered sequence, usually in a binary tree. If you were allowed to modify it, you could corrupt the container and the program would crash. Btw, it still can happen in some situations.

You can change your code to this:

test.erase(30);

Or use ArunSaha's (+1) code for more complicated criteria.

Answer 2

Erase-remove idiom cannot be used with associative containers. Associative containers do not allow modifications of the entire container element through the iterator, which immediately means that mutating sequence operations (like std::remove) cannot be applied to them.

Answer 3

If I remember well, std::remove is never to be used with a std::set element.

As a set is not a pure array you have to use erase.

Answer 4

In std::set, the elements are not modifiable. So, the std::set::iterator is also unmodifiable. From this tutorial, section 27.3.2.1:

In simple associative containers, where the elements are the keys, the elements are completely immutable; the nested types iterator and const_iterator are therefore the same.

Hence, the erase-remove idiom cannot be applied as is. You have to write a for loop, and use the member function std::set::erase inside it. See this question and this accepted answer and another answer for exact details, but in short, the loop is like the following

typename std::set::iterator set_iter; 

for( set_iter it = s.begin(); it != s.end(); /* blank */ ) {
    if( some_condition() ) {
        s.erase( it++ );       // Note the subtlety here
    }
    else {
        ++it;
    }
}