Map and multimap containers are containers that manage key/value pairs as
elements. They sort their elements automatically according to a certain sorting
criterion that is used for the actual key. The difference between the two is
that multimaps allow duplicates, whereas maps do not (figure below).
Figure: Maps and Multimaps
To use a map or multimap, you must include the header file
<map>:
There, the type is defined as a class template inside namespace std:
The first template argument is the type of the element's key, and the second
template argument is the type of the element's value. The elements of a map or
multimap may have any types Key and T that meet the following two requirements:
-
The key/value pair must be assignable and copyable.
-
The key must be comparable with the sorting criterion.
The optional third template argument defines the sorting criterion. Like
sets, this sorting criterion must define a "strict weak ordering" The elements are sorted according to their keys, thus the value doesn't
matter for the order of the elements. The sorting criterion is also used to
check equality; that is, two elements are equal if neither key is less than the
other. If a special sorting criterion is not passed, the default criterion less is used. The function object less sorts the elements by comparing them with operator <
The optional fourth template parameter defines the memory model. The default memory model is the
model
allocator, which is provided by the C++ standard
library.
Abilities of Maps and Multimaps
Like all standardized associative container classes, maps and multimaps are
usually implemented as balanced binary trees (figure below). The standard does not specify
this but it follows from the complexity of the map and multimap operations. In
fact, sets, multisets, maps, and multimaps typically use the same internal data
type. So, you could consider sets and multisets as special maps and multimaps,
respectively, for which the value and the key of the elements are the same
objects. Thus, maps and multimaps have all the abilities and operations of sets
and multisets. Some minor differences exist, however. First, their elements are
key/value pairs. In addition, maps can be used as associative arrays.
Figure: Internal Structure of Maps and Multimaps
Maps and multimaps sort their elements automatically according to the
element's keys. Thus they have good performance when searching for elements that
have a certain key. Searching for elements that have a certain value promotes
bad performance. Automatic sorting imposes an important constraint on maps and
multimaps: You may not change the key of an element directly because this
might compromise the correct order. To modify the key of an element, you must
remove the element that has the old key and insert a new element that has the
new key and the old value. As a consequence, from the
iterator's point of view, the element's key is constant. However, a direct
modification of the value of the element is still possible (provided the type of
the value is not constant).
Map and Multimap Operations
Create, Copy, and Destroy Operations
Table below lists the constructors and
destructors of maps and multimaps.
Table:- Constructors and Destructors of Maps and
Multimaps
| Operation |
Effect |
| map c |
Creates an empty map/multimap without any
elements |
| map c(op) |
Creates an empty map/multimap that uses op as the sorting criterion |
| map c1(c2) |
Creates a copy of another map/multimap of the same type (all
elements are copied) |
| map c(beg,end)
|
Creates a map/multimap initialized by the elements of the range
[beg,end) |
| map c(beg,end,op)
|
Creates a map/multimap with the sorting criterion op initialized by the elements of the range [beg,end) |
| c. ~map
() |
Destroys all elements and frees the
memory |
Here,
map may be one of the following:
| Map |
Effect |
| map<Key,Elem> |
A map that sorts keys with less<>
(operator <) |
| map<Key,Elem,Op> |
A map that sorts keys with Op
|
| multimap<Key,Elem> |
A multimap that sorts keys with less<> (operator <)
|
| multimap<Key,Elem,Op>
|
A multimap that sorts keys with Op
|
You can define the sorting criterion in two ways:
-
As a template parameter.
For example:
In this case, the sorting criterion is part of the type. Thus, the type
system ensures that only containers with the same sorting criterion can be
combined. This is the usual way to specify the sorting criterion. To be more
precise, the third parameter is the type of the sorting criterion. The
concrete sorting criterion is the function object that gets created with the
container. To do this, the constructor of the container calls the default
constructor of the type of the sorting criterion.
-
As a constructor parameter.
In this case you might have a type for several sorting criteria, and the
initial value or state of the sorting criteria might differ. This is useful when
processing the sorting criterion at runtime, or when sorting criteria are needed
that are different but of the same data type. A typical example is specifying
the sorting criterion for string keys at runtime.
If no special sorting criterion is passed, the default sorting criterion,
function object less<>, is used. which sorts the
elements by using operator <.
You should make a type definition to avoid the boring repetition of the type
whenever it is used:
The constructor for the beginning and the end of a range could be used to
initialize the container with elements from containers that have other types,
from arrays, or from the standard input. However, the
elements are key/value pairs, so you must ensure that the elements from the
source range have or are convertible into type pair<key,value>.
Nonmodifying and Special Search Operations
Maps and multimaps provide the usual nonmodifying operations - those that
query size aspects and make comparisons (table below).
Table :- Nonmodifying Operations of Maps and Multimaps
| Operation |
Effect |
| c.size() |
Returns the actual number of elements |
| c.empty() |
Returns whether the container is empty (equivalent to size()==0, but might be faster) |
| c.max_size() |
Returns the maximum number of elements
possible |
| c1 == c2 |
Returns whether c1 is equal to c2 |
| c1 != c2 |
Returns whether c1 is not equal to c2 (equivalent to !(c1==c2)) |
| c1 < c2 |
Returns whether c1 is less than c2 |
| c1 > c2 |
Returns whether c1 is greater than c2 c2<c1) |
| c1 <= c2 |
Returns whether c1 is less than or
equal to c2 (equivalent to !(c2<c1)) |
| c1 >= c2 |
Returns whether c1 is greater than or
equal to c2 (equivalent to !(c1<c2)) |
Comparisons are provided only for containers of the same type. Thus, the key,
the value, and the sorting criterion must be of the same type. Otherwise, a type
error occurs at compile time. For example:
To check whether a container is less than another container is done by a
lexicographical comparison. To compare containers of different
types (different sorting criterion),
Special Search Operations
Like sets and multisets, maps and multimaps provide special search member
functions that perform better because of their internal tree structure (table below).
The find() member function searches for the first
element that has the appropriate key and returns its iterator position. If no
such element is found, find() returns end() of the container. You can't use the find() member function to search for an element that has a
certain value. Instead, you have to use a general algorithm such as the find_if() algorithm, or program an explicit loop. Here is an
example of a simple loop that does something with each element that has a
certain value:
Table :- Special Search Operations of Maps and Multimaps
| 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) |
Be careful when you want to use such a loop to remove elements. It might
happen that you saw off the branch on which you are sitting. Using the find_if() algorithm to search for an
element that has a certain value is even more complicated than writing a loop
because you have to provide a function object that compares the value of an
element with a certain value.
The lower_bound(), upper_bound(), and equal_range() functions behave as they do for sets (see page
180), except that the elements are key/value pairs.
Assignments
Maps and multimaps provide only the fundamental assignment operations that
all containers provide (table below)
Table :- Assignment Operations of Maps and Multimaps
| Operation |
Effect |
| c1 = c2 |
Assigns all elements of c2 c1
|
| c1.swap(c2) |
Swaps the data of c1 and c2 |
| swap(c1,c2) |
Same (as global
function) |
For these operations both containers must have the same type. In particular,
the type of the comparison criteria must be the same, although the comparison
criteria themselves may be different. If the criteria are different, they
also get assigned or swapped.
Iterator Functions and Element Access
Maps and multimaps do not provide direct element access, so the usual way to
access elements is via iterators. An exception to that rule is that maps provide
the subscript operator to access elements directly. Table below lists the usual member
functions for iterators that maps and multimaps provide.
Table 6.30. Iterator Operations of Maps and Multimaps
| Operation |
Effect |
| c.begin() |
Returns a bidirectional iterator for the first element (keys
are considered const) |
| c.end() |
Returns a bidirectional iterator for the position after the
last element (keys are considered const)
|
| c.rbegin() |
Returns a reverse iterator for the first element of a reverse
iteration |
| c.rend() |
Returns a reverse iterator for the position after the last
element of a reverse iteration |
As for all associative container classes, the iterators are bidirectional. Thus, you can't
use them in algorithms that are provided only for random access iterators (such
as algorithms for sorting or random shuffling).
More important is the constraint that the key of all elements inside a map
and a multimap is considered to be constant. Thus, the type of the elements is
pair<const Key, T>. This is also necessary to
ensure that you can't compromise the order of the elements by changing their
keys. However, you can't call any modifying algorithm if the destination is a
map or multimap. For example, you can't call the remove() algorithm to remove elements because it "removes"
only by overwriting "removed" elements with the following arguments. To remove elements in maps and multimaps, you can use only member
functions provided by the container.
The following is an example of the use of iterators:
Here, the iterator
pos iterates through the sequence
of
string/float pairs. The expression
yields the key of the actual element, whereas the expression
yields the value of the actual element.
Trying to change the value of the key results in an error:
However, changing the value of the element is no problem (as long as the type
of the value is not constant):
To change the key of an element, you have only one choice: You must replace
the old element with a new element that has the same value. Here is a generic
function that does this:
The insert() and erase()
member functions are discussed in the next subsection.
To use this generic function you simply must pass the container the old key
and the new key. For example:
It works the same way for multimaps.
Note that maps provide a more convenient way to modify the key of an element.
Instead of calling replace_key(), you can simply write
the following:
Inserting and Removing Elements
Table below shows the operations
provided for maps and multimaps to insert and remove elements.
Table :- Insert and Remove Operations of Maps and
Multimaps
| Operation |
Effect |
| c.insert(elem) |
Inserts a copy of elem and returns the
position of the new element and, for maps, whether it succeeded |
| c.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) |
| c.insert(beg,end) |
Inserts a copy of all elements of the range [beg,end)(returns nothing) |
| c.erase(elem) |
Removes all elements with value elem
and returns the number of removed elements |
| c.erase(pos) |
Removes the element at iterator position pos (returns nothing) |
| c.erase(beg,end) |
Removes all elements of the range [beg,end)(returns nothing) |
| c.clear() |
Removes all elements (makes the container
empty) |
In
particular, the return types of these operations have the same differences as
they do for sets and multisets. However, note that the elements here are
key/value pairs. So, the use is getting a bit more complicated.
To insert a key/value pair, you must keep in mind that inside maps and
multimaps the key is considered to be constant. You either must provide the
correct type or you need to provide implicit or explicit type conversions. There
are three different ways to pass a value into a map:
-
Use value_type
To avoid implicit type conversion, you could pass the correct type explicitly
by using value_type, which is provided as a type
definition by the container type. For example:
-
Use pair<>
Another way is to use pair<> directly. For
example:
In the first insert() statement the type is not quite
right, so it is converted into the real element type. For this to happen, the
insert() member function is defined as a member
template.
-
Use make_pair()
Probably the most convenient way is to use the make_pair() function. This function produces a
pair object that contains the two values passed as arguments:
Again, the necessary type conversions are performed by the insert() member template.
Here is a simple example of the insertion of an element into a map that also
checks whether the insertion was successful:
To remove an element that has a certain value, you simply call
erase():
This version of erase() returns the number of removed
elements. When called for maps, the return value of erase() can only be 0 or 1.
If a multimap contains duplicates, you can't use erase() to remove only the first element of these
duplicates. Instead, you could code as follows:
You should use the member function find() instead of
the find() algorithm here because it is faster. However,
you can't use the find() member functions to remove
elements that have a certain value (instead of a certain key).
When removing elements, be careful not to saw off the branch on which you are
sitting. There is a big danger that will you remove an element to which your
iterator is referring. For example:
Calling erase() for the element to which you are
referring with pos invalidates pos as an iterator of coll. Thus, if
you use pos after removing its element without any
reinitialization, then all bets are off. In fact, calling ++pos results in undefined behavior.
A solution would be easy if erase() always returned
the value of the following element:
It was a design decision not to provide this trait, because if not needed, it
costs unnecessary time. I don't agree with this decision however, because code
is getting more error prone and complicated (and may cost even more in terms of
time).
Here is an example of the correct way to remove elements to which an iterator
refers:
Note that
pos++ increments
pos so that it refers to the next element but yields a copy
of its original value. Thus,
pos doesn't refer to the
element that is removed when
erase() is called.
Using Maps as Associative Arrays
Associative containers don't typically provide abilities for direct element
access. Instead, you must use iterators. For maps, however, there is an
exception to this rule. Nonconstant maps provide a subscript operator for direct
element access (table below). However,
the index of the subscript operator is not the integral position of the element.
Instead, it is the key that is used to identify the element. This means that the
index may have any type rather than only an integral type. Such an interface is
the interface of a so-called associative array.
Table :- Direct Element Access of Maps with Operator [ ]
| Operation |
Effect |
| m[key] |
Returns a reference to the value of the element with key key Inserts an element with key if
it does not yet exist |
The type of the index is not the only difference from ordinary arrays. In
addition, you can't have a wrong index. If you use a key as the index, for which
no element yet exists, a new element gets inserted into the map automatically.
The value of the new element is initialized by the default constructor of its
type. Thus, to use this feature you can't use a value type that has no default
constructor. Note that the fundamental data types provide a default constructor
that initializes their values to zero.
This behavior of an associative array has both advantages and
disadvantages:
-
The advantage is that you can insert new elements into a map with a more
convenient interface.
For example:
The statement
is processed here as follows:
Process coll["otto"] expression:
-
If an element with key "otto" exists, the expression
returns the value of the element by reference.
-
If, as in this example, no element with key "otto"
exists, the expression inserts a new element automatically with "otto" as key and the value of the default constructor of
the value type as the element value. It then returns a reference to that new
value of the new element.
Assign value 7.7:
-
The second part of the statement assigns 7.7 to the
value of the new or existing element.
The map then contains an element with key "otto" and
value 7.7.
The disadvantage is that you might insert new elements by accident or
mistake. For example, the following statement does something you probably hadn't
intended or expected:
It inserts a new element with key "ottto" and prints
its value, which is 0 by default. However, it should
have generated an error message telling you that you wrote "otto" incorrectly.
Note, too, that this way of inserting elements is slower than the usual way
for maps. This is because the new value is first
initialized by the default value of its type, which is then overwritten by the
correct value.
Exception Handling
Maps and multimaps provide the same behavior as sets and multisets with
respect to exception safety. This behavior is mentioned on page 185.
Examples of Using Maps and Multimaps
Using a Map as an Associative Array
The following example shows the use of a map as an associative array. The map
is used as a stock chart. The elements of the map are pairs in which the key is
the name of the stock and the value is its price:
The program has the following output:
Using Multimap as a Directory
The following example shows how to use a multimap as a dictionary:
The program has the following output:
Find Elements with Certain Values
The following example shows how to use the global find_if() algorithm to find an element with a certain
value:
The output of the program is as follows:
Example with Maps, Strings, and Sorting Criterion at Runtime
Here is another example. It is for advanced programmers rather than STL
beginners. You can take it as an example of both the power and the snags of the
STL. In particular, this example demonstrates the following techniques:
-
How to use maps
-
How to write and use function objects
-
How to define a sorting criterion at runtime
-
How to compare strings in a case-insensitive way
main() creates two containers and calls fillAndPrint() for them. fillAndPrint() fills the containers with the same elements
and prints the contents of them. However, the containers have two different
sorting criteria:
-
coll1 uses the default function object of type RuntimeStringCmp, which compares the elements by using
operator <.
-
coll2 uses a function object of type RuntimeStringCmp that is initialized by value nocase of class RuntimeStringCmp.
nocase forces this function object to sort strings in a case-insensitive
way.
The program has the following output:
The first block of the output prints the contents of the first container that
compares with operator <. The output starts with all
uppercase keys followed by all lowercase keys.
The second block prints all case-insensitive items, so the order changed. But
note, the second block has one item less. This is because the uppercase word "Unternehmen" is, from a case-insensitive point of view,
equal to the lowercase word "unternehmen," and we use a map that
does not allow duplicates according to its comparison criterion. Unfortunately
the result is a mess because the German key that is the translation for
"enterprise" got the value "undertake." So probably a multimap should be used
here. This makes sense because a multimap is the typical container for
dictionaries.
