Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C++ (http://www.velocityreviews.com/forums/f39-c.html)
-   -   removing elements invalidates only those iterators that had specifically pointed at the removed elements (http://www.velocityreviews.com/forums/t457042-removing-elements-invalidates-only-those-iterators-that-had-specifically-pointed-at-the-removed-elements.html)

Alien 09-20-2006 06:04 PM

removing elements invalidates only those iterators that had specifically pointed at the removed elements
 
According to MSDN, removing elements invalidates only those iterators
that had specifically pointed at the removed elements.

But I tried following codes, and find that without the repeated
it=map_.begin();
there will be memory violation.
So, the iterator IS invalidated even if it's not the removed one.
why?

-----------
#include <map>
#include <iostream>
using namespace std;

class CCLL;
map<int, CCLL*> map_;

class CCLL
{
int i_;
public:
CCLL(){i_=0;};
CCLL(int i){i_=i;};
int getI(){return i_;};
void killI(int i)
{
for(map<int, CCLL*>::iterator it=map_.begin();it!=map_.end();it++)
{
if(it->second->getI()==i)
{
map_.erase(it);
return;
}
}
};
~CCLL(){};
};


int main()
{
map_[3] = new CCLL(3);
map_[5] = new CCLL(5);
map_[7] = new CCLL(7);
map_[1] = new CCLL(5);
for(map<int, CCLL*>::iterator it=map_.begin();it!=map_.end();it++)
{
if(it->second->getI()==5)
continue;
it->second->killI(it->second->getI());
it=map_.begin();
}
for(map<int, CCLL*>::iterator it=map_.begin();it!=map_.end();it++)
{
cout<<it->first<<"...."<<it->second->getI()<<endl;
}
}


Thomas Tutone 09-20-2006 06:42 PM

Re: removing elements invalidates only those iterators that had specifically pointed at the removed elements
 
Alien wrote:


> According to MSDN, removing elements invalidates only those iterators
> that had specifically pointed at the removed elements.


That's true with respect to maps, if you are referring to the
map::erase member function. It is not necessarily true for other
standard containers.

>
> But I tried following codes, and find that without the repeated
> it=map_.begin();
> there will be memory violation.
> So, the iterator IS invalidated even if it's not the removed one.
> why?


Your question doesn't make sense. The iterator is invalidated when you
remove it. After that it is invalid. You can't, for example,
increment it, because it's invalid. And that iterator is the removed
one.

> -----------
> #include <map>
> #include <iostream>
> using namespace std;
>
> class CCLL;
> map<int, CCLL*> map_;
>
> class CCLL
> {
> int i_;
> public:
> CCLL(){i_=0;};
> CCLL(int i){i_=i;};
> int getI(){return i_;};
> void killI(int i)
> {
> for(map<int, CCLL*>::iterator it=map_.begin();it!=map_.end();it++)
> {
> if(it->second->getI()==i)
> {
> map_.erase(it);
> return;
> }
> }
> };
> ~CCLL(){};
> };
>
>
> int main()
> {
> map_[3] = new CCLL(3);
> map_[5] = new CCLL(5);
> map_[7] = new CCLL(7);
> map_[1] = new CCLL(5);
> for(map<int, CCLL*>::iterator it=map_.begin();it!=map_.end();it++)
> {
> if(it->second->getI()==5)
> continue;
> it->second->killI(it->second->getI());


At this point "it" is invalid. If you didn't reset it to a valid
iterator (such as begin()), your attempt to then increment "it" - which
is invalid - as part of the for loop would lead to undefined behavior.

> it=map_.begin();
> }
> for(map<int, CCLL*>::iterator it=map_.begin();it!=map_.end();it++)
> {
> cout<<it->first<<"...."<<it->second->getI()<<endl;
> }
> }


Best regards,

Tom


Alien 09-20-2006 08:42 PM

Re: removing elements invalidates only those iterators that had specifically pointed at the removed elements
 

Thomas Tutone wrote:
> Alien wrote:
>
>
> > According to MSDN, removing elements invalidates only those iterators
> > that had specifically pointed at the removed elements.

>
> That's true with respect to maps, if you are referring to the
> map::erase member function. It is not necessarily true for other
> standard containers.
>
> >
> > But I tried following codes, and find that without the repeated
> > it=map_.begin();
> > there will be memory violation.
> > So, the iterator IS invalidated even if it's not the removed one.
> > why?

>
> Your question doesn't make sense. The iterator is invalidated when you
> remove it. After that it is invalid. You can't, for example,
> increment it, because it's invalid. And that iterator is the removed

^^^^^^^^^^^^^^^^^^^^^^^
I see. I cannot even increment it.
But can I record the previous it as oldIt, and oldIt++ after the erase?
> one.
>
> > -----------
> > #include <map>
> > #include <iostream>
> > using namespace std;
> >
> > class CCLL;
> > map<int, CCLL*> map_;
> >
> > class CCLL
> > {
> > int i_;
> > public:
> > CCLL(){i_=0;};
> > CCLL(int i){i_=i;};
> > int getI(){return i_;};
> > void killI(int i)
> > {
> > for(map<int, CCLL*>::iterator it=map_.begin();it!=map_.end();it++)
> > {
> > if(it->second->getI()==i)
> > {
> > map_.erase(it);
> > return;
> > }
> > }
> > };
> > ~CCLL(){};
> > };
> >
> >
> > int main()
> > {
> > map_[3] = new CCLL(3);
> > map_[5] = new CCLL(5);
> > map_[7] = new CCLL(7);
> > map_[1] = new CCLL(5);
> > for(map<int, CCLL*>::iterator it=map_.begin();it!=map_.end();it++)
> > {
> > if(it->second->getI()==5)
> > continue;
> > it->second->killI(it->second->getI());

>
> At this point "it" is invalid. If you didn't reset it to a valid
> iterator (such as begin()), your attempt to then increment "it" - which
> is invalid - as part of the for loop would lead to undefined behavior.
>
> > it=map_.begin();
> > }
> > for(map<int, CCLL*>::iterator it=map_.begin();it!=map_.end();it++)
> > {
> > cout<<it->first<<"...."<<it->second->getI()<<endl;
> > }
> > }

>
> Best regards,
>
> Tom



Alien 09-20-2006 09:03 PM

Re: removing elements invalidates only those iterators that had specifically pointed at the removed elements
 

Thomas Tutone wrote:
> Alien wrote:
>
>
> > According to MSDN, removing elements invalidates only those iterators
> > that had specifically pointed at the removed elements.

>
> That's true with respect to maps, if you are referring to the
> map::erase member function. It is not necessarily true for other
> standard containers.
>
> >
> > But I tried following codes, and find that without the repeated
> > it=map_.begin();
> > there will be memory violation.
> > So, the iterator IS invalidated even if it's not the removed one.
> > why?

>
> Your question doesn't make sense. The iterator is invalidated when you
> remove it. After that it is invalid. You can't, for example,
> increment it, because it's invalid. And that iterator is the removed
> one.
>
> > -----------
> > #include <map>
> > #include <iostream>
> > using namespace std;
> >
> > class CCLL;
> > map<int, CCLL*> map_;
> >
> > class CCLL
> > {
> > int i_;
> > public:
> > CCLL(){i_=0;};
> > CCLL(int i){i_=i;};
> > int getI(){return i_;};
> > void killI(int i)
> > {
> > for(map<int, CCLL*>::iterator it=map_.begin();it!=map_.end();it++)
> > {
> > if(it->second->getI()==i)
> > {
> > map_.erase(it);
> > return;
> > }
> > }
> > };
> > ~CCLL(){};
> > };
> >
> >
> > int main()
> > {
> > map_[3] = new CCLL(3);
> > map_[5] = new CCLL(5);
> > map_[7] = new CCLL(7);
> > map_[1] = new CCLL(5);
> > for(map<int, CCLL*>::iterator it=map_.begin();it!=map_.end();it++)
> > {
> > if(it->second->getI()==5)
> > continue;
> > it->second->killI(it->second->getI());

>
> At this point "it" is invalid. If you didn't reset it to a valid
> iterator (such as begin()), your attempt to then increment "it" - which
> is invalid - as part of the for loop would lead to undefined behavior.
>
> > it=map_.begin();
> > }
> > for(map<int, CCLL*>::iterator it=map_.begin();it!=map_.end();it++)
> > {
> > cout<<it->first<<"...."<<it->second->getI()<<endl;
> > }
> > }

>
> Best regards,
>
> Tom


Is there any simple way that I can avoid calling the repeated
it=map_.begin()?
You know it's not effective because I have to go from the beginning
again and again.
Assume that our modifications are limited in main function.
Thanks.


Thomas Tutone 09-20-2006 09:13 PM

Re: removing elements invalidates only those iterators that had specifically pointed at the removed elements
 
Alien wrote:


> Thomas Tutone wrote:
> > Alien wrote:
> >
> >
> > > According to MSDN, removing elements invalidates only those iterators
> > > that had specifically pointed at the removed elements.

> >
> > That's true with respect to maps, if you are referring to the
> > map::erase member function. It is not necessarily true for other
> > standard containers.
> >
> > >
> > > But I tried following codes, and find that without the repeated
> > > it=map_.begin();
> > > there will be memory violation.
> > > So, the iterator IS invalidated even if it's not the removed one.
> > > why?

> >
> > Your question doesn't make sense. The iterator is invalidated when you
> > remove it. After that it is invalid. You can't, for example,
> > increment it, because it's invalid. And that iterator is the removed

> ^^^^^^^^^^^^^^^^^^^^^^^
> I see. I cannot even increment it.
> But can I record the previous it as oldIt, and oldIt++ after the erase?
> > one.


Yes, _if_ oldIt is still a valid iterator (i.e., you didn't remove it
as well).

Best regards,

Tom


Thomas Tutone 09-20-2006 09:16 PM

Re: removing elements invalidates only those iterators that had specifically pointed at the removed elements
 

Thomas Tutone wrote:
> Alien wrote:
>
>
> > Thomas Tutone wrote:
> > > Alien wrote:
> > >
> > >
> > > > According to MSDN, removing elements invalidates only those iterators
> > > > that had specifically pointed at the removed elements.
> > >
> > > That's true with respect to maps, if you are referring to the
> > > map::erase member function. It is not necessarily true for other
> > > standard containers.
> > >
> > > >
> > > > But I tried following codes, and find that without the repeated
> > > > it=map_.begin();
> > > > there will be memory violation.
> > > > So, the iterator IS invalidated even if it's not the removed one.
> > > > why?
> > >
> > > Your question doesn't make sense. The iterator is invalidated when you
> > > remove it. After that it is invalid. You can't, for example,
> > > increment it, because it's invalid. And that iterator is the removed

> > ^^^^^^^^^^^^^^^^^^^^^^^
> > I see. I cannot even increment it.
> > But can I record the previous it as oldIt, and oldIt++ after the erase?
> > > one.

>
> Yes, _if_ oldIt is still a valid iterator (i.e., you didn't remove it
> as well).


BTW, please get in the habit of using ++it rather than it++ - the
latter may create and then destroy a temporary for no good reason, and
map iterators are not as lightweight as say, pointers, where it doesn't
really matter.

Best regards,

Tom
>
> Best regards,
>
> Tom



lhyatt@gmail.com 09-21-2006 03:13 PM

Re: removing elements invalidates only those iterators that had specifically pointed at the removed elements
 

> Is there any simple way that I can avoid calling the repeated
> it=map_.begin()?
> You know it's not effective because I have to go from the beginning
> again and again.
> Assume that our modifications are limited in main function.
> Thanks.


Here is the standard idiom for a loop which needs to delete iterators,
when the deletion only invalidates the iterator being deleted:

Iterator i = begin(); //whatever container.begin() you need
Iterator const end = end(); //etc
while (i != end) {
if(whatever) erase(i++);
else ++i;
}

it's safe to do erase(i++) because the iterator is incremented while it
is valid, then its old value is passed to erase, which deletes and
invalidates it.

if you want to erase the place an iterator is pointing, then you can't
auto-increment the iterator like in your for loop.



All times are GMT. The time now is 12:43 PM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.