map, hash_map

Both map and hash_map are associative containers that manage a set of ordered key/value pairs. They are identical in behavior to a multimap , except they do not allow a pair to be inserted if a pair with a matching key is already present. This section provides an overview of map and hash_map. Hash containers are only a proposed addition to the ANSI/ISO Standard Template Library, and have not been accepted for inclusion in the final specification. Hash containers are included in Standards<ToolKit> to provide the latest STL technology available.

Iterator Type

A map has bidirectional iterators. A hash_map has forward iterators.

Implementation

A map is implemented using a red-black binary search tree with nodes holding the pair< const Key, Value > objects. The comparator object orders the pairs based only on their keys. Some compilers do not compile const templates correctly; in these cases, a map 's tree holds pair< Key, Value > objects.

A hash_map is implemented as a hash table, using a user-specified hash function to position and retrieve item nodes. Like map , each node holds a pair< const Key, Value > object.

Insertion Notes

When inserting a single item, the copy constructor is called once. When inserting multiple items, the copy constructor is called once for each item inserted. Insertion does not affect iterators or references.

Erasure Notes

When erasing a single item, the destructor is called once. When erasing a range of items, the destructor is called once for each item in the range. Erasure only invalidates the iterators and references to the erased elements.

Common Uses

The map and hash_map containers are useful for implementing a collection of one-to-one mappings.

Interface

Since the interface to map is nearly identical to that of hash_map , only map is fully discussed in this section.

There are two main differences between a multimap and a map . First, insert() returns a paired result instead of a simple iterator.

insert

pair< iterator, bool > insert( const pair_type& apair )

If the map does not contain a key/value pair whose key matches that of apair , inserts a copy of apair and returns a pair object whose first element is an iterator positioned at the new key/value pair and whose second element is true . If the map already contains a key/value pair whose key matches that of apair , returns a pair whose first element is an iterator positioned at the existing key/value pair and whose second element is false .

Second, an operator[] exists to conveniently access and modify a key's associated value. In the following description, note that operator[] adds an association to a key if one does not exist already.

[]

Value& operator[]( const Key& key )

If no value is associated with key , associates key with a default-constructed value and returns a reference to this new value; otherwise, returns a reference to the value already associated with key .

The following examples illustrate both of these functions.

#include <iostream>
#include <functional>
#include <map>

typedef less< char > lessp;
typedef map< char, int, lessp > maptype;

void
main()
  {
  maptype m;

  // Store mappings between roman numerals and decimals.
  m[ `l' ] = 50;
  m[ `x' ] = 20; // Deliberate mistake.
  m[ `v' ] = 5;
  m[ `i' ] = 1;
  cout << "m[ `x' ] = " << m[ `x' ] << "\n";

  m[ `x' ] = 10; // Correct mistake.
  cout << "m[ `x' ] = " << m[ `x' ] << "\n";

  // Note default value ( 0 ) is added.
  cout << "m[ `z' ] = " << m[ `z' ] << "\n";
  cout << "m.count( `z' ) = " << m.count( `z' ) << "\n";

  pair< maptype::iterator, bool > p;
  p = m.insert( make_pair( `c', 100 ) );
  if ( p.second )
    cout << "First insertion successful\n";

  p = m.insert( make_pair( `c', 100 ) );
  if ( p.second )
    cout << "Second insertion successful\n";
  else
    cout
      << "Existing pair "
      << ( *( p.first ) ).first
      << " -> "
      << ( *( p.first ) ).second
      << "\n";
  }

m[`x'] = 20
m[`x'] = 10
m[`z'] = 0
m.count (`z') = 1
First insertion successful
Existing pair c -> 100

#include <iostream>
#include <functional>
#include <ospace/osstd/hashmap.h>

typedef hash_map< char, int, hash<char>, equal_to<char> > map_type;

void
main()
  {
  map_type m;

  // Store mappings between roman numerals and decimals.
  m[ 'l' ] = 50;
  m[ 'x' ] = 20; // Deliberate mistake.
  m[ 'v' ] = 5;
  m[ 'i' ] = 1;
  cout << "m[ 'x' ] = " << m[ 'x' ] << "\n";

  m[ 'x' ] = 10; // Correct mistake.
  cout << "m[ 'x' ] = " << m[ 'x' ] << "\n";

  // Note default value ( 0 ) is added.
  cout << "m[ 'z' ] = " << m[ 'z' ] << "\n";
  cout << "m.count( 'z' ) = " << m.count( 'z' ) << "\n";

  pair< map_type::iterator, bool > p;
  p = m.insert( pair< char, int >( char, int )( 'c', 100 ) );
  if ( p.second )
    cout << "First insertion successful\n";

  p = m.insert( pair< char, int >( char, int )( 'c', 100 ) );
  if ( p.second )
    cout << "Second insertion successful\n";
  else
    cout
      << "Existing pair "
      << ( *( p.first ) ).first
      << " -> "
      << ( *( p.first ) ).second
      << "\n";
  }

m[`x'] = 20
m[`x'] = 10
m[`z'] = 0
m.count (`z') = 1
First insertion successful
Existing pair c -> 100


 
 

Copyright©1994-2026 Recursion Software LLC
All Rights Reserved - For use by licensed users only.