Click here to Skip to main content
Click here to Skip to main content

Fast Indexable Stacks

, 19 Nov 2005 Public Domain
Rate this:
Please Sign up or sign in to vote.
I provide an implementation of fast-growing indexable stacks which outperforms std::vector and std::deque.

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 <span class="code-keyword"><cstdlib>
</span>
#include <span class="code-keyword"><cassert>
</span>
#include <span class="code-keyword"><memory>
</span>
#include <span class="code-keyword"><algorithm>
</span>
#include <span class="code-keyword"><iostream>
</span>

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!

License

This article, along with any associated source code and files, is licensed under A Public Domain dedication

Share

About the Author

Christopher Diggins
Software Developer Autodesk
Canada Canada
This article was written by Christopher Diggins, a computer science nerd who currently works at Autodesk as an SDK specialist.
Follow on   Twitter   Google+   LinkedIn

Comments and Discussions

 
QuestionHow to limit stack size? Pinmemberfilippov.anton28-Jun-06 0:45 
GeneralBug (of sorts) PinmemberStewart Tootill23-Nov-05 5:50 
GeneralRe: Bug (of sorts) PinmemberChristopher Diggins23-Nov-05 7:01 
GeneralPreallocation, virtual memory is your friend! PinmemberPedroMC23-Nov-05 0:32 
GeneralNot understand Pinmemberjesusdesantos22-Nov-05 12:56 
GeneralRe: Not understand PinmemberChristopher Diggins23-Nov-05 4:57 
QuestionFaster indexing and is Destruct/CopyConstruct really necessary? PinmemberSimon Hofverberg22-Nov-05 0:16 
AnswerRe: Faster indexing and is Destruct/CopyConstruct really necessary? PinmemberChristopher Diggins22-Nov-05 4:06 
GeneralRe: Faster indexing and is Destruct/CopyConstruct really necessary? PinmemberSimon Hofverberg23-Nov-05 3:17 
GeneralRe: Faster indexing and is Destruct/CopyConstruct really necessary? PinmemberChristopher Diggins23-Nov-05 4:54 
QuestionWhat about iterators? PinmemberWREY21-Nov-05 3:16 
AnswerRe: What about iterators? PinmemberChristopher Diggins21-Nov-05 3:20 

WREY wrote:
Does this mean iterators are never invalidated even as growth occurs?

 
That is correct, though I haven't supplied code for iterators. You can't use a simple pointer as you might with a std::vector, you have to use something a little more sophisticated.
 
Christopher Diggins

GeneralRe: interesting, but not enough PinmemberChristopher Diggins21-Nov-05 3:34 
GeneralRe: interesting, but not enough PinmemberCraig Muller21-Nov-05 9:11 
GeneralRe: interesting, but not enough PinmemberChristopher Diggins21-Nov-05 14:32 
GeneralRe: interesting, but not enough Pinmemberbonadt23-Nov-05 23:16 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web02 | 2.8.141015.1 | Last Updated 19 Nov 2005
Article Copyright 2005 by Christopher Diggins
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid