Fast Indexable Stacks

• Download source files - 170 Kb

Introduction

The ootl::stack is a template class similar to std::vector which provides extremely fast element growth: O(1) complexity in both the average and worst cases, rather than the O(N) complexity of std::vector in the worst case. The ootl::stack template also provides fast indexing, outperforming std::deque by as much as 6x or more.

The reverse doubling ArrayList

The ootl::stack template is based on a data structure called the "reverse doubling array list" (which as far as I know is original, but if anyone knows otherwise please let me know. The reverse doubling array list is a linked list of arrays, each one twice the size of the next. When the array of the first node (or last node depending on how you want to envision it) is filled to capacity, a new node is created with twice the capacity as the previous. Since the original data isn't moved, only 2N memory is used at any given time, no deallocation occurs, and there is no need for the N destruction and copy-construction operations.

Quite clearly this data structure supports efficient growth, since there are no copies, and less wasted space. However what is somewhat counterintuitive is that this data structure provides, on an average, random element access with constant complexity. The key to achieving indexing with O(1) complexity is the list must be traversed from the biggest node to the smallest.

Analyzing the complexity of indexing

The reverse doubling array list has half of its elements in the first node, 1/4 of its elements in the second node, 1/8 in the third node, and so on until some lower bound is reached. On an average you will find a node you want after two elements, and in the worst case you'll find it in O(Log N) time complexity. Here's why: ignoring lookup operations, the mean number of nodes you need to visit to access an element using an index lookup is expressed by the following equation:

  (1/2)n + (2/4)n + (3/8)n + ... + (i/2^i)n / n

The factors of n in the quotient are the infinite series 1/2 + 2/4 + 3/8 + 4/16 + ... + (i/2^i). This series converges at the value of two. In order to understand why this is so, consider that it is equivalent to the following infinite sum of infinite sums:

  (1/2 + 1/4 + 1/8 + ...) + (1/4 + 1/8 + 1/16 + ...) + 
                              (1/8 + 1/16 + 1/32 + ...) + ...

These infinite series are very well-known and easily recognizable to be equal to:

  1 + 1/2 + 1/4 + ...

Benchmarks

I've run a few informal tests to compare the performance of the described stack class with the std::vector and std::vector implementations which come with the STLPort 4.6.2 implementation of the C++ standard library. The following results were achieved under Windows XP Service Pack 2, running on an Intel Celeron 1.80 GHZ machine with 512 MB of RAM, using the MinGW GCC 3.4 compiler with full optimizations:

// appending 12.8 million integers

std::vector = 1015 msec
std::deque = 734 msec
ootl::stack = 577 msec

// indexing speeds of 12.8 million integers

std::vector = 593 msec
std::deque = 6733 msec
ootl::stack = 1171 msec

These are fairly representative excerpts from the full benchmarking suite.

The interface

The ootl::stack template itself (which is listed later) is quite complex so first here is its simplified interface:

template<typename
class stack
{
public:
    // public

    typedef T value_type;
    typedef stack self;
    
    // 'structors

    stack();
    stack(self& x);
    stack(int nsize, const T& x = T());
    ~stack();
    
    // model the OOTL Indexable concept

    T& operator[](int n);
    int count();
    
    // model the OOTL Stackable concept

    void push(const T& x = T());
    void pop();
    bool is_empty();
    T& top();
    
    // model the OOTL Iterable concept

    tempate<Procedure>
    void for_each(Procedure& p);
};

The implementation

Here's the big ol' implementation:

// Public Domain by Christopher Diggins 

// http://www.ootl.org 


#ifndef OOTL_STACK_HPP
#define OOTL_STACK_HPP

#include <cstdlib>

#include <cassert>

#include <memory>

#include <algorithm>

#include <iostream>


namespace ootl {

    template<
      typename T, 
      int Factor_N = 2, 
      int Initial_N = 8, 
      typename Alloc = std::allocator<T> 
    >
    struct indexable_stack_impl
    {
    public:
      typedef T value_type;
      typedef indexable_stack_impl self;  
    private:
      // local buffer type

      struct buffer {
        buffer(int n, int i = 0, buffer* x = NULL) : 
          size(n), index(i), prev(x), begin(a.allocate(n)), end(begin + n)
        { }
        ~buffer() { 
          a.deallocate(begin, size); 
        }
        template<typename Procedure>
        void for_each(Procedure& proc, T* end) {
          if (prev != NULL) {
            prev->for_each(proc, prev->end);
          }
          T* p = begin;
          while (p != end) {
            proc(*p++);
          }
        }
        int index; 
        int size;
        T* begin;
        Alloc a; 
        T* end;
        buffer* prev;
      };  
    private:
      // begin fields 

      buffer* buff;
      T* last;
      int cnt;
      int cap;
      int init;
    public:
      indexable_stack_impl() { 
        initialize(Initial_N);
      }
      indexable_stack_impl(self& x) { 
        initialize(x.capacity());
        x.for_each(stacker(*this));
      }
      indexable_stack_impl(int nsize, const T& x = T()) { 
        if (nsize >= Initial_N) {
          initialize(nsize);
        }
        else {
          initialize(Initial_N);      
        }    
        last = buff->begin + nsize;
        while (cnt < nsize) {
          buff->a.construct(buff->begin + cnt++, x);
        }
        assert(last == buff->begin + cnt);
      }
      ~indexable_stack_impl() { 
        while (cnt > 0) {      
          pop();
        }
        assert(buff != NULL);
        delete buff; 
      } 
      // implementation of OOTL Indexable

      T& operator[](int n) {
        if (n >= buff->index) { 
          return buff->begin[n - buff->index]; 
        }
        buffer* curr = buff->prev;
      loop:
        if (n >= curr->index) { 
          return curr->begin[n - curr->index]; 
        }
        curr = curr->prev;
        goto loop;
      }
      int count() const {
        return cnt;
      }
      // implementation of OOTL Stack concept

      void push(const T& x = T()) {
        assert(last >= buff->begin);
        assert(last <= buff->end);
        if (last == buff->end) {
          add_buffer();
        }
        buff->a.construct(last++, x);
        ++cnt;
      }
      void pop() {        
        assert(last >= buff->begin);
        assert(last <= buff->end);
        if (last == buff->begin) {
          remove_buffer();
        }
        assert(buff != NULL);
        buff->a.destroy(--last);          
        --cnt;
      }
      bool is_empty() {
        return count() == 0;
      }
      T& top() {
        return *(top_pointer());
      }
      // implementation of OOTL Iterable concept 

      template<typename Procedure>
      void for_each(Procedure& proc) {
        buff->for_each(proc, last);
      }  
    private:
      void initialize(int ncap) {
        assert(ncap >= Initial_N);
        buff = new buffer(ncap); 
        cnt = 0;
        cap = ncap;
        last = buff->begin;
      }
      T* top_pointer() {
        assert(!is_empty());
        assert(last >= buff->begin);
        assert(last <= buff->end);
        if (last == buff->begin) {
          return buff->prev->end - 1; 
        }
        else {
          return last - 1;
        }    
      }
      void add_buffer() {
        buff = new buffer(buff->size * Factor_N, cap, buff);
        cap += buff->size;
        last = buff->begin;
        assert(count() < capacity());
      }    
      void remove_buffer() {
        buffer* tmp = buff;
        cap -= buff->size;
        buff = buff->prev;
        tmp->prev = NULL; 
        last = buff->end;
        delete(tmp);
      }    
      int capacity() const {
        return cap;     
      }
    };
    
    ///////////////////////////////////////////////////////////////

    // A stack_extension contains additional functions which 

    // can be easily derived from a stack

    
    template
    <
      typename Implementation,
      typename Inherited 
    >
    struct stack_extension : Inherited
    {
      // public typedef

      typedef Inherited inh;
      typedef Implementation impl;
      typedef typename inh::value_type value_type;
      
      // constructors

      stack_extension() : inh() { }
      stack_extension(impl& x) : inh(x) { }
      stack_extension(int nsize, const value_type& x = value_type()) : 
                                                       inh(nsize, x) { }
    
      // implementation of OOTL Growable concept

      void grow(int n = 1, const value_type& x = value_type()) {      
        while (n > 0) inh::push(x);
      } 
      // implementation of OOTL Shrinkable concept

      void shrink(int n = 1) {      
        while (n--) inh::pop();
      }  
      // implementation of OOTL Resizable concept  

      void resize(int n, const value_type& x = value_type()) {      
        while (n > inh::count()) inh::push(x);
        while (n < inh::count()) inh::pop();
      }    
      // implementation of OOTL Sortable concept

      bool lt(int i, int j) {
        return inh::operator[](i) < inh::operator[](j);
      }
      void swap(int i, int j) {
        std::swap(inh::operator[](i), inh::operator[](j));
      }
      // utility functions

      void clear() {
        while (!inh::is_empty()) {
          inh::pop();
        }
      }
      void dup() {
        inh::push(inh::top());
      }
      void reverse() {
        int max = inh::count() - 1;
        int n = inh::count() / 2;
        for (int i=0; i < n; ++i) {
          inh::swap(i, max - i);
        }
      }
    };
    
    ///////////////////////////////////////////////

    // The contract checks the preconditions and 

    // postconditions of the functions 

    
    template
    <
      typename Implementation,
      typename Inherited 
    >
    struct stack_contract : Inherited
    {
      // public typedef

      typedef Inherited inh;
      typedef Implementation impl;
      typedef typename inh::value_type value_type;
      
      // constructors

      stack_contract() : inh() { }
      stack_contract(impl& x) : inh(x) { }
      stack_contract(int nsize, value_type x = value_type()) 
        : inh(nsize, x) { }
      
      // public functions

      void pop() {
        int old = inh::count();
        assert(!inh::is_empty());
        inh::pop();
        assert(count() == old - 1);
      }  
      void push(const value_type& x) {
        int old = inh::count();
        inh::push(x);
        assert(inh::count() == old + 1);
      }
      value_type& top() {
        assert(!inh::is_empty());
        value_type& ret = inh::top();
        value_type& tmp = inh::operator[](inh::count() - 1);
        assert(&ret == &tmp);
        return ret;
      }
      int count() {
        int ret = inh::count();
        assert(ret >= 0);
        assert(ret > 0 ? !inh::is_empty() : inh::is_empty());
        return ret;
      }
      bool is_empty() {
        bool ret = inh::is_empty();
        assert(ret ? inh::count() == 0 : inh::count() > 0);
        return ret; 
      }
      value_type& operator[](int n) {      
        assert(n >= 0);
        assert(n < inh::count()); 
        return inh::operator[](n);    
      }
    };
    
    /////////////////////////////////////////////////////////

    // The final version of the stack

    
    #ifndef _NDEBUG
      template
      <
        typename T, 
        typename Implementation = indexable_stack_impl<T>, 
        typename Contract = stack_contract<Implementation, Implementation>,
        typename Extension = stack_extension<Implementation, Contract>
      >
      struct stack : Extension
      {     
        typedef Implementation impl;
        typedef Extension inh;
        stack() : inh() { }
        stack(impl& x) : inh(impl& x) { }
        stack(int nsize, const T& x = T()) : inh(nsize, x) { }
      };
    #else 
      template
      <
        typename T, 
        typename Implementation = indexable_stack_impl<T>,
        typename Extension = stack_extension<Implementation, Implementation>
      >
      struct stack : Extension
      {     
        typedef Implementation impl;
        typedef Extension inh;
        stack() : inh() { }
        stack(impl& x) : inh(x) { }
        stack(int nsize, const T& x = T()) : inh(nsize, x) { }
      };
    #endif
}
#endif

Final words

Unfortunately, the code will not work as-is for versions of Visual C++ earlier than 7.1. You'll have to do some trimming to make it work. The code is public domain, so feel free to do what you want with it. I'd always be appreciative though of a quick note on the forum, just to let me know what kind of application this code finds a home in, it'll make me happy to know. If you want to release a more portable version, I'm sure other readers will appreciate it greatly!