Definition
An instance M of the parameterized data type map2<I1,I2,E> is an injective mapping from the pairs in I1x 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.
Creation
| map2<I1,I2,E> | M; | creates an injective function m from I1x 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 I1x 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(I1 i, I2 j) | returns the variable M(i). |
| bool | M.defined(I1 i, 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).