C++ Tutorial: Standard Template Library I

bogotobogo

Bogotobogo
contact@bogotobogo.com

C++ Tutorial - Standard Template Library II
- Maps - 2012

Full List of C++ Tutorials

Standard Template Library (STL) II - Associative Containers

A map is an ordered sequence of pairs (key, value) in which we can look up a value based on a key. Data structures similar to map are associative arrays, hash tables, and red-black trees.

Your Ad Here

Associative Containers

map an ordered container of (key,value) pairs
set an ordered container of keys
unordered_map an unordered container of (key,value) pairs
unordered_set an unordered container of keys
multimap a map where a key can occur multiple times
multiset a set where a key can occur multiple times
unordered_multimap a unordered_map where a key can occur multiple times
unordered_multiset a unordered_set where a key can occur multiple times

Maps

What is a map?
The map class template looks like this:

std::map<Key, Data, Compare, Alloc>

STP map implementations are more like a balanced binary search trees (BST). To be more specific, they are red-black trees.

Picture source: http://en.wikipedia.org/wiki/Red-black_tree

A tree is built up from nodes. A node holds a key, its corresponding value, and pointers to two descendants' nodes. We won't go into details, but one thing we should remember is that the red-black tree has guaranteed log(n) height tree.

Let's look at the simple code which shows how to use maps.

#include <iostream>
#include <map>
#include <string>
#include <utility> 
using namespace std;
 
int main()
{
	typedef map<string, int> mapType;
	mapType populationMap;
 
	populationMap.insert(pair<string, int>("China", 1339));
	populationMap.insert(pair<string, int>("India", 1187));
	populationMap.insert(mapType::value_type("US", 310)); 
	populationMap.insert(mapType::value_type("Indonesia", 234)); 
	populationMap.insert(make_pair("Brasil", 193)); 
	populationMap.insert(make_pair("Pakistan", 170)); 

	// Erase the end element using the erase function
	// Because it's ordered map (by key), 
	// map elements are not in the order of the entry 
	// In this map it's US since it's ordered alphabetically.
	mapType::iterator iter = --populationMap.end();
	populationMap.erase(iter);
 
	// output the size of the map
	cout << "Size of populationMap: " << populationMap.size() << '\n';
 
	for (iter = populationMap.begin(); iter != populationMap.end(); ++iter) {
		cout << iter->first <<": " 
			<< iter->second << " million\n";
	}

	// find will return an iterator to the matching element if it is found
	// or to the end of the map if the key is not found
	string country("Indonesia");
	iter = populationMap.find(country);
	if( iter != populationMap.end() ) 
		cout << country <<"'s populations is "
			<< iter->second << " million\n";
	else
		cout << "Key is not in populationMap" << '\n';
 
	// clear the entries in the map
	populationMap.clear();
}

Output from the run is:

Size of populationMap: 5
Brasil: 193 million
China: 1339 million
India: 1187 million
Indonesia: 234 million
Pakistan: 170 million
Indonesia's populations is 234 million

To use a map, we must include the header file <map>

#include <map>

Let's look at the sample program counting the number of words in the input file.

When we define:

map<string, int>

the first template argument is the type of the element's key, and the second template argument is the type of the element's value.

The template for the map defined inside namespace std is:

namespace std {
	template <class Key, class T,
			class Compare = less<Key>,
			class Allocator = allocator<pair<const Key, T> > >
	class map;

The elements of a map may have any types of key and value that meet the following two requirements:

The key/value pair must be assignable and copyable.
The key must be comparable with the sorting criterion.

In the code:

