Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

The Standard Librarian:Hash Tables for the Standard Library


April 2002/The Standard Librarian/Sidebar

Standardese for the Hash Table Proposal


A. Requirements

Hashed associative containers provide an ability for fast retrieval of data based on keys. The worst-case complexity for most operations is linear, but the average case is much faster. The library provides four basic kinds of hashed associative containers: hash_set, hash_map, hash_multiset, and hash_multimap.

Each hashed associative container is parameterized by Key, by a function object Hash that acts as a hash function for values of type Key, and on a binary predicate Pred that induces an equivalence relation on values of type Key. Additionally, hash_map and hash_multimap associate an arbitrary mapped type T with the Key.

A hash function is a function object that takes a single argument of type Key and returns a value of type std::size_t in the range [0, std::numeric_limits<std::size_t>::max()).

Two values k1 and k2 of type Key are considered equal if the container's equality function object returns true when passed those values. If k1 and k2 are equal, the hash function must return the same value for both.

A hashed associative container supports unique keys if it may contain at most one element for each key. Otherwise, it supports equivalent keys. hash_set and hash_map support unique keys. hash_multiset and hash_multimap support equivalent keys. In containers that support equivalent keys, elements with equivalent keys are adjacent to each other.

For hash_set and hash_multiset the value type is the same as the key type. For hash_map and hash_multimap it is equal to std::pair<const Key, T>.

The iterator types iterator and const_iterator of a hashed associative container are of at least the forward iterator category. For hashed associative containers where the key type and value type are the same, both iterator and const_iterator are const iterators.

The elements of a hashed associative container are organized into buckets. Keys with the same hash code appear in the same bucket. The number of buckets is automatically increased as elements are added to a hashed associative container so that the average number of elements per bucket is kept below a bound. Rehashing invalidates iterators, changes ordering between elements, and changes which buckets elements appear in, but does not invalidate pointers or references to elements.

In the following table, X is a hashed associative container class, a is an object of type X, a_uniq is an object of type X when X supports unique keys, a_eq is an object of type X when X supports equivalent keys, i and j are input iterators that refer to value_type, [i, j) is a valid range, p and q2 are valid iterators to a, q and q1 are valid dereferenceable iterators to a, [q1, q2) is a valid range in a, r and r1 are valid dereferenceable const iterators to a, r2 is a valid const iterator to a, [r1, r2) is a valid range in a, t is a value of type X::value_type, k is a value of type key_type, hf is a value of type hasher, eq is a value of type key_equal, n is a value of type size_type, and z is a value of type double.

Hashed Associative Container Requirements (in Addition to Container)
Expression Return Type Assertion/Note
Pre/Post-Condition
Complexity
X::key_type Key Key is Assignable and CopyConstructible Compile time
X::hasher Hash Hash is a unary function object that takes an argument of type Key and returns a value of type std::size_t. Compile time
X::key_equal Pred Pred is a binary predicate that takes two arguments of type Key. Pred is an equivalence relation. Compile time
X::local_iterator An iterator type whose category, value type, difference type, and pointer and reference types are the same as X::iterator's. A local_iterator object may be used to iterate through a single bucket, but may not be used to iterate across buckets. Compile time
X::const_local_iterator An iterator type whose category, value type, difference type, and pointer and reference types are the same as X::const_iterator's. A const_local_iterator object may be used to iterate through a single bucket, but may not be used to iterate across buckets. Compile time
X(n, hf, eq)
X a(n, hf, eq);
X Constructs an empty container with at least n buckets, using hf as the hash function and hf as the key equality predicate. Constant
X(n, hf)
X a(n, hf);
X Constructs an empty container with at least n buckets, using hf as the hash function and key_equal() as the key equality predicate. Constant
X(n)
X a(n);
X Constructs an empty container with at least n buckets, using hasher() as the hash function and key_equal() as the key equality predicate. Constant
X()
X a;
X Constructs an empty container with an unspecified number of buckets, using hasher() as the hash function and key_equal as the key equality predicate. Constant
X(i, j, n, hf, eq)
X a(i, j, n, hf, eq);
X Constructs an empty container with at least n buckets, using hf as the hash function and hf as the key equality predicate, and inserts elements from [i, j) into it. Average case O(N)
(N is
std::distance(i, j));
worse case O(N2)
X(i, j, n, hf)
X a(i, j, n, hf);
X Constructs an empty container with at least n buckets, using hf as the hash function and key_equal() as the key equality predicate, and inserts elements from [i, j) into it. Average case O(N)
(N is
std::distance(i, j));
worse case O(N2)
X(i, j, n)
X a(i, j, n);
X Constructs an empty container with at least n buckets, using hasher() as the hash function and key_equal() as the key equality predicate, and inserts elements from [i, j) into it. Average case O(N)
(N is
std::distance(i, j));
worse case O(N2)
X(i, j)
X a(i, j);
X Constructs an empty container with an unspecified number of buckets, using hasher() as the hash function and key_equal as the key equality predicate, and inserts elements from [i, j) into it. Average case O(N)
(N is
std::distance(i, j));
worse case O(N2)
a.hash_funct() hasher Returns the hash function out of which a was constructed. Constant
a.key_eq() key_equal Returns the key equality function out of which a was constructed. Constant
a_uniq.insert(t) std::pair<iterator, bool> Inserts t if and only if there is no element in the container with key equivalent to the key of t. The bool component of the returned pair indicates whether the insertion takes place, and the iterator component points to the element with key equivalent to the key of t. Average case O(1); worst case O(a_uniq.size())
a_eq.insert(t) iterator Inserts t, and returns an iterator pointing to the newly inserted element. Average case O(1); worst case O(a_uniq.size())
a.insert(r, t) iterator Equivalent to a.insert(t). Return value is an iterator pointing to the element with the key equivalent to that of t. The const iterator r is a hint pointing to where the search should start. Implementations are permitted to ignore the hint. Average case O(1); worst case O(a.size())
a.insert(i, j) void Pre: i and j are not iterators in a.
Equivalent to a.insert(t) for each element in [i,j).
Average case O(N), where N is std::distance(i, j); worst case O(N * a.size())
a.erase(k) size_type Erases all elements with key equivalent to k. Returns the number of elements erased. Average case O(a.count(k)); worst case O(a.size()
a.erase(r) void Erases the element pointed to by r. Average case O(1); worst case O(a.size())
a.erase(r1, r2) void Erases all elements in the range [r1, t2). Average case O(std::distance(r1, r2)); worst case O(a.size())
a.clear() void Erases all elements in the container.
Post: a.size() == 0
Linear
a.find(k) iterator;
const_iterator for const a
Returns an iterator pointing to an element with key equivalent to k, or a.end() if no such element exists. Average case O(1); worst case O(a.size())
a.count(k) size_type Returns the number of elements with key equivalent to k. Average case O(1); worst case O(a.size())
a.equal_range(k) std::pair<iterator, iterator>;
std::pair<const_iterator, const_iterator> for const a
Returns a range containing all elements with keys equivalent to k. Returns std::make_pair(a.end(), a.end()) if no such elements exist. Average case O(a.count(k)); worst case O(a.size())
a.bucket_count() size_type Returns the number of buckets that a contains. Constant
a.max_bucket_count() size_type Returns an upper bound on the number of buckets that a might ever contain. Constant
a.bucket(k) size_type Returns the index of the bucket in which elements with keys equivalent to k would be found, if any such elements exist.
Post: the return value is in the range [0, a.bucket_count()).
Constant
a.bucket_size(n) size_type Pre: n is in the range [0, a.bucket_count()).
Returns the number of elements in the nth bucket.
O(a.bucket_size(n))
a.begin(n) local_iterator;
const_local_iterator for const a
Pre: n is in the range [0, a.bucket_count()).
Note: [a.begin(n), a.end(n)) is a valid range containing all of the elements in the nth bucket.
Constant
a.end(n) local_iterator;
const_local_iterator for const a
Pre: n is in the range [0, a.bucket_count()). Constant
a.load_factor() double Returns the average number of elements per bucket. Constant
a.max_load_factor() double Returns a number that the container attempts to keep the load factor less than or equal to. The container automatically increases the number of buckets as necessary to keep the load factor below this number.
Post: return value is positive.
Constant
a.set_max_load_factor(z) void Pre: z is positive.
Changes the container's maximum load load factor.
Post: a.max_load_factor() == z
Constant
a.rehash(n) void Pre: n > a.size() / a.max_load_factor().
Changes the number of buckets so that it is at least n.
O(a.size()).

B. Hash Function

1. To be added to the <functional> synopsis

    // Hash function base template
    template <class T> struct hash;

    // Hash function specializations

    template <> struct hash<char>;
    template <> struct hash<signed char>;
    template <> struct hash<unsigned char>;
    template <> struct hash<wchar_t>;
    template <> struct hash<short>;
    template <> struct hash<int>;
    template <> struct hash<long>;
    template <> struct hash<unsigned short>;
    template <> struct hash<unsigned int>;
    template <> struct hash<unsigned long>;

    template <class charT, class traits>
    struct hash<std::basic_string<charT, traits> >;

    template<> struct hash<const char*>;
    template<> struct hash<char*>;

2. Class template hash

The function object hash is used as the default hash function by the hashed associative containers. This class template is required to be instantiable only for the following types: char, signed char, unsigned char, wchar_t, short, int, long, unsigned short, unsigned int, unsigned long, char*, const char*, and (for any valid set of charT, traits, and Alloc) std::basic_string<charT, traits, Alloc>.

    template <class T>
    struct hash : public std::unary_function<T, std::size_t>
    {
      std::size_t operator()(T val) const;
    };

The return value of operator() is unspecified, except that equal arguments yield the same result. For char* and const char*, two arguments s1 and s2 yield the same result if std::strcmp(s1, s2) == 0.

C. Hashed Associative Containers

1. Header <hash_set> synopsis

namespace std {
 template <class Value,
            class Hash = hash<Value>,
            class Pred = std::equal_to<Value>,
            class Alloc = std::allocator<Value> > class hash_set;

 template <class Value, class Hash, class Pred, class Alloc>
 bool operator==(const hash_set<Value, Hash, Pred, Alloc>&,
                 const hash_set<Value, Hash, Pred, Alloc>&);

 template <class Value, class Hash, class Pred, class Alloc>
 bool operator!=(const hash_set<Value, Hash, Pred, Alloc>&,
                 const hash_set<Value, Hash, Pred, Alloc>&);

 template <class Value,
            class Hash = hash<Value>,
            class Pred = std::equal_to<Value>,
            class Alloc = std::allocator<Value> > class hash_multiset;

 template <class Value, class Hash, class Pred, class Alloc>
 bool operator==(const hash_multiset<Value, Hash, Pred, Alloc>&,
                 const hash_multiset<Value, Hash, Pred, Alloc>&);

 template <class Value, class Hash, class Pred, class Alloc>
 bool operator!=(const hash_multiset<Value, Hash, Pred, Alloc>&,
                 const hash_multiset<Value, Hash, Pred, Alloc>&);}

2. Header <hash_map> synopsis

namespace std { 
 template <class Key,
            class T,
            class Hash = hash<Key>,
            class Pred = std::equal_to<Key>,
            class Alloc = std::allocator<std::pair<const Key, T> > > class hash_set;

 template <class Key, class T, class Hash, class Pred, class Alloc> 
 bool operator==(const hash_set<Key, T, Hash, Pred, Alloc>&,    
                 const hash_set<Key, T, Hash, Pred, Alloc>&);

 template <class Key, class T, class Hash, class Pred, class Alloc>
 bool operator!=(const hash_set<Key, T, Hash, Pred, Alloc>&,
                 const hash_set<Key, T, Hash, Pred, Alloc>&);

 template <class Key,
            class T,
            class Hash = hash<Key>,
            class Pred = std::equal_to<Key>,
            class Alloc = std::allocator<std::pair<const Key, T> > > class hash_multiset;

 template <class Key, class T, class Hash, class Pred, class Alloc> 
 bool operator==(const hash_multiset<Key, T, Hash, Pred, Alloc>&,
                 const hash_multiset<Key, T, Hash, Pred, Alloc>&);

 template <class Key, class T, class Hash, class Pred, class Alloc>
 bool operator!=(const hash_multiset<Key, T, Hash, Pred, Alloc>&,
                 const hash_multiset<Key, T, Hash, Pred, Alloc>&);}

3. Class template hash_set

A hash_set is a kind of hashed associative container that supports unique keys (a hash_set contains at most one of each key value) and in which the elements' keys are the elements themselves.

A hash_set satisfies all of the requirements of a container and of a hashed associative container. It provides the operations described in the preceding requirements table for unique keys; that is, a hash_set supports the a_uniq operations in that table, not the a_eq operations. For a hash_set<Value> the key type and the value type are both Value. The iterator and const_iterator types are both const iterator types. It is unspecified whether or not they are the same type.

This section only describes operations on hash_set that are not described in one of the requirement tables, or for which there is additional semantic information.

 namespace std {
    template <class Value, 
              class Hash = hash<Value>,
              class Pred = std::equal_to<Value>,
              class Alloc = std::allocator<Value> >
    class hash_set
    {
    public:
      // types
      typedef Value                                    key_type;
      typedef Value                                    value_type;
      typedef Hash                                     hasher;
      typedef Pred                                     key_equal;
      typedef Alloc                                    allocator_type;
      typedef typename allocator_type::pointer         pointer;
      typedef typename allocator_type::const_pointer   const_pointer;
      typedef typename allocator_type::reference       reference;
      typedef typename allocator_type::const_reference const_reference;
      typedef <b>implementation defined</b>            size_type;
      typedef <b>implementation defined</b>difference_type;

      typedef <b>implementation defined</b>            iterator;
  typedef <b>implementation defined</b>            const_iterator;

typedef <b>implementation defined</b>
              local_iterator;
      typedef <b>implementation defined</b>
              const_local_iterator;
      // construct/destroy/copy
      explicit hash_set(size_type n = <b>implementation defined</b>,
                        const hasher& hf = hasher(),
                        const key_equal& eql = key_equal(),
                        const allocator_type& a = allocator_type());
      template <class InputIterator>
        hash_set(InputIterator f, InputIterator l,
                 size_type n = <b>implementation defined</b>,
                 const hasher& hf = hasher(),
                 const key_equal& eql = key_equal(),
                 const allocator_type& a = allocator_type());
      hash_set(const hash_set&);
      ~hash_set();
      hash_set& operator=(const hash_set&);
      allocator_type get_allocator() const;

      // size and capacity
      bool empty() const;
      size_type size() const;
      size_type max_size() const;

      // iterators
      iterator       begin();
      const_iterator begin() const;
      iterator       end();
      const_iterator end() const;

      // modifiers
      std::pair<iterator, bool> insert(const value_type& obj);
      iterator insert(const_iterator hint, const value_type& obj);
      template <class InputIterator>
        void insert(InputIterator first, InputIterator last);

      void erase(const_iterator position);
      size_type erase(const key_type& k);
      void erase(const_iterator first, const_iterator last);
      void clear();
      void swap(hash_set&);

      // observers
      hasher hash_funct() const;
      key_equal key_eq() const;

      // lookup
      iterator       find(const key_type& k);
      const_iterator find(const key_type& k) const;
      size_type count(const key_type& k) const;
      std::pair<iterator, iterator> 
        equal_range(const key_type& k);
      std::pair<const_iterator, const_iterator>
        equal_range(const key_type& k) const;

      // bucket interface
      size_type bucket_count() const;
      size_type max_bucket_count() const;
      size_type bucket_size(size_type n);
      size_type bucket(const key_type& k);
      local_iterator begin(size_type n);
      const_local_iterator begin(size_type n) const;
      local_iterator end(size_type n);
      const_local_iterator end(size_type n) const;

      // hash policy
      double load_factor() const;
      double max_load_factor() const;
      void set_max_load_factor(double z);
      void rehash(size_type n);
    };

    template <class Value, class Hash, class Pred, class Alloc>
    bool operator==(const hash_set<Value, Hash, Pred, Alloc>& x,
                    const hash_set<Value, Hash, Pred, Alloc>& y);

    template <class Value, class Hash, class Pred, class Alloc>
    bool operator!=(const hash_set<Value, Hash, Pred, Alloc>& x,
                    const hash_set<Value, Hash, Pred, Alloc>& y);

    template <class Value, class Hash, class Pred, class Alloc>
      void swap(const hash_set<Value, Hash, Pred, Alloc>& x,
                const hash_set<Value, Hash, Pred, Alloc>& y); }

a. hash_set constructors

      explicit hash_set(size_type n = <b>implementation defined</b>,
                        const hasher& hf = hasher(),
                        const key_equal& eql = key_equal(),
                        const allocator_type& a = allocator_type());

Effects: Constructs an empty hash_set using the specified hash function, key equality function, and allocator, and using at least n buckets. If n is not provided, the number of buckets is implementation defined.

Complexity: Constant.

Note: The maximum load factor is initially 1.0.

      template <class InputIterator>
        hash_set(InputIterator f, InputIterator l,
                 size_type n = <b>implementation defined</b>,
                 const hasher& hf = hasher(),
                 const key_equal& eql = key_equal(),
                 const allocator_type& a = allocator_type());

Effects: Constructs an empty hash_set using the specified hash function, key equality function, and allocator, and using at least n buckets. (If n is not provided, the number of buckets is implementation defined.) Then inserts elements from the range [first, last).

Complexity: Average case linear; worst case quadratic.

Note: The maximum load factor is initially 1.0.

b. hash_set swap

      template <class Value, class Hash, class Pred, class Alloc>
        void swap(const hash_set<Value, Hash, Pred, Alloc>& x,
                  const hash_set<Value, Hash, Pred, Alloc>& y);

Effects:

 x.swap(y);

4. Class template hash_map

A hash_map is a kind of hashed associative container that supports unique keys (a hash_map contains at most one of each key value) and that associates values of another type mapped_type with the keys.

A hash_map satisfies all of the requirements of a container and of a hashed associative container. It provides the operations described in the preceding requirements table for unique keys; that is, a hash_map supports the a_uniq operations in that table, not the a_eq operations. For a hash_map<Key, T> the key type is Key, the mapped type is T, and the value type is std::pair<const Key, T>.

This section only describes operations on hash_map that are not described in one of the requirement tables, or for which there is additional semantic information.

 namespace std {
    template <class Key,
              class T,
              class Hash = hash<Key>,
       class Pred = std::equal_to<Key>,
              class Alloc = std::allocator<std::pair<const Key, T> > >
    class hash_map
    {
    public:
      // types
      typedef Key key_type;
      typedef std::pair<const Key, T>                  value_type;
      typedef T mapped_type;
      typedef Hash                                     hasher;
      typedef Pred                                     key_equal;
      typedef Alloc                                    allocator_type;
      typedef typename allocator_type::pointer         pointer;
      typedef typename allocator_type::const_pointer   const_pointer;
      typedef typename allocator_type::reference       reference;
 typedef typename allocator_type::const_reference const_reference;
      typedef <b>implementation defined</b>  size_type;
      typedef <b>implementation defined</b> difference_type;

      typedef <b>implementation defined</b> iterator;
      typedef <b>implementation defined</b> const_iterator;

  typedef <b>implementation defined</b>
              local_iterator;
      typedef <b>implementation defined</b>
              const_local_iterator;

      // construct/destroy/copy
      explicit hash_map(size_type n = <b>implementation defined</b>,
                        const hasher& hf = hasher(),
                        const key_equal& eql = key_equal(),
                        const allocator_type& a = allocator_type());

      template <class InputIterator>
        hash_map(InputIterator f, InputIterator l,
                 size_type n = <b>implementation defined</b>,
                 const hasher& hf = hasher(),
                 const key_equal& eql = key_equal(),
                 const allocator_type& a = allocator_type());
      hash_map(const hash_map&);
      ~hash_map();
      hash_map& operator=(const hash_map&);
      allocator_type get_allocator() const;

      // size and capacity
      bool empty() const;
      size_type size() const;
      size_type max_size() const;

      // iterators
      iterator       begin();
      const_iterator begin() const;
      iterator       end();
      const_iterator end() const;

      // modifiers
      std::pair<iterator, bool> insert(const value_type& obj);
      iterator insert(const_iterator hint, const value_type& obj);
      template <class InputIterator>
        void insert(InputIterator first, InputIterator last);

      void erase(const_iterator position);
      size_type erase(const key_type& k);
      void erase(const_iterator first, const_iterator last);
      void clear();

      void swap(hash_map&);

      // observers
      hasher hash_funct() const;
      key_equal key_eq() const;

      // lookup
      iterator       find(const key_type& k);
      const_iterator find(const key_type& k) const;
      size_type count(const key_type& k) const;
      std::pair<iterator, iterator> 
        equal_range(const key_type& k);
      std::pair<const_iterator, const_iterator>
        equal_range(const key_type& k) const;

      mapped_type& operator[](const key_type& k);

      // bucket interface
      size_type bucket_count() const;
      size_type max_bucket_count() const;
      size_type bucket_size(size_type n);
      size_type bucket(const key_type& k);
      local_iterator begin(size_type n);
      const_local_iterator begin(size_type n) const;
      local_iterator end(size_type n);
      const_local_iterator end(size_type n) const;

       // hash policy
      double load_factor() const;
      double max_load_factor() const;
      void set_max_load_factor(double z);
      void rehash(size_type n);
    };

    template <class Key, class T, class Hash, class Pred, class Alloc>
    bool operator==(const hash_map<Key, T, Hash, Pred, Alloc>& x,
                    const hash_map<Key, T, Hash, Pred, Alloc>& y);

    template <class Key, class T, class Hash, class Pred, class Alloc>
    bool operator!=(const hash_map<Key, T, Hash, Pred, Alloc>& x,
                    const hash_map<Key, T, Hash, Pred, Alloc>& y);

    template <class Key, class T, class Hash, class Pred, class Alloc>
      void swap(const hash_map<Key, T, Hash, Pred, Alloc>& x,
                const hash_map<Key, T, Hash, Pred, Alloc>& y); }

a. hash_map constructors

      explicit hash_map(size_type n = <b>implementation defined</b>,
                        const hasher& hf = hasher(),
                        const key_equal& eql = key_equal(),
                        const allocator_type& a = allocator_type());

Effects: Constructs an empty hash_map using the specified hash function, key equality function, and allocator, and using at least n buckets. If n is not provided, the number of buckets is implementation defined.

Complexity: Constant.

Note: The maximum load factor is initially 1.0.

      template <class InputIterator>
        hash_map(InputIterator f, InputIterator l,
                 size_type n = <b>implementation defined</b>,
                 const hasher& hf = hasher(),
                 const key_equal& eql = key_equal(),
                 const allocator_type& a = allocator_type());

Effects: Constructs an empty hash_map using the specified hash function, key equality function, and allocator, and using at least n buckets. (If n is not provided, the number of buckets is implementation defined.) Then inserts elements from the range [first, last).

Complexity: Average case linear; worst case quadratic.

Note:The maximum load factor is initially 1.0.

b. hash_map element access

      mapped_type& operator[](const key_type& k);

Effects: If the hash_map does not already contain an element whose key is equivalent to k, inserts std::pair<const key_type, mapped_type>(k, mapped_type()).

Returns: A reference to x.second, where x is the (unique) element whose key is equivalent to k.

c. hash_map swap

      template <class Value, class Hash, class Pred, class Alloc>
        void swap(const hash_map<Value, Hash, Pred, Alloc>& x,
                  const hash_map<Value, Hash, Pred, Alloc>& y);

Effects:

 x.swap(y);

5. Class template hash_multiset

A hash_multiset is a kind of hashed associative container that supports equivalent keys (a hash_multiset may contain multiple copies of the same key value) and in which the elements' keys are the elements themselves.

A hash_multiset satisfies all of the requirements of a container and of a hashed associative container. It provides the operations described in the preceding requirements table for equivalent keys; that is, a hash_multiset supports the a_eq operations in that table, not the a_uniq operations. For a hash_multiset<Value> the key type and the value type are both Value. The iterator and const_iterator types are both const iterator types. It is unspecified whether or not they are the same type.

This section only describes operations on hash_multiset that are not described in one of the requirement tables, or for which there is additional semantic information.

 namespace std {
    template <class Value, 
              class Hash = hash<Value>,
              class Pred = std::equal_to<Value>,
              class Alloc = std::allocator<Value> >
    class hash_multiset
    {
    public:
      // types
      typedef Value                                    key_type;
      typedef Value                                    value_type;
      typedef Hash                                     hasher;
      typedef Pred                 key_equal;
      typedef Alloc                                    allocator_type;
      typedef typename allocator_type::pointer         pointer;
      typedef typename allocator_type::const_pointer   const_pointer;
      typedef typename allocator_type::reference       reference;
      typedef typename allocator_type::const_reference const_reference;
      typedef <b>implementation defined</b> size_type;
      typedef <b>implementation defined</b> difference_type;

      typedef <b>implementation defined</b> iterator;
      typedef <b>implementation defined</b> const_iterator;

      typedef <b>implementation defined</b>
              local_iterator;
      typedef <b>implementation defined</b>
              const_local_iterator;

      // construct/destroy/copy
      explicit hash_multiset(size_type n = <b>implementation defined</b>,
                             const hasher& hf = hasher(),
                             const key_equal& eql = key_equal(),
                             const allocator_type& a = allocator_type());
      template <class InputIterator>
        hash_multiset(InputIterator f, InputIterator l,
                 size_type n = <b>implementation defined</b>,
       const hasher& hf = hasher(),
                 const key_equal& eql = key_equal(),
                 const allocator_type& a = allocator_type());
      hash_multiset(const hash_multiset&);
      ~hash_multiset();
      hash_multiset& operator=(const hash_multiset&);
      allocator_type get_allocator() const;

      // size and capacity
      bool empty() const;
      size_type size() const;
      size_type max_size() const;

      // iterators
      iterator       begin();
      const_iterator begin() const;
      iterator       end();
      const_iterator end() const;

      // modifiers
      iterator insert(const value_type& obj);
      iterator insert(const_iterator hint, const value_type& obj);
      template <class InputIterator>
        void insert(InputIterator first, InputIterator last);

      void erase(const_iterator position);
      size_type erase(const key_type& k);
      void erase(const_iterator first, const_iterator last);
      void clear();

      void swap(hash_multiset&);

      // observers
      hasher hash_funct() const;
      key_equal key_eq() const;

      // lookup
      iterator       find(const key_type& k);
      const_iterator find(const key_type& k) const;
      size_type count(const key_type& k) const;
      std::pair<iterator, iterator> 
        equal_range(const key_type& k);
      std::pair<const_iterator, const_iterator>
        equal_range(const key_type& k) const;

      // bucket interface
      size_type bucket_count() const;
      size_type max_bucket_count() const;
      size_type bucket_size(size_type n);
      size_type bucket(const key_type& k);
      local_iterator begin(size_type n);
      const_local_iterator begin(size_type n) const;
      local_iterator end(size_type n);
      const_local_iterator end(size_type n) const;

      // hash policy
      double load_factor() const;
      double max_load_factor() const;
      void set_max_load_factor(double z);
      void rehash(size_type n);
    };

    template <class Value, class Hash, class Pred, class Alloc>
    bool operator==(const hash_multiset<Value, Hash, Pred, Alloc>& x,
                    const hash_multiset<Value, Hash, Pred, Alloc>& y);

    template <class Value, class Hash, class Pred, class Alloc>
    bool operator!=(const hash_multiset<Value, Hash, Pred, Alloc>& x,
                    const hash_multiset<Value, Hash, Pred, Alloc>& y);

    template <class Value, class Hash, class Pred, class Alloc>
      void swap(const hash_multiset<Value, Hash, Pred, Alloc>& x,
                const hash_multiset<Value, Hash, Pred, Alloc>& y); }

a. hash_multiset constructors

      explicit hash_multiset(size_type n = <b>implementation defined</b>,
                             const hasher& hf = hasher(),
 const key_equal& eql = key_equal(),
                             const allocator_type& a
 = allocator_type());

Effects: Constructs an empty hash_multiset using the specified hash function, key equality function, and allocator, and using at least n buckets. If n is not provided, the number of buckets is implementation defined.

Complexity: Constant.

Note: The maximum load factor is initially 1.0.

      template <class InputIterator>
        hash_multiset(InputIterator f, InputIterator l,
 size_type n = <b>implementation defined</b>,
 const hasher& hf = hasher(),
                      const key_equal& eql = key_equal(),
                      const allocator_type& a = allocator_type());

Effects: Constructs an empty hash_multiset using the specified hash function, key equality function, and allocator, and using at least n buckets. (If n is not provided, the number of buckets is implementation defined.) Then inserts elements from the range [first, last).

Complexity: Average case linear; worst case quadratic.

Note: The maximum load factor is initially 1.0.

b. hash_multiset swap

      template <class Value, class Hash, class Pred, class Alloc>
        void swap(const hash_multiset<Value, Hash, Pred, Alloc>& x,
                  const hash_multiset<Value, Hash, Pred, Alloc>& y);

Effects:

 x.swap(y);

6. Class template hash_multimap

A hash_multimap is a kind of hashed associative container that supports equivalent keys (a hash_multimap may contain multiple copies of each key value) and that associates values of another type mapped_type with the keys.

A hash_multimap satisfies all of the requirements of a container and of a hashed associative container. It provides the operations described in the preceding requirements table for equivalent keys; that is, a hash_multimap supports the a_eq operations in that table, not the a_uniq operations. For a hash_multimap<Key, T> the key type is Key, the mapped type is T, and the value type is std::pair<const Key, T>.

This section only describes operations on hash_multimap that are not described in one of the requirement tables, or for which there is additional semantic information.

 namespace std {
    template <class Key,
            class T,
              class Hash = hash<Key>,
              class Pred = std::equal_to<Key>,
              class Alloc = std::allocator<std::pair<const Key, T> > >
    class hash_multimap
    {
    public:
      // types
      typedef Key key_type;
      typedef std::pair<const Key, T>            value_type;
      typedef T mapped_type;
      typedef Hash                                     hasher;
      typedef Pred key_equal;
      typedef Alloc                                    allocator_type;
      typedef typename allocator_type::pointer         pointer;
      typedef typename allocator_type::const_pointer   const_pointer;
      typedef typename allocator_type::reference       reference;
      typedef typename allocator_type::const_reference const_reference;
      typedef <b>implementation defined</b> size_type;
      typedef <b>implementation defined</b> difference_type;

      typedef <b>implementation defined</b> iterator;
      typedef <b>implementation defined</b> const_iterator;

      typedef <b>implementation defined</b>
              local_iterator;
      typedef <b>implementation defined</b>
              const_local_iterator;

      // construct/destroy/copy
      explicit hash_multimap(size_type n = <b>implementation defined</b>,
                             const hasher& hf = hasher(),
                             const key_equal& eql = key_equal(),
                             const allocator_type& a = allocator_type());
      template <class InputIterator>
        hash_multimap(InputIterator f, InputIterator l,
                      size_type n = <b>implementation defined</b>,
                      const hasher& hf = hasher(),
                      const key_equal& eql = key_equal(),
                      const allocator_type& a = allocator_type());
      hash_multimap(const hash_multimap&);
      ~hash_multimap();
      hash_multimap& operator=(const hash_multimap&);
      allocator_type get_allocator() const;

      // size and capacity
      bool empty() const;
      size_type size() const;
      size_type max_size() const;

      // iterators
      iterator       begin();
      const_iterator begin() const;
      iterator       end();
      const_iterator end() const;

      // modifiers
      iterator insert(const value_type& obj);
      iterator insert(const_iterator hint, const value_type& obj);
    template <class InputIterator>
        void insert(InputIterator first, InputIterator last);

      void erase(const_iterator position);
      size_type erase(const key_type& k);
      void erase(const_iterator first, const_iterator last);
      void clear();

      void swap(hash_multimap&);

      // observers
      hasher hash_funct() const;
      key_equal key_eq() const;

      // lookup
      iterator       find(const key_type& k);
      const_iterator find(const key_type& k) const;
      size_type count(const key_type& k) const;
      std::pair<iterator, iterator> 
        equal_range(const key_type& k);
      std::pair<const_iterator, const_iterator>
        equal_range(const key_type& k) const;

      mapped_type& operator[](const key_type& k);

      // bucket interface
      size_type bucket_count() const;
      size_type max_bucket_count() const;
      size_type bucket_size(size_type n);
      size_type bucket(const key_type& k);
      local_iterator begin(size_type n);
      const_local_iterator begin(size_type n) const;
      local_iterator end(size_type n);
      const_local_iterator end(size_type n) const;

      // hash policy
      double load_factor() const;
      double max_load_factor() const;
      void set_max_load_factor(double z);
      void rehash(size_type n);
    };

    template <class Key, class T, class Hash, class Pred, class Alloc>
    bool operator==(const hash_multimap<Key, T, Hash, Pred, Alloc>& x,
                    const hash_multimap<Key, T, Hash, Pred, Alloc>& y);

    template <class Key, class T, class Hash, class Pred, class Alloc>
    bool operator!=(const hash_multimap<Key, T, Hash, Pred, Alloc>& x,
                    const hash_multimap<Key, T, Hash, Pred, Alloc>& y);

    template <class Key, class T, class Hash, class Pred, class Alloc>
      void swap(const hash_multimap<Key, T, Hash, Pred, Alloc>& x,
                const hash_multimap<Key, T, Hash, Pred, Alloc>& y); }

a. hash_multimap constructors

      explicit hash_multimap(size_type n = <b>implementation defined</b>,
                             const hasher& hf = hasher(),
                             const key_equal& eql = key_equal(),
                             const allocator_type& a 
= allocator_type());

Effects: Constructs an empty hash_multimap using the specified hash function, key equality function, and allocator, and using at least n buckets. If n is not provided, the number of buckets is implementation defined.

Complexity: Constant.

Note: The maximum load factor is initially 1.0.

      template <class InputIterator>
        hash_multimap(InputIterator f, InputIterator l,
                      size_type n = <b>implementation defined</b>,
                      const hasher& hf = hasher(),
                      const key_equal& eql = key_equal(),
                      const allocator_type& a = allocator_type());

Effects: Constructs an empty hash_multimap using the specified hash function, key equality function, and allocator, and using at least n buckets. (If n is not provided, the number of buckets is implementation defined.) Then inserts elements from the range [first, last).

Complexity: Average case linear; worst case quadratic.

Note: The maximum load factor is initially 1.0.

b. hash_multimap swap

      template <class Value, class Hash, class Pred, class Alloc>
        void swap(const hash_multimap<Value, Hash, Pred, Alloc>& x,
                  const hash_multimap<Value, Hash, Pred, Alloc>& y);

Effects:

 x.swap(y);


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.