Persistant references in STL Containers

Question

When using C++ STL containers, under what conditions must reference values be accessed? For example are any references invalidated after the next function call to the container?

{
std::vector<int> vector;
vector.push_back (1);
vector.push_back (2);
vector.push_back (3);

vector[0] = 10;       //modifies 0'th element

int& ref = vector[0];
ref = 10;             //modifies 0'th element

vector.push_back (4);
ref = 20;             //modifies 0'th element???

vector.clear ();
ref = 30;             //clearly obsurd
}

I understand that in most implementations of the stl this would work, but I'm interested in what the standard declaration requires.

--edit: Im interested becuase I wanted to try out the STXXL (http://stxxl.sourceforge.net/) library for c++, but I realised that the references returned by the containers were not persistent over multiple reads, and hence not compatible without making changes (however superficial) to my existing stl code. An example:

{
std::vector<int> vector;
vector.push_back (1);
vector.push_back (2);


int& refA = vector[0];
int& refB = vector[1]; //refA is not gaurenteed to be valid anymore
}

I just wanted to know if this meant that STXXL containers where not 100% compatible, or indeed if I had been using STL containers in an unsafe/implementation dependant way the whole time.

Answer 1

I expect that references would be invalidated only by any explicit or implicit resize() (see also the max_size, capacity, and reserve methods).

Answer 2

Vector will invalidate its iterator and references when it reallocates, which depends upon its current capacity. Although the above code might work in some cases, you shouldn't rely on this as the reference might be invalidated after the push_back(4) call.

Answer 3

Some basic rules for vector:

• Reallocation invalidates all references, pointers, and iterators for elements of the vector.
• Insertions may invalidate references, pointers, and iterators.
• Inserting or removing elements invalidates references, pointers, and iterators that refer to the following elements.
• If an insertion causes reallocation, it invalidates all references, iterators, and pointers.

Answer 4

About inserting into vectors, the standard says in 23.2.4.3/1:

[insert()] causes reallocation if the new size is greater than the old capacity. If no reallocation happens, all the iterators and references before the insertion point remain valid.

(Although this in fact this talks about insert(), Table 68 indicates that a.push_back(x) must be equivalent to a.insert(a.end(), x) for any vector a and value x.) This means that if you reserve() enough memory beforehand, then (and only then) iterators and references are guaranteed not to be invalidated when you insert() or push_back() more items.

Regarding removing items, 23.2.4.3/3 says:

[erase()] invalidates all the iterators and references after the point of the erase.

According to Table 68 and Table 67 respectively, pop_back() and clear() are equivalent to appropriate calls to erase().