Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > STL container relocated in memory!? (shifting sands)

Reply
Thread Tools

STL container relocated in memory!? (shifting sands)

 
 
Olumide
Guest
Posts: n/a
 
      11-16-2008
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
 
Reply With Quote
 
 
 
 
Olumide
Guest
Posts: n/a
 
      11-16-2008
> 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.
 
Reply With Quote
 
 
 
 
red floyd
Guest
Posts: n/a
 
      11-16-2008
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.
 
Reply With Quote
 
Erik Wikström
Guest
Posts: n/a
 
      11-16-2008
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
 
Reply With Quote
 
Juha Nieminen
Guest
Posts: n/a
 
      11-16-2008
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.)
 
Reply With Quote
 
George Kettleborough
Guest
Posts: n/a
 
      11-16-2008
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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
relocated memory detap Computer Support 2 04-06-2007 09:30 AM
container inside container in stl wolverine C++ 2 07-24-2006 03:08 PM
Copy elements from one STL container to another STL container Marko.Cain.23@gmail.com C++ 4 02-16-2006 05:03 PM
STL: container's values setup by another container Maitre Bart C++ 2 02-11-2004 12:11 AM
std::container::iterator vs std::container::pointer Vivi Orunitia C++ 11 02-04-2004 08:09 AM



Advertisments