An STL compliant sorted vector

• Download source files - 7 Kb

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.

Namespace

sorted_vector resides in the namespace codeproject.

Basic Usage

The following small table shows corresponding declarations of sorted_vector's and set's/multiset's.

(sorted_vector<Key,Pred,true> means sorted_vector<Key,Pred,bNoDuplicates=true>)

The various set/multiset insert and erase member functions as well as the set/multiset functions count, lower_bound,upper_bound, equal_range are part of sorted_vector's interface and behave the same as there set/multiset counterparts. The following code snippet shows the use of a sorted_vector to hold the set intersection of the content of two std::vector's.

#pragma warning(disable:4786)
#include "sorted_vector.h"

size_t             //build intersection using set interface of sorted_vector

BuildIntersection(  const std::vector<int>& v0,const std::vector<int>& v1,
                    codeproject::sorted_vector<int,true>& svecIntersection)
{		
    codeproject::sorted_vector<int,true> svec(v0.begin(),v0.end());
    for(int i=0;i<v1.size();i++){
        if( svec.find(v1[i])!=svec.end() ){
            svecIntersection.insert(v1[i]);
        }
    }
    return svecIntersection.size();
}

The code example shows the use of the member functions find and insert. If you replace codeproject::sorted_vector<int,true> by std::set<int> you get exactly the same result. This piece of code can be optimized for speed by replacing the insert calls in the loop by calls to push_back of the base container (a vector) followed by a call to the member function sort at the end of the loop.

#pragma warning(disable:4786)
#include "sorted_vector.h"

size_t             //same as previous example, optimized insertions 

BuildIntersection1(  const std::vector<int>& v0,const std::vector<int>& v1,
                    codeproject::sorted_vector<int,true>& svecIntersection)
{		
    codeproject::sorted_vector<int,true> svec(v0.begin(),v0.end());
    codeproject::sorted_vector<int,true>::Cont& vInterSect 
        = svecIntersection.get_container();
    for(int i=0;i<v1.size();i++){
        if( svec.find(v1[i])!=svec.end() ){
            vInterSect.push_back(v1[i]);
        }
    }
    svecIntersection.sort();
    return svecIntersection.size();
}

Interface of sorted_vector

Points of Interest

An interview with Alexander Stepanov (inventor of the STL) at http://www.stlport.org/resources/StepanovUSA.html , in which he proposed to implement a sorted container as an adapter of a std::container gave me the idea for this work. The real surprise to me was the unexpected good performance of sorted_vector compared to set/multiset. The outcome of my tests indicate, that the std::set/std::multiset has only one (important) advantage over a sorted vector, namely that iterators remain valid in a set/multiset, even when more elements are added.

The implementation work itself was easy and did not require any advanced C++/STL feature. It can be summarized as follows: Most of the member functions of sorted_vector forward the call to the vec_ data member, which is a std::vector. The set/multiset specific functions for inserting/erasing and locating elements mostly use STL algorithms to deal with the sorted sequence present in the vec_ data member. The low level interface consisting of the member functions get_container() (which returns a reference to the vec_ data member) and sort and stable_sort (which restore the sort order) are necessary to improve insertion performance (by allowing a temporary violation of the sorting order). Only one function was unexpectedly difficult to implement: The function unique, which must be called after sort and stable_sort in the case of a set. This function is part of the STL and requires a predicate as third argument. This predicate must return true, if the passed elements are equal. But the class sorted_vector only has access to a predicate which evaluates the < relation. In theory, it should be possible, to transform a predicate evaluating the < relation into another predicate evaluating ==, but in practice this is only possible, when the < predicate is implemented as object derived from std::binary_function. Ultimately, I had to implement unique myself because of that.

History

• 1.0: November 19th, 2002; Initial release.
• 1.1: November 28th, 2002; Documentation and code Update
  • changed namespace from std to codeproject
  • supports member templates for constructing/inserting from iterator range in case of VC++7.0