Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #2990 > unrolled thread

list::begin() iterator comportement after push_back operations

Back to article view | Back to comp.lang.c++

Contents

  list::begin() iterator comportement after push_back operations Hizo <hizostudio@gmail.com> - 2011-04-02 04:46 -0700
    Re: list::begin() iterator comportement after push_back operations "Bo Persson" <bop@gmb.dk> - 2011-04-02 13:57 +0200
      Re: list::begin() iterator comportement after push_back operations Hizo <hizostudio@gmail.com> - 2011-04-02 05:23 -0700
      Re: list::begin() iterator comportement after push_back operations Hizo <hizostudio@gmail.com> - 2011-04-02 05:24 -0700
      Re: list::begin() iterator comportement after push_back operations Hizo <hizostudio@gmail.com> - 2011-04-02 05:28 -0700
      Re: list::begin() iterator comportement after push_back operations Hizo <hizostudio@gmail.com> - 2011-04-02 05:32 -0700
        Re: list::begin() iterator comportement after push_back operations "Bo Persson" <bop@gmb.dk> - 2011-04-02 15:37 +0200
        Re: list::begin() iterator comportement after push_back operations James Kanze <james.kanze@gmail.com> - 2011-04-03 10:01 -0700

#2990 — list::begin() iterator comportement after push_back operations

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.

[toc] | [next] | [standalone]

#2991

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

[toc] | [prev] | [next] | [standalone]

#2992

On 2 avr, 13:57, "Bo Persson" <b...@gmb.dk> 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.

[toc] | [prev] | [next] | [standalone]

#2993

On 2 avr, 13:57, "Bo Persson" <b...@gmb.dk> 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.

[toc] | [prev] | [next] | [standalone]

#2994

On 2 avr, 13:57, "Bo Persson" <b...@gmb.dk> 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.

[toc] | [prev] | [next] | [standalone]

#2995

On 2 avr, 13:57, "Bo Persson" <b...@gmb.dk> 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

[toc] | [prev] | [next] | [standalone]

#2998

Hizo wrote:
> On 2 avr, 13:57, "Bo Persson" <b...@gmb.dk> 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

[toc] | [prev] | [next] | [standalone]

#3046

On Apr 2, 1:32 pm, Hizo <hizostu...@gmail.com> wrote:
> On 2 avr, 13:57, "Bo Persson" <b...@gmb.dk> 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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c++

csiph-web