13.35 map

13.35 <map>

The <map> header is one of the standard container template headers. It declares the map and multimap class templates and a few global function templates that operate on map and multimap objects.

A map is a container that stores pairs of keys and values. Looking up keys, inserting keys, and deleting keys can all be performed in logarithmic or better time. Maps support bidirectional iterators (no random access). In other languages and libraries, maps are also called dictionaries and associative arrays.

See Chapter 10 for information about containers. See the <utility> section later in this chapter for information about the pair class template.

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.

Examples

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 or 1 .

bool empty ( ) const

Returns size( ) == .

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, 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.

 template <class Key, class T, class Compare = less<Key>,           class Alloc = allocator<pair<const Key, T> > > class  multimap  { 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 multimap;   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  multimap  (const Compare& comp = Compare(  ),      const Alloc& = Alloc(  ));   template <class InputIterator>  multimap  (InputIterator first, InputIterator last,     const Compare& comp = Compare(  ), const Alloc& = Alloc(  ));  multimap  (const multimap<Key,T,Compare,Alloc>& x);  ~multimap  (  );   multimap<Key,T,Compare,Alloc>&  operator=  (const multimap<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;   // Modifiers   iterator  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  (multimap<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 multimap class template represents a map container that can store duplicate keys. A map stores pairs of 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. See Example 13-28 (earlier in this section), which shows how to change a key by erasing and reinserting an object.

Inserting into a map does not invalidate any iterators for that map. Erasing an element invalidates only iterators that refer to that element.

Inserting a single item 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 following are the member functions of multimap . Note that multimap does not have a subscript operator.

explicit multimap (const Compare& comp = Compare( ), const Alloc& = Alloc( ))

Creates an empty map.

template <class InputIterator>

multimap (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.

multimap (const multimap<Key,T,Compare,Alloc>& x)

Creates a new map and copies 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 in linear time.

size_type count (const key_type& x) const

Returns the number of pairs whose keys are equivalent to x . Complexity is proportional to log( size( ) ) + the return value.

bool empty ( ) const

Returns size( ) == .

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 all the pairs equivalent to x if any are present, returning a count of the number of pairs erased. The third version erases all elements in the range [ first , last ). The last two forms take time proportional to log( size( ) ) + the number of elements erased.

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. If x occurs more than once, the iterator might point to any of the equivalent pairs.

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. The first version inserts the pair x in logarithmic time.

The third version copies all the pairs in the range [ first , last ), which must be pointing to a different multimap 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 the position of its first occurrence; 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 (multimap<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 all occurrences of x . Performance is logarithmic.

value_compare value_comp ( ) const

multimap<Key,T,Compare,Alloc>& operator= (const multimap<Key,T,Compare,Alloc>& x)

Erases all the elements of the map and replaces them with copies of the elements of x .

13.35 <map>

Examples

Example 13-28. One way to modify a key in a map

Example 13-29. Using a map to count word frequencies

See Also

See Also

See Also

See Also

See Also