Pointers to elements of std::vector and std::list

Question

Hi,

I'm having a std::vector with elements of some class ClassA. Additionally I want to create an index using a std::map<key,ClassA*> which maps some key value to pointers to elements contained in the vector.

Is there any guarantee that these pointers remain valid (and point to the same object) when elements are added at the end of the vector (not inserted). I.e, would the following code be correct:

std::vector<ClassA> storage;
std::map<int, ClassA*> map;

for (int i=0; i<10000; ++i) {
  storage.push_back(ClassA());
  map.insert(std::make_pair(storage.back().getKey(), &(storage.back()));
}
// map contains only valid pointers to the 'correct' elements of storage

How is the situation, if I use std::list instead of std::vector?

Answer 1

As far as I understand, there is no such guarantee. Adding elements to the vector will cause elements re-allocation, thus invalidating all your pointers in the map.

Answer 2

Vectors - No. Because the capacity of vectors never shrinks, it is guaranteed that references, pointers, and iterators remain valid even when elements are deleted or changed, provided they refer to a position before the manipulated elements. However, insertions may invalidate references, pointers, and iterators.

Lists - Yes, inserting and deleting elements does not invalidate pointers, references, and iterators to other elements

Answer 3

Just make them both store pointers an explicitly delete the objects when you don't need them.

std::vector<ClassA*> storage;
std::map<int, ClassA*> map;

for (int i=0; i<10000; ++i) {
  ClassA* a = new ClassA()
  storage.push_back(a)
  map.insert(std::make_pair(a->getKey(), a))
}
// map contains only valid pointers to the 'correct' elements of storage

Answer 4

I'm not sure whether it's guaranteed, but in practice storage.reserve(needed_size) should make sure no reallocations occur.

But why don't you store indexes?
It's easy to convert indexes to iterators by adding them to the begin iterator (storage.begin()+idx) and it's easy to turn any iterator into a pointer by first dereferencing it, and then taking its address (&*(storage.begin()+idx)).

Answer 5

Use std::deque! Pointers to the elements are stable when only push_back() is used.

Note: Iterators to elements may be invalidated! Pointers to elements won't.

Edit: this answer explains the details why: http://stackoverflow.com/questions/1658956/c-deques-iterator-invalidated-after-push-front/1659688#1659688

Answer 6

From one of the comments to another answer, it seems as if all that you want is centralize (ease) memory management. If that is really the case, you should consider using prepackaged solutions like the boost pointer container library and keep your own code as simple as possible.

In particular, take a look at ptr_map