Basic Data Structures

All basic OGDF data structures are C++ templates allowing arbitrary element-types.
This page already contains some class names as they will appear in the next release (Bubinga). The current names for Jacaranda are also given.

Predefined Elements
`String`
`Tuple2`, `Tuple3`, `Tuple4`	simple structures combining multiple (2-4) data elements into one large unit. Useful when using tuples as data elements of lists, etc.
Arrays
`Array`	dynamic array which allows resizing, size queries, and arbitrary array bounds. Supports bound checking in Debug mode
`Array2D`	2-dimensional variant of `Array`
Lists
`List`	doubly-linked list; allows constant time size queries
`ListPure`	doubly-linked list
`SList`	singly-linked list; allows constant time size queries
`SListPure`	singly-linked list
Buffers, Stacks, Queues
`ArrayBuffer`	array-based stack which allows traditional array operations and supports resizing
`Queue`	list-based queue
`Stack`	list-based stack
`BoundedQueue`	array-based, fixed-size queue
`BoundedStack`	array-based, fixed-size stack
Heaps, Priority Queues
`BinaryHeap`	binary heap implementing a full priority queue interface, i.e., key/data separation, decrease key, etc.
`MinHeap`	binary heap tuned for efficiency on a smaller interface: key=data (i.e. data elements are themselves comparable), no decrease key operation
`Top10Heap`	a variant of `MinHeap` which always holds only the X (e.g. X=10) elements with the highest keys
Others
`Hashing`	dynamically resizing hash-table, using open hashing (aka. hashing with chaining)
`HashArray`	a simplified `Hashing` interface offering array-syntax
`HashArray2D`	2-dimensional variant of `HashArray`
`Skiplist`	randomized skip list (the stored elements are pointers)

tech/basicds.txt · Last modified: 14:10 12.02.2008 by carsten

This page is driven by DokuWiki