

An "associative array" is a data structure that acts like a onedimensional array of unbounded size whose subscripts are not restricted to integral types: it associates values of one type with values of another type (the two types may be the same). Such data structures are common in AWK and SNOBOL4 but unusual in languages such as C, which have traditionally concentrated on lowerlevel data structures.
Suppose that m is an associative array, or map, whose subscripts, or keys, are of type String and whose elements, or values, are integers. Suppose further that s and t are String variables. Then m[s] is an int called "the value associated with" s. In this example m[s] is an lvalue: it may be used on either side of an assignment. If s and t are equal, m[s] and m[t] are the same int object. If s and t are unequal, m[s] and m[t] are different objects.
This is exactly analogous to the way ordinary arrays work in most languages, except that it is much harder to preallocate enough memory in advance to contain all relevant elements. Thus some kind of dynamic memory scheme is necessary to allow a map to accommodate all its elements.
C data structures do not expand automatically, and no such expanding structures are built into C++ either. But C++ is extensible: although it does little to provide highlevel data structures by itself, it makes it possible to implement such structures in ways that are easy to use.