Introducing stable_vector

We present 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.

• stable_vector.hpp. The code uses Boost.
• test_stable_vector.cpp: Test suite for stable_vector.
  

In the following we are using the terminology of the C++98 standard.

General properties. stable_vector satisfies all the requirements of a container, a reversible container and a sequence and provides all the optional operations present in std::vector. Like std::vector, iterators are random access. 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 stable_vector.

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 std::vector, 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 std::vector:

operation	exception safety for std::vector<T>	exception safety for stable_vector<T>
insert	strong unless copy or assignment of T throw (basic)	strong
erase	no-throw unless copy or assignment of T throw (basic)	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 T is

m_v = 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

m_sv = (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

m_sv/m_v ≈ (fp + e + p)/fe.

So, stable_vector uses less memory than std::vector only when e > p and the capacity to size ratio exceeds a given threshold:

m_sv < m_v ↔ 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.

Summary. 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 std::vector.