Computing › Stl › Containers › Associative ›

Map

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

View version details

Contents

Definition
Description
Performance
Map Operations
Page Comments

Key Facts

Gyroscopic Couple: The rate of change of angular momentum ( $\inline \tau$ ) = $\inline I\omega\Omega$ (In the limit).

$\inline I$ = Moment of Inertia.
$\inline \omega$ = Angular velocity
$\inline \Omega$ = Angular velocity of precession.

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 strict weak ordering is a binary relation $\inline <$ on a set $\inline S$ that is a strict partial order (a transitive relation that is irreflexive, or equivalently, that is asymmetric) in which the relation "neither $\inline a < b$ nor $\inline b < a$ " is transitive.

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 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:

Example - accessing values of a map

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