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).