Stable memory addresses using a std container (like vector, list, queue, ...) [duplicate]

Question

Note: I didn't realize that pointers are to be considered iterators, hence one may fairly argue that what I call lack of memory address stability should be called iterator invalidation. Please read the duplicate for a more abstract and sound version of my question.

My question is related to this one: C++ reference changes when push_back new element to std::vector .

I want to work with a set of objects which should, for simplicity, only exist once in memory. Therefore I want to use a container, like std::vector, to store all the objects once. Then I will use a pointer to the objects in other structures. Unfortunately, std::vector may change the memory address of it's elements, hence using pointers to these elements is ill-defined. I need the pointers, as I want to refer to these objects using other structures, like std::priority_queue or other std data structures.

In the specific case the objects are labels for connections in a graph algorithm, meaning that they are created throughout the algorithm and hence cannot be pre-allocated. This means that a std::vector is not adequate, as it may relocate its content, invalidating pointers to these labels which may exist in std::priority_queues or other data structures.

However, the only moments I need the labels, is when they are created or when I can access them from data structures other than the containing data structure. Hence I never need to get the n-th element from the container, I only need to be able to keep objects on the stack or the heap and get the pointer when they are created to use it in other structures. Finally, when the container is popped from the stack, the elements in it need to be cleaned up nicely. I thought a std::list may be appropriate, as my knowledge of an abstract linked list never needs to reallocate; allowing for stable pointers.

However, I cannot find anywhere that this pointer stability is true for std::lists. And maybe there is something superior, some container class which does exactly what I want. Of course, I can always use new, append all the pointers to a std::list and iterate doing a delete at the end. But this is not my preferred way, as it takes more memory management as I think should be needed for just getting stable pointers.

Question: Is std::list pointer stable? Is there a better solution than std::list?

To illustrate the problem, I also made this example: http://ideone.com/OZYeuw . Replace the std::list with a std::vector, and the behavior becomes undefined.

#include <iostream>
#include <list>
#include <queue>
#include <vector>

struct Foo {
    Foo(int _a) : a(_a) {}
    int a;
};

struct FooComparator {
    bool operator()(Foo *a, Foo *b) { return a->a < b->a; }
};

int main() {
    std::list<Foo> foos;
    //std::vector<Foo> foos; // when used instead, the behaviour will become undefined
    std::priority_queue<Foo *, std::vector<Foo *>, FooComparator> pq;

    // Simulate creation and 'containment' of objects, while they are being processed by other structures.
    for(int i=0; i<100; ++i) {
        foos.push_back(Foo((100-i) % 10));
        pq.emplace(&foos.back());
    }

    while(not pq.empty()) {
        std::cout << pq.top()->a << " "; // the dereference -> may segfault if foos is not *pointer stable*
        pq.pop();
    }

    std::cout << std::endl;
    return 0;
}

Answer 1

There are specific rules for pointer/reference and iterator invalidation for all of the standard containers. Even std::vector<T> may be an option if you can predict the maximum capacity:

• Adding/removing objects at the end of a std::vector<T> keeps pointers and iterators stable unless the std::vector<T> needs to reallocate its internal structure. That is, pointers and iterators get only invalidated when an object is added and v.size() == v.capacity(). You can use v.reserve(n) to reserve space.
• Adding/removing objects at either end of a std::deque<T> keeps pointers stable but does invalidate iterators.
• Adding/removing objects anywhere in a std::list<T> keeps both pointers and iterators stable.

Obviously, pointers and iterators to removed objects are invalidated in all case. However, pointer and iterators to other objects obey the rules above.

The overhead for operations and memory increase in the order the containers are show. That is, ideally you'd use a std::vector<T> and allocate enough memory ahead of time to keep the objects stable. If you can't predict the maximum size needed, std::deque<T> is the next best option: std::deque<T> is an array of fixed sized arrays, i.e., there is a relatively small per object overhead and relatively few memory allocation. Only if you need to keep both pointers and iterators table, can't predicate the size of the container, std::list<T> is a reasonable option. To lower the per-object overhead you might consider using a std::forward_list<T> which has the same invalidation constraints as std::list<T> but can only be traversed in one direction and is somewhat more inconvenient to use.

I'd use a std::vector<T> with sufficient reserved memory. If I can't, I would make so that I can use a std:vector<T>. Only if that is really impossible, I would consider using a std::deque<T> for storing objects. ... and I rarely use std::list<T> as there is hardly any reason to ever use it.

Answer 2

Yes, inserting to a list does not invalidate any iterators (pointers are iterators), erasing an element only invalidates iterators representing that element.

cplusplus.com has section iterator validity for each member function of standard containers for example: http://www.cplusplus.com/reference/list/list/insert/. These claims are usually based on the standard, but you can check that if you have doubts. Standard states guarantees for member functions in a form like this: "Effects: ... Does not affect the validity of iterators and references."