The map and the multimap are both containers that manage key/value
pairs as single components. The essential difference between the two is
that in a map the keys must be unique, while a multimap permits
duplicate keys. In both containers, the sort order of components is the
sort order of the keys, with the values corresponding to keys
determining the order for duplicate keys in a multimap. Nearly
everything said here about maps is also true of multimaps, with minor
differences showing up in the count() member function and one
of the insert() member functions.
Default Constructor
- map<Ktype, Vtype> m;
- Construct an empty map m which can hold values of type
pair<Ktype, Vtype>.
Copy Constructor
There is, of course, only one copy constructor, but there are two
syntactic forms that invoke it, and both are shown.
- map<Ktype, Vtype> m(otherMap);
- Construct m as a copy of otherMap, whose
component type must be pair<Ktype,
Vtype>. The copy has the same size as the
original.
- map<Ktype, Vtype> m = otherMap;
- Copy constructor (alternate usage syntax).
Other Constructors
- map<Ktype, Vtype> m(binPred);
- Construct an empty map m which can hold values of type
pair<Ktype, Vtype>, and
which uses binPred to sort keys.
- map<Ktype, Vtype> m(inIterBegin, inIterEnd);
- Construct m containing values from the range
[inIterBegin,inIterEnd) in another (not necessarily map)
container, but whose component type is the same as the component type
of m.
- map<Ktype, Vtype> m(inIterBegin, inIterEnd, binPred);
- Construct m containing values from the range
[inIterBegin,inIterEnd) in another (not necessarily map)
container, but whose component type is the same as the component type
of m, and which uses binPred to sort keys.
Destructor
- m.~map<Ktype, Vtype>()
- Destroy all components of m and free the associated
memory.
Assignment operator
- m1 = m2
- Assign m2 to m1, and return the common value.
The map on the left of an assignment receives the values and size of
the one on the right.
Relational operators
Maps are compared in the "lexicographic ordering" sense. This
essentially means that the two maps are compared by comparing their
pair values pairwise, starting at the beginning, with each comparison
looking at two pair values in corresponding positions, until a
determination of the relationship between the two maps can be made.
Only maps of the same component type can be compared of course, and the
== and < operators must be defined for the types
used as the Ktype and Vtype for the pairs in the component type of the
maps.
- m1 == m2
- Return true if m1 and m2 have the same
component type and the same size, and the components with the same
keys have the same value; otherwise return false.
- m1 != m2
- Return true if m1==m2 returns false;
otherwise return false.
- m1 < m2
- Return true if, in the pairwise comparison of values
from m1 and m2, in the first pair in which the two
values differ, the one from m1 is less than the one from
m2; otherwise return false.
- m1 <= m2
- Return true if either m1<m2 or
m1==m2 is true; otherwise return
false.
- m1 > m2
- Return true if m2<m1 is true;
otherwise return false.
- m1 >= m2
- Return true if either m1>m2 or
m1==m2 is true, otherwise return
false.
operator[ ]
- m[key]
- Return a reference (or const_reference) to the
component of m whose key value is key, if this
component exists. If this component does not exist, insert a new
component into m, the value of whose key is key,
and for which the corresponding value is the default value of type
Vtype.
Each of the member functions in this section has both a
const and a non-const version.
- m.begin()
- Return an iterator (or const_iterator) pointing
to the first component of m.
- m.end()
- Return an iterator (or const_iterator) pointing
to one-past-the-last component of m.
- m.rbegin()
- Return a reverse_iterator (or
const_reverse_iterator) pointing to the last component of
m.
- m.rend()
- Return a reverse_iterator (or
const_reverse_iterator) pointing to one-before-the-first
component of m.
- m.max_size()
- Return a value of type size_type giving the maximum
possible size of m, which will depend on the size of the
component type <Ktype, Vtype> of the map object, and
the amount of available memory.
- m.size()
- Return a value of type size_type giving the number of
values currently in m.
- m.empty()
- Return true if m is empty (contains zero
values); otherwise return false.
- m.insert(pVal)
-
Try to insert the pair value pVal into m and
return
- for a map, a value of type pair<iterator,
bool>, with the iterator value pointing at the
new component, if it actually went into the map, and the
bool value being true if the insertion
succeeded; otherwise the iterator points at the pair value that
was already in the map, and the bool value is
false
- for a multimap, an iterator pointing at the newly inserted
component
- m.insert(iter, pVal)
- Try to insert the pair value pVal into m, using
iter as a "hint" for where the search for the insertion
point should begin, and return an iterator pointing to the new
component, or to the old component if the value was already in
m.
- m.insert(inIterBegin, inIterEnd)
- Try to insert into m the pair values from the range
[inIterBegin,inIterEnd) in another (not necessarily map)
container, but whose values must be of the same type as the values of
m.
- m.clear()
- Delete all values of m. The size of m is
reduced to zero.
- m.erase(kVal)
- Delete all components for which the key is kVal and
return the number of deleted values (0 or 1). The size of m
is reduced by this value.
- m.erase(iter)
- Delete the value of m pointed to by iter. The
size of m is reduced by one.
- m.erase(iterBegin, iterEnd)
- Delete all values of m from the range
[iterBegin,iterEnd). The size of m is reduced by
the number of values in this range.
- m.count(kVal)
- Return the number of components in m which have their
key equal to kVal. This number is restricted to be 0 or 1
for a map, since keys are unique.
- m.find(kVal)
- Return an iterator (or const_iterator) pointing
to the component in m in which the key value is
kVal, or to one-past-the-last if this component does not
exist.
- m.lower_bound(kVal)
- Return an iterator (or const_iterator) pointing
to the first component in m in which the key value is >=
kVal, or to one-past-the-last if this component does not
exist. (This is the first place that a component with a key value of
kVal could be inserted.)
- m.upper_bound(kVal)
- Return an iterator (or const_iterator) pointing
to the first component in m in which the key value is >
kVal, or to one-past-the-last if this component does not
exist. (This is the last place that a component with a key value of
kVal could be inserted.)
- m.equal_range(kVal)
- Return a pair with both components of type iterator (or
const_iterator) containing the same two iterators that would
be returned by lower_bound() and upper_bound() (in
that order).
- m.swap(otherMap)
- Exchange values in m with those in otherMap.
The sizes are swapped as well.
- m.key_comp()
- Return the function object used to compare values of type
Ktype (the type of the first component of the pairs stored
in the map).
- m.value_comp()
- Return the function object used to compare values of type
Vtype (the type of the second component of the pairs stored
in the map).
- m.getallocator()
- Return the allocator of m. (This is possibly the most
infrequently used of all member functions of the map class.)
- The somewhat unusual behavior of m[kVal] for maps
- If you have used the STL vector and deque container classes, then
you will have certain expectations about the use of m[kVal] in the
context of the map container class. So, be sure to read carefully the
description of the behavior of operator[ ] for maps (see the
relevant section above).
- Implementation
- Standard C++ does not say how the STL containers and algorithms
must be implemented. It does, however, state certain constraints,
such as complexity constraints, to which each implementation must
adhere. Thus it is much better to base your programs on the STL's
performance guarantees, rather than upon any assumption about how a
particular feature, like the map or multimap classes, may be
implemented. As users, all we have a right to assume is that maps and
multimaps sort their components automatically according to the sort
order of the keys in the key/value pairs. That having been said, we
can also say that maps and multimaps are generally implelmented using
some variation of a balanced binary search tree, not because the
Standard mandates this, but because that is the most logical choice,
given the perfomance constraints imposed on these two
containers.
There are two groups of sample programs:
- The first group involves only STL maps and generic C++.
- The second group highlights the differences between maps and
multimaps.
The programs should be studied in the sequence given, since the
description of each new sample program in the sequence mentions only
the new features illustrated for the first time in that particular
program, and features seen in earlier sample programs will continue to
reappear in later programs.
All of the programs have been compiled and run successfully under
Microsoft Visual Studio .NET 2005, unless otherwise noted.
Programs involving only maps (and generic C++)
- map01.cpp | Windows_executable | program_output (text)
- Illustrates the default map constructor, inserting and accessing
map values with m[kVal], and the
member functions size() and empty().
- map02.cpp | Windows_executable | program_output (text)
- Illustrates the copy constructor and the overloaded assignment
operator = for maps.
- map03.cpp | Windows_executable | program_output (text)
- Illustrates member function max_size(), and how the
maximum size for a map object depends on the size of its component
type.
- map04.cpp | Windows_executable | program_output (text)
- Illustrates the unusual behavior of m[kVal].
- map05.cpp | Windows_executable | program_output (text)
- Illustrates another map constructor, the default (bidirectional)
iterator for the map class, member functions begin() and
end(), and the use of operators =, ++,
--, ==, !=, -> and *
with map iterators.
- map06.cpp | Windows_executable | program_output (text)
- Illustrates more map construction and manipulation, as well as
the use of the make_pair() function from
<utility> to create some pairs for a map.
- map07.cpp | Windows_executable | program_output (text)
- Illustrates reverse iterators for the map class, as well as
member functions rbegin() and rend().
- map08.cpp | Windows_executable | program_output (text)
- Illustrates a typical use of a const iterator.
- map09.cpp | Windows_executable | program_output (text)
- Illustrates the count() member function.
- map10.cpp | Windows_executable | program_output (text)
- Illustrates the find() member function.
- map11.cpp | Windows_executable | program_output (text)
- Illustrates the insert() member function.
- map12.cpp | Windows_executable | program_output (text)
- Illustrates the clear() and erase() member
functions.
- map13.cpp | Windows_executable | program_output (text)
- Illustrates the lower_bound() member function.
- map14.cpp | Windows_executable | program_output (text)
- Illustrates the upper_bound() member function.
- map15.cpp | Windows_executable | program_output (text)
- Illustrates the equal_range() member function.
- map16.cpp | Windows_executable | program_output (text)
- Illustrates the swap() member function.
- map17.cpp | Windows_executable | program_output (text)
- Illustrates how the relational operators can be used to compare
one map with another.
- map18.cpp | Windows_executable | program_output (text)
- Illustrates the use of a map to create a "phone book".
Programs highlighting the differences between maps and
multimaps
Since the multimap interface is very nearly the same as the map
interface, the sample programs in this section are designed to
highlight the differences between maps and multimaps.
- multimap01.cpp |
Windows_executable | program_output (text)
- Illustrates the difference in behavior when you try to insert
pairs with duplicate keys into a map and into a multimap.
- multimap02.cpp |
Windows_executable | program_output (text)
- Illustrates how to find the first of several duplicate keys and
then process all components with that key.
- multimap03.cpp |
Windows_executable | program_output (text)
- Illustrates why a multimap makes a "better phone book" than the
map did when we used a map for the same purpose in map18.cpp.
For enhanced readability in each of the prototypes given below, each
parameter in each parameter list appears on a separate line. Also, some
formatting liberties are taken, in the interest of greater readability.
For example, rather than aligning all prototypes at the left margin,
const and non-const versions of a member function are
aligned in such a way as to allow the reader to more easily compare the
two visually.
Template specification for the map class
template<class Ktype,
class Vtype,
class BinaryPred less<Ktype>,
class Allocator = allocator<Ktype, Vtype> >
class map { ... }
Constructors
explicit map(const BinaryPred& binPred = BinaryPred(),
const Allocator& a = Allocator());
template<class InIterator>
map(InIterator inIterBegin,
InIterator inIterEnd,
const BinaryPred& binPred = BinaryPred(),
const Allocator& a = Allocator());
Copy Constructor
map(const map<Ktype, Vtype, BinaryPred, Allocator>& otherMap);
Destructor
~map();
begin
iterator begin();
const_iterator begin() const;
clear
void clear();
count
size_type count(const Ktype& kVal) const;
empty
bool empty() const;
end
iterator end();
const_iterator end() const;
equal_range
pair<iterator, iterator> equal_range(const Ktype& kVal);
pair<const_iterator, const_iterator> equal_range(const Ktype& kVal) const;
erase
size_type erase(const Ktype& kVal);
void erase(iterator iter);
void erase(iterator iterBegin,
iterator iterEnd);
find
iterator find(const Ktype& kVal);
const_iterator find(const Ktype& kVal) const;
get_allocator
allocator_type get_allocator() const;
insert
pair<iterator, bool> insert(const pair<Ktype, Vtype>& vVal);
iterator insert(iterator iter,
const pair<Ktype, Vtype>& vVal);
template<class InIterator>
void insert(InIterator inIterBegin,
InIterator inIterEnd);
key_comp
key_compare key_comp() const;
lower_bound
iterator lower_bound(const Ktype& kVal);
const_iterator lower_bound(const Ktype& kVal) const;
max_size
size_type max_size() const;
operator[ ]
reference operator[](size_type i);
const_reference operator[](size_type i) const;
rbegin
reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
rend
reverse_iterator rend();
const_reverse_iterator rend() const;
size
size_type size() const;
swap
void swap(map<T, Allocator>& otherMap);
upper_bound
iterator upper_bound(const Ktype& kVal);
const_iterator upper_bound(const Ktype& kVal) const;
value_comp
value_compare value_comp() const;