Object Oriented Programming with C++10CS36

Maps

The map class supports an associative container in which unique keys are mapped with values. In essence, a key is simply a name that you give to a value. Once a value has been stored, you can retrieve it by using its key. Thus, in its most general sense, a map is a list of key/value pairs. The power of a map is that you can look up a value given its key. For example, you could define a map that uses a person's name as its key and stores that person's telephone number as its value. Associative containers are becoming more popular in programming. As mentioned, a map can hold onlyunique keys. Duplicate keys are not allowed.

To create a map that allows nonunique keys, use multimap. The map container has the following template specification: template <class Key, class T, class Comp = less<Key>, class Allocator = allocator<pair<constkey, T> > class map

Here, Key is the data type of the keys, T is the data type of the values being stored (mapped), and Comp is a function that compares two keys. This defaults to the standard less( ) utility function object. Allocator is the allocator (which defaults to allocator) .

A map has the followingconstructors:

explicit map(const Comp &cmpfn= Comp( ),

const Allocator &a = Allocator( ) );

map(const map<Key, T, Comp, Allocator> &ob);

template <class InIter> map(InIterstart, InIterend, const Comp &cmpfn= Comp( ), const Allocator &a = Allocator( ));

The first form constructs an empty map. The second form constructs a map that contains the same elements as ob. The third form constructs a map that contains the elements in the range specified by the iterators start and end. The function specified by cmpfn, if present, determines the ordering of the map.In general, any object used as a key should define a default constructor and overload the < operator and any other necessary comparison operators. The specific requirementsvaryfrom compiler to compiler.

The followingcomparison operators are defined for map.

==, <, <=, !=, >, >= key_typeis the type of the key, and value_typerepresents pair<Key, T>.

Key/value pairs are stored in a map as objects of type pair, which has this template specification.

template <class Ktype, class Vtypestruct pair { typedefKtypefirst_type; // type of key typedefVtypesecond_type; // type of value Ktype first; // contains the key

Vtype second; // contains the value

//

constructors pair();

pair(constKtype &k, constVtype &v); template<class A, class B> pair(const<A,B> &ob);

}

As the comments suggest, the value in first contains the key and the value in second contains the value associated with that key. You can construct a pair using either one of pair's constructors or by using make_pair( ), which constructs a pair object based upon the types of the data used as parameters. make_pair( ) is a generic function that has this prototype.

template <class Ktype, class Vtype> pair<Ktype,Vtype

make_pair(constKtypek, constVtypev);

As you can see, it returns a pair object consisting of values of the types specified by Ktypeand Vtype. The advantage of make_pair( ) is that the types of the objects be stored are determined automaticallybythe compiler rather than being explicitlyspecified by you.

The following program illustrates the basics of using a map. It stores key/value pairs that show the mapping between the uppercase letters and their ASCII character codes. Thus, the key is a character and the value is an integer.

The key/value pairs stored are

A65

B66C 67

and so on. Once the pairs have been stored, you are prompted for a key (i.e., a letter between A and Z), and the ASCIIcode for that letter is displayed.

// A simple map demonstration.

#include <iostream> #include <map> using namespace std; intmain() { map<char, int> m;

inti;

// put pairs into map for(i=0; i<26; i++) { m.insert(pair<char, int>('A'+i,

65+i)); } char ch; cout < "Enter key: "; cinch; map<char, int>::iterator p; // find value given key p = m.find(ch); if(p != m.end()) cout < "Its ASCIIvalue is " < p->second; else cout < "Keynot in map.\n"; return 0;

}

Notice the use of the pair template class to construct the key/value pairs. The data types specified by pair must match those of the map into which the pairs are being inserted. Once the map has been initialized with keys and values, you can search for a value given its key by using the find( ) function. find( ) returns an iterator to the matching element or to the end of the map if the key is not found. When a match is found, the value associated with the key is contained in the second member of pair.

In the preceding example, key/value pairs were constructed explicitly, using pair<char, int. While there is nothing wrong with this approach, it is often easier to use make_pair( ), which constructs a pair object based upon the types of the data used as parameters. For example, assuming the previous program, this line of code will also insert key/value pairs into m.

m.insert(make_pair((char)('A'+i), 65+i)); Here, the cast to char is needed to override the automatic conversion to intwhen iis added to 'A.' Otherwise, the type determination is automatic.

Storing Class Objects in a Map

As with all of the containers, you can use a map to store objects of types that you create. For example, the next program creates a simple phone directory. That is, it creates a map of names with their numbers. To do this, it creates two classes called name and number. Since a map maintains a sorted list of keys, the program also defines the operator for objects of type name. In general, you must define the operator for any classes that you will use as the key.

(Some compilers mayrequire that additional comparison operators be defined.) // Use a map to create a phone directory.

#include <iostream

#include <map> #include <cstring> using namespace std; class name { charstr[40]; public:

name() { strcpy(str, ""); } name(char *s) { strcpy(str, s); } char *get() { return str; }

};

// Must define less than relative to name objects.

bool operator<(namea, name b)

{

return strcmp(a.get(), b.get()) <0;

}

class phoneNum{

charstr[80]; public:

phoneNum() { strcmp(str, ""); }

phoneNum(char *s) { strcpy(str, s); } char *get() { return str; }

};

int main() {

map<name, phoneNum> directory; // put names and numbers into map

directory.insert (pair<name, phoneNum>(name("Tom"), phoneNum("555-4533")));

directory.insert (pair<name, phoneNum>(name("Chris"), phoneNum("555-9678")));

directory.insert (pair<name, phoneNum>(name("John"), phoneNum("555-8195")));

directory.insert (pair<name,

phoneNum>(name("Rachel"), phoneNum("555-0809"))); // given a name, find number char str[80];

cout < "Enter name: ";

cinstr; map<name, phoneNum>::iterator p; p = directory.find(name(str));

if(p != directory.end()) cout < "Phone number: " < p->second.get();

else

cout < "Name not in directory.\n";

return 0;

}

Here is a sample run:

Enter name: Rachel

Phone number: 555-0809.

In the program, each entry in the map is a character array that holds a null- terminated string. Later in this chapter, you will see an easier way to write this program that uses the standard string type.