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/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[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(I i)	returns true if i $\in$ dom(M).
void	M.clear()	makes M empty.
void	M.clear(E x)	makes M empty and sets xdef to x.

Iteration:

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

forall_defined(i, M) { ``the indices in dom(M) are successively assigned to i'' }.
Precondition I must be an integer or pointer type.

Implementation

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