C++ Maps

C/C++ Reference

begin
Syntax:
  #include <map>
  iterator begin();
  const_iterator begin() const;

The function begin() returns an iterator to the first element of the map. begin() should run in constant time.

For example, the following code uses begin() to initialize an iterator that is used to traverse a list:

  map<string,int> stringCounts;
  string str;  

  while( cin >> str ) stringCounts[str]++;   

  map<string,int>::iterator iter;   
  for( iter = stringCounts.begin(); iter != stringCounts.end(); iter++ ) {
    cout << "word: " << iter->first << ", count: " << iter->second << endl;
  }

When given this input:

  here are some words and here are some more words

...the above code generates this output:

  word: and, count: 1
  word: are, count: 2
  word: here, count: 2
  word: more, count: 1
  word: some, count: 2
  word: words, count: 2
Related topics:

clear
Syntax:
  #include <map>
  void clear();

The function clear() deletes all of the elements in the map. clear() runs in linear time.

Related topics:

count
Syntax:
  #include <map>
  size_type count( const key_type& key );

The function count() returns the number of occurrences of key in the map.

count() should run in logarithmic time.


empty
Syntax:
  #include <map>
  bool empty() const;

The empty() function returns true if the map has no elements, false otherwise.

For example, the following code uses empty() as the stopping condition on a while loop to clear a map and display its contents in order:

  struct strCmp {
    bool operator()( const char* s1, const char* s2 ) const {
      return strcmp( s1, s2 ) < 0;
    }
  };

  ...

  map<const char*, int, strCmp> ages;
  ages["Homer"] = 38;
  ages["Marge"] = 37;
  ages["Lisa"] = 8;
  ages["Maggie"] = 1;
  ages["Bart"] = 11;

  while( !ages.empty() ) {
    cout << "Erasing: " << (*ages.begin()).first << ", " << (*ages.begin()).second << endl;
    ages.erase( ages.begin() );
  }

When run, the above code displays:

  Erasing: Bart, 11
  Erasing: Homer, 38
  Erasing: Lisa, 8
  Erasing: Maggie, 1
  Erasing: Marge, 37
Related topics:

end
Syntax:
  #include <map>
  iterator end();
  const_iterator end() const;

The end() function returns an iterator just past the end of the map.

Note that before you can access the last element of the map using an iterator that you get from a call to end(), you'll have to decrement the iterator first.

For example, the following code uses begin() and end() to iterate through all of the members of a vector:

 vector<int> v1( 5, 789 );
 vector<int>::iterator it;
 for( it = v1.begin(); it != v1.end(); it++ ) {
   cout << *it << endl;
 }              

The iterator is initialized with a call to begin(). After the body of the loop has been executed, the iterator is incremented and tested to see if it is equal to the result of calling end(). Since end() returns an iterator pointing to an element just after the last element of the vector, the loop will only stop once all of the elements of the vector have been displayed.

end() runs in constant time.

Related topics:

equal_range
Syntax:
  #include <map>
  pair<iterator, iterator> equal_range( const key_type& key );

The function equal_range() returns two iterators - one to the first element that contains key, another to a point just after the last element that contains key.


erase
Syntax:
  #include <map>
  void erase( iterator pos );
  void erase( iterator start, iterator end );
  size_type erase( const key_type& key );

The erase function() either erases the element at pos, erases the elements between start and end, or erases all elements that have the value of key.

For example, the following code uses erase() in a while loop to incrementally clear a map and display its contents in order:

  struct strCmp {
    bool operator()( const char* s1, const char* s2 ) const {
      return strcmp( s1, s2 ) < 0;
    }
  };

  ...

  map<const char*, int, strCmp> ages;
  ages["Homer"] = 38;
  ages["Marge"] = 37;
  ages["Lisa"] = 8;
  ages["Maggie"] = 1;
  ages["Bart"] = 11;

  while( !ages.empty() ) {
    cout << "Erasing: " << (*ages.begin()).first << ", " << (*ages.begin()).second << endl;
    ages.erase( ages.begin() );
  }

When run, the above code displays:

  Erasing: Bart, 11
  Erasing: Homer, 38
  Erasing: Lisa, 8
  Erasing: Maggie, 1
  Erasing: Marge, 37
Related topics:

find
Syntax:
  #include <map>
  iterator find( const key_type& key );

The find() function returns an iterator to key, or an iterator to the end of the map if key is not found.

find() runs in logarithmic time.

For example, the following code uses the find() function to determine how many times a user entered a certain word:

  map<string,int> stringCounts;
  string str;

  while( cin >> str ) stringCounts[str]++;

  map<string,int>::iterator iter = stringCounts.find("spoon");
  if( iter != stringCounts.end() ) {
    cout << "You typed '" << iter->first << "' " << iter->second << " time(s)" << endl;
  }

When run with this input:

my spoon is too big.  my spoon is TOO big!  my SPOON is TOO big!  I am a BANANA!

...the above code produces this output:

You typed 'spoon' 2 time(s)

insert
Syntax:
  #include <map>
  iterator insert( iterator i, const TYPE& pair );
  void insert( input_iterator start, input_iterator end );
  pair<iterator,bool> insert( const TYPE& pair );

The function insert() either:

  • inserts pair after the element at pos (where pos is really just a suggestion as to where pair should go, since sets and maps are ordered), and returns an iterator to that element.
  • inserts a range of elements from start to end.
  • inserts pair<key,val>, but only if no element with key key already exists. The return value is an iterator to the element inserted (or an existing pair with key key), and a boolean which is true if an insertion took place.

