STL container relocated in memory!? (shifting sands)

[Olumide]

Hello -

To begin with, I'm not the most experienced STL use out there but I'm
slowly getting there. One bug(?) that's plagued me of recent is the
way the OS (or is it STL?) appears to relocate a container in memory
if for example the container needs to grow, with the result that any
references (iterators included) to items in such a container cease to
be valid and may return the address 0xCDCDCD or 0xDDDDDD in the
windows environment (I now know what these pointers mean). I haven't
read the standard but I'm guessing it there's something about elements
of some(?) containers needing to be stored contiguously in memory, and
as such the runtime(?) may relocate a container to guarantee this. Is
this so?

Also, lately, its happened that while in the middle of a series of
function calls that do nothing to alter (i.e. grow) the container, an
existing iterator to the container ceases to be valid, apparently the
container has been moved, or so it seems.

Here's a small example I just cooked up:

#include <iostream>
#include <vector>

using namespace std;

int main(int argc, char* argv[])
{
vector<int test;

for( unsigned i = 1; i < 10; i++ )
{
test.push_back(i); cout << "pointer: " << &test.front() << endl;
}
return 0;
}

Output:
pointer: 00335448
pointer: 00335570 // changed
pointer: 00335670
pointer: 00335570
pointer: 00335670
pointer: 00335670
pointer: 003356B8 // changed
pointer: 003356B8
pointer: 003356B8
Oddly, lists are not so affected i.e. when I change the type of test
to list<int , the problem no longer happens:

pointer: 00335488
pointer: 00335488
pointer: 00335488
pointer: 00335488
pointer: 00335488
pointer: 00335488
pointer: 00335488
pointer: 00335488
pointer: 00335488

I guess I've partly figured out the problem, but I'd appreciate more
insight on this problem/feature.

Thanks,

- Olumide

[Olumide]

I guess I've partly figured out the problem, but I'd appreciate more

insight on this problem/feature.

If I may clarify, although it seems this problem does not affect
lists, I would like to avoid one extreme of not using vectors etc.

[red floyd]

Olumide wrote:

Hello -

To begin with, I'm not the most experienced STL use out there but I'm
slowly getting there. One bug(?) that's plagued me of recent is the
way the OS (or is it STL?) appears to relocate a container in memory
if for example the container needs to grow, with the result that any
references (iterators included) to items in such a container cease to
be valid and may return the address 0xCDCDCD or 0xDDDDDD in the
windows environment (I now know what these pointers mean). I haven't
read the standard but I'm guessing it there's something about elements
of some(?) containers needing to be stored contiguously in memory, and
as such the runtime(?) may relocate a container to guarantee this. Is
this so?

The standard says that iterators (and pointers or references to content)
into certain containers (*cough*vector*cough*) are invalidated when the
container grows.

[=?UTF-8?B?RXJpayBXaWtzdHLDtm0=?=]

On 2008-11-16 17:52, Olumide wrote:

Hello -

To begin with, I'm not the most experienced STL use out there but I'm
slowly getting there. One bug(?) that's plagued me of recent is the
way the OS (or is it STL?) appears to relocate a container in memory
if for example the container needs to grow, with the result that any
references (iterators included) to items in such a container cease to
be valid and may return the address 0xCDCDCD or 0xDDDDDD in the
windows environment (I now know what these pointers mean). I haven't
read the standard but I'm guessing it there's something about elements
of some(?) containers needing to be stored contiguously in memory, and
as such the runtime(?) may relocate a container to guarantee this. Is
this so?

Yes, some of the standard containers may re-locate the elements which
causes invalidation of any iterators and/or pointers to the elements.

Also, lately, its happened that while in the middle of a series of
function calls that do nothing to alter (i.e. grow) the container, an
existing iterator to the container ceases to be valid, apparently the
container has been moved, or so it seems.

That should not happen, if you do not add or remove elements in the
container the elements should stay in place.

Oddly, lists are not so affected i.e. when I change the type of test
to list<int , the problem no longer happens:

Yes, node-based containers (such as list, set, and map) does not
relocate elements, this is because each element is a node with pointers
to other elements. When you insert/remove elements you only have to
update the pointers and not move the nodes.

I guess I've partly figured out the problem, but I'd appreciate more
insight on this problem/feature.

Any good reference to the standard library should specify if an
operation can invalidate iterators.

--
Erik Wikström

[Juha Nieminen]

Olumide wrote:

To begin with, I'm not the most experienced STL use out there but I'm
slowly getting there. One bug(?) that's plagued me of recent is the
way the OS (or is it STL?) appears to relocate a container in memory
if for example the container needs to grow

What you need is a good reference manual on the STL containers.

Some containers, as per the C++ standard, guarantee that
pointers/references and/or iterators to existing elements remain valid
even if new elements are added to the container, while other containers
do not make such guarantee. These are completely unambiguously and
precisely documented, and it's just a question of checking for each
container what it does and doesn't guarantee.

Knowing how the containers work internally will make it easier to
remember which guarantees what. (Also knowing their internal workings is
good when you want to choose the most efficient container for a given task.)

[George Kettleborough]

On 16/11/08 17:15, red floyd wrote:

Olumide wrote:

>Hello -

To begin with, I'm not the most experienced STL use out there but I'm
slowly getting there. One bug(?) that's plagued me of recent is the
way the OS (or is it STL?) appears to relocate a container in memory
if for example the container needs to grow, with the result that any
references (iterators included) to items in such a container cease to
be valid and may return the address 0xCDCDCD or 0xDDDDDD in the
windows environment (I now know what these pointers mean). I haven't
read the standard but I'm guessing it there's something about elements
of some(?) containers needing to be stored contiguously in memory, and
as such the runtime(?) may relocate a container to guarantee this. Is
this so?

The standard says that iterators (and pointers or references to content)
into certain containers (*cough*vector*cough*) are invalidated when the
container grows.

Vectors invalidate all iterators, pointers and references whenever
reallocation takes place.

Deques invalidate iterators whenever *any* insertion takes place.
Pointers and references to elements remain valid only if inserting to
the front or back.

Definitely worth learning how the STL containers actually work. Then you
can decide which container is most appropriate for what you need to do
with it (sounds like list is the most appropriate for you). You should
get a book like The C++ Standard Library by Josuttis.

--
George Kettleborough