VList

VList is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Data Structure
This illustrates a data structure, a means of storing data within a program.

You may see other such structures in the Data Structures category.

This page uses content from Wikipedia. The original article was at VList. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)

In computer science, the VList is a persistent data structure that combines the fast indexing of arrays with the easy extension of cons-based (or singly-linked) linked lists.

Like arrays, VLists have constant-time lookup on average and are highly compact, requiring only O(log n) storage for pointers, allowing them to take advantage of locality of reference. Like singly-linked or cons-based lists, they are persistent, and elements can be added to or removed from the front in constant time. Length can also be found in O(log n) time.

The primary operations of a VList are:

• Locate the kth element (O(1) average, O(log n) worst-case)
• Add an element to the front of the VList (O(1) average, with an occasional allocation)
• Obtain a new array beginning at the second element of an old array (O(1))
• Compute the length of the list (O(log n))

The primary advantages VLists have over arrays are that they are threadsafe (when locking is used; see the discussion page) and that different updated versions of the VList automatically share structure. Because VLists are immutable, they are most useful in functional programming languages, where their efficiency allows a purely functional implementation of data structures traditionally thought to require mutable arrays, such as hash tables.

However, VLists also have a number of disadvantages over their competitors:

• While immutability is a benefit, it is also a drawback, making it inefficient to modify elements in the middle of the array.
• Access near the end of the list can be as expensive as O(log n); it is only constant on average over all elements. This is still, however, much better than performing the same operation on cons-based lists.
• Wasted space in the first block is proportional to n. This is similar to linked lists, but there are data structures with less overhead. When used as a fully persistent data structure, the overhead may be considerably higher and this data structure may not be appropriate.

C++

This example is incorrect. Please fix the code and remove this message. Details: It only shows the declaration of the operations, not the implementation of them.

OOTL Implementation

<lang cpp>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();

};</lang>