For example, the following code uses the insert() function (along with the make_pair() function) to insert some data into a map and then displays that data:

  map<string,int> theMap;
  theMap.insert( make_pair( "Key 1", -1 ) ); 
  theMap.insert( make_pair( "Another key!", 32 ) ); 
  theMap.insert( make_pair( "Key the Three", 66667 ) ); 

  map<string,int>::iterator iter;
  for( iter = theMap.begin(); iter != theMap.end(); ++iter ) {
    cout << "Key: '" << iter->first << "', Value: " << iter->second << endl; 
  }

When run, the above code displays this output:

  Key: 'Another key!', Value: 32
  Key: 'Key 1', Value: -1
  Key: 'Key the Three', Value: 66667

Note that because maps are sorted containers, the output is sorted by the key value. In this case, since the map key data type is string, the map is sorted alphabetically by key.

Related topics:

key_comp
Syntax:
  #include <map>
  key_compare key_comp() const;

The function key_comp() returns the function that compares keys.

key_comp() runs in constant time.

Related topics:

lower_bound
Syntax:
  #include <map>
  iterator lower_bound( const key_type& key );

The lower_bound() function returns an iterator to the first element which has a value greater than or equal to key.

lower_bound() runs in logarithmic time.

Related topics:

Map Constructors & Destructors
Syntax:
  #include <map>
  map();
  map( const map& m );
  map( iterator start, iterator end );
  map( iterator start, iterator end, const key_compare& cmp );
  map( const key_compare& cmp );
  ~map();

The default constructor takes no arguments, creates a new instance of that map, and runs in constant time. The default copy constructor runs in linear time and can be used to create a new map that is a copy of the given map m.

You can also create a map that will contain a copy of the elements between start and end, or specify a comparison function cmp.

The default destructor is called when the map should be destroyed.

For example, the following code creates a map that associates a string with an integer:

  struct strCmp {
    bool operator()( const char* s1, const char* s2 ) const {
      return strcmp( s1, s2 ) < 0;
    }
  };

  ...

  map<const char*, int, strCmp> ages;
  ages["Homer"] = 38;
  ages["Marge"] = 37;
  ages["Lisa"] = 8;
  ages["Maggie"] = 1;
  ages["Bart"] = 11;

  cout << "Bart is " << ages["Bart"] << " years old" << endl;
Related topics:

Map operators
Syntax:
  #include <map>
  TYPE& operator[]( const key_type& key );
  map operator=(const map& c2);
  bool operator==(const map& c1, const map& c2);
  bool operator!=(const map& c1, const map& c2);
  bool operator<(const map& c1, const map& c2);
  bool operator>(const map& c1, const map& c2);
  bool operator<=(const map& c1, const map& c2);
  bool operator>=(const map& c1, const map& c2);

Maps can be compared and assigned with the standard comparison operators: ==, !=, <=, >=, <, >, and =. Individual elements of a map can be examined with the [] operator.

Performing a comparison or assigning one map to another takes linear time.

Two maps are equal if:

  1. Their size is the same, and
  2. Each member in location i in one map is equal to the the member in location i in the other map.

Comparisons among maps are done lexicographically.

For example, the following code defines a map between strings and integers and loads values into the map using the [] operator:

  struct strCmp {
    bool operator()( const char* s1, const char* s2 ) const {
      return strcmp( s1, s2 ) < 0;
    }
  };

  map<const char*, int, strCmp> ages;
  ages["Homer"] = 38;
  ages["Marge"] = 37;
  ages["Lisa"] = 8;
  ages["Maggie"] = 1;
  ages["Bart"] = 11;

  cout << "Bart is " << ages["Bart"] << " years old" << endl;

  cout << "In alphabetical order: " << endl;
  for( map<const char*, int, strCmp>::iterator iter = ages.begin(); iter != ages.end(); iter++ ) {
    cout << (*iter).first << " is " << (*iter).second << " years old" << endl;
  }

When run, the above code displays this output:

  Bart is 11 years old
  In alphabetical order:
  Bart is 11 years old
  Homer is 38 years old
  Lisa is 8 years old
  Maggie is 1 years old
  Marge is 37 years old  
Related topics:

max_size
Syntax:
  #include <map>
  size_type max_size() const;

The max_size() function returns the maximum number of elements that the map can hold. The max_size() function should not be confused with the size() or (C++ Strings) capacity() functions, which return the number of elements currently in the map and the the number of elements that the map will be able to hold before more memory will have to be allocated, respectively.

Related topics:

rbegin
Syntax:
  #include <map>
  reverse_iterator rbegin();
  const_reverse_iterator rbegin() const;

The rbegin() function returns a reverse_iterator to the end of the current map.

rbegin() runs in constant time.

Related topics:

rend
Syntax:
  #include <map>
  reverse_iterator rend();
  const_reverse_iterator rend() const;

The function rend() returns a reverse_iterator to the beginning of the current map.

rend() runs in constant time.

Related topics:

size
Syntax:
  #include <map>
  size_type size() const;

The size() function returns the number of elements in the current map.

Related topics:

swap
Syntax:
  #include <map>
  void swap( container& from );

The swap() function exchanges the elements of the current map with those of from. This function operates in constant time.

For example, the following code uses the swap() function to exchange the values of two strings:

   string first( "This comes first" );
   string second( "And this is second" );
   first.swap( second );
   cout << first << endl;
   cout << second << endl;          

The above code displays:

   And this is second
   This comes first             
Related topics:

upper_bound
Syntax:
  #include <map>
  iterator upper_bound( const key_type& key );

The function upper_bound() returns an iterator to the first element in the map with a key greater than key.

Related topics:

value_comp
Syntax:
  #include <map>
  value_compare value_comp() const;

The value_comp() function returns the function that compares values.

value_comp() runs in constant time.

Related topics: