Yolinux.com Tutorial

C++ STL MAP and multiMAP:

Description, use and examples of C++ STL "pair", "map" and "multimap" associative containers. The STL associative container class is a variable sized container which supports retrieval of an element value given a search key.
  • STL pair: A container which holds two values. The data types may or may not be different.
  • STL map: Associative key-value pair held in balanced binary tree structure. Each key is unique.
  • STL multimap: Same as an STL map except that duplicate keys are allowed.

Also see:

Related YoLinux tutorials:

°Linux and C++

°C++ Unions & Structures

°C++ Enumerations

°C++ Templates

°C++ STL

°Boost: list of pointers

°C++ String Class

°C++ Singleton

°C++ Coding Style

°C++ XML Beans

°C/C++ Dynamic Memory

°C++ Memory Corruption

°C/C++ Signal Handling

°C++ CGI

°Software development tools

°Advanced VI

°Emacs and C/C++

°YoLinux Tutorials Index




Free Information Technology Magazines and Document Downloads
TradePub link image


Free Information Technology Software and Development Magazine Subscriptions and Document Downloads


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;

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

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

Employees[3374]=Charlie M.

Map size: 5
1923: David D.
3374: Charlie M.
5234: Mike C.
5328: Peter Q.
7582: John A.
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. The overloaded = and < operators are required 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["A"] = Ablob;

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

   Ablob.z=3.2355;
   M["C"] = 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: 7 2 4.2355

B: 5 2 4.2355

C: 5 2 3.2355

D: 3 7 7.2355
[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


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.

Amazon.com
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.

Amazon.com
Data Structures with C++ Using STL
William Ford, Willaim Topp
ISBN #0130858501, Prentice Hall
Amazon.com
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
Amazon.com
The C++ Templates: The complete guide.
David Vandevoorde, Nicolai Josuttis
ISBN #0201734842, Addison Wesley Pub Co.

Covers complex use of C++ Templates.

Amazon.com
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.

Amazon.com
   

    Bookmark and Share


Advertisements




Copyright © 2007 - 2013 by Greg Ippolito