Map(3C++)


Map -- Parameterized variable-size associative arrays

Synopsis

   #include <Map.h>
   #include <Mapio.h>
   namespace SCO_SC {
   

template <class T,class V> class Map{ public: // Constructors, destructor Map(); Map(const V& u); ~Map(); // Copy and assign Map(const Map<T,V>& m); Map<T,V>& operator=(const Map<T,V>& m); // Insert and remove elements V& operator[](const T& t); int remove(const T& t); void make_empty(); // Length int size()const; // Iterating Mapiter<T,V> element(const T& t)const; Mapiter<T,V> first()const; Mapiter<T,V> last()const; }; // Stream insertion template <class T,class V> ostream& operator<<(ostream& os, Map<T,V>& m); // Structure used by Mapiter template <class T,class V> struct Map_pair{ const T key; V value; }; template <class T,class V> class Mapiter{ public: // Constructors, destructor Mapiter(const Map<T,V>& m); ~Mapiter(); // Copy and assign Mapiter(const Mapiter<T,V>& mi); Mapiter<T,V>& operator=(const Mapiter<T,V>& mi); // Check the attachment Map<T,V>* the_map(); // Test for vacuity operator void*()const; // Remove elements void remove(); // Map_pair functions Map_pair<T,V>* curr(); Map_pair<T,V>* next(); Map_pair<T,V>* prev(); }; }

Description

A Map<T,V> is a collection of elements, consisting of a key of type T and a value of type V. The elements of a Map all have distinct keys. Thus it must be possible to compare values of type T for equality. Moreover, Map elements are ordered by key, so T must have a strong total order relation defined by operator<. Additional requirements on T and V are described below.

Each Map carries a default value of type V. This is normally the value of an otherwise uninitialized static object of type V, but an alternate value can be specified when a Map is created by using the special constructor provided for this purpose. Default values are used to initialize newly-created elements (see Map<T,V>::operator[ ]).

Each Map type has an associated iterator type whose objects may be used for iterating over Map elements in key order.

T can be any type having:

V may be any type having:

Map<T,V>

Constructors, destructor

Map(); An empty Map whose default value is that of an otherwise uninitialized static object of type V. Runs in O(1).

Map(const V& u); An empty Map whose default value is u. Runs in O(1).

~Map(); Destructor. All iterators currently attached to this Map will be informed of the Map's destruction (see the function Mapiter<T,V>::the_map()). Runs in O(#iterators).

Copy and assign

Map<T,V>(const Map<T,V>& m); Copy constructor. Creates a copy of m, including its default value. Runs in O(m.size()).

Map<T,V>& operator=(const Map<T,V>& m); Assignment. Creates a copy of the elements of m, but not its default value. Runs in O(lnsize() + lnm.size()).

Insert and remove elements

V& operator[](const T& t); Returns a reference to the value part of the element with key t. If an element having this key does not exist, one is created and its value initialized with the default value for this Map. The element value can be changed by using the reference as the target of an assignment. Runs in O(lnsize()).

int remove(const T& t); Finds the element with key t and removes it. Returns 1 if the element was found and 0 otherwise. Any iterators that refer to the removed element will continue to refer to that element until they are incremented or decremented; that is, the removal appears "delayed" to such iterators (see the Example). Runs in O(lnsize()).

void make_empty(); Removes all elements. Behavior is undefined if there are any iterators attached to the Map.

Length

int size()const; The number of elements. Runs in O(1).

Iterating

Each of the following functions returns an iterator (see below) attached to this Map.

Mapiter<T,V> element(const T& t)const; The iterator refers to the element with key t. If no such element exists, the iterator will test as vacuous. Runs in O(lnsize()).

Mapiter<T,V> first()const; The iterator refers to the element with the lowest key. If the Map is empty, the iterator will test as vacuous. Runs in O(lnsize()).

Mapiter<T,V> last()const; The iterator refers to the element with the highest key. If the Map is empty, the iterator will test as vacuous. Runs in O(lnsize()).

Stream insertion

ostream& operator<<(ostream& os, Map<T,V>& m); Inserts an ASCII representation of m into os. The representation is in the form

       {[ key1 val1 ] [ key2 val2 ] ... [ keyn valn ]}

Notice that all the keys and values are separated by white space. Runs in O(size()).

Mapiter<T,V>

For each class Map<T, V>, there is a class Mapiter<T,V> whose objects, called iterators, are used for iterating over Map elements in key order. An iterator of type Mapiter<T,V> can only be attached to a Map of type Map<T,V>, and refers to a current element in that Map. Incrementing or decrementing an iterator normally makes the iterator refer to the next or previous element, respectively, in key order. Two special boundary cases exist, for which an iterator will test as vacuous (that is, for which operator void* will return zero). These are: (1) an iterator that has been incremented after returning the element with the highest key and (2) an iterator that has been decremented after returning the element with the lowest key. A vacuous iterator may be incremented or decremented to obtain the element with the lowest or highest key, respectively. The behavior of all iterator operations except the_map() are undefined when the Map to which an iterator is attached ceases to exist.

Constructors, destructor

Mapiter(const Map<T,V>& m); Creates a new iterator attached to Map m. The iterator is initially vacuous. Runs in O(1).

~Mapiter(); Destructor. Runs in O(#iterators).

Copy and assign

Copying or assigning a Mapiter creates a copy of its value.

Mapiter(const Mapiter<T,V>& mi); Copy constructor. Runs in O(1).

Mapiter<T,V>& operator=(const Mapiter<T,V>& mi); Assignment. Runs in O(#iterators).

Check the attachment

Map<T,V>* the_map(); Returns a pointer to the Map to which this iterator is attached, or 0 if there is no such Map (this will happen if the Map is destroyed). Runs in O(1).

Test for vacuity

operator void*()const; Returns zero if the iterator is vacuous. Runs in O(1).

Remove elements

void remove(); Removes the current element. If the iterator is vacuous, the Map is unchanged. This iterator (as well as any other iterators that refer to the current element) will continue to refer to the current element until they are incremented or decremented; that is, the removal appears "delayed" to such iterators (see the Example). Runs in O(lnsize()).

Map_pair functions

Map_pair<T,V>* curr();

Map_pair<T,V>* next();

Map_pair<T,V>* prev(); Returns a pointer to a Map_pair structure that the Mapiter refers to. The next function first advances the iterator, the prev function first moves the iterator back. If the iterator is vacuous, a zero pointer is returned.

Bugs

A core dump is likely if memory is exhausted unless the client has provided an error handler for operator new.

Example

The following program illustrates "delayed removal" (see Mapiter<T, V>::remove()). It prints is now the time ?.

       Map<String,int> m;
       m["now"];
       m["is"];
       m["the"];
       m["time"];
       Mapiter<String,int> mi(m), mj(m);
       while(mi.next() && mj.next()){
           mi.remove();
           cout << mj.curr()->key << ' ';
       }
       cout << '?';

References

String(3C++)
© 2004 The SCO Group, Inc. All rights reserved.
UnixWare 7 Release 7.1.4 - 25 April 2004