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 >
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. |
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'' }
Implementation
Maps are implemented by hashing with chaining and table doubling. Access operations M[i] take expected time O(1).