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
Iteration:
forall(x, M ) { ``the entries M[i] with i 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) .