	populationMap.insert(pair<string, int>("China", 1339));
	populationMap.insert(pair<string, int>("India", 1187));
	populationMap.insert(mapType::value_type("US", 310)); 
	populationMap.insert(mapType::value_type("Indonesia", 234)); 
	populationMap.insert(make_pair("Brasil", 193)); 
	populationMap.insert(make_pair("Pakistan", 170));

we are inserting a key/value pair in three different ways:

Use pair<>
Use pair<> directly.
```
pair<string, int>("India", 1187));
```

Use value_type
To avoid implicit type conversion, we pass the correct type explicitly by using value_type, which is provided as a type definition by the container type.
```
populationMap.insert(mapType::value_type("US", 310));
```
Use make_pair
The most convenient way is to use make_pair function. This function produces a pair object that contains the two values passed as arguments:
```
populationMap.insert(make_pair("Brasil", 193));
```

Then when we tried to erase the element at the end, we used '--' operator on the iterator end() because it is pointing to the one passed the end element.

	mapType::iterator iter = --populationMap.end();

Maps for Word Count

Following code counts the word using maps.
It first reads in the Stairway To Heaven Lyrics (Led Zeppelin), then put it into a map<string,int>. The first string argument is the word and the second argument is the counter which shows how many times the key appeared in the lyric.

#include <iostream>
#include <fstream>
#include <map>
#include <algorithm>
#include <string>
#include <iterator>
using namespace std;
int main()
{
	const string delims(" \t,.;");
	map<string,int> words;
	string line, str;
	ifstream myFile("stairwaytoheaven.txt", ios_base::in);
	while (getline(myFile,line)) {
		string::size_type beg, end;
		beg = line.find_first_not_of(delims);
		while (beg != string::npos) {
			end = line.find_first_of(delims,beg);
			if(end == string::npos) {
				end = line.length();
			}
			str.assign(line,beg,end-beg+1);
			++words[str];
			beg = line.find_first_not_of(delims,end);
		}
	}
	typedef map<string,int>::const_iterator iter;
	for(iter p = words.begin(); p != words.end(); ++p)
		cout << p->first << ":" << p->second << endl;

	myFile.close();
	return 0;
}

Output should look like this:

'Cause :1
All :1
And :12
Aw,:1
But :2
Dear :1
Don't :1
Echo :1
For :3
How :1
I :3
If :3
In :3
It's :1
May :1
Misgiven :1
Oh,:1
Ooh,:5
Our :1
Rings :1
Sometimes :1
.......
whispering :1
white :1
who :2
who's :1
whoa,:5
will :4
wind :2
wind? :1
with :1
won't :1
wonder :5
word :1
words :1
you :8
you're :1
your :1

To extract a word from a string, we use several separators (delimiters) as in the line:

const string delims(" \t,.;");

It include space, tab, '.', and ';'.

Then we find the beginning and end of the word in between the delimiters:

beg = line.find_first_not_of(delims);
		while (beg != string::npos) {
			end = line.find_first_of(delims,beg);

Then we assign the word extracted to a string "str" while incrementing the count:

			str.assign(line,beg,end-beg+1);
			++words[str];

Hash Table vs. STL map

Compare a hash table vs. an STL map
How we implement hash table?
Instead of hash table, what data structure options can be used for the case when the number of input is small?

Hash Table
- A value is stored by applying hash function on a key. So, values are not stored in sorted order.
- Because hash table uses the key to find the index that will store the value, an insert/loopkup can be done in O(1) time if we can assume there are only a few collisions in the hash table.
- Potential collisions should be handled properly.
STL map
- Insertion of key/value is in sorted order of key.
- It uses a tree to store values - O(logN) insert/lookup.
- No need to handle collisions.
- An STL map works well to:

So, how a hash table implemented?

A good hash function is needed to ensure that the hash values are uniformly distributed.
A collision protection method is required:
- chaining - for dense table entries.
- probing - sparse table entries.
Implement methods to dynamically increase or decrease the hash table size on a given criterion.

When the number of inputs is small, we can use STL map as an option for data structure. Since n is small, O(logN) is negligible.

In the following Chapters, we'll look at iterators, and algorithms in detail.

Full List of C++ Tutorials