Iterators

Every map class Map<K,V> has a companion "map iterator" class Mapiter<K,V> which is useful for extracting elements from a map. A map iterator refers to a particular map and optionally to a particular element of that map. For example:

   Map<String,int> m;
   Mapiter<String,int> mi(m);

These declarations create a map m and an iterator mi that can refer to an element of m. We did not specify any element in this example, so mi doesn't refer to one right now. Thus we call mi vacuous.

We can make mi identify the element of m with key k by saying:

   mi = m.element(k);

If m[k] exists, mi now identifies it; otherwise mi is vacuous.

Thus we see that element actually yields an iterator. We can tell whether an iterator is vacuous by using it as the subject of a test:

   if (mi)
           // mi is not vacuous

Assigning a map to an iterator yields a vacuous iterator. Thus, after executing:

   mi = m;

mi is a vacuous iterator referring to m.

The remove function can also be used on an iterator:

   mi.remove();

This removes the element referred to by mi from the map. If mi is vacuous, there is no change to the map.

Map elements are always kept sorted by key. Thus it makes sense to ask about the lowest and highest keys. For a map m, m.first() is an iterator that refers to the first element (the element with the lowest key) and m.last() is an iterator that refers to the last element (the element with the highest key). If m is empty, both m.first() and m.last() are vacuous.

If mi refers to an element, mi.next() makes mi refer to the element whose key immediately follows the current one. Similarly mi.prev() makes mi refer to the immediately preceding key.

If mi is vacuous, mi.next() effectively assigns m.first() to mi and mi.prev() effectively assigns m.last() to mi. If mi refers to m.last(), mi.next() makes mi vacuous, and if mi refers to m.first(), mi.prev() makes mi vacuous. Thus we can think of all the keys in a map as being circularly connected, with a vacuous ``key'' marking a starting (and ending) point in the circle.

At this point we know at least two ways to refer to every element in a map:

   for (Mapiter<K,V> mi = m.first(); mi; mi.next())
           // do something with mi

or

   for (Mapiter<K,V> mi = m; mi.next(); )
           // do something with mi

but we need a way to get at the key and value parts of the element referenced by mi. To this end, map iterators have a member function called curr() which returns a pointer to a Map_pair. Map_pair has data fields key and value that can be accessed directly. Thus we might write:

   for (Mapiter<K,V> mi = m.first(); mi; mi.next()) {
           K k = mi.curr()->key;
           V v = mi.curr()->value;
           // do something}

If mi is vacuous, mi.curr() returns a null pointer.

In addition, the functions next() and prev() also return a pointer to a Map_pair object, so we can write:

   Map_pair<K,V>* mp;
   for (Mapiter<K,V> mi = m; mp = mi.next(); ) {
           K k = mp->key;
           V v = mp->value;
           // do something}

Using the Mapiter functions that refer to the current Map_pair can make some operations on a Map faster. For example, the code for incrementing a Map element that was shown in the section, ``Using a Map'':

   if (m.element(word))
           m[word]++;
   else
           m[word] = 1;

can be done more efficiently this way:

   Map_pair<String,int>* mp;
   if (mp = m.element(word).curr())
           mp->value++;
   else
           m[word] = 1;

The value part of a Map_pair can be looked at or modified, but the key part cannot be modified.