map class template — Associative map container with unique keys
template <typename Key, typename T, typename Compare = less<Key>, typename Alloc = allocator<pair<const Key, T> > > class map { public: typedef Key key_type; typedef T mapped_type; typedef pair<const Key, T> value_type; typedef Compare key_compare; typedef Alloc allocator_type; typedef typename Alloc::reference reference; typedef typename Alloc::const_reference const_reference; typedef . . . iterator; typedef . . . const_iterator; typedef . . . size_type; typedef . . . difference_type; typedef typename Alloc::pointer pointer; typedef typename Alloc::const_pointer const_pointer; typedef std::reverse_iterator<iterator> reverse_iterator; typedef std::reverse_iterator<const_iterator> const_reverse_iterator; class value_compare : public binary_function<value_type,value_type,bool> { friend class map; protected: Compare comp; value_compare(Compare c) : comp(c) {} public: bool operator( )(const value_type& x, const value_type& y) const { return comp(x.first, y.first); } }; explicit map(const Compare& comp = Compare( ), const Alloc& = Alloc( )); template <class InputIterator> map(InputIterator first, InputIterator last, const Compare& comp = Compare( ), const Alloc& = Alloc( )); map(const map<Key,T,Compare,Alloc>& x); ~map( ); map<Key,T,Compare,Alloc>& operator=(const map<Key,T,Compare,Alloc>& x); allocator_type get_allocator( ) const; // Iterators iterator begin( ); const_iterator begin( ) const; iterator end( ); const_iterator end( ) const; reverse_iterator rbegin( ); const_reverse_iterator rbegin( ) const; reverse_iterator rend( ); const_reverse_iterator rend( ) const; // Capacity bool empty( ) const; size_type size( ) const; size_type max_size( ) const; // Element access T& operator[](const key_type& x); // Modifiers pair<iterator, bool> insert(const value_type& x); iterator insert(iterator hintpos, const value_type& x); template <class InputIterator> void insert(InputIterator first, InputIterator last); void erase(iterator position); size_type erase(const key_type& x); void erase(iterator first, iterator last); void swap(map<Key,T,Compare,Alloc>&); void clear( ); // Observers key_compare key_comp( ) const; value_compare value_comp( ) const; // Map operations iterator find(const key_type& x); const_iterator find(const key_type& x) const; size_type count(const key_type& x) const; iterator lower_bound(const key_type& x); const_iterator lower_bound(const key_type& x) const; iterator upper_bound(const key_type& x); const_iterator upper_bound(const key_type& x) const; pair<iterator,iterator> equal_range(const key_type& x); pair<const_iterator,const_iterator> equal_range(const key_type& x) const; };
The map
class template
represents a map container. A map stores pairs of unique keys and
associated objects, in which the key type is specified by the
Key
template parameter, and the
associated type is the T
template
parameter. The values stored in the map are of type pair<const
Key
, T>
(which has the convenience typedef
value_type
).
A map's iterators are bidirectional. They return value_type
references; use the first
member to access the key or second
to access the associated
object.
Note that keys are const
in
the map. You must not change the key while it is stored in a map.
More precisely, you must not change the key in a way that alters its
relative order with the other keys in the map. If you need to modify
a key, you can erase the key from the map, modify the key, and
insert the new key with its original associated value, as shown in
Example 13-28.
Example 13-28. One way to modify a key in a map
template <typename Key, typename T, typename C, typename A> void change_key(std::map<Key, T, C, A>& m, const Key& oldkey, const Key& newkey) { using std::map; typedef typename map<Key, T, C, A>::iterator map_iterator; map_iterator i = m.find(oldkey); if (i != m.end( )) { // Save a copy of i->second because erase invalidates i. T tmp = i->second; m.erase(i); m[newkey] = tmp; } // Exercise: What if newkey is already in m? }
Within a map, keys are ordered in ascending order, according
to the Compare
template parameter
(which can be a function pointer or functor that compares two
objects of type Key
and returns
true if the first argument should come before the second). Keys must
be unique, but note that uniqueness is determined only by calling
Compare
, not by using the
==
operator. That is, two
objects, a
and b
, are different (and therefore can both
be present in a single map
object) if Compare(a
, b)
is true or Compare(b
, a)
is true. See multimap
later in this section for a map
container that can store non-unique keys.
Inserting into a map does not invalidate any iterators for that map or references to pairs in the map. Erasing an element invalidates only iterators and references that refer to that element.
Inserting into a map and searching for an element in a map usually take logarithmic time. Erasing a single element, given an iterator, takes amortized constant time.
The subscript operator ([]
)
lets you use a map as an associative array, for which the array
indices are keys. If a key is not already present in the map, it is
added. Using operator[]
allows
for compact, easy-to-read code, as you can see in Example 13-29, which shows how
to use map
to count word
frequencies in the standard input.
Example 13-29. Using a map to count word frequencies
#include <cstddef> #include <iostream> #include <istream> #include <map> #include <ostream> #include <string> typedef std::map<std::string, std::size_t> freqmap; // Print a single word and its count. void print(const freqmap::value_type info) { std::cout << info.first << '\t' << info.second << '\n'; } int main( ) { freqmap fm; std::string word; // Count words. If a word is not in the map, add it. When a new word is added, // its count is initially 0. Each time, including the first, increment the // count. while (std::cin >> word) ++fm[word]; // Print the frequencies of each word, in order. std::for_each(fm.begin( ), fm.end( ), print); }
The following are the member functions of map
:
explicit
map
(const Compare& comp = Compare( ),
const Alloc& = Alloc( ))
Creates an empty map.
template <class
InputIterator>
, map
(InputIterator first, InputIterator last,
const
Compare&
comp
=
Compare(
)
, const
Alloc&
=
Alloc(
))
Creates an empty map and then copies all pairs in the
range [first
, last
) into the new map.
map
(const map<Key,T,Compare,Alloc>&
x)
Creates a new map and copies the allocator and all the
pairs from x
to the new
map.
iterator
begin
( )
, const_iterator
begin
( )
const
Returns an iterator that points to the first item in the map.
void
clear
( )
Erases every item in the map.
size_type
count
(const
key_type&
x)
const
Returns the number of pairs whose keys are equivalent to
x
. This value is always
0
or 1
.
bool
empty
( )
const
Returns size( )
==
0
.
iterator
end
( )
, const_iterator
end
( )
const
Returns an iterator that points to one past the last item in the map.
pair<iterator,iterator>
equal_range
(const key_type&
x)
, pair<const_iterator,const_iterator>
equal_range
(const
key_type&
x)
const
Returns the lower bound and upper bound as a pair
:
std::make_pair(lower_bound(x), upper_bound(x))
void
erase
(iterator
position)
, size_type
erase
(const key_type&
x)
, void
erase
(iterator first, iterator
last)
Erases one or more pairs from the map. The first version
erases the pair at position
in constant time (amortized over many calls). The second
version erases the pair equivalent to x
, if it is present, returning a
count of the number of pairs erased, that is, 0
or 1
. It runs in logarithmic time. The
third version erases all elements in the range [first
, last
) in a time proportional to log
size( )
+ (last
- first
).
iterator
find
(const key_type&
x)
, const_iterator
find
(const key_type& x)
const
Searches for a pair whose key is equivalent to x
and returns an iterator that
points to that pair or end(
)
if it is not found. It runs in logarithmic
time.
allocator_type
get_allocator
( )
const
Returns the map's allocator.
pair<iterator,
bool>
insert
(const value_type&
x)
, iterator
insert
(iterator
hintpos
, const
value_type&
x)
, template
<class
InputIterator> void
insert
(InputIterator
first
, InputIterator
last)
Inserts one or more pairs into the map, but only if an
equivalent key is not already present in the map. If the key
is already present, the insert attempt is ignored. The first
version attempts to insert the pair x
in logarithmic time.
The second version inserts the pair x
using hintpos
as a position hint. If
x
is inserted immediately
after hintpos
, the
performance is constant (amortized over many insertions); at
any other position, the performance is logarithmic. Use this
form when inserting many items that are already in the desired
order.
The third version copies all the pairs in the range
[first
, last
), which must be pointing to a
different map
object. If
the items are already in the desired order, the performance is
linear; otherwise, it is N
log
(size( )
+
N
)
, in which
N
is last
- first
.
key_compare
key_comp
( )
const
Returns the comparator function pointer or object, which
compares keys. The key_compare
type is the same as the
Compare
template parameter.
See also the value_comp
member.
iterator
lower_bound
(const
key_type&
x)
, const_iterator
lower_bound
(const
key_type&
x) const
Returns an iterator that points to the first pair in the
map that does not come before x
. That is, if x
is in the map, the iterator points
to its position; otherwise, the iterator points to the first
position where x
should be
inserted. Performance is logarithmic.
size_type
max_size
( )
const
Returns the largest number of pairs that can be in the map.
reverse_iterator
rbegin
( )
, const_reverse_iterator
rbegin
( )
const
Returns a reverse iterator that points to the last element of the map.
reverse_iterator
rend
( )
, const_reverse_iterator
rend
( )
const
Returns a reverse iterator that points to one position before the first element of the map.
size_type
size
( )
const
Returns the number of pairs in the map.
void
swap
(map<Key,T,Compare,Alloc>&)
Swaps the contents of the map with the contents of
x
.
iterator
upper_bound
(const key_type&
x)
, const_iterator
upper_bound
(const key_type& x) const
Returns an iterator that points to the first pair in the
map that comes after x
.
Performance is logarithmic.
value_compare
value_comp
( )
const
Returns a value_compare
object, which can be
used to compare pairs. The value_compare
object takes two
value_type
arguments and
compares their keys, returning true
if the first should come before
the second in the map.
map<Key,T,Compare,Alloc>&
operator=
(const
map<Key,T,Compare,Alloc>&
x)
Erases all the elements of the map and replaces them
with copies of the elements of x
.
T&
operator[]
(const
key_type&
x)
Returns a reference to the object associated with the
key x
. If x
is not in the map, it is added
with a default associated object, and a reference to that new
object is returned. That is, operator[]
returns:
(*((insert(std::make_pair(x, T( )))).first)).second
Note that there is no const
version of this
operator.