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

Discussion in 'C++' started by Alien, Sep 20, 2006.

  1. Alien

    Alien Guest

    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;
    }
    }
    Alien, Sep 20, 2006
    #1
    1. Advertising

  2. 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
    Thomas Tutone, Sep 20, 2006
    #2
    1. Advertising

  3. Alien

    Alien Guest

    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, Sep 20, 2006
    #3
  4. Alien

    Alien Guest

    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.
    Alien, Sep 20, 2006
    #4
  5. 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, Sep 20, 2006
    #5
  6. 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
    Thomas Tutone, Sep 20, 2006
    #6
  7. Alien

    Guest

    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.
    , Sep 21, 2006
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Eqbal
    Replies:
    0
    Views:
    285
    Eqbal
    Sep 15, 2004
  2. BinnuChowdary
    Replies:
    1
    Views:
    520
    Swanand Mokashi
    May 1, 2006
  3. BinnuChowdary
    Replies:
    0
    Views:
    401
    BinnuChowdary
    May 2, 2006
  4. BinnuChowdary
    Replies:
    1
    Views:
    534
    =?UTF-8?B?R8O2cmFuIEFuZGVyc3Nvbg==?=
    May 2, 2006
  5. Fayland Lam
    Replies:
    2
    Views:
    66
    Fayland Lam
    Dec 25, 2007
Loading...

Share This Page