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 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: Sorted Sequences ( sortseq Up: Dictionary Types Previous: Maps ( map )   Contents   Index
Christian Uhrig 2017-04-07