What happen to pointers when vectors need more mem

问题:

When vector needs more memory it will reallocate memory somewhere, I don't know where yet! and then pointers become invalid, is there any good explanation on this?

I mean where they go, what happen to my containers? ( not linked list ones )

回答1:

Short answer: Everything will be fine. Don't worry about this and get back to work.

Medium answer: Adding elements to or removing them from a vector invalidates all iterators and references/pointers (possibly with the exception of removing from the back). Simple as that. Don't refer to any old iterators and obtain new ones after such an operation. Example:

std::vector<int> v = get_vector();

int & a = v[6];
int * b = &v[7];
std::vector<int>::iterator c = v.begin();
std::advance(it, 8);

v.resize(100);

Now a, b and c are all invalid: You cannot use a, and you cannot dereference b or c.

Long answer: The vector keeps track of dynamic memory. When the memory is exhausted, it allocates a new, larger chunk elsewhere and copies (or moves) all the old elements over (and then frees up the old memory, destroying the old objects). Memory allocation and deallocation is done by the allocator (typically std::allocator<T>), which in turn usually invokes ::operator new() to fetch memory, which in turn usually calls malloc(). Details may vary and depend on your platform. In any event, any previously held references, pointers or iterators are no longer valid (presumably because they refer to the now-freed memory, though it's not specified in the standard why they're invalid).

回答2:

When you add or remove items from a vector, all iterators (and pointers) to items within it are invalidated. If you need to store a pointer to an item in a vector, then make the vector const, or use a different container.

It shouldn't matter to you where the vector stores things. You don't need to do anything, just let it do its job.

回答3:

When you use std::vector, the class takes care of all the details regarding memory allocation, pointers, resizing and so on.

The vector class exposes its contents through iterators and references. Mutations of the vector will potentially invalidate iterators and references because reallocation may be necessary.

It is valid to access the contents using pointers because the vector class guarantees to store its elements at contiguous memory locations. Clearly any mutation of the list will potentially invalidate any pointers to its contents, because of potential reallocation. Therefore, if you ever access an element using pointers, you must regard those pointers as invalid once you mutate the vector. In short the same rules apply to pointers to the contents as do to references.

If you want to maintain a reference to an item in the vector, and have this reference be valid even after mutation, then you should remember the index rather than a pointer or reference to the item. In that case it is perfectly safe to add to the end of the vector and your index value still refers to the same element.