# Map

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 strict

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

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