The Map Data Type

Benefits of the Map Data Type

The map is a data type that offers the following benefits:

• Data is maintained in a sorted state.
• Because of this, data access is fast: time to access an element is proportional to log(n) where n is the number of elements in the map.
• Insertions and deletions are also fast (proportional to log(n)). (they do not require data to be moved)
• Iterators are valid under most changes. Inserting new elements does not invalidate an iterator, and deleting elements (besides the one the iterator refers to) does not invalidate an iterator.
• They are a convenient way of storing indexed data. For example, if we wanted to store data indexed by names (or in fact anything besides consecutive integers), the map structure is ideal.

Binary Search Trees and C++ Maps

C++ maps are internally represented as binary search trees. While the standard does not require this, it is implicit in the performance requirements for the data type. Roughly speaking, a binary tree consists of several nodes that obey the following rules:

• There is a key data type with a total ordering. Common examples include numbers ordered by size, strings ordered lexically, year/month/date triples ordered chronologically.
• A node consists of a search key (for example, a student ID number) and data (for example, a students academic record) For the rest of this discussion, we will refer to a nodes key as node.key and the nodes data as node.data
• One node is the root node of the tree
• Each node may have up to two child nodes, node.left and node.right
• For each node, node.left.key < node.key < node.right.key
• The above rule implies that there are no cycles.

Here's a schematic that shows what a tree might ``look'' like. In this example, the search keys are lower case letters, and there is no data attached to each key. The node with key k is the root node. The other nodes are arranged so that the left node always precedes its parent, and th right node always succeeds its parent.

                  k
                /   \
               d     n
              / \   / \
             a   f  l  o
              \         \
               c         z

As you can see, this structure makes searching for data very easy. (One can deduce the algorithm by looking at the above diagram)

In C++, trees have more requirements. The requirements gaurantee that the insertion and deletion algorithms are good enough that the tree is not left in an unbalanced state. (the log(n) lookup requirement in itself implies that balancing algorithms must be used) Here's an example of a tree that's in an unbalanced state:

                     k
                    / \
                   j   m
                  /
                 h
                /
               c
              /
             b
	 

The two commonly used Balanced binary search trees are known as AVL trees and Red/black trees. Further discussion on trees is beyond the scope of this discussion. For further reading, try Introduction to Algorithms, Cormen et al.

Pairs

The map datatype requires two data types -- one for tekys and one for values. So this raises a question: what data type does a map store ? The answer is that it stores a custom datatype called pair. A pair is a general template struct whose primary function is to store pairs of elements of arbitrary type. The convenience function make_pair is provided because it avoids the awkward syntax of using constructors. For example:

	
myfunction ( pair<std::string, int> ( s, x ) ); // messy
myfunction ( make_pair(s,x) ); // much simpler

The make_pair function provides a convenient method to insert data into a map.

std::map<std::string, int> m;
m.insert ( make_pair ( "Tom", 18 ) );
m.insert ( make_pair ( "Jennifer", 25 ));
m.insert ( make_pair ( "Carlos", 32 ));

The two fields in a pair are named respectively first and second. So given a map iterator it, the data it refers to, (*it) is a pair, and we get at the key with the notation it->first and the value with it->second

So we're ready for a simple example: loading up a map with values and printing them out.

#include <map>
#include <string>
#include <iostream>
using std::string;
using std::map;

int main()
{
    map<string, int> m;
    m.insert ( make_pair ( string("Donovan"), 27 ));
    m.insert ( make_pair ( string("Brian"), 54 ));
    m.insert ( make_pair ( string("Genevieve"), 18 ));

    map<string, int>::const_iterator it;
    for ( it = m.begin(); it != m.end(); ++it )
        std::cout << it->first << " : " << it->second << std::endl;

    return 0;
}

Retrieving Data From Maps By Specifying Keys

To search for data in a map, one uses the find method. This method is not to be confused with the find function by the same name in the algorithm header. The more general version supplied by the algorithm header may be used, but it's slower than the member function. The member function is used like this (for example):

 std::map<std::string, int>::iterator it = myMap.find ( "Brian" );