\manpage {map} {I,E} {Maps}
 
\definition
An instance $M$ of the parameterized data type \name\ 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$.
 
\creation M 
 
\create { }
   {
creates an injective function $a$ from $I$ to the set of unused variables of
type $E$, initializes all variables in the range of $a$ using the 
default constructor of type $E$ and assigns $a$ to $M$. }
 
 
\create {(E\ x)}
   {
creates an injective function $a$ from $I$ to the set of unused variables of
type $E$, assigns $x$ to all variables in the range of $a$ and initializes $M$
with $a$. }
 
 
\operations 2 4.5 
 
\arrop E\&  {I\ i}
         {  returns the variable $M(i)$. }
 
 
\op  bool defined {(I\ i)}
           {  returns true if $i \in dom(M)$, false otherwise; here
             $dom(M)$ is the set of all $i\in I$ for which $M[i]$ has
             already been executed. }
 
 
\implementation
Maps are implemented by hashing with chaining and table doubling. 
Access operations $M[i]$ take expected time $O(1)$. 
 
