Previous fileTop of DocumentContentsIndex pageNext file
Apache C++ Standard Library User's Guide

9.2 map and multimap Operations

This section describes the member functions provided by the map and multimap class templates. While member functions provide basic operations, using generic algorithms on map and multimap containers provide even more flexibility. Generic algorithms are described in Part IV.

9.2.1 Declaration and Initialization of map

The declaration of a map follows the pattern we have seen repeatedly in the C++ Standard Library. A map class template is specialized on the type of the keys, the type of the associated values, and an optional comparison operator to be used in comparing keys. If no comparison operator is provided, keys are compared with operator< for the key type.

A map can be declared with no initial elements, or initialized from another container by providing a pair of iterators. In the latter case, the iterators must denote values of type pair; the first field in each pair is taken to be a key, while the second field is a value. A copy constructor also permits maps to be created as copies of other maps:

A map can be assigned to another map, and two maps can exchange their values using the swap() operation, like the other C++ Standard Library containers.

9.2.2 Type Definitions

The class templates map and multimap include a number of type definitions, most commonly used in declaration statements. For example, an iterator for a map of standard strings to ints can be declared as follows:

In addition to iterator, map and multimap define the following types:

Table 15: Type definitions for the classes map and multimap 

Type Definition

key_type

The type of the keys used to index the map.

value_type

The type held by the container, a key/value pair.

mapped_type

The type associated with values.

const_iterator

An iterator that does not allow modification of the underlying sequence.

reverse_iterator

An iterator that moves in a backward direction.

const_reverse_iterator

A reverse iterator that does not allow modification of the underlying sequence.

reference

A reference to an underlying value.

const_reference

A reference to an underlying value that will not permit the element to be modified.

pointer

A pointer to an underlying element

const_pointer

A constant pointer to an underlying element.

size_type

An unsigned integer type, used to refer to the size of containers.

key_compare

A function object that can be used to compare two keys.

value_compare

A function object that can be used to compare two elements.

difference_type

A signed integer type, used to describe the distances between iterators.

allocator_type

An allocator used by the container for all storage management.

9.2.3 Insertion and Access

Values can be inserted into a map or a multimap using the insert() operation. Note that the argument must be a key-value pair. This pair is often constructed using the datatype value_type associated with the map:

Insertions can also be performed using an iterator pair, for example, as generated by another map.

With a map, but not a multimap, values can be accessed and inserted using the subscript operator. Simply using a key as a subscript creates an entry--the default element is used as the associated value. Assigning to the result of the subscript changes the associated binding.

9.2.4 Removal of Values

Values can be removed from a map or a multimap by naming the key value. In a multimap, the erasure removes all elements with the associated key. An element to be removed can also be denoted by an iterator, like the iterator yielded by a find() operation. A pair of iterators can be used to erase an entire range of elements:

If the underlying element type provides a destructor, the destructor is invoked prior to removing the key and value pair from the collection.

9.2.5 Iterators

The member functions begin() and end() produce bidirectional iterators for both maps and multimaps. Dereferencing an iterator for either a map or a multimap yields a pair of key/value elements. The field names first and second can be applied to these values to access the individual fields. The first field is constant, and cannot be modified. The second field, however, can be used to change the value being held in association with a given key. Elements are generated in sequence, based on the ordering of the key fields.The member functions rbegin() and rend() produce iterators that yield the elements in reverse order.


NOTE -- Unlike a vector or deque, the insertion or removal of elements from a map does not invalidate iterators which may be referencing other portions of the container.

9.2.6 Searching and Counting

The member function size() yields the number of elements held by a container. The member function empty() returns a boolean true value if the container is empty, and is generally faster than testing the size against zero.

The member function find() takes a key argument, and returns an iterator denoting the associated key/value pair. For multimaps, the first such value is returned. In both cases, the past-the-end iterator is returned if no such value is found:

The member function lower_bound() yields the first entry that matches the argument key, while the member function upper_bound() returns the first value past the last entry matching the argument. Finally, the member function equal_range() returns a pair of iterators, holding the lower and upper bounds. An example showing the use of these procedures is presented later in this chapter.

The member function count() returns the number of elements that match the key value supplied as the argument. For a map, this value is always either zero or one, whereas for a multimap it can be any nonnegative value. If you simply want to determine whether or not a collection contains an element indexed by a given key, using count() is often easier than using the find() function and testing the result against the end-of-sequence iterator:

9.2.7 Element Comparisons

The member functions key_comp() and value_comp(), which take no arguments, return function objects that can be used to compare elements of the key or value types. Values used in these comparisons need not be contained in the collection, and neither function has any effect on the container.

9.2.8 Other map Operations

Because maps and multimaps are ordered collections, and because the iterators for maps return pairs, many of the functions described in Part IV (Algorithms), are meaningless or difficult to use. However, there are a few notable exceptions. The functions std::for_each(), std::adjacent_find(), and std::accumulate() each have their own uses. In all cases it is important to remember that the functions supplied as arguments should take a key/value pair as arguments.



Previous fileTop of DocumentContentsIndex pageNext file