Is posible erase element while iterating in a stl container ?

[jose luis fernandez diaz]

Hi,

Is this right any stl container (vector, deque, list, . . .)?


typedef vector container;

int main()
{
container<int> c1;
c1.push_back(1);
c1.push_back(2);
c1.push_back(3);

container<int>::iterator it=c1.begin();
while(it != c1.end())
{
if(*it=2)
c1.erase(it);
it++;
}
}


Thanks,
Jose Luis.

 

[Christopher Benson-Manica]

Is this right any stl container (vector, deque, list, . . .)?

Josuttis has a lovely table where he lists whether inserting or
removing from a standard container invalidates iterators (which I
gather is the gist of your question):

vector: on reallocation
deque: always
list: never
set: never
multiset: never
map: never
multipmap: never

I don't know whether erase() can cause reallocation for a vector, so I
don't know if your code is safe.

 

[Siemel Naran]

Is this right any stl container (vector, deque, list, . . .)?

All the containers' erase functions returns an iterator that points to the
next element. Thus,

container<int>::iterator it=c1.begin();
while(it != c1.end())
{
if(*it=2)
c1.erase(it);
it++;
}

should be rewritten as

container<int>::iterator it=c1.begin();
while(it != c1.end())
{
if(*it=2)
it = c1.erase(it);
else
++it;
}

As an aside, note that I used pre-increment ++it because on many compilers
this will be more efficient than it++.

Note that repeated calls to erase may degrade performance, and could make
the entire erase operation run in O(N^2) time.

You can use std::remove too

container<int>::iterator it= std::remove(c1.begin(), c1.end(), 2);

This transforms the array { 1, 2, 3, 4, 3, 2, 1 } into { 1, 3, 4, 3, 1, 2,
2 } and returns an iterator to the first '2'. Therefore you can call erase
to actually erase the elements:

c1.erase(it, it.end());

Note that class list has list::erase.

 

[Michiel Salters]

Josuttis has a lovely table where he lists whether inserting or
removing from a standard container invalidates iterators (which I
gather is the gist of your question):

vector: on reallocation
deque: always
list: never
set: never
multiset: never
map: never
multipmap: never

That refers to all allocators except the erased one, of course.
[ 23.1.2/8 ]

Regards,
Michiel Salters

 

[Michiel Salters]

All the containers' erase functions returns an iterator that points to the
next element.

All _sequence_ containers. std::multiset<T>::erase(T) will return the
number erased, as does multimap::erase. Other associative_container::erase
methods return void.

Regards,
Michiel Salters

 

[Christopher Benson-Manica]

That refers to all allocators except the erased one, of course.

^^^^^^^^^^ Iterators?

One would hope that'd be fairly obvious...

 

[Siemel Naran]

All _sequence_ containers. std::multiset<T>::erase(T) will return the
number erased, as does multimap::erase. Other associative_container::erase
methods return void.

Thanks. Just one question. My version of the standard has
multimap::erase(iterator position) returning void, not the number (of
elements) erased. Can you comment?

 

[Rob Williscroft]

Siemel Naran wrote in
in
comp.lang.c++:

Thanks. Just one question. My version of the standard has
multimap::erase(iterator position) returning void, not the number (of
elements) erased. Can you comment?

Think about it, iterator is either 'iterating' to 1 element
or it is multimap<>::end(), so you could write:

template < typename K, typename V >
int erase(
std::multimap< K, V > &map,
typename std::multimap< K, V >::iterator ptr
)
{
if ( ptr == map.end() ) return 0;

map.erase( ptr );
return 1;
}

But would you bother ?

My £0.02

Rob.