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;
}
