C++: STL Map and MultiMap

Example: STL map:

Sparse array example: (why hold space for thousands of elements when all we have is five)

#include <string.h>
#include <iostream>
#include <map>
#include <utility>

using namespace std;

int main()
{
   map<int, string> Employees;

   // 1) Assignment using array index notation
   Employees[5234] = "Mike C.";
   Employees[3374] = "Charlie M.";
   Employees[1923] = "David D.";
   Employees[7582] = "John A.";
   Employees[5328] = "Peter Q.";

   cout << "Employees[3374]=" << Employees[3374] << endl << endl;

   cout << "Map size: " << Employees.size() << endl;

   cout << endl << "Natural Order:" << endl;
   for( map<int,string>::iterator ii=Employees.begin(); ii!=Employees.end(); ++ii)
   {
       cout << (*ii).first << ": " << (*ii).second << endl;
   }

   cout << endl << "Reverse Order:" << endl;
   for( map<int,string>::reverse_iterator ii=Employees.rbegin(); ii!=Employees.rend(); ++ii)
   {
       cout << (*ii).first << ": " << (*ii).second << endl;
   }
}

Compile: g++ testMap.cpp
Run: ./a.out

Employees[3374]=Charlie M.

Map size: 5

Natural Order:
1923: David D.
3374: Charlie M.
5234: Mike C.
5328: Peter Q.
7582: John A.

Reverse Order:
7582: John A.
5328: Peter Q.
5234: Mike C.
3374: Charlie M.
1923: David D.

Example using a "string" as an array index:

#include <string.h>
#include <iostream>
#include <map>
#include <utility>

using namespace std;

int main()
{
   map<string, int> Employees;

   // Examples of assigning Map container contents

   // 1) Assignment using array index notation
   Employees["Mike C."] = 5234;
   Employees["Charlie M."] = 3374;

   // 2) Assignment using member function insert() and STL pair
   Employees.insert(std::pair<string,int>("David D.",1923));
 
   // 3) Assignment using member function insert() and "value_type()"
   Employees.insert(map<string,int>::value_type("John A.",7582));

   // 4) Assignment using member function insert() and "make_pair()"
   Employees.insert(std::make_pair("Peter Q.",5328));

   cout << "Map size: " << Employees.size() << endl;

   for( map<string, int>::iterator ii=Employees.begin(); ii!=Employees.end(); ++ii)
   {
       cout << (*ii).first << ": " << (*ii).second << endl;
   }
}

Compile: g++ testMap.cpp
Run: ./a.out

Map size: 5
Charlie M.: 3374
David D.: 1923
John A.: 7582
Mike C.: 5234
Peter Q.: 5328

Note: The fully defined STL map defines a comparison operator in the map declaration so that the indexes can be ordered. This is used to provide a default comparison operator for the data type. In the above example, the key type is an integer and the C++ "equals" (=) and "less than" operator (<) can operate on an integer so the example works. The use of the STL algorithm std::less<> can be specified explicitly as in the following declaration:

std::map<int, string, std::less< int > >

If defining your own class as the index (first value), C++ will not know how to perform the comparison, thus you will have to provide an operator to perform this function.

The first element in a map can be a class or even another STL container such as a pair. If using a class, the class must provide an overloaded "equals" (=) and "less than" operator (<).

Thus using "char" instead of "string" requires the use of a comparison function:

#include <string.h>
#include <iostream>
#include <map>
#include <utility>

using namespace std;

struct cmp_str 
{
   bool operator()(char const *a, char const *b) 
   {
      return std::strcmp(a, b) < 0;
   }
};

int main()
{
   map<char *, int, cmp_str> Employees;

   // Examples of assigning Map container contents

   // 1) Assignment using array index notation
   Employees["Mike C."] = 5234;
   Employees["Charlie M."] = 3374;

   // 2) Assignment using member function insert() and STL pair
   Employees.insert(std::pair<char *,int>("David D.",1923));
 
   // 3) Assignment using member function insert() and "value_type()"
   Employees.insert(map<char *,int>::value_type("John A.",7582));

   // 4) Assignment using member function insert() and "make_pair()"
   Employees.insert(std::make_pair((char *)"Peter Q.",5328));

   cout << "Map size: " << Employees.size() << endl;

   for( map<char *, int, cmp_str>::iterator ii=Employees.begin(); ii!=Employees.end(); ++ii)
   {
       cout << (*ii).first << ": " << (*ii).second << endl;
   }
}

