CodeCogs

Map and multimap containers are containers that manage key/value pairs as elements.

Definition

The map template is defined in the standard header <map>, and in the nonstandard backward-compatibility header <map.h>.

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

Description

The map template associates, or maps, values of some key type to values of some other type. For example, it is possible to use a map to associate names represented as strings with some other type that you chose, such as floating-point values. This would allow you to associate a person's name with a bank account balance, grade point average, etc.

The main characteristics of a map are:

each element has an unique key
each element is composed of a key and a mapped value
elements follow a strict weak ordering

A short example declaring a map is:

map<string, double> aMap; // associates strings with doubles

Performance

Map has the important property that inserting a new element into a map does not invalidate iterators that point to existing elements. Erasing an element from a map also does not invalidate any iterators, except, of course, for iterators that actually point to the element that is being erased.

The asymptotic complexity of the operations that can be applied to maps are as follows:

Operation	Complexity
Searching for an element	O(log n)
Inserting a new element	O(log n)
Incrementing/decrementing an iterator	O(log n)
Removing a single map element	O(log n)
Copying an entire map	O(n)
Iterating through all elements	O(n)

There is also a http://codecogs.izyba.com/reference/computing/containers/associative_containers/multimap.php"multimap" container class where the keys do not have to be unique (a key can be associated with more than one value).

Map Operations

Create, Copy, and Destroy Operations

Operation	Effect
map m	Creates an empty map without any elements
map m(op)	Creates an empty map that uses op as the sorting criterion
map m1(m2)	Creates a copy of another map of the same type (all elements are copied)
map m(beg,end)	Creates a map initialized by the elements of the range [beg,end)
map m(beg,end,op)	Creates a map with the sorting criterion op initialized by the elements of the range [beg,end)
m.~map()	Destroys all elements and frees the memory

Map	Effect
map< Key,el >	A map that sorts keys with `less<>` (operator `<`)
map< Key,el,op >	A map that sorts keys with op

Nonmodifying Operations of Maps

Operation	Effect
m.size()	Returns the actual number of elements in the container
m.empty()	Returns if the container is empty (equivalent to size()==0)
m.max_size()	Returns the maximum number of elements possible
m1==m2	Returns if m1 is equal to m2
m1!=m2	Returns if m1 is not equal to m2 (equivalent to !(m1==m2))
m1<m2	Returns if m1 is less than m2
m1>m2	Returns if m1 is greater than m2 (equivalent to m2<m1)
m1<=m2	Returns if m1 is less than or equal to m2 (equivalent to !(m2<m1))
m1>=m2	Returns if m1 is greater than or equal to m2 (equivalent to !(m1<m2))

Note: Operator [ ] (m[key]) returns a reference to the component of m whose key value is key, if this component exists. If this component does not exist, inserts a new component into m, the value of whose key is key, and for which the corresponding value is the default value of type el.

Special Search Operations of Maps

Operation	Effect
count(key)	Returns the number of elements with key key
find(key)	Returns the position of the first element with key key or end()
lower_bound(key)	Returns the first position where an element with key key would get inserted (the first element with key >= key)
upper_bound(key)	Returns the last position where an element with key key would get inserted (the first element with key > key)
equal_range(key)	Returns the first and last positions where elements with key key would get inserted (the range of elements with key == key)

Assignment Operations of Maps

Operation	Effect
m1=m2	Assigns all elements of m2 to m1
m1.swap(m2)	Swaps the data of m1 and m2
swap(m1,m2)	Same (as global function)

Iterator Operations of Maps

