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 one. 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:
std::vector = 1015 msec
std::deque = 734 msec
ootl::stack = 577 msec
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:
typedef T value_type;
typedef stack self;
stack();
stack(self& x);
stack(int nsize, const T& x = T());
~stack();
T& operator[](int n);
int count();
void push(const T& x = T());
void pop();
bool is_empty();
T& top();
tempate<Procedure>
void for_each(Procedure& p);
};
The Implementation
Here's the big ol' implementation:
#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:
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:
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;
}
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;
}
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());
}
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;
}
};
template
<
typename Implementation,
typename Inherited
>
struct stack_extension : Inherited
{
typedef Inherited inh;
typedef Implementation impl;
typedef typename inh::value_type value_type;
stack_extension() : inh() { }
stack_extension(impl& x) : inh(x) { }
stack_extension(int nsize, const value_type& x = value_type()) :
inh(nsize, x) { }
void grow(int n = 1, const value_type& x = value_type()) {
while (n > 0) inh::push(x);
}
void shrink(int n = 1) {
while (n--) inh::pop();
}
void resize(int n, const value_type& x = value_type()) {
while (n > inh::count()) inh::push(x);
while (n < inh::count()) inh::pop();
}
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));
}
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);
}
}
};
template
<
typename Implementation,
typename Inherited
>
struct stack_contract : Inherited
{
typedef Inherited inh;
typedef Implementation impl;
typedef typename inh::value_type value_type;
stack_contract() : inh() { }
stack_contract(impl& x) : inh(x) { }
stack_contract(int nsize, value_type x = value_type())
: inh(nsize, x) { }
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);
}
};
#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!
