Farid’s Blog

This is part 2 of a fast paced C++ tutorial for programmers familiar with high level languages like Python and Perl.

Introducing std::map

Associative arrays a.k.a. dictionaries are one of the most useful data structures. That’s why they are so popular among very high level programming languages like Python or Perl. In C++, the STL data type std::map is one possible implementation of dictionaries, though it’s not the only one available.

Declaring a std::map variable

We must first determine the data type of the keys and values, since std::map is templated. Let’s suppose that keys are std::string, and values are int. To declare a map variable aMap. we start by including the necessary headers:

#include <string>
#include <map>

Declaring the map variable aMap is as simple as:

std::map<std::string, int> aMap;

While this is enough for most uses, it can become quite cumbersome to repeat it, e.g. in function definitions:

std::map<std::string, int>
merge_maps(const std::map<std::string, int> &someMap,
           const std::map<std::string, int> &someOtherMap);

To simplify such code, typedefs are quite useful:

typedef std::map<std::string, int> map_t;

map_t aMap;

map_t
merge_maps(const map_t &someMap, const map_t &someOtherMap);

Of course, we can also allocate a map variable dynamically. With the previously typedef‘d map_t:

map_t *map_ptr = new map_t;
// ... do something with *map_ptr, then:
delete map_ptr;

Adding, changing, and erasing key/value pairs

The main idea of maps is to add key/value pairs to them:

aMap["C++"] = 10;
aMap["Python"] = 8;
aMap["Perl"] = 6;
aMap["Scheme"] = 7;
aMap["Java"] = 3;

Changing a value is easy:

++aMap["Python"];               // is now 9
aMap["C++"] = aMap["C++"] + 10; // is now 20

We may want to remove a key/value pair, knowing its key:

aMap.erase("Scheme"); // remove "Scheme"/7 from map.

Querying a value, knowing a key

Querying a map is easiest, if we already know the key:

#include <iostream>

std::cout << "Ranking of C++: " << aMap["C++"] << std::endl;
std::cout << "Ranking of Python: " << aMap["Python"] << std::endl;

Gotcha! However, we can’t query if a key is in the map using the subscript notation, because writing something like aMap["Prolog"] automatically instantiates a new key/value pair with the key “Prolog” and the default value for the mapped type (here 0) if it doesn’t already exist:

int value = aMap["Prolog"]; // WRONG!
// now aMap["Prolog"] == 0, while it didn'e exist before

The equivalent of Python’s dict.has_key function, which doesn’t gratuitously add a new key/value pair to the map can be implemented like this in C++:

bool
has_key(const map_t &the_map, const map_t::key_type &the_key)
{
  map_t::const_iterator iter = the_map.find(the_key);
  return iter != the_map.end();
}

This brings us to std::map iterators, and how to traverse a map.

Traversing a std::map with iterators

So what’s in aMap? If we don’t know which keys are in it, we can’t query it directly (think about it, it’s quite obvious). Unlike Python, we don’t have a function that returns a list of keys, so that we can iterate over it. But fortunately, C++’s std::map provides iterators that can be used like this:

typedef map_t::const_iterator iter_t;

for (iter_t i = aMap.begin(); i != aMap.end(); ++i)
{
  // i->first is the curent key
  // i->second is the current value
  // *i is a std::pair<const std::string, int>

  std::cout << "key: " << i->first << std::endl;
  std::cout << "value: " << i->second << std::endl;
}

The difference between an map_t::const_iterator and map_t::iterator is that we can’t change the mapped type with a const_iterator. Bumping all values requires an iterator:

for (map_t::iterator i = aMap.begin(); i != aMap.end(); ++i)
  ++(i->second);

So, to implement the equivalent of the Python dict.keys method, which returns a list of keys of a dictionary in C++:

#include <list>

std::list<map_t::key_type>
keys(const map_t &the_map)
{
  std::list<map_t::key_type> theKeys;
  map_t::const_iterator iter;

  for (iter = the_map.begin(); iter != the_map.end(); ++iter)
    theKeys.push_back(iter->first);

  return theKeys;
}

This can be used like this:

#include <algorithm>

void
printme(const map_t::key_type &aKey)
{
  std::cout << "Key=" << aKey << std::endl;
}

int main(int argc, char *argv[])
{
  // ...
  std::list<map_t::key_type> allKeys;
  allKeys = keys(aMap);
  std::for_each(allKeys.begin(), allKeys.end(), printme);
  // ...
}

A practical example

With what we’ve learned so far, we can write a simple C++ program that counts how often words occur in a text:

// tut_02_01.cpp -- word count using std::map

#include <cstdlib>
#include <iostream>
#include <string>
#include <map>

int
main (int argc, char *argv[])
{
  typedef std::map<std::string, unsigned int> wc_t;

  wc_t wordCount;
  std::string aWord;

  while (std::cin >> aWord) {
    ++wordCount[aWord];
  }

  typedef wc_t::const_iterator wc_iter_t;
  for (wc_iter_t i=wordCount.begin(); i != wordCount.end(); ++i)
    std::cout << i->first << ": " << i->second << std::endl;

  return EXIT_SUCCESS;
}

If we compile and run this program on the following file tut_02_01.txt:

a horse is a horse
of course of course
a test is a test
and is successful if passed
and crap if failed

we get this output:

% c++ -Wall -o tut_02_01 tut_02_01.cpp
% ./tut_02_01 < tut_02_01.txt
a: 4
and: 2
course: 2
crap: 1
failed: 1
horse: 2
if: 2
is: 3
of: 2
passed: 1
successful: 1
test: 2

As you can see, the keys are sorted alphabetically.

Not yet covered so far

In subsequent parts of this tutorial:

• User-defined classes in maps
• Multimaps
• Hash maps
• Bimaps
• Persistent maps