Stable memory addresses using std container (e.g. vector, list, queue, ...)

Question

Note. . I did not understand that pointers should be considered iterators, so it can rightly be argued that what I call the lack of stability of the memory address should be called the invalidity of the iterator. Read the duplicate for a more abstract and sound version of my question.

My question is related to this: The C ++ link changes when a new push_back element is added to std :: vector .

I want to work with a set of objects that should, for simplicity, exist only once in memory. Therefore, I want to use a container, for example std :: vector, to store all objects once. Then I will use a pointer to objects in other structures. Unfortunately, std :: vector can change the memory address of its elements, so the use of pointers to these elements is undefined. I need pointers because I want to reference these objects using other structures, such as std :: priority_queue or other std data structures.

In a specific case, objects are labels for connections in the graph algorithm, which means that they are created throughout the algorithm and, therefore, cannot be pre-selected. This means that std :: vector is not adequate, because it can move its contents with invalid pointers to these labels, which may exist in std :: priority_queues or other data structures.

However, I only need labels when they are created or when I can access them from data structures other than the data structure. Therefore, I never need to get the nth element from the container, I only need to save the objects on the stack or heap and get a pointer when they are created to use it in other structures. Finally, when the container is popped out of the stack, the items in it must be cleaned beautifully. I thought std :: list might be appropriate since my knowledge of an abstract linked list never needs to be redistributed; which allows the use of persistent pointers.

However, I cannot find anywhere that this pointer stability is true for std :: lists. And maybe there is something superb, some kind of container class that does exactly what I want. Of course, I can always use new ones, add all pointers to std :: list and iterate, doing deletion at the end. But this is not my preferred method, since more memory management requires more, since I think it is necessary to get 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 std :: list with std :: vector and the behavior will become 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 special rules for pointer / reference and iterator non-iteration for all standard containers. Even std::vector<T> could be an option if you can predict the maximum capacity:

• Adding / removing objects at the end of std::vector<T> keeps pointers and iterators stable, unless std::vector<T> redistributes the internal structure. That is, pointers and iterators only become invalid when adding an object and v.size() == v.capacity() . You can use v.reserve(n) to reserve space.
• Adding / removing objects from either end of std::deque<T> keeps pointers stable but invalidates iterators.
• Adding / removing objects anywhere std::list<T> supports stabilization of both pointers and iterators.

Obviously, pointers and iterators of remote objects are invalid in all cases. However, pointers and iterators for other objects obey the above rules.

The overhead for operations and memory increases in the order the containers are displayed. That is, ideally, you would use std::vector<T> and preallocate enough memory to maintain object stability. If you cannot predict the maximum size, std::deque<T> is the next best option: std::deque<T> is an array of arrays with a fixed size, i.e. a relatively small overhead object and relatively little memory allocation. Only if you need to save a table of pointers and iterators, cannot predict the size of the container, std::list<T> is a reasonable option. To reduce the overhead for each object, you can use std::forward_list<T> , which has the same invalidation restrictions as std::list<T> , but can only be moved in one direction and is somewhat more inconvenient for use.

I would use std::vector<T> with enough reserved memory. If I cannot, I would make it so that I can use std:vector<T> . Only if this is not possible, I would consider using std::deque<T> to store objects .... and I rarely use std::list<T> , since there is hardly any reason to ever use it.

Answer 2

Yes, inserting into the list does not cancel any iterators (pointers are iterators), deleting an element only cancels the iterators representing this element.

cplusplus.com has a 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 this if you are in doubt. Standard states guarantee member functions in this form: "Effects: ... Does not affect the validity of iterators and links."