Follow Techotopia on Twitter

On-line Guides
All Guides
eBook Store
iOS / Android
Linux for Beginners
Office Productivity
Linux Installation
Linux Security
Linux Utilities
Linux Virtualization
Linux Kernel
System/Network Admin
Scripting Languages
Development Tools
Web Development
GUI Toolkits/Desktop
Mail Systems
Eclipse Documentation

How To Guides
General System Admin
Linux Security
Linux Filesystems
Web Servers
Graphics & Desktop
PC Hardware
Problem Solutions
Privacy Policy




Thinking in C++ Vol 2 - Practical Programming
Prev Home Next

Multimaps and duplicate keys

A multimap is a map that can contain duplicate keys. At first this may seem like a strange idea, but it can occur surprisingly often. A phone book, for example, can have many entries with the same name.

Suppose you are monitoring wildlife, and you want to keep track of where and when each type of animal is spotted. Thus, you may see many animals of the same kind, all in different locations and at different times. So if the type of animal is the key, you ll need a multimap. Here s what it looks like:

//: C07:WildLifeMonitor.cpp
#include <algorithm>
#include <cstdlib>
#include <cstddef>
#include <ctime>
#include <iostream>
#include <iterator>
#include <map>
#include <sstream>
#include <string>
#include <vector>
using namespace std;
class DataPoint {
int x, y; // Location coordinates
time_t time; // Time of Sighting
DataPoint() : x(0), y(0), time(0) {}
DataPoint(int xx, int yy, time_t tm) :
x(xx), y(yy), time(tm) {}
// Synthesized operator=, copy-constructor OK
int getX() const { return x; }
int getY() const { return y; }
const time_t* getTime() const { return &time; }
string animal[] = {
"chipmunk", "beaver", "marmot", "weasel",
"squirrel", "ptarmigan", "bear", "eagle",
"hawk", "vole", "deer", "otter", "hummingbird",
const int ASZ = sizeof animal/sizeof *animal;
vector<string> animals(animal, animal + ASZ);
// All the information is contained in a
// "Sighting," which can be sent to an ostream:
typedef pair<string, DataPoint> Sighting;
operator<<(ostream& os, const Sighting& s) {
return os << s.first << " sighted at x= "
<< s.second.getX() << ", y= " << s.second.getY()
<< ", time = " << ctime(s.second.getTime());
// A generator for Sightings:
class SightingGen {
vector<string>& animals;
enum { D = 100 };
SightingGen(vector<string>& an) : animals(an) {}
Sighting operator()() {
Sighting result;
int select = rand() % animals.size();
result.first = animals[select];
result.second = DataPoint(
rand() % D, rand() % D, time(0));
return result;
// Display a menu of animals, allow the user to
// select one, return the index value:
int menu() {
cout << "select an animal or 'q' to quit: ";
for(size_t i = 0; i < animals.size(); i++)
cout <<'['<< i <<']'<< animals[i] << ' ';
cout << endl;
string reply;
cin >> reply;
if( == 'q') return 0;
istringstream r(reply);
int i;
r >> i; // Converts to int
i %= animals.size();
return i;
int main() {
typedef multimap<string, DataPoint> DataMap;
typedef DataMap::iterator DMIter;
DataMap sightings;
srand(time(0)); // Randomize
generate_n(inserter(sightings, sightings.begin()),
50, SightingGen(animals));
// Print everything:
copy(sightings.begin(), sightings.end(),
ostream_iterator<Sighting>(cout, ""));
// Print sightings for selected animal:
for(int count = 1; count < 10; count++) {
// Use menu to get selection:
// int i = menu();
// Generate randomly (for automated testing):
int i = rand() % animals.size();
// Iterators in "range" denote begin, one
// past end of matching range:
pair<DMIter, DMIter> range =
copy(range.first, range.second,
ostream_iterator<Sighting>(cout, ""));
} ///:~

All the data about a sighting is encapsulated into the class DataPoint, which is simple enough that it can rely on the synthesized assignment and copy-constructor. It uses the Standard C library time functions to record the time of the sighting.

In the array of string, animal, notice that the char* constructor is automatically used during initialization, which makes initializing an array of string quite convenient. Since it s easier to use the animal names in a vector, the length of the array is calculated, and a vector<string> is initialized using the vector(iterator, iterator) constructor.

The key-value pairs that make up a Sighting are the string, which names the type of animal, and the DataPoint, which says where and when it was sighted. The standard pair template combines these two types and is typedefed to produce the Sighting type. Then an ostream operator<< is created for Sighting; this will allow you to iterate through a map or multimap of Sightings and display it.

SightingGen generates random sightings at random data points to use for testing. It has the usual operator( ) necessary for a function object, but it also has a constructor to capture and store a reference to a vector<string>, which is where the aforementioned animal names are stored.

A DataMap is a multimap of string-DataPoint pairs, which means it stores Sightings. It is filled with 50 Sightings using generate_n( ) and displayed. (Notice that because there is an operator<< that takes a Sighting, an ostream_iterator can be created.) At this point the user is asked to select the animal for which they want to see all the sightings. If you press q, the program will quit, but if you select an animal number, the equal_range( ) member function is invoked. This returns an iterator (DMIter) to the beginning of the set of matching pairs and an iterator indicating past-the-end of the set. Since only one object can be returned from a function, equal_range( ) makes use of pair. Since the range pair has the beginning and ending iterators of the matching set, those iterators can be used in copy( ) to print all the sightings for a particular type of animal.

Thinking in C++ Vol 2 - Practical Programming
Prev Home Next

   Reproduced courtesy of Bruce Eckel, MindView, Inc. Design by Interspire