A Fast Indexable Stack

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 case, rather than O(N) complexity of std::vector. The ootl::stack template also provides fast indexing, outperforming std::deque by as much as 6x or more in some cases.

The Interface

The following is a simplified interface of the ootl::stack template.

  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);
  };
  

back to the OOTL documentation home page
back to the OOTL.org home page

http://www.ootl.org
last modified: November 13, 2005
Copyright Christopher Diggins, 2005
OOTL logo copyright 2005 Paige Lybbert.