STL compliant sorted vector class (std::map replacement) from CodeProject.

STL compliant sorted vector class (std::map replacement) from CodeProject.

Source:
http://www.codeproject.com/Articles/3217/An-STL-compliant-sorted-vector?display=Print

Introduction:

sorted_vector adapts a std::vector to the interface required by
std::set/std::multiset, thereby providing set/multiset and vector
functionality (random access) in one container.

Tests show that sorted_vector's element retrieval (find) speed
outperforms that of std::set/std::multiset by a factor of 2 (on most
machines). On the downward side is the poor performance of
sorted_vector's insert member function, because it inserts an element
somewhere in the middle of the sorted vector in order to preserve the
sort order. By using sorted_vector's low level interface one can solve
this performance bottleneck by inserting a bunch of objects using a
series of push_back's followed by a call to the member function sort,
which restores the sort order.

sorted_vector should be preferred over std::set/std::multiset if many
small elements must be stored. Most STL implementations use a variant of
a balanced tree to implement set and multiset, which imposes a per
element storage overhead of 3 pointers. The most important reason to use
a std::set/std::multiset instead of sorted_vector is the need to keep
iterators into a set/multiset while inserting more elements into the
set. These iterators remain valid in the case of a set/multiset, but are
invalidated in the case of a sorted_vector container.