Compile: g++ testMap.cpp
Run: ./a.out

Map size: 5
Charlie M.: 3374
David D.: 1923
John A.: 7582
Mike C.: 5234
Peter Q.: 5328

SGI Map Documentation:

Using STL MAP to store class objects:

This example uses a string as the MAP index and an object as the value pair. In order for a class to be stored in an STL container, it must have a default constructor, the class must be assignable, less than comparable and equality comparable. Thus the overloaded = and < operators are provided to satisfy MAP container use.

#include <iostream>
#include <map>
using namespace std;

class AAA
{
   friend ostream &operator<<(ostream &, const AAA &);

   public:
      int x;
      int y;
      float z;

      AAA();
      AAA(const AAA &);
      ~AAA(){};
      AAA &operator=(const AAA &rhs);
      int operator==(const AAA &rhs) const;
      int operator<(const AAA &rhs) const;
};

AAA::AAA()   // Constructor
{
   x = 0;
   y = 0;
   z = 0;
}

AAA::AAA(const AAA &copyin)   // Copy constructor to handle pass by value.
{                             
   x = copyin.x;
   y = copyin.y;
   z = copyin.z;
}

ostream &operator<<(ostream &output, const AAA &aaa)
{
   output << aaa.x << ' ' << aaa.y << ' ' << aaa.z << endl;
   return output;
}

AAA& AAA::operator=(const AAA &rhs)
{
   this->x = rhs.x;
   this->y = rhs.y;
   this->z = rhs.z;
   return *this;
}

int AAA::operator==(const AAA &rhs) const
{
   if( this->x != rhs.x) return 0;
   if( this->y != rhs.y) return 0;
   if( this->z != rhs.z) return 0;
   return 1;
}

int AAA::operator<(const AAA &rhs) const
{
   if( this->x == rhs.x && this->y == rhs.y && this->z < rhs.z) return 1;
   if( this->x == rhs.x && this->y < rhs.y) return 1;
   if( this->x < rhs.x ) return 1;
   return 0;
}

main()
{
   map<string, AAA> M;
   AAA Ablob ;

   Ablob.x=7;
   Ablob.y=2;
   Ablob.z=4.2355;
   M["C"] = Ablob;

   Ablob.x=5;
   M["B"] = Ablob;

   Ablob.z=3.2355;
   M["A"] = Ablob;

   Ablob.x=3;
   Ablob.y=7;
   Ablob.z=7.2355;
   M["D"] = Ablob;

   for( map<string, AAA>::iterator ii=M.begin(); ii!=M.end(); ++ii)
   {
       cout << (*ii).first << ": " << (*ii).second << endl;
   }

   return 0;
}

Compile: g++ testMap.cpp
Run: ./a.out
Output:

A: 5 2 3.2355

B: 5 2 4.2355

C: 7 2 4.2355

D: 3 7 7.2355

Note: The Map elements were inserted out of order but put in order in the internal Map structure and thus printed out in order. This is why the overloaded "<" operator was required. An alternative friend class with an overloaded "()" operator is shown in the next example.

[Potential Pitfall]: The following error occurs when the < operator is omitted from the class AAA.

/tmp/cca5a9G9.o: In function `main': testMap.cpp:(.text+0x3c6): undefined reference to `operator<<(std::basic_ostream<char, std::char_traits<char> >&, AAA const&)' collect2: ld returned 1 exit status

[Potential Pitfall]: The following error occurs when the = operator is omitted from the class AAA.

