ootl::vlist

The ootl::vlist is an implementation of a data structure called the Vlist described in the paper Fast Functional Lists, Hash-Lists, Deques and Variable Length Arrays by Phil Bagwell. The Vlist is implemented 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 one time, no deallocation occurs, and 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 average, random element access with constant complexity. The key to achieving indexing with O(1) complexity the list must be traversed from the biggest node to the smallest.

One of the other important advantages of a Vlist is that memory locations remain fixed as the structure grows. This makes it a very useful data-structure when the number of elements is not known in advance.

Analyzing the Complexity of Indexing

The Vlist is able to provide constant indexing complexity in the average case due to the fact that the array sizes have a decreasing geometric relationship. Specifically the Vlist 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 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 an attempt to explain the math: 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

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

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

Implementation

The ootl::vlist is intended to be implemented by higher-level collection classes such as ootl::stack and ootl::hash_map. Here is the interface of ootl::vlist in a nutshell:

  template
  <
    typename T,
    int Factor_N = 2,
    int Initial_N = 8
  >
  struct vlist
  {
  public:
    typedef T value_type;
    typedef vlist self;

  protected:
    struct buffer {
      size_t index;
      size_t size_minus_one;
      size_t size;
      T* begin;
      T* end;
      buffer* prev;
      buffer* next;
    };

    struct iterator {
      typedef iterator self;
      typedef T value_type;
      iterator(buffer* x, T* y);
      iterator(const iterator& x);
      self& operator+=(size_t n);
      self operator+(size_t n);
      self& operator-=(size_t n);
      self operator-(size_t n);
      self& operator++();
      self& operator--();
      self operator++(int);
      self operator--(int);
      bool operator==(const self& x);
      bool operator!=(const self& x);
      bool operator<(const self& x);
      T& operator*();
    };

    struct reverse_iterator {
      // same as iterator
    };

  private:
    buffer* buff;
    size_t cap;

  public:
    vlist();
    ~vlist();
    buffer* get_first_buffer();
    buffer* get_last_buffer();
    T* get_pointer(size_t n);
    size_t capacity() const;
    void initialize(size_t n);
    void add_buffer();
    void add_buffer(buffer* x);
    void remove_buffer();
    void clear();
    iterator begin();
    iterator end();
    reverse_iterator rbegin();
    reverse_iterator rend();
  };

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.