STL container relocated in memory!? (shifting sands)

Discussion in 'C++' started by Olumide, Nov 16, 2008.

  1. Olumide

    Olumide Guest

    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, Nov 16, 2008
    #1
    1. Advertising

  2. Olumide

    Olumide Guest

    > 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.
    Olumide, Nov 16, 2008
    #2
    1. Advertising

  3. Olumide

    red floyd Guest

    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.
    red floyd, Nov 16, 2008
    #3
  4. 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
    Erik Wikström, Nov 16, 2008
    #4
  5. 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.)
    Juha Nieminen, Nov 16, 2008
    #5
  6. 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
    George Kettleborough, Nov 16, 2008
    #6
    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. Maitre Bart
    Replies:
    2
    Views:
    520
    Maitre Bart
    Feb 11, 2004
  2. Replies:
    4
    Views:
    797
    Daniel T.
    Feb 16, 2006
  3. wolverine
    Replies:
    2
    Views:
    449
    Marcus Kwok
    Jul 24, 2006
  4. toton
    Replies:
    7
    Views:
    436
    Jerry Coffin
    Jul 31, 2006
  5. Me
    Replies:
    17
    Views:
    655
    JohnQ
    Jul 27, 2007
Loading...

Share This Page