Operation	Effect
m.begin()	Returns a bidirectional iterator for the first element (keys are considered `const)`
m.end()	Returns a bidirectional iterator for the position after the last element (keys are considered `const)`
m.rbegin()	Returns a reverse iterator for the first element of a reverse iteration
m.rend()	Returns a reverse iterator for the position after the last element of a reverse iteration

Inserting and Removing Elements of Maps

Operation	Effect
m.insert(elem)	Inserts a copy of elem and returns the position of the new element and, for maps, if it succeeded
m.insert(pos,elem)	Inserts a copy of elem and returns the position of the new element (pos is used as a hint pointing to where the insert should start the search)
m.insert(beg,end)	Inserts a copy of all elements of the range [beg,end)(returns nothing)
m.erase(elem)	Removes all elements with value elem and returns the number of removed elements
m.erase(pos)	Removes the element at iterator position pos (returns nothing)
m.erase(beg,end)	Removes all elements of the range [beg,end)(returns nothing)
m.clear()	Removes all elements

References

http://www.mtsu.edu
http://www.sgi.com
http://en.wikipedia.org
Nicolai M. Josuttis: "The C++ Standard Library"

Example 1

Problem

This example of program creates an empty map, places three key/value pairs into it, then displays the values by accessing them via their keys.

Workings

#include <iostream>
#include <map>

using namespace std;

int main()
{
 map<char, int> m;
 if (m.empty())
 cout << "\nThe created map is currently empty.";

 m['x'] = 1;
 m['y'] = 2;
 m['z'] = 3;

 cout << "\nAfter entering the three key/value pairs, the size of the map is now " << m.size();
 cout << "\nIf the component key is x, the component value is "<< m['x'];
 cout << "\nIf the component key is y, the component value is "<< m['y'];
 cout << "\nIf the component key is z, the component value is "<< m['z'];

 return 0;
}

Solution

Output:

The newly created map is currently empty.

After entering the three key/value pairs, the size of the map is now 3.

If the component key is x, the component value is 1
If the component key is y, the component value is 2
If the component key is z, the component value is 3

Example 2

Problem

This program creates a map of months and the number of days in the month.

Workings

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

using namespace std;

typedef std::map<std::string, int, std::less<std::string>,
                 std::allocator<std::pair<const std::string, 
                                int>> >
        months_type;

inline std::ostream&
operator<< (std::ostream &out, const months_type &m)
{
    for (months_type::const_iterator it = m.begin (); 
         it != m.end (); ++it)
        std::cout << (*it).first << " has " 
                  << (*it).second << " days\n";

    return out;
}

int main()
{
  typedef months_type::value_type value_type;

  // put the months in the multimap
  months.insert (value_type (std::string ("January"),   31));
  months.insert (value_type (std::string ("February"),  28));
  months.insert (value_type (std::string ("February"),  29));
  months.insert (value_type (std::string ("March"),     31));
  months.insert (value_type (std::string ("April"),     30));
  months.insert (value_type (std::string ("May"),       31));
  months.insert (value_type (std::string ("June"),      30));
  months.insert (value_type (std::string ("July"),      31));
  months.insert (value_type (std::string ("August"),    31));
  months.insert (value_type (std::string ("September"), 30));
  months.insert (value_type (std::string ("October"),   31));
  months.insert (value_type (std::string ("November"),  30));
  months.insert (value_type (std::string ("December"),  31));
  
  // Print out the months.  Second February is not present.
  std::cout << months << std::endl;

  // find the number of days in June
  months_type::iterator p = months.find(std::string("June"));

  // print out the number of days in June
  if (p != months.end ())
    std::cout << std::endl << (*p).first << " has "<<(*p).second<<" days";

  return 0;
}

Solution

Output:

April has 30 days
August has 31 days
December has 31 days
February has 28 days
January has 31 days
July has 31 days
June has 30 days
March has 31 days
May has 31 days
November has 30 days
October has 31 days
September has 30 days

June has 30 days

Example 3

Problem

This program illustrates the construction of a map from an array of pairs.The map is then displayed in two different ways. The code illustrates the use of a map iterator, the begin() and end() functions, and the operators =, !=, ++, --, *, -> and == with map iterators.

Workings

#include <iostream>
#include <map>
#include <utility>

using namespace std;

int main()
{
  // create an array of pairs
  pair<char, int> a[] =
  {
    pair<char, int>('B', 66),
    pair<char, int>('A', 65),
    pair<char, int>('D', 68),
    pair<char, int>('C', 67),
    pair<char, int>('E', 69)
  };

  // initialize a map with values from the array
  map<char, int> m(a, a+5);

  cout << endl;
  map<char, int>::iterator p;
  for (p = m.begin(); p != m.end(); ++p)
  cout << p->first << " has an ASCII code of " << p->second << ".\n";
  if (p == m.end())
  cout << "Our iterator is now pointing to one-past-the-last position.";

  p = m.end();
  cout << endl;
  while (p != m.begin())
  {
    --p;
    cout << p->first << " has an ASCII code of " << p->second << ".\n";
  }
  if (p == m.begin())
  cout << "Our iterator is now pointing to the first position.";
  if (*p == *m.begin())
  cout << "\nWe confirm this by checking component equality as well.";

  return 0;
}

Solution

Output:

A has an ASCII code of 65.
B has an ASCII code of 66.
C has an ASCII code of 67.
D has an ASCII code of 68.
E has an ASCII code of 69.
Our iterator is now pointing to one-past-the-last position.

E has an ASCII code of 69.
D has an ASCII code of 68.
C has an ASCII code of 67.
B has an ASCII code of 66.
A has an ASCII code of 65.
Our iterator is now pointing to the first position.
We confirm this by checking component equality as well.

Example 4

Problem

This program illustrates the lower_bound() member function of the map interface.

Workings

#include <iostream>
#include <map>
#include <utility>

using namespace std;

int main()
{
  pair<char, int> a[] =
  {
    pair<char, int>('D', 68),
    pair<char, int>('E', 69),
    pair<char, int>('F', 70),
    pair<char, int>('G', 71),
    pair<char, int>('H', 72),
    pair<char, int>('I', 73),
    pair<char, int>('J', 74),
    pair<char, int>('K', 75),
    pair<char, int>('L', 76),
    pair<char, int>('M', 77)
  };

  // suppose we begin with a map containing the following pairs:
  map<char, int> m(a, a+10);
  map<char, int>::iterator p = m.begin();

  while (p != m.end())
  {
    cout << p->first << " " << p->second << endl;
    ++p;
  }
  // we use the lower_bound() function to find the lower bound for a key in the map,
 // then for a key that precedes any key in the map, and finally for a key   that follows all keys

  cout << "\nThe lower bound for the key H is the position of this pair:\n";
  p = m.lower_bound('H');
  cout << p->first << " " << p->second;
  
  cout << "\nThe lower bound for the key A is the position of this pair:\n";
  p = m.lower_bound('A');
  cout << p->first << " " << p->second;

  p = m.lower_bound('T');
  if (p == m.end())
  cout << "\nThe lower bound for the key T is the one-past-the-last "
  "position.";

  return 0;
}

Solution

Output:

Suppose we begin with a map containing the following pairs:
D 68
E 69
F 70
G 71
H 72
I 73
J 74
K 75
L 76
M 77

The lower bound for the key H is the position of this pair:
H 72

The lower bound for the key A is the position of this pair:
D 68

The lower bound for the key T is the one-past-the-last position.

Example 7

Problem

This program illustrates a const map iterator.

Workings

#include <iostream>
#include <map>
#include <utility>

using namespace std;

void DisplayASCIICodes
(
  const map<char, int>& asciiCodes //in
);

int main()
{
  //Create an array of pairs
  pair<char, int> a[] =
  {
    pair<char, int>('A', 65),
    pair<char, int>('B', 66),
    pair<char, int>('C', 67),
    pair<char, int>('D', 68),
    pair<char, int>('E', 69),
  };

  //Initialize a map with values from the array
  map<char, int> asciiCodes(a, a+5);
 
  DisplayASCIICodes(asciiCodes);

  return 0;
}  

void DisplayASCIICodes
(
  const map<char, int>& asciiCodes //in
)
{
  map<char, int>::const_iterator p = asciiCodes.begin();
  cout <<endl;

  while (p != asciiCodes.end())
  {
    cout <<p->first<<" has an ASCII code of "<< p->second<<".\n";
    ++p;
  }
}

Solution

Output:

A has an ASCII code of 65.
B has an ASCII code of 66.
C has an ASCII code of 67.
D has an ASCII code of 68.
E has an ASCII code of 69.