/tmp/cciGBZgS.o: In function `main':
testMap.cpp:(.text+0x263): undefined reference to `AAA::operator=(AAA const&)'
testMap.cpp:(.text+0x2c8): undefined reference to `AAA::operator=(AAA const&)'
testMap.cpp:(.text+0x32e): undefined reference to `AAA::operator=(AAA const&)'
testMap.cpp:(.text+0x3a2): undefined reference to `AAA::operator=(AAA const&)'
collect2: ld returned 1 exit status

Using class objects as a Map key:

#include <iostream>
#include <string>
#include <map>
using namespace std;

class Person
{
    friend class PersonLessThan;
public:
    string firstName;
    string lastName;

    Person(const string &firstName, const string &lastName);
};

Person::Person(const string &_firstName, const string &_lastName)
    : firstName(_firstName), lastName(_lastName)
{}

class PersonLessThan
{
public:
    bool operator( )(const Person& p1, const Person& p2) const {
      if (p1.lastName < p2.lastName)
         return(true);
      else if (p1.lastName == p2.lastName)
         return(p1.firstName < p2.firstName);
      else
         return(false);
   }
};

main()
{
   map<Person, bool, PersonLessThan> M;
   Person p_1("Wilma","Flintstone");
   Person p_2("Betty","Rubble");
   Person p_3("Fred","Flintstone");
   Person p_4("Barney","Rubble");
 
   M[p_1] = true;
   M[p_2] = true;
   M[p_3] = true;
   M[p_4] = true;

   for( map<Person, bool>::iterator ii=M.begin(); ii!=M.end(); ++ii)
   {
       cout << ((*ii).first).lastName << ", " << ((*ii).first).firstName << ": " << (*ii).second << endl;
   } 
}

Compile: g++ -o examplePersonKey examplePersonKey.cpp

Run: ./examplePersonKey

Flintstone, Fred: 1
Flintstone, Wilma: 1
Rubble, Barney: 1
Rubble, Betty: 1

The people are written out in sorted order as defined by the class PersonLessThan operator "()". The underlying Map structure requires a sort method so that it can insert the object into the underlying structure. You have two choices:

Map definition: map<key, value> M;
Sort defined as a key class overloaded operator "<"
Shown in previous example.
Map definition: map<key, value, CompareClass> M;
Sort defined as a key class friend class with an overloaded "()" operator.
Shown in this example.

Map member functions:

Constructor/Declaration:

Method/operator Description

map<K,T> m; Map declaration of key of type "K" and value of type "T".
Allocate an empty map: map<int,int> m = new map<int,int>();

map<K,T,compare> m; Map declaration of key of type "K" and value of type "T". A class (or struct) with an overloaded "()" operator function to compare keys so that they can be ordered in the underlying tree storage structure.
Allocate an empty map:
map<int,float,CFnCompare> m = new map<int,float,CFnCompare>();
Where CFnCompare is a class which defines the overloaded operator "()" which can compare the key type (in this case int)

Method/operator	Description
map<K,T> m;	Map declaration of key of type "K" and value of type "T". Allocate an empty map: `map<int,int> m = new map<int,int>();`
map<K,T,compare> m;	Map declaration of key of type "K" and value of type "T". A class (or struct) with an overloaded "()" operator function to compare keys so that they can be ordered in the underlying tree storage structure. Allocate an empty map: `map<int,float,CFnCompare> m = new map<int,float,CFnCompare>();` Where `CFnCompare` is a class which defines the overloaded operator "()" which can compare the key type (in this case int)

C++ 11 and C++14 have introduced constructors which allow one to provide the memory allocators.

Size methods/operators:

Method/operator	Description
empty()	Returns bool (true/false). True if empty. Declaration: bool empty() const
size()	Number of elements of the map. Declaration: `size_type size() const`
max_size()	Number of elements of the map. Declaration: `size_type max_size() const`

Note: size_type is an unsigned integer.

Other methods/operators:

Method/operator	Description
erase(&key) erase(iterator) erase( iterator first, iterator last )	Erase element of the Map identified by key, at element pos or elements in a range Declaration (all C++): `size_type erase( const key_type& key )` Declaration (until c++11): `void erase(iterator pos)` `void erase(iterator first, iterator last )` Declaration (after C++11): `iterator erase(iterator pos)` `iterator erase(iterator first, iterator last )`
clear()	Remove all elements of the entire Map Declaration: `void clear()`
=	Assign/copy entire contents of one Map to another Declaration: `map& operator=( const map& other ) C++11 introduces additional prototypes which use allocators`
== != < <= > >=	C++ operators available to compare Map elements
[key]	Access the contents of one Map element indicated by its key Declaration: `T& operator[]( const Key& key )`
at(key)	Access the contents of one Map element indicated by its key Declaration: `const T& at( const Key& key ) const;` Introduced in C++11
insert(std::pair)	Insert one Map element with the specified key/value pair. Declaration: `std::pair<iterator,bool> insert( const std::pair<key,value> );`
swap(&other)	Swap one Map with another. This Map class member function should not be confused with `std::swap(std::map)` Declaration: `void swap( map& other )`
find(&key)	Finds the Map iterator for the specified key. Declaration: `iterator find( const Key& key )` This function bridges the key/index vs iterator methodologies.

Iterator methods/operators:

Method/operator	Description
begin()	Return iterator to first element of the map. Declaration: `const_iterator begin() const`
end()	Return iterator to element after the last element of the map. No element exists in this location and attempting to access is undefined behavior Declaration: `const_iterator end() const`
rbegin()	Return iterator to first element of the map (reverse order). This is equivalent to the last element of the non-reversed container. Declaration: `const_reverse_iterator rbegin() const`
rend()	Return iterator to end of the map (not last element but past last element) (reverse order). This is equivalent to the element preceding the first element of the non-reversed container. Note that this is a placeholder and that no element exists in this location and attempting to access is undefined behavior Declaration: `const_reverse_iterator rend() const`

Note that for empty Maps, begin and end point to the same position.

Example: STL multimap:

The STL multipmap allows duplicate keys.

 
#include <string.h>
#include <iostream>
#include <map>
#include <utility>

using namespace std;

int main()
{
  // Compare (<) function not required since it is built into string class.
  // else declaration would comparison function in multimap definition.
  // i.e. multimap<string, int, compare> m;

  multimap<string, int> m;

  m.insert(pair<string, int>("a", 1));
  m.insert(pair<string, int>("c", 2));
  m.insert(pair<string, int>("b", 3));
  m.insert(pair<string, int>("b", 4));
  m.insert(pair<string, int>("a", 5));
  m.insert(pair<string, int>("b", 6));

  cout << "Number of elements with key a: " << m.count("a") << endl;
  cout << "Number of elements with key b: " << m.count("b") << endl;
  cout << "Number of elements with key c: " << m.count("c") << endl;

  cout << "Elements in m: " << endl;
  for (multimap<string, int>::iterator it = m.begin();
       it != m.end();
       ++it)
   {
       cout << "  [" << (*it).first << ", " << (*it).second << "]" << endl;
   }

   pair<multimap<string, int>::iterator, multimap<string, int>::iterator> ppp;

   // equal_range(b) returns pair<iterator,iterator> representing the range
   // of element with key b
   ppp = m.equal_range("b");

   // Loop through range of maps of key "b"
   cout << endl << "Range of \"b\" elements:" << endl;
   for (multimap<string, int>::iterator it2 = ppp.first;
       it2 != ppp.second;
       ++it2)
   {
       cout << "  [" << (*it2).first << ", " << (*it2).second << "]" << endl;
   }

// Can't do this (??)
//   cout << ppp.first << endl;
//   cout << ppp.second << endl;

   m.clear();
}

Compile: g++ testMultimap.cpp
Run: ./a.out

Number of elements with key a: 2
Number of elements with key b: 3
Number of elements with key c: 1
Elements in m:
  [a, 1]
  [a, 5]
  [b, 3]
  [b, 4]
  [b, 6]
  [c, 2]

Range of "b" elements:
  [b, 3]
  [b, 4]
  [b, 6]

SGI STL Documentation:

Books:

	The C++ Standard Library: A Tutorial Reference Nicolai M. Josuttis ISBN #0201379260, Addison Wesley Longman This book is the only book I have seen which covers string classes as implemented by current Linux distributions. It also offers a fairly complete coverage of the C++ Standard Template Library (STL). Good reference book.
	STL for C++ programmers Leen Ammeraal ISBN #0 471 97181 2, John Wiley & Sons Ltd. Short book which teaches C++ Standard Template Library (STL) by example. Not as great as a reference but is the best at introducing all the concepts necessary to grasp STL completely and good if you want to learn STL quickly. This book is easy to read and follow.
	Data Structures with C++ Using STL William Ford, Willaim Topp ISBN #0130858501, Prentice Hall
	STL Tutorial and Reference Guide: C++ Programming with the Standard Template Library David R. Musser, Gillmer J. Derge, Atul Saini ISBN #0201379236, Addison-Wesley Publications
	The C++ Templates: The complete guide. David Vandevoorde, Nicolai Josuttis ISBN #0201734842, Addison Wesley Pub Co. Covers complex use of C++ Templates.
	C++ How to Program by Harvey M. Deitel, Paul J. Deitel ISBN #0131857576, Prentice Hall Fifth edition. The first edition of this book (and Professor Sheely at UTA) taught me to program C++. It is complete and covers all the nuances of the C++ language. It also has good code examples. Good for both learning and reference.

C++ STL MAP and multiMAP:

Using STL MAP to store class objects:

Using class objects as a Map key:

Constructor/Declaration:

Size methods/operators:

Other methods/operators:

Iterator methods/operators: