468,754 Members | 1,332 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,754 developers. It's quick & easy.

Is posible erase element while iterating in a stl container ?

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.
Jul 22 '05 #1
7 4180
jose luis fernandez diaz <jo**********************@yahoo.es> spoke thus:
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.
container<int>::iterator it=c1.begin();
while(it != c1.end())
{
if(*it=2)
c1.erase(it);
it++;
}


--
Christopher Benson-Manica | I *should* know what I'm talking about - if I
ataru(at)cyberspace.org | don't, I need to know. Flames welcome.
Jul 22 '05 #2
"jose luis fernandez diaz" <jo**********************@yahoo.es> wrote in
message
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.
Jul 22 '05 #3
Christopher Benson-Manica <at***@nospam.cyberspace.org> wrote in message news:<c6**********@chessie.cirr.com>...
jose luis fernandez diaz <jo**********************@yahoo.es> spoke thus:
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


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

Regards,
Michiel Salters
Jul 22 '05 #4
"Siemel Naran" <Si*********@REMOVE.att.net> wrote in message news:<Rs********************@bgtnsc04-news.ops.worldnet.att.net>...
"jose luis fernandez diaz" <jo**********************@yahoo.es> wrote in
message
Is this right any stl container (vector, deque, list, . . .)?


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
Jul 22 '05 #5
Michiel Salters <Mi*************@logicacmg.com> spoke thus:
That refers to all allocators except the erased one, of course.

^^^^^^^^^^ Iterators? :)

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

--
Christopher Benson-Manica | I *should* know what I'm talking about - if I
ataru(at)cyberspace.org | don't, I need to know. Flames welcome.
Jul 22 '05 #6
"Michiel Salters" <Mi*************@logicacmg.com> wrote in message
"Siemel Naran" <Si*********@REMOVE.att.net> wrote in message

news:<Rsmhc.12091
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.


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?
Jul 22 '05 #7
Siemel Naran wrote in
news:qb********************@bgtnsc04-news.ops.worldnet.att.net in
comp.lang.c++:
"Michiel Salters" <Mi*************@logicacmg.com> wrote in message
"Siemel Naran" <Si*********@REMOVE.att.net> wrote in message

news:<Rsmhc.12091
> 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.


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.
--
http://www.victim-prime.dsl.pipex.com/
Jul 22 '05 #8

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

13 posts views Thread by Paras | last post: by
26 posts views Thread by Pieter Thysebaert | last post: by
3 posts views Thread by jose luis fernandez diaz | last post: by
3 posts views Thread by Chad E. Dollins | last post: by
8 posts views Thread by olanglois | last post: by
4 posts views Thread by sks | last post: by
1 post views Thread by newbie | last post: by
5 posts views Thread by subramanian100in | last post: by
12 posts views Thread by Philip Mueller | last post: by
reply views Thread by zhoujie | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.