The Map Data Type

Benefits of the Map Data Type

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

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:

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.

                /   \
               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:

                    / \
                   j   m

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.


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" );
It returns myMap.end() if unsuccesful, otherwise it returns a valid iterator.