stable_vector, a fully STL-compliant stable container that provides most of the features of
std::vector except element contiguity. The underlying data structure has been discussed in a prior entry.
In the following we are using the terminology of the C++98 standard.
stable_vector satisfies all the requirements of a container, a reversible container and a sequence and provides all the optional operations present in
stable_vector does not provide element contiguity; in exchange for this absence, the container is stable, i.e. references and iterators to an element of a
stable_vector remain valid as long as the element is not erased, and an iterator that has been assigned the return value of
end() always remain valid until the destruction of the associated
Operation complexity. The big-O complexities of
stable_vector operations match exactly those of
std::vector. In general, insertion/deletion is constant time at the end of the sequence and linear elsewhere. Unlike
stable_vector does not internally perform any
value_type destruction, copy or assignment operations other than those exactly corresponding to the insertion of new elements or deletion of stored elements, which can sometimes compensate in terms of performance for the extra burden of doing more pointer manipulation and an additional allocation per element.
Exception safety. (according to Abrahams' terminology) As
stable_vector does not internally copy elements around, some operations provide stronger exception safety guarantees than in
|operation||exception safety for||exception safety for|
|strong unless copy or assignment of ||strong|
|no-throw unless copy or assignment of ||no-throw|
Memory overhead. The C++ standard does not specifiy requirements on memory consumption, but virtually any implementation of
std::vector has the same behavior wih respect to memory usage: the memory allocated by a vector
v with n elements of type
mv = c·e,
where c is
v.capacity() and e is
sizeof(T). c can be as low as n if the user has explicitly reserved the exact capacity required; otherwise, the average value c for a growing vector oscillates between 1.25·n and 1.5·n for typical resizing policies. For
stable_vector, the memory usage is
msv = (c + 1)p + (n + 1)(e + p),
where p is the size of a pointer. We have c + 1 and n + 1 rather than c and n because a dummy node is needed at the end of the sequence. If we call f the capacity to size ratio c/n and assume that n is large enough, we have that
msv/mv ≈ (fp + e + p)/fe.
stable_vector uses less memory than
std::vector only when e > p and the capacity to size ratio exceeds a given threshold:
msv < mv ↔ f > (e + p)/(e − p). (provided e > p)
This threshold approaches typical values of f below 1.5 when e > 5p; in a 32-bit architecture, when e > 20 bytes.
stable_vector is a drop-in replacement for
std::vector providing stability of references and iterators, in exchange for missing element contiguity and also some performance and memory overhead. When the element objects are expensive to move around, the performance overhead can turn into a net performance gain for
stable_vector if many middle insertions or deletions are performed or if resizing is very frequent. Similarly, if the elements are large there are situations when the memory used by
stable_vector can actually be less than required by