next up previous contents index
Next: Sorted Sequences ( sortseq Up: Dictionary Types Previous: Maps ( map )   Contents   Index


Two-Dimensional Maps ( map2 )

Definition

An instance M of the parameterized data type map2<I1,I2,E> is an injective mapping from the pairs in I1 x I2 , 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, j) to denote the variable indexed by (i, j) and we use dom(M) to denote the set of ``used indices''. This set is empty at the time of creation and is modified by map2 accesses.

Related data types are map, d_arrays, h_arrays, and dictionaries.

#include < LEDA/core/map2.h >

Types

map2< I1,I2,E> ::item the item type.

map2< I1,I2,E> ::index_type1 the first index type.

map2< I1,I2,E> ::index_type2 the second index type .

map2< I1,I2,E> ::element_type the element type.

Creation

map2< I1,I2,E> M creates an injective function m from I1 x I2 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 stays undefined) and dom(M) to the empty set, and initializes M with m .

map2< I1,I2,E> M(E x) creates an injective function m from I1 x I2 to the set of unused variables of type E , sets xdef to x and dom(M) to the empty set, and initializes M with m .

Operations

E& M(const I1& i, const I2& j)
    returns the variable M(i) .

bool M.defined(const I1& i, const I2& j)
    returns true if i $ \in$ dom(M) and false otherwise.

void M.clear() clears M by making dom(M) the empty set.

Implementation

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


next up previous contents index
Next: Sorted Sequences ( sortseq Up: Dictionary Types Previous: Maps ( map )   Contents   Index
Christian Uhrig 2017-04-07