skiprope.h File Reference

This file defines the skiprope container class. More...

#include <stdlib.h>
#include <new>
#include <vector>
#include <portable_io.h>

Include dependency graph for skiprope.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	skiprope< T >
	An vector-like collection<T> which is implemented in such a way that no large blocks of memory are created. This allows inserts and deletes to be done in a time which is proportional to the size of the block being acted upon -- rather than upon the whole size of the container. To pay for _this_ performance gain, random accesses within the vector require O(ln(N)) time rather than O(1) as you usually see in a vector. Iteration is still O(1) but is much slower than iteration in a vector<T>. More...
struct	node_info
	A structure describing a node in the rope. It is used in navigating the node data structure more easily than keeping track of the separate components of the description. More...
class	skiprope_const_iterator< T >
	A skiprope iterator simulates a pointer to type const T. The iterator knows about the structure of a skiprope. It knows that a skiprope is a linked list of nodes of varying widths. More...
class	skiprope_iterator< T >
	A skiprope iterator simulates a pointer to type T. The iterator knows about the structure of a skiprope. It knows that a skiprope is a linked list of nodes of varying widths. More...
struct	skiprope_level_desc< T >
class	skiprope_node< T >
	A skiprope_node is a chunk of a skiprope<T>. Each node is a vector<T> and the number of T's in the vector varies from node to node. The start position of any given node is equal to the sum of the nodes before it. More...
struct	link_info
Namespaces
namespace	cxxtls
	The namespace that encapsulates most of the functionality in the CXX toolkit.

---

Detailed Description

This file defines the skiprope container class.

A skiprope<T> is very large vector of T's which can be iterated over and which has ln(N) insertion, removal, and positioning characteristics. Once an iterator is found for a given position within the vector, inc'ing and dec'ing it are O(1), but Adding a specific amount to it is O(N).

The memory utilization of an empty skiprope<T> is quite high, so don't bother using this container if you need to save every byte of memory -- it is meant to give fast inserts and deletes in large vector situations.

Note that every insert or erase to the skiprope invalidates all iterators into the rope. This is a vector, not a list.

Definition in file skiprope.h.