list::begin() iterator comportement after push_back operations

[Hizo]

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.

 

[Bo Persson]

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

 

[Hizo]

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]

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]

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]

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

 

[Bo Persson]

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

 

[James Kanze]

[...]
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.)