list::begin() iterator comportement after push_back operations

Discussion in 'C++' started by Hizo, Apr 2, 2011.

  1. Hizo

    Hizo Guest

    Hi there,

    I have a problem with the begin iterator of STL Lists.
    Indeed, if we keep the begin iterator of an empty list when we test it
    after multiple push_back operations it becomes the end iterator.
    Here is my code:

    -------------------------------------------
    #include <iostream>
    using std::cout;
    using std::endl;
    using std::boolalpha;

    #include <list>
    using std::list;

    int main(int argc, char * argv[])
    {
    list<int> l;
    list<int>::const_iterator it = l.begin();
    list<int>::const_reverse_iterator rit = l.rbegin();

    l.push_back(1);
    l.push_back(2);

    cout << boolalpha << (it == l.end()) << endl;
    cout << boolalpha << (rit == l.rend()) << endl;

    return 0;
    }
    -------------------------------------------

    It actually returns:
    true
    false

    with gcc version 4.3.4 (Gentoo 4.3.4 p1.0, pie-10.1.5)

    Is it possible to keep in memory the begin iterator of a list (not
    using reverse iterators) which will really point to the begin of the
    list after push_back operations on the list (obviously I am not able
    to use l.begin() after (because it is an initial state in my algorithm
    and I then update the iterator that pointed to the begin iterator
    initialy))

    Thanks for your help.
    Hizo, Apr 2, 2011
    #1
    1. Advertising

  2. Hizo

    Bo Persson Guest

    Hizo wrote:
    > Hi there,
    >
    > I have a problem with the begin iterator of STL Lists.
    > Indeed, if we keep the begin iterator of an empty list when we test
    > it after multiple push_back operations it becomes the end iterator.
    > Here is my code:
    >
    > -------------------------------------------
    > #include <iostream>
    > using std::cout;
    > using std::endl;
    > using std::boolalpha;
    >
    > #include <list>
    > using std::list;
    >
    > int main(int argc, char * argv[])
    > {
    > list<int> l;
    > list<int>::const_iterator it = l.begin();
    > list<int>::const_reverse_iterator rit = l.rbegin();
    >
    > l.push_back(1);
    > l.push_back(2);
    >
    > cout << boolalpha << (it == l.end()) << endl;
    > cout << boolalpha << (rit == l.rend()) << endl;
    >
    > return 0;
    > }
    > -------------------------------------------
    >
    > It actually returns:
    > true
    > false
    >
    > with gcc version 4.3.4 (Gentoo 4.3.4 p1.0, pie-10.1.5)
    >
    > Is it possible to keep in memory the begin iterator of a list (not
    > using reverse iterators) which will really point to the begin of the
    > list after push_back operations on the list (obviously I am not able
    > to use l.begin() after (because it is an initial state in my
    > algorithm and I then update the iterator that pointed to the begin
    > iterator initialy))
    >
    > Thanks for your help.


    Short answer: No.

    All containers start out with c.begin() == c.end(), as that is one way
    of seeing that the container is empty.

    When you add elements to the container, some or all iterators will be
    invalidated. A little different for each container type, but
    definitely the begin() iterator will change when you add an element to
    the start of the container (which of course happens when you add to an
    empty container).

    Reverse iterators will not help either, as they will be equally
    invalidated.


    Bo Persson
    Bo Persson, Apr 2, 2011
    #2
    1. Advertising

  3. Hizo

    Hizo Guest

    On 2 avr, 13:57, "Bo Persson" <> wrote:
    > Hizo wrote:
    > > Hi there,

    >
    > > I have a problem with the begin iterator of STL Lists.
    > > Indeed, if we keep the begin iterator of an empty list when we test
    > > it after multiple push_back operations it becomes the end iterator.
    > > Here is my code:

    >
    > > -------------------------------------------
    > > #include <iostream>
    > > using std::cout;
    > > using std::endl;
    > > using std::boolalpha;

    >
    > > #include <list>
    > > using std::list;

    >
    > > int main(int argc, char * argv[])
    > > {
    > > list<int> l;
    > > list<int>::const_iterator it = l.begin();
    > > list<int>::const_reverse_iterator rit = l.rbegin();

    >
    > > l.push_back(1);
    > > l.push_back(2);

    >
    > > cout << boolalpha << (it == l.end()) << endl;
    > > cout << boolalpha << (rit == l.rend()) << endl;

    >
    > > return 0;
    > > }
    > > -------------------------------------------

    >
    > > It actually returns:
    > > true
    > > false

    >
    > > with gcc version 4.3.4 (Gentoo 4.3.4 p1.0, pie-10.1.5)

    >
    > > Is it possible to keep in memory the begin iterator of a list (not
    > > using reverse iterators) which will really point to the begin of the
    > > list after push_back operations on the list (obviously I am not able
    > > to use l.begin() after (because it is an initial state in my
    > > algorithm and I then update the iterator that pointed to the begin
    > > iterator initialy))

    >
    > > Thanks for your help.

    >
    > Short answer: No.
    >
    > All containers start out with c.begin() == c.end(), as that is one way
    > of seeing that the container is empty.
    >
    > When you add elements to the container, some or all iterators will be
    > invalidated. A little different for each container type, but
    > definitely the begin() iterator will change when you add an element to
    > the start of the container (which of course happens when you add to an
    > empty container).
    >
    > Reverse iterators will not help either, as they will be equally
    > invalidated.
    >
    > Bo Persson


    Alright...
    But I thought that in lists, it should not be the case since iterators
    are not invalidated when adding elements.

    And the reverse iterator seems not to be invalidated here ? (cf result
    of my code)
    But I could not use them anyway...

    Thanks.
    Hizo, Apr 2, 2011
    #3
  4. Hizo

    Hizo Guest

    On 2 avr, 13:57, "Bo Persson" <> wrote:
    > Hizo wrote:
    > > Hi there,

    >
    > > I have a problem with the begin iterator of STL Lists.
    > > Indeed, if we keep the begin iterator of an empty list when we test
    > > it after multiple push_back operations it becomes the end iterator.
    > > Here is my code:

    >
    > > -------------------------------------------
    > > #include <iostream>
    > > using std::cout;
    > > using std::endl;
    > > using std::boolalpha;

    >
    > > #include <list>
    > > using std::list;

    >
    > > int main(int argc, char * argv[])
    > > {
    > > list<int> l;
    > > list<int>::const_iterator it = l.begin();
    > > list<int>::const_reverse_iterator rit = l.rbegin();

    >
    > > l.push_back(1);
    > > l.push_back(2);

    >
    > > cout << boolalpha << (it == l.end()) << endl;
    > > cout << boolalpha << (rit == l.rend()) << endl;

    >
    > > return 0;
    > > }
    > > -------------------------------------------

    >
    > > It actually returns:
    > > true
    > > false

    >
    > > with gcc version 4.3.4 (Gentoo 4.3.4 p1.0, pie-10.1.5)

    >
    > > Is it possible to keep in memory the begin iterator of a list (not
    > > using reverse iterators) which will really point to the begin of the
    > > list after push_back operations on the list (obviously I am not able
    > > to use l.begin() after (because it is an initial state in my
    > > algorithm and I then update the iterator that pointed to the begin
    > > iterator initialy))

    >
    > > Thanks for your help.

    >
    > Short answer: No.
    >
    > All containers start out with c.begin() == c.end(), as that is one way
    > of seeing that the container is empty.
    >
    > When you add elements to the container, some or all iterators will be
    > invalidated. A little different for each container type, but
    > definitely the begin() iterator will change when you add an element to
    > the start of the container (which of course happens when you add to an
    > empty container).
    >
    > Reverse iterators will not help either, as they will be equally
    > invalidated.
    >
    > Bo Persson


    Alright...
    But I thought that in lists, it should not be the case since iterators
    are not invalidated when adding elements.

    And the reverse iterator seems not to be invalidated here ? (cf result
    of my code and dereferencing it give the expected result)
    But I could not use them anyway...

    Thanks.
    Hizo, Apr 2, 2011
    #4
  5. Hizo

    Hizo Guest

    On 2 avr, 13:57, "Bo Persson" <> wrote:
    > Hizo wrote:
    > > Hi there,

    >
    > > I have a problem with the begin iterator of STL Lists.
    > > Indeed, if we keep the begin iterator of an empty list when we test
    > > it after multiple push_back operations it becomes the end iterator.
    > > Here is my code:

    >
    > > -------------------------------------------
    > > #include <iostream>
    > > using std::cout;
    > > using std::endl;
    > > using std::boolalpha;

    >
    > > #include <list>
    > > using std::list;

    >
    > > int main(int argc, char * argv[])
    > > {
    > > list<int> l;
    > > list<int>::const_iterator it = l.begin();
    > > list<int>::const_reverse_iterator rit = l.rbegin();

    >
    > > l.push_back(1);
    > > l.push_back(2);

    >
    > > cout << boolalpha << (it == l.end()) << endl;
    > > cout << boolalpha << (rit == l.rend()) << endl;

    >
    > > return 0;
    > > }
    > > -------------------------------------------

    >
    > > It actually returns:
    > > true
    > > false

    >
    > > with gcc version 4.3.4 (Gentoo 4.3.4 p1.0, pie-10.1.5)

    >
    > > Is it possible to keep in memory the begin iterator of a list (not
    > > using reverse iterators) which will really point to the begin of the
    > > list after push_back operations on the list (obviously I am not able
    > > to use l.begin() after (because it is an initial state in my
    > > algorithm and I then update the iterator that pointed to the begin
    > > iterator initialy))

    >
    > > Thanks for your help.

    >
    > Short answer: No.
    >
    > All containers start out with c.begin() == c.end(), as that is one way
    > of seeing that the container is empty.
    >
    > When you add elements to the container, some or all iterators will be
    > invalidated. A little different for each container type, but
    > definitely the begin() iterator will change when you add an element to
    > the start of the container (which of course happens when you add to an
    > empty container).
    >
    > Reverse iterators will not help either, as they will be equally
    > invalidated.
    >
    > Bo Persson


    Alright...
    I thought that in lists, it should not be the case since iterators
    are not invalidated when adding elements.

    Anyway, thanks.
    Hizo, Apr 2, 2011
    #5
  6. Hizo

    Hizo Guest

    On 2 avr, 13:57, "Bo Persson" <> wrote:
    > Hizo wrote:
    > > Hi there,

    >
    > > I have a problem with the begin iterator of STL Lists.
    > > Indeed, if we keep the begin iterator of an empty list when we test
    > > it after multiple push_back operations it becomes the end iterator.
    > > Here is my code:

    >
    > > -------------------------------------------
    > > #include <iostream>
    > > using std::cout;
    > > using std::endl;
    > > using std::boolalpha;

    >
    > > #include <list>
    > > using std::list;

    >
    > > int main(int argc, char * argv[])
    > > {
    > > list<int> l;
    > > list<int>::const_iterator it = l.begin();
    > > list<int>::const_reverse_iterator rit = l.rbegin();

    >
    > > l.push_back(1);
    > > l.push_back(2);

    >
    > > cout << boolalpha << (it == l.end()) << endl;
    > > cout << boolalpha << (rit == l.rend()) << endl;

    >
    > > return 0;
    > > }
    > > -------------------------------------------

    >
    > > It actually returns:
    > > true
    > > false

    >
    > > with gcc version 4.3.4 (Gentoo 4.3.4 p1.0, pie-10.1.5)

    >
    > > Is it possible to keep in memory the begin iterator of a list (not
    > > using reverse iterators) which will really point to the begin of the
    > > list after push_back operations on the list (obviously I am not able
    > > to use l.begin() after (because it is an initial state in my
    > > algorithm and I then update the iterator that pointed to the begin
    > > iterator initialy))

    >
    > > Thanks for your help.

    >
    > Short answer: No.
    >
    > All containers start out with c.begin() == c.end(), as that is one way
    > of seeing that the container is empty.
    >
    > When you add elements to the container, some or all iterators will be
    > invalidated. A little different for each container type, but
    > definitely the begin() iterator will change when you add an element to
    > the start of the container (which of course happens when you add to an
    > empty container).
    >
    > Reverse iterators will not help either, as they will be equally
    > invalidated.
    >
    > Bo Persson


    Alright...
    I thought that in lists, it should not be the case since iterators
    are not invalidated when adding elements.

    I tried this:

    -------------------------------------------
    #include <iostream>
    using std::cout;
    using std::endl;
    using std::boolalpha;

    #include <list>
    using std::list;

    int main(int argc, char * argv[])
    {
    list<int> l;
    l.push_back(0);

    list<int>::const_iterator it = l.begin();
    l.pop_back();

    l.push_back(1);
    l.push_back(2);

    cout << *it << endl;

    cout << boolalpha << (it == l.end()) << endl;

    return 0;
    }
    -------------------------------------------

    The result (with gcc version 4.3.4 (Gentoo 4.3.4 p1.0, pie-10.1.5))
    is:
    1
    false

    (i.e. the expected result)

    But is it a standard comportement in the STL ?
    Can I really rely on this example ?

    Thanks
    Hizo, Apr 2, 2011
    #6
  7. Hizo

    Bo Persson Guest

    Hizo wrote:
    > On 2 avr, 13:57, "Bo Persson" <> wrote:
    >> Hizo wrote:
    >>> Hi there,

    >>
    >>> I have a problem with the begin iterator of STL Lists.
    >>> Indeed, if we keep the begin iterator of an empty list when we
    >>> test it after multiple push_back operations it becomes the end
    >>> iterator. Here is my code:

    >>
    >>> -------------------------------------------
    >>> #include <iostream>
    >>> using std::cout;
    >>> using std::endl;
    >>> using std::boolalpha;

    >>
    >>> #include <list>
    >>> using std::list;

    >>
    >>> int main(int argc, char * argv[])
    >>> {
    >>> list<int> l;
    >>> list<int>::const_iterator it = l.begin();
    >>> list<int>::const_reverse_iterator rit = l.rbegin();

    >>
    >>> l.push_back(1);
    >>> l.push_back(2);

    >>
    >>> cout << boolalpha << (it == l.end()) << endl;
    >>> cout << boolalpha << (rit == l.rend()) << endl;

    >>
    >>> return 0;
    >>> }
    >>> -------------------------------------------

    >>
    >>> It actually returns:
    >>> true
    >>> false

    >>
    >>> with gcc version 4.3.4 (Gentoo 4.3.4 p1.0, pie-10.1.5)

    >>
    >>> Is it possible to keep in memory the begin iterator of a list (not
    >>> using reverse iterators) which will really point to the begin of
    >>> the list after push_back operations on the list (obviously I am
    >>> not able to use l.begin() after (because it is an initial state
    >>> in my algorithm and I then update the iterator that pointed to
    >>> the begin iterator initialy))

    >>
    >>> Thanks for your help.

    >>
    >> Short answer: No.
    >>
    >> All containers start out with c.begin() == c.end(), as that is one
    >> way of seeing that the container is empty.
    >>
    >> When you add elements to the container, some or all iterators will
    >> be invalidated. A little different for each container type, but
    >> definitely the begin() iterator will change when you add an
    >> element to the start of the container (which of course happens
    >> when you add to an empty container).
    >>
    >> Reverse iterators will not help either, as they will be equally
    >> invalidated.
    >>
    >> Bo Persson

    >
    > Alright...
    > I thought that in lists, it should not be the case since iterators
    > are not invalidated when adding elements.
    >
    > I tried this:
    >
    > -------------------------------------------
    > #include <iostream>
    > using std::cout;
    > using std::endl;
    > using std::boolalpha;
    >
    > #include <list>
    > using std::list;
    >
    > int main(int argc, char * argv[])
    > {
    > list<int> l;
    > l.push_back(0);
    >
    > list<int>::const_iterator it = l.begin();
    > l.pop_back();
    >
    > l.push_back(1);
    > l.push_back(2);
    >
    > cout << *it << endl;
    >
    > cout << boolalpha << (it == l.end()) << endl;
    >
    > return 0;
    > }
    > -------------------------------------------
    >
    > The result (with gcc version 4.3.4 (Gentoo 4.3.4 p1.0, pie-10.1.5))
    > is:
    > 1
    > false
    >
    > (i.e. the expected result)
    >
    > But is it a standard comportement in the STL ?
    > Can I really rely on this example ?
    >
    > Thanks


    Dereferencing an invalid iterator is undefined behavior, so we can't
    test for it - anything could happen, like the list allocator reusing
    the deleted node for one of the new nodes.

    But we can't rely on that.


    Bo Persson
    Bo Persson, Apr 2, 2011
    #7
  8. Hizo

    James Kanze Guest

    On Apr 2, 1:32 pm, Hizo <> wrote:
    > On 2 avr, 13:57, "Bo Persson" <> wrote:


    [...]
    > I thought that in lists, it should not be the case since iterators
    > are not invalidated when adding elements.


    They aren't. When the list is empty, begin() returns the same
    iterator as end(), i.e. an iterator which points to one past the
    last element. Regardless of what you do after that, that
    iterator will point to one past the last element.

    > I tried this:


    > -------------------------------------------
    > #include <iostream>
    > using std::cout;
    > using std::endl;
    > using std::boolalpha;


    > #include <list>
    > using std::list;


    > int main(int argc, char * argv[])
    > {
    > list<int> l;
    > l.push_back(0);


    > list<int>::const_iterator it = l.begin();


    it points to the first element, i.e. the element with 0 in it.

    > l.pop_back();


    This invaliates it, since it removes the element it points to.

    > l.push_back(1);
    > l.push_back(2);


    > cout << *it << endl;


    And this is undefined behavior.

    > cout << boolalpha << (it == l.end()) << endl;
    > return 0;}
    > -------------------------------------------


    > The result (with gcc version 4.3.4 (Gentoo 4.3.4 p1.0, pie-10.1.5))
    > is:
    > 1
    > false


    > (i.e. the expected result)


    On what grounds is it expected?

    Try compiling with -D_GLIBCXX_CONCEPT_CHECKS -D_GLIBCXX_DEBUG
    -D_GLIBCXX_DEBUG_PEDANTIC. (These options really should be the
    default, but like most compilers, g++'s defaults are rather
    worthless.)

    --
    James Kanze
    James Kanze, Apr 3, 2011
    #8
    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. Emmanuel Freund

    applet's call comportement

    Emmanuel Freund, Oct 25, 2004, in forum: Java
    Replies:
    10
    Views:
    589
    Emmanuel Freund
    Nov 4, 2004
  2. Jesus M. Salvo Jr.
    Replies:
    2
    Views:
    4,161
    robert
    Feb 11, 2006
  3. Replies:
    6
    Views:
    643
    Jim Langston
    Oct 30, 2005
  4. SpreadTooThin
    Replies:
    9
    Views:
    1,610
    SpreadTooThin
    Jun 25, 2009
  5. Jaydeep Chovatia

    core dump in std::list push_back

    Jaydeep Chovatia, Mar 24, 2011, in forum: C++
    Replies:
    9
    Views:
    1,197
    Angus
    Mar 25, 2011
Loading...

Share This Page