Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Erase-remove idiom with std::set failing with constness-related error [duplicate]

Tags:

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
like image 414
Jared Avatar asked Sep 25 '10 05:09

Jared


3 Answers

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;
    }
}
like image 64
Arun Avatar answered Oct 21 '22 16:10

Arun


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.

like image 35
AnT Avatar answered Oct 21 '22 17:10

AnT


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.

like image 42
Yakov Galka Avatar answered Oct 21 '22 16:10

Yakov Galka