Go to the first, previous, next, last section, table of contents.
Maps support associative array operations (insertion, deletion, and
membership of records based on an associated key). They require
the specification of two types, the key type and the contents type.
These are currently implemented in several ways, differing in
representation strategy, algorithmic efficiency, and appropriateness for
various tasks. (Listed next to each are average (followed by worstcase,
if different) time complexities for [a] accessing (via op [],
contains), [d] deleting elements).
AVLMaps

implement ordered Maps via threaded AVL trees
([a O(log n)], [d O(log n)]).
RAVLMaps

Similar, but also maintain ranking information, used via
ranktoPix(int r)
, that returns the Pix
of the
item at rank r, and rank(key)
that returns the
rank of the corresponding item.
([a O(log n)], [d O(log n)]).
SplayMaps

implement ordered Maps via Sleator and Tarjan's (JACM 1985)
splay trees. The algorithms use a version of "simple topdown
splaying" (described on page 669 of the article).
(Amortized: [a O(log n)], [d O(log n)]).
VHMaps

implement unordered Maps via hash tables.
The tables are automatically resized when their capacity is exhausted.
([a O(1)/O(n)], [d O(1)/O(n)]).
CHMaps

implement unordered Maps via chained hash tables.
([a O(1)/O(n)], [d O(1)/O(n)]).
The different implementations differ in whether their constructors
require an argument specifying their initial capacity. Initial
capacities are required for hash table based Maps. If none is
given DEFAULT_INITIAL_CAPACITY
(from `<T>defs.h') is
used.
All Map classes share the following operations (for some Map class,
Map
instance d
, Pix ind
and key variable k
,
and contents variable x
).
Pixbased operations are more fully described in the section
on Pixes. See section Pseudoindexes
Map d(x); Map d(x, int initial_capacity)

Declare d to be an empty Map. The required argument, x, specifies
the default contents, i.e., the contents of an otherwise
uninitialized location. The second version, specifying
initial capacity is allowed for Maps with an initial capacity
argument.
d.empty()

returns true if d contains no items.
d.length()

returns the number of items in d.
d[k]

returns a reference to the contents of item with key k. If no
such item exists, it is installed with the default contents.
Thus d[k] = x installs x, and x = d[k] retrieves it.
d.contains(k)

returns true if an item with key field k exists in d.
d.del(k)

deletes the item with key k.
d.clear()

deletes all items from the table.
x = d.dflt()

returns the default contents.
k = d.key(ind)

returns a reference to the key at Pix ind.
x = d.contents(ind)

returns a reference to the contents at Pix ind.
ind = d.first()

returns the Pix of the first element in d, or 0 if d is empty.
d.next(ind)

advances ind to the next element, or 0 if there are no more.
ind = d.seek(k)

returns the Pix of element with key k, or 0 if k is not in d.
Go to the first, previous, next, last section, table of contents.