*** UNIX MANUAL PAGE BROWSER ***

MAP(3+) MAP(3+) NAME map - associative array classes SYNOPSIS #include <Map.h> Mapdeclare(S,T) Mapimplement(S,T) struct Map(S,T) { Map(S,T)(); Map(S,T)(const T&); Map(S,T)(const Map(S,T)&); ~Map(S,T); Map(S,T)& operator= (const Map(S,T)&); T& operator[] (int); int size(); Mapiter(S,T) element(const S&); Mapiter(S,T) first(); Mapiter(S,T) last(); }; struct Mapiter(S,T) { Mapiter(S,T) (const Map(S,T)&); ~Mapiter(S,T); operator int(); S key(); T value(); Mapiter(S,T)& operator++ (Mapiter(S,T)&); Mapiter(S,T)& operator-- (Mapiter(S,T)&); }; DESCRIPTION A map is a collection of elements, each of which contains a key part of type S and a value part of type T, where S and T are type names. Both S and T must have value semantics: assignment or initialization have the effect of copying. (It is unlikely for S and T to be pointers.) Map elements are ordered by key: type S must have a transitive boolean operator<. The macro call declares the classes Map(S,T) and Mapiter(S,T). It must appear once in every source file that uses either. The macro call Mapimplement(S,T) defines the functions that implement the map classes. It must appear exactly once in the entire program. Map constructors Map(S,T)() An empty map. The value part of future elements is the value of an otherwise uninitialized static object of type T . Map(S,T)(x) An empty map whose future elements have default value x . Map(S,T)(m) A copy of map m obtained by copying the elements and de- fault value of m. Map operators n = m All the elements of map n are deleted and and copies of the elements of m are added. The default value of n does not change. Running time is O(log(|m|) + log(|n|)), where |m| means m.size(). m[k] A reference to the value part of the element of map m with key k. If the element does not exist, it is created. Run- ning time is O(log(|m|)). Other Map functions m.size() The number of elements in Running time is O(1). m.element(k) A map iterator referring to the element of m with key k if such an element exists. Otherwise the result is vacuous. Running time is O(log(|m|)). m.first() m.last() A map iterator referring to the element of m with the smallest (or largest) key. If has no elements, the result is vacuous. Running time is O(log(|m|)). Map iterators For every class Map(S,T) there is a class Mapiter(S,T). A map iterator identifies a map object and possibly an element in that map. An itera- tor that does not identify an element is vacuous. Mapiter constructors Mapiter(S,T)(m) A vacuous iterator referring to map m. Running time is O(1). Mapiter operators i = j Make iterator i refer (for now) to the same map as does j. (int)i Zero if iterator i is vacuous, otherwise nonzero. ++i --i If iterator i is vacuous, make it refer to the map element with the smallest (or largest) key Otherwise, make it refer to the map element with the next key greater (or less) than the key of the current element. If no such element exists, i becomes vacuous. The running time of a single increment operation for map m is O(log(|m|)). However an iterator takes only time O(|m|) to sequence through the whole map. Other mapiter functions i.key() i.value() The key (or value) part of the element referred to by i . If i is vacuous, return the value of an otherwise unini- tialized static object of appropriate type. Running time is O(1). EXAMPLES struct city { char name[100]; }; typedef int population; int operator< (const city&, const city&); Mapdeclare(name,population) Map(name,population) gazetteer; // Print big cities; set populations of others to zero. for(Mapiter(name,population) i = gazetteer.first(); i; i++) if(i.value() > 1000000) printf("%s\n", i.key().name); else gazetteer[i.key()] = 0; BUGS A `type name' Map(S,T) or Mapiter(S,T) that contains spaces will be mangled by cpp(8). There is no way to delete a single element. Ambiguities can occur if the type name S contains an underscore. No precautions are taken against running out of memory. MAP(3+)