vector.erase(iterator iter) will change "iter" or not?

Discussion in 'C++' started by thomas, Feb 21, 2008.

  1. thomas

    thomas Guest

    suppose I will delete an element pointed to by "iter".
    like this:

    vector<int> s;
    for(vector<int>::iterator iter=s.begin(); iter!=s.end(); iter++){
    if(*iter==3)
    s.erase(iter); //A
    }

    in line A, if element by "iter" is erased, will "iter" point to the
    next element(now should be the current element) automatically?
    thomas, Feb 21, 2008
    #1
    1. Advertising

  2. thomas wrote:
    > suppose I will delete an element pointed to by "iter".
    > like this:
    >
    > vector<int> s;
    > for(vector<int>::iterator iter=s.begin(); iter!=s.end(); iter++){
    > if(*iter==3)
    > s.erase(iter); //A
    > }
    >
    > in line A, if element by "iter" is erased, will "iter" point to the
    > next element(now should be the current element) automatically?


    The iterator that refers to the removed element and all elements
    after the removed one are invalidated by that operation. IOW, the
    Standard makes no attempt to define what the 'iter' would point to
    after being erased.

    V
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
    Victor Bazarov, Feb 21, 2008
    #2
    1. Advertising

  3. On Thu, 21 Feb 2008 15:16:11 +0100, thomas <> wrote:

    > suppose I will delete an element pointed to by "iter".
    > like this:
    >
    > vector<int> s;
    > for(vector<int>::iterator iter=s.begin(); iter!=s.end(); iter++){
    > if(*iter==3)
    > s.erase(iter); //A
    > }
    >
    > in line A, if element by "iter" is erased, will "iter" point to the
    > next element(now should be the current element) automatically?


    Do :

    vector<int> s;
    for(vector<int>::iterator iter=s.begin(); iter!=s.end(); iter++){
    if(*iter==3)
    iter= s.erase(iter);
    }
    David Côme, Feb 21, 2008
    #3
  4. In message <fpk2sg$5du$>, Victor Bazarov
    <> writes
    >thomas wrote:
    >> suppose I will delete an element pointed to by "iter".
    >> like this:
    >>
    >> vector<int> s;
    >> for(vector<int>::iterator iter=s.begin(); iter!=s.end(); iter++){
    >> if(*iter==3)
    >> s.erase(iter); //A
    >> }
    >>
    >> in line A, if element by "iter" is erased, will "iter" point to the
    >> next element(now should be the current element) automatically?

    >
    >The iterator that refers to the removed element and all elements
    >after the removed one are invalidated by that operation. IOW, the
    >Standard makes no attempt to define what the 'iter' would point to
    >after being erased.


    I wonder if the OP is confused because the iterator is passed by value
    and therefore not modified? Obviously erase(iter) can't change its
    _value_, but it certainly changes its _meaning_ - what it points to is
    no longer valid.

    (And the higher-level answer to his question is that he should probably
    be using std::remove anyway:

    s.erase(remove(s.begin(), s.end(), 3), s.end());

    )
    --
    Richard Herring
    Richard Herring, Feb 21, 2008
    #4
  5. thomas

    thomas Guest


    > (And the higher-level answer to his question is that he should probably
    > be using std::remove anyway:
    >
    > s.erase(remove(s.begin(), s.end(), 3), s.end());
    >


    What's this?
    will "s.erase()" get all the elements after "3" removed?
    thomas, Feb 21, 2008
    #5
  6. thomas

    Eric Pruneau Guest

    "thomas" <> a écrit dans le message de news:
    ...
    >
    >> (And the higher-level answer to his question is that he should probably
    >> be using std::remove anyway:
    >>
    >> s.erase(remove(s.begin(), s.end(), 3), s.end());
    >>

    >
    > What's this?
    > will "s.erase()" get all the elements after "3" removed?


    remove will remove all element equal to 3. beware, removing is not
    erasing... Remove returns an iterator to the new end of the sequence s (it
    does not actually modify s.end() ) , so you can use this iterator in the
    vector::erase function. The size of the vector is not modified after a
    remove, but the element between the returned end and the actual s.end() but
    the element are unspecified.

    so you can do

    vector<int>::iterator NewEnd = remove(s.begin(), s.end(), 3);
    s.erase(NewEnd, s.end);


    Eric Pruneau
    Eric Pruneau, Feb 21, 2008
    #6
  7. In message
    <>,
    thomas <> writes
    >
    >> (And the higher-level answer to his question is that he should probably
    >> be using std::remove anyway:
    >>
    >> s.erase(remove(s.begin(), s.end(), 3), s.end());

    >
    >What's this?


    It's a C++ STL idiom.

    >will "s.erase()" get all the elements after "3" removed?


    No. It erases everything in the range defined by the _two_ iterators
    being passed to it. And remove() copies the non-3 elements down to the
    beginning of s, returning an iterator to the first element beyond them.

    If you don't know this stuff, you'd do better to read a good book than
    ask random questions here.

    --
    Richard Herring
    Richard Herring, Feb 21, 2008
    #7
  8. thomas

    Martin York Guest

    Just a small correction.

    > vector<int> s;
    > for(vector<int>::iterator iter=s.begin(); iter!=s.end(); iter++){
    > if(*iter==3)
    > iter= s.erase(iter);
    > }


    After the erase() call iter points at the next element in the
    container. Thus when the iter++ is called you will effectively skip
    an element or if the erased element is the last element it now points
    one after end().

    Also for efficiency it is a god idea to get in the habit of using
    prefix increment (In this case it probably makes no difference but
    for the generic case it does).
    Martin York, Feb 21, 2008
    #8
  9. thomas

    Old Wolf Guest

    On Feb 22, 4:31 am, Richard Herring <junk@[127.0.0.1]> wrote:
    > In message <fpk2sg$>, Victor Bazarov
    > >The iterator that refers to the removed element and all elements
    > >after the removed one are invalidated by that operation. IOW, the
    > >Standard makes no attempt to define what the 'iter' would point to
    > >after being erased.

    >
    > I wonder if the OP is confused because the iterator is passed by value
    > and therefore not modified? Obviously erase(iter) can't change its
    > _value_, but it certainly changes its _meaning_ - what it points to is
    > no longer valid.


    The value certainly is changed: previously it was
    well-defined and now it is indeterminate! It doesn't
    point anywhere; it's nonsensical to say that what
    it points to is not valid. Perhaps you mean to say
    that the representation isn't changed;
    Old Wolf, Feb 22, 2008
    #9
  10. thomas

    Triple-DES Guest

    On 22 Feb, 08:31, Old Wolf <> wrote:
    > On Feb 22, 4:31 am, Richard Herring <junk@[127.0.0.1]> wrote:
    >
    > > In message <fpk2sg$>, Victor Bazarov
    > > >The iterator that refers to the removed element and all elements
    > > >after the removed one are invalidated by that operation.  IOW, the
    > > >Standard makes no attempt to define what the 'iter' would point to
    > > >after being erased.

    >
    > > I wonder if the OP is confused because the iterator is passed by value
    > > and therefore not modified? Obviously erase(iter) can't change its
    > > _value_, but it certainly changes its _meaning_ - what it points to is
    > > no longer valid.

    >
    > The value certainly is changed: previously it was
    > well-defined and now it is indeterminate! It doesn't
    > point anywhere; it's nonsensical to say that what
    > it points to is not valid.  Perhaps you mean to say
    > that the representation isn't changed;


    That's an interesting point. Consider:
    int * p = new int(441);
    delete p;

    Would you say that the last line changes the value of p?

    DP
    Triple-DES, Feb 22, 2008
    #10
  11. In message
    <>, Old
    Wolf <> writes
    >On Feb 22, 4:31 am, Richard Herring <junk@[127.0.0.1]> wrote:
    >> In message <fpk2sg$>, Victor Bazarov
    >> >The iterator that refers to the removed element and all elements
    >> >after the removed one are invalidated by that operation. IOW, the
    >> >Standard makes no attempt to define what the 'iter' would point to
    >> >after being erased.

    >>
    >> I wonder if the OP is confused because the iterator is passed by value
    >> and therefore not modified? Obviously erase(iter) can't change its
    >> _value_, but it certainly changes its _meaning_ - what it points to is
    >> no longer valid.

    >
    >The value certainly is changed: previously it was
    >well-defined and now it is indeterminate!


    Its value has become singular, certainly, but that's because the set of
    singular values has changed, not because the iterator has.

    > It doesn't
    >point anywhere; it's nonsensical to say that what
    >it points to is not valid.


    If it doesn't point anywhere, it points nowhere. "nowhere" looks pretty
    invalid to me.

    > Perhaps you mean to say
    >that the representation isn't changed;


    Perhaps.

    --
    Richard Herring
    Richard Herring, Feb 22, 2008
    #11
  12. thomas

    Old Wolf Guest

    On Feb 22, 11:54 pm, Richard Herring <junk@[127.0.0.1]> wrote:
    > If it doesn't point anywhere, it points nowhere. "nowhere" looks pretty
    > invalid to me.


    Non-sequitur ; there are three possible states for
    pointers (or iterators): pointing to a valid object,
    null, or indeterminate. By 'anywhere' I do not
    include the indeterminate case.
    Old Wolf, Feb 22, 2008
    #12
  13. thomas

    Old Wolf Guest

    On Feb 22, 8:47 pm, Triple-DES <> wrote:
    > That's an interesting point. Consider:
    > int * p = new int(441);
    > delete p;
    >
    > Would you say that the last line changes the value of p?


    Yes
    Old Wolf, Feb 22, 2008
    #13
  14. In message
    <>, Old
    Wolf <> writes
    >On Feb 22, 11:54 pm, Richard Herring <junk@[127.0.0.1]> wrote:


    [big snip noted]

    >> If it doesn't point anywhere, it points nowhere. "nowhere" looks pretty
    >> invalid to me.

    >
    >Non-sequitur ; there are three possible states for
    >pointers (or iterators): pointing to a valid object,
    >null, or indeterminate.


    The standard refers to this state as "[having] singular values".

    >By 'anywhere' I do not
    >include the indeterminate case.


    But you obviously meant "not anywhere" to include singular states when
    you wrote this:

    >>> previously it was well-defined and now it is indeterminate! It
    >>>doesn't point anywhere;


    --
    Richard Herring
    Richard Herring, Feb 22, 2008
    #14
  15. thomas

    Old Wolf Guest

    On Feb 23, 2:38 am, Richard Herring <junk@[127.0.0.1]> wrote:
    > But you obviously meant "not anywhere" to include singular states when
    > you wrote this:
    >
    > >>> previously it was well-defined and now it is indeterminate! It
    > >>>doesn't point anywhere;


    Actually I didn't. I'll try to use more precise
    terms than "anywhere" in future.
    Old Wolf, Feb 22, 2008
    #15
  16. thomas

    James Kanze Guest

    On Feb 22, 8:31 am, Old Wolf <> wrote:
    > On Feb 22, 4:31 am, Richard Herring <junk@[127.0.0.1]> wrote:


    > > In message <fpk2sg$>, Victor Bazarov
    > > >The iterator that refers to the removed element and all elements
    > > >after the removed one are invalidated by that operation. IOW, the
    > > >Standard makes no attempt to define what the 'iter' would point to
    > > >after being erased.


    > > I wonder if the OP is confused because the iterator is
    > > passed by value and therefore not modified? Obviously
    > > erase(iter) can't change its _value_, but it certainly
    > > changes its _meaning_ - what it points to is no longer
    > > valid.


    > The value certainly is changed: previously it was
    > well-defined and now it is indeterminate!


    I'm not sure whether you can use the word "changed" here or
    not. After the erase, iter has no value. At least, not one you
    can legally access.

    > It doesn't point anywhere; it's nonsensical to say that what
    > it points to is not valid. Perhaps you mean to say that the
    > representation isn't changed;


    Not with the implementation I use After the erase, the only way
    you could look at the representation is by means of a memcpy,
    and if you do:

    unsigned char before[ sizeof( std::vector<int>::iterator ] ;
    memcpy( before, &iter, sizeof( std::vector<int>::iterator ) ) ;
    v.erase( iter ) ;
    memcmp( before, &iter, sizeof( std::vector<int>::iterator ) ) ;

    the memcmp will return a value not equal to 0.

    And trying to use the iterator will cause a core dump. (To be
    very, very clear:

    #include <vector>

    int
    main()
    {
    static int const init[] = { 1, 2, 3, 4, 5 } ;
    std::vector< int > v( init, init + 5 ) ;
    std::vector< int >::iterator
    iter = v.begin() + 3 ;
    v.erase( iter ) ;
    std::vector< int >::iterator
    i2 = iter ;
    }

    core dumps on the last line in main. You cannot read an invalid
    iterator other than as an array of bytes.)

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
    James Kanze, Feb 22, 2008
    #16
  17. thomas

    James Kanze Guest

    On Feb 22, 11:54 am, Richard Herring <junk@[127.0.0.1]> wrote:
    > In message
    > <>, Old
    > Wolf <> writes


    > >On Feb 22, 4:31 am, Richard Herring <junk@[127.0.0.1]> wrote:
    > >> In message <fpk2sg$>, Victor Bazarov
    > >> >The iterator that refers to the removed element and all
    > >> >elements after the removed one are invalidated by that
    > >> >operation. IOW, the Standard makes no attempt to define
    > >> >what the 'iter' would point to after being erased.


    > >> I wonder if the OP is confused because the iterator is
    > >> passed by value and therefore not modified? Obviously
    > >> erase(iter) can't change its _value_, but it certainly
    > >> changes its _meaning_ - what it points to is no longer
    > >> valid.


    > >The value certainly is changed: previously it was
    > >well-defined and now it is indeterminate!


    > Its value has become singular, certainly, but that's because
    > the set of singular values has changed, not because the
    > iterator has.


    > >It doesn't point anywhere; it's nonsensical to say that what
    > >it points to is not valid.


    > If it doesn't point anywhere, it points nowhere. "nowhere"
    > looks pretty invalid to me.


    It doesn't point, period.

    > > Perhaps you mean to say that the representation isn't
    > > changed;


    > Perhaps.


    Consider:

    #include <vector>
    #include <cstring>
    #include <iostream>

    int
    main()
    {
    static int const init[] = { 1, 2, 3, 4, 5 } ;
    std::vector< int > v( init, init + 5 ) ;
    std::vector< int >::iterator
    iter = v.begin() + 3 ;
    unsigned char before[ sizeof( iter ) ] ;
    std::memcpy( before, &iter, sizeof( iter ) ) ;
    v.erase( iter ) ;
    if ( std::memcmp( before, &iter, sizeof( iter ) ) == 0 ) {
    std::cout << "unchanged" << std::endl ;
    } else {
    std::cout << "changed" << std::endl ;
    }
    }

    On my implementation, this outputs "changed". And any attempt
    to access iter as an std::vector< int >::iterator (e.g. to copy
    it, compare it, etc.) generates a core dump.

    I don't quite know what you mean by "its representation". If
    it's just the underlying bits in memory, then it's changed. If
    it's anything else, then you can't tell, because there's nothing
    you can do other than look at the bytes that has defined
    behavior (and the implementation I normally use core dumps in
    all of the cases of undefined behavior).

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
    James Kanze, Feb 22, 2008
    #17
  18. thomas

    James Kanze Guest

    On Feb 21, 6:45 pm, Martin York <> wrote:

    [...]
    > Also for efficiency it is a god idea to get in the habit of
    > using prefix increment (In this case it probably makes no
    > difference but for the generic case it does).


    Measurements? Or is this just speculation on your part. (I've
    actually measured with g++, and all of the standard iterators.
    No measurable difference.)

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
    James Kanze, Feb 22, 2008
    #18
  19. thomas

    Old Wolf Guest

    On Feb 23, 6:40 am, James Kanze <> wrote:
    > unsigned char before[ sizeof( std::vector<int>::iterator ] ;
    > memcpy( before, &iter, sizeof( std::vector<int>::iterator ) ) ;
    > v.erase( iter ) ;
    > memcmp( before, &iter, sizeof( std::vector<int>::iterator ) ) ;
    >
    > the memcmp will return a value not equal to 0.


    How does that work? I agree that it's legal, but I wouldn't
    expect it anywhere except the DS9000; it seems that the
    implementation, when faced with vector::erase, would have
    to go out of its way to go and change bits in the original
    'iter' that the parameter to vector::erase was copied from.

    > And trying to use the iterator will cause a core dump.


    To be expected when using indeterminate 'values'.
    Old Wolf, Feb 23, 2008
    #19
  20. thomas

    James Kanze Guest

    Old Wolf wrote:
    > On Feb 23, 6:40 am, James Kanze <> wrote:
    > > unsigned char before[ sizeof( std::vector<int>::iterator ] ;
    > > memcpy( before, &iter, sizeof( std::vector<int>::iterator ) ) ;
    > > v.erase( iter ) ;
    > > memcmp( before, &iter, sizeof( std::vector<int>::iterator ) ) ;


    > > the memcmp will return a value not equal to 0.


    > How does that work?


    About how you'd expect. The container knows about the iterators
    which refer to it, and marks them as invalid whenever it
    invalidates them.

    > I agree that it's legal, but I wouldn't expect it anywhere
    > except the DS9000; it seems that the implementation, when
    > faced with vector::erase, would have to go out of its way to
    > go and change bits in the original 'iter' that the parameter
    > to vector::erase was copied from.


    I'm not sure what you mean by "go out of its way". Every
    pre-standard iterator I ever wrote did this. Logically, the
    iterator knows about the container, and vice versa.

    > > And trying to use the iterator will cause a core dump.


    > To be expected when using indeterminate 'values'.


    Huh? On my system, I don't get a core dump just because I copy
    an invalid pointer (say, after a delete). I do if I copy an
    invalid iterator, however. (If, after the erase above, I assign
    iter to some other iterator, I get a core dump, with a message
    that I've used an invalid iterator.)

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
    James Kanze, Feb 23, 2008
    #20
    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. Replies:
    8
    Views:
    1,915
    Csaba
    Feb 18, 2006
  2. erase vs. erase

    , Mar 25, 2006, in forum: C++
    Replies:
    7
    Views:
    363
    Pete Becker
    Mar 30, 2006
  3. Anil
    Replies:
    5
    Views:
    438
    Jim Langston
    Dec 18, 2007
  4. , India
    Replies:
    3
    Views:
    339
    James Kanze
    May 2, 2008
  5. Gennaro Prota
    Replies:
    1
    Views:
    339
    Gennaro Prota
    Aug 21, 2008
Loading...

Share This Page