next up previous contents index
Next: Two-Dimensional Maps ( map2 Up: Dictionary Types Previous: Hashing Arrays ( h_array   Contents   Index


Maps ( map )

Definition

An instance M of the parameterized data type map<I,E> is an injective mapping from the data type I, called the index type of M, to the set of variables of data type E, called the element type of M. I must be a pointer, item, or handle type or the type int. We use M(i) to denote the variable indexed by i. All variables are initialized to xdef, an element of E that is specified in the definition of M. A subset of I is designated as the domain of M. Elements are added to dom(M) by the subscript operator; however, the domain may also contain indices for which the access operator was never executed.

Related data types are d_arrays, h_arrays, and dictionaries.

#include < LEDA/core/map.h >

Types

map<I,E>::item the item type.

map<I,E>::index_type the index type.

map<I,E>::element_type the element type.

Creation

map<I,E> M creates an injective function m from I to the set of unused variables of type E, sets xdef to the default value of type E (if E has no default value then xdef is set to an unspecified element of E), and initializes M with m.

map<I,E> M(E x) creates an injective function m from I to the set of unused variables of type E, sets xdef to x, and initializes M with m.

map<I,E> M(E x, int table_sz) as above, but uses an initial table size of table_sz instead of the default size 1.

Operations

E& M[const I& i] returns the variable M(i) and adds i to dom(M). If M is a const-object then M(i) is read-only and i is not added to dom(M).

bool M.defined(const I& i) returns true if i $\in$ dom(M).

void M.clear() makes M empty.

void M.clear(const E& x) makes M empty and sets xdef to x.

void M.set_default_value(const E& x)
    sets xdef to x.

E M.get_default_value() returns the default value xdef.


Iteration:

forall(x, M) { ``the entries M[i] with i $\in$ dom(M) are successively assigned to x'' }

Note that it is not possible to iterate over the indices in dom(M). If you need this feature use the type h_array instead.


Implementation

Maps are implemented by hashing with chaining and table doubling. Access operations M[i] take expected time O(1).


next up previous contents index
Next: Two-Dimensional Maps ( map2 Up: Dictionary Types Previous: Hashing Arrays ( h_array   Contents   Index