A proof of concept of a semistable C++ vector container

Summary

A proof of concept of a semistable vector container # include < semistable/vector.hpp > # include < iostream > int main () { semistable::vector< int > x = { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 }; auto it = x. begin () + 5 ; std::cout << *it << " " ; // prints 5 x. erase (x. begin ()); // erases first element std::cout << *it << " " ; // prints 5 again! } std::vector stores its contents in a contiguous block of memory, so mid insertions and erasures invalidate references and iterators to previous elements. semistable::vector is called semistable in the sense that, while references are still unstable, its iterators correctly track elements in situations like the above. semistable::vector stores elements contiguously and provides the same API as std::vector with the extra guarantee of iterator stability (including end() ). The library is header-only and depends solely on Boost.Config. C++11 or later required. Implementation From the point of view of stability, there are three types of operation that cause iterators to become invalid in a classical std::vector : insertion of elements before a given position, erasure of elements before a given position, reallocation to a new buffer (e.g. with a call to reserve ). When any of these operations happens, semistable::vector creates a new epoch descriptor indicating the change. Outstanding iterators internally point to the epoch that was current when they were last used. All arrows in the diagram are std::shared_ptr s: When the iterators are used, they follow the chain of epoch descriptors till the last one, making the necessary adjustments to their stored position along the way. This ensures that dereference (as well as other iterator operations) are consistent with the current state of the vector: When an epoch descriptor is outdated (all outstanding iterators are past it), it gets automatically deleted (no shared_ptr points to it any longer). Performance The graph shows normalized execution times of the following operatio...