tpl_dynSkipList.H File Reference

Dynamic ordered set implemented with a Skip List. More...

#include <climits>
#include <ctime>
#include <utility>
#include <initializer_list>
#include <gsl/gsl_rng.h>
#include <ah-errors.H>
#include <ah-args-ctor.H>
#include <ahDry.H>
#include <ahFunctional.H>
#include <ahIterator.H>
#include <ah-iterator.H>
#include <ah-dry.H>

Include dependency graph for tpl_dynSkipList.H:

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

Go to the source code of this file.

Classes
class	Aleph::DynSkipList< Key, Compare >
	Dynamic ordered set implemented with a Skip List. More...
struct	Aleph::DynSkipList< Key, Compare >::Node
	Internal node structure. More...
class	Aleph::DynSkipList< Key, Compare >::Iterator
	Forward iterator for DynSkipList. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Detailed Description

Dynamic ordered set implemented with a Skip List.

DynSkipList<Key, Compare> is a dynamic set that automatically manages memory for its elements. It uses a Skip List as the underlying data structure, providing expected O(log n) time for search, insert, and delete operations.

Features

• Automatic memory management (RAII)
• Expected O(log n) for all operations
• Simple implementation (no rotations like balanced trees)
• Good cache locality for sequential access
• Functional programming operations (map, filter, fold, etc.)

Comparison with DynSetTree

• DynSkipList uses randomization; DynSetTree uses deterministic balancing
• Skip lists are simpler to implement and reason about
• Both provide O(log n) operations (expected vs worst-case)
• Skip lists are easier to make concurrent (not implemented here)

The class internally uses the gsl random number generator of GSL - GNU Scientific Library. By default, the Mersenne twister is used and the seed is taken from system time.

See also

DynSetTree DynSetHash

Pugh, W. "Skip Lists: A Probabilistic Alternative to Balanced Trees" (1990)

Author

Leandro Rabindranath León

Definition in file tpl_dynSkipList.H.