Silicon Graphics, Inc.

hash_map<Key, Data, HashFcn, EqualKey, Alloc>

Category: containers Component type: type

Description

Hash_map is a Hashed Associative Container that associates objects of type Key with objects of type Data. Hash_map is a Pair Associative Container, meaning that its value type is pair<const Key, Data>. It is also a Unique Associative Container, meaning that no two elements have keys that compare equal using EqualKey.

Looking up an element in a hash_map by its key is efficient, so hash_map is useful for "dictionaries" where the order of elements is irrelevant. If it is important for the elements to be in a particular order, however, then map is more appropriate.

Example

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

int main()
{
  hash_map<const char*, int, hash<const char*>, eqstr> months;
  
  months["january"] = 31;
  months["february"] = 28;
  months["march"] = 31;
  months["april"] = 30;
  months["may"] = 31;
  months["june"] = 30;
  months["july"] = 31;
  months["august"] = 31;
  months["september"] = 30;
  months["october"] = 31;
  months["november"] = 30;
  months["december"] = 31;
  
  cout << "september -> " << months["september"] << endl;
  cout << "april     -> " << months["april"] << endl;
  cout << "june      -> " << months["june"] << endl;
  cout << "november  -> " << months["november"] << endl;
}

Definition

Hash_map is declared in hash_map.h. The implementation is in hash_map.h and hashtable.h.

Template parameters

Parameter Description Default
Key The hash_map's key type. This is also defined as hash_map::key_type.  
Data The hash_map's data type. This is also defined as hash_map::data_type.  
HashFcn The hash function used by the hash_map. This is also defined as hash_map::hasher. hash<Key>
EqualKey The hash_map key equality function: a binary predicate that determines whether two keys are equal. This is also defined as hash_map::key_equal. equal_to<Key>
Alloc The hash_map's allocator, used for all internal memory management. alloc

Model of

Unique Hashed Associative Container, Pair Associative Container

Type requirements

Public base classes

None.

Members

Member Where defined Description
key_type Associative Container The hash_map's key type, Key.
data_type Pair Associative Container The type of object associated with the keys.
value_type Pair Associative Container The type of object, pair<const key_type, data_type>, stored in the hash_map.
hasher Hashed Associative Container The hash_map's hash function.
key_equal Hashed Associative Container Function object that compares keys for equality.
pointer Container Pointer to T.
reference Container Reference to T
const_reference Container Const reference to T
size_type Container An unsigned integral type.
difference_type Container A signed integral type.
iterator Container Iterator used to iterate through a hash_map. [1]
const_iterator Container Const iterator used to iterate through a hash_map.
iterator begin() Container Returns an iterator pointing to the beginning of the hash_map.
iterator end() Container Returns an iterator pointing to the end of the hash_map.
iterator begin() const Container Returns an const_iterator pointing to the beginning of the hash_map.
iterator end() Container Returns an const_iterator pointing to the end of the hash_map.
size_type size() const Container Returns the size of the hash_map.
size_type max_size() const Container Returns the largest possible size of the hash_map.
bool empty() const Container true if the hash_map's size is 0.
size_type bucket_count() const Hashed Associative Container Returns the number of buckets used by the hash_map.
void resize(size_type n) Hashed Associative Container Increases the bucket count to at least n.
hasher hash_funct() const Hashed Associative Container Returns the hasher object used by the hash_map.
key_equal key_eq() const Hashed Associative Container Returns the key_equal object used by the hash_map.
hash_map() Container Creates an empty hash_map.
hash_map(size_type n) Hashed Associative Container Creates an empty hash_map with at least n buckets.
hash_map(size_type n, const hasher& h) Hashed Associative Container Creates an empty hash_map with at least n buckets, using h as the hash function.
hash_map(size_type n, const hasher& h, const key_equal& k) Hashed Associative Container Creates an empty hash_map with at least n buckets, using h as the hash function and k as the key equal function.
hash_map(const_iterator, const_iterator) Unique Hashed Associative Container Creates a hash_map with a copy of a range.
hash_map(const_iterator, const_iterator, size_type n) Unique Hashed Associative Container Creates a hash_map with a copy of a range and a bucket count of at least n.
hash_map(const_iterator, const_iterator, size_type n, const hasher& h) Unique Hashed Associative Container Creates a hash_map with a copy of a range and a bucket count of at least n, using h as the hash function.
hash_map(const_iterator, const_iterator, size_type n, const hasher& h, const key_equal& k) Unique Hashed Associative Container Creates a hash_map with a copy of a range and a bucket count of at least n, using h as the hash function and k as the key equal function.
hash_map(const hash_map&) Container The copy constructor.
hash_map& operator=(const hash_map&) Container The assignment operator
void swap(hash_map&) Container Swaps the contents of two hash_maps.
pair<iterator, bool> insert(const value_type& x) Unique Associative Container Inserts x into the hash_map.
void insert(const_iterator first, const_iterator last) Unique Associative Container Inserts a range into the hash_map.
void erase(iterator pos) Associative Container Erases the element pointed to by pos.
size_type erase(const key_type& k) Associative Container Erases the element whose key is k.
void erase(iterator first, iterator last) Associative Container Erases all elements in a range.
const_iterator find(const key_type& k) const Associative Container Finds an element whose key is k.
iterator find(const key_type& k) Associative Container Finds an element whose key is k.
size_type count(const key_type& k) const Unique Associative Container Counts the number of elements whose key is k.
pair<const_iterator, const_iterator> equal_range(const key_type& k) const Associative Container Finds a range containing all elements whose key is k.
pair<iterator, iterator> equal_range(const key_type& k) Associative Container Finds a range containing all elements whose key is k.
data_type& 
operator[](const key_type& k) [2]
hash_map See below.
bool operator==(const hash_map&, const hash_map&) Hashed Associative Container Tests two hash_maps for equality. This is a global function, not a member function.

New members

These members are not defined in the Unique Hashed Associative Container and Pair Associative Container requirements, but are specific to hash_map.
Member Description
data_type& 
operator[](const key_type& k) [2]
Returns a reference to the object that is associated with a particular key. If the hash_map does not already contain such an object, operator[] inserts the default object data_type(). [2]

Notes

[1] Hash_map::iterator is not a mutable iterator, because hash_map::value_type is not Assignable. That is, if i is of type hash_map::iterator and p is of type hash_map::value_type, then *i = p is not a valid expression. However, hash_map::iterator isn't a constant iterator either, because it can be used to modify the object that it points to. Using the same notation as above, (*i).second = p is a valid expression.

[2] Since operator[] might insert a new element into the hash_map, it can't possibly be a const member function. Note that the definition of operator[] is extremely simple: m[k] is equivalent to (*((m.insert(value_type(k, data_type()))).first)).second. Strictly speaking, this member function is unnecessary: it exists only for convenience.

See also

Associative Container, Hashed Associative Container, Pair Associative Container, Unique Hashed Associative Container, set, map multiset, multimap, hash_set, hash_multiset, hash_multimap,
[Silicon Surf] [STL Home]
Copyright © 1996 Silicon Graphics, Inc. All Rights Reserved. TrademarkInformation