The two random access containers of the C++ standard library,
std::deque, have the same big-O complexity as
stable_vector for the following operations:
push_back: amortized constant
Yet the differences in actual performance vary wildly. I have written a profile program that measures the time taken by the three containers at these operations for two different value types:
int and a "heavy" user defined type
bigobj holding an
int and an
std::string. The program was built with release mode settings with MSVC++ 8.0 and GNU GCC 3.4.4 for Cygwin/MinGW. Resulting times are summarized in the following table: values are normalized to the minimum among the three containers.
|GNU GCC 3.4.4|
For small objects like
std::vector is, as expected, the fastest or very close to the fastest at every operation.
push_back takes much longer for
std::deque presumably because the latter allocates element chunks thus amortizing allocation time whereas
stable_vector performs an allocation for every new node. The poor performance of
insert can be attributed to the operation of adjustment of "up" pointers with each insertion operation, which is considerably slower than the simple
int copying incurred by the other two containers. Finally, note that random access is very slow for
std::deque because it involves some non-trivial arithmetical calculations, whereas
stable_vector only perform simple pointer offsets and indirections.
When storing heavy objects with expensive copy, the situation changes somewhat. The fact that
stable_vector does not internally copy elements upon resizing or shrinking improves its relative performance with respect to the other two containers at
push_back, and specially at
stable_vector is the fastest.
This basic analysis suggests that the main performance handicap of
stable_vector stems from the fact that it is a node-based container, as opposed to the chunk-based nature of
std::deque. This drawback might be alleviated by the use of burst-allocation, as proposed by Ion Gaztañaga.