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

Accepted answer

Score: 20

There are specific rules for pointer/reference 28 and iterator invalidation for all of the 27 standard containers. Even std::vector<T> may be an option 26 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 25 and iterators to removed objects are invalidated 24 in all case. However, pointer and iterators 23 to other objects obey the rules above.

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

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

Score: 3

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

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

Source: stackoverflow.com

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

converting vector iterator to pointer

Vector Iterators Casting

Is a C# list like a C++ list?

Is vector in c++ a pointer?

Pointer and vectors in C++

c++ How to return a vector by reference?

vector<char> VS vector<bool> in C++11

Use vector<int>::iterator by reference but with error

How can I sort a vector of unique_ptr?

Does std::vector::insert reserve by definition?