Hash Multimap
A collision occurs when distinct key values are mapped into the same hashed value.
Hash multimap is a hash map that can contain multiple for a same key
Definition
Hash_multimap template class is defined in the header <hash_map>, and in the backward-compatibility header <hash_map.h>. This class is an SGI extension; it is not part of the C++ standard.
Interface
#include <hash_map>
namespace std{
template < class Key, class Type,
class Traits = hash_compare<Key, less<Key> >,
class Allocator = allocator<pair <const Key, Type> > >
class hash_multimap;
}Parameters
| Parameter | Description |
| Key | The element data type to be stored in the hash_multimap |
| Type | The element data type to be stored in the hash_multimap |
| Traits | The type that includes two function objects, one of class Traits that is a binary predicate able to compare two element values as sort keys to determine their relative order and a hash function that is a unary predicate mapping key values of the elements to unsigned integers of type size_t. This argument is optional, and the hash_compare<Key, less<Key> > is the default value |
| Allocator | The type that represents the stored allocator object that encapsulates details about the hash_multimap's allocation and de-allocation of memory. This argument is optional, and the default value is allocator<pair <const Key, Type> > |
Description
Hash_multimap is an extension of the Standard Template Library and is used for the storage and fast retrieval of data from a collection in which each element is a pair that has a sort key whose value need NOT be unique and an associated data value.
Hash_multimap is a Hashed Associative Container because its elements are grouped into buckets based on the value of a hash function applied to the key values of the elements and is a Pair Associative Container, because its element data values are distinct from its key values.
Hash_multimap is also an Multiple Associative Container meaning that its elements do NOT need to have a unique keys, so that one key value may have many element data values associated with it and is reversible, because it provides a bidirectional iterator to access its elements.
Examples of declaring a hash_multimap:
// Create an empty hash_multimap hmp0 of key type integer
hash_multimap <int, int> hmp0;
// Create an empty hash_multimap hmp1 with the key comparison function of less than
hash_multimap <int, int, hash_compare <int, less<int> > > hmp1;Performance
The main advantage of hashing over sorting is greater efficiency; a successful hashing performs insertions, deletions, and finds in constant average time as compared with a time proportional to the logarithm of the number of elements in the container for sorting techniques.
The value of an element in a hash_multimap, but not its associated key value, may be changed directly. Instead, key values associated with old elements must be deleted and new key values associated with new elements inserted.
Hashed associative containers are optimized for the operations of lookup, insertion and removal. The member functions that explicitly support these operations are efficient when used with a well-designed hash function, performing them in a time that is on average constant and not dependent on the number of elements in the container. A well-designed hash function produces a uniform distribution of hashed values and minimizes the number of collisions. In the worst case, with the worst possible hash function, the number of operations is proportional to the number of elements in the sequence (linear time).
Hash Multimap Header Members
Operators
| Operator | Description |
| operator!= | Tests if the hash_multimap object on the left side of the operator is not equal to the hash_multimap object on the right side |
| operator< | Tests if the hash_multimap object on the left side of the operator is less than the hash_multimap object on the right side |
| operator<= | Tests if the hash_multimap object on the left side of the operator is less than or equal to the hash_multimap or object on the right side |
| operator== | Tests if the hash_multimap object on the left side of the operator is equal to the hash_multimap object on the right side |
| operator> | Tests if the hash_multimap object on the left side of the operator is greater than the hash_multimap object on the right side |
| operator>= | Tests if the hash_multimap object on the left side of the operator is greater than or equal to the hash_multimap object on the right side |
| operator[ ] | Inserts an element into a hash_multimap with a specified key value |
Classes
| Class | Description |
| hash_compare | Describes an object that can be used by any of the hash associative containers: hash_map, hash_multimap, hash_set, or hash_multiset, as a default Traits parameter object to order and hash the elements they contain |
| value_compare | Provides a function object that can compare the elements of a hash_multimap by comparing the values of their keys to determine their relative order in the hash_multimap |
| hash_multimap | Used for the storage and fast retrieval of data from a collection in which each element is a pair that has a sort key whose value need NOT be unique and an associated data value |
Hash Multimap Template Class Members
Typedefs
| Typedef | Description |
| allocator_type | A type that represents the allocator class for the hash_multimap object |
| const_iterator | A type that provides a bidirectional iterator that can read a const element in the hash_multimap |
| const_pointer | A type that provides a pointer to a const element in a hash_multimap |
| const_reference | A type that provides a reference to a const element stored in a hash_multimap for reading and performing const operations |
| const_reverse_iterator | A type that provides a bidirectional iterator that can read any const element in the hash_multimap |
| difference_type | A signed integer type that can be used to represent the number of elements of a hash_multimap in a range between elements pointed to by iterators |
| iterator | A type that provides a bidirectional iterator that can read or modify any element in a hash_multimap |
| key_compare | A type that provides a function object that can compare two sort keys to determine the relative order of two elements in the hash_multimap |
| key_type | A type that describes the sort key object that constitutes each element of the hash_multimap |
| mapped_type | A type that represents the data type stored in a hash_multimap |
| pointer | A type that provides a pointer to an element in a hash_multimap |
| reference | A type that provides a reference to an element stored in a hash_multimap |
| reverse_iterator | A type that provides a bidirectional iterator that can read or modify an element in a reversed hash_multimap |
| size_type | An unsigned integer type that can represent the number of elements in a hash_multimap |
| value_type | A type that provides a function object that can compare two elements as sort keys to determine their relative order in the hash_multimap |
Member Functions
| Function | Description |
| begin() | Returns an iterator addressing the first element in the hash_multimap |
| rbegin() | Returns an iterator addressing the first element in a reversed hash_multimap |
| clear() | Erases all the elements of a hash_multimap |
| count() | Returns the number of elements in a hash_multimap whose key matches a parameter-specified key |
| empty() | Tests if a hash_multimap is empty |
| end() | Returns an iterator that addresses the location succeeding the last element in a hash_multimap |
| rend() | Returns an iterator that addresses the location succeeding the last element in a reversed hash_multimap |
| equal_range() | Returns an iterator that addresses the location succeeding the last element in a hash_multimap |
| erase() | Removes an element or a range of elements in a hash_multimap from specified positions |
| find() | Returns an iterator addressing the location of an element in a hash_multimap that has a key equivalent to a specified key |
| get_allocator() | Returns a copy of the allocator object used to construct the hash_multimap |
| hash_multimap() | Hash_multimap constructor, constructs a list of a specific size or with elements of a specific value or with a specific allocator or as a copy of some other hash_multimap |
| insert() | Inserts an element or a range of elements into the hash_multimap at a specified position |
| key_comp() | Retrieves a copy of the comparison object used to order keys in a hash_multimap |
| lower_bound() | Returns an iterator to the first element in a hash_multimap that with a key value that is equal to or greater than that of a specified key |
| upper_bound() | Returns an iterator to the first element in a hash_multimap that with a key value that is greater than that of a specified key |
| size() | Specifies a new size for a hash_multimap |
| max_size() | Returns the maximum length of the hash_multimap |
| swap() | Exchanges the elements of two hash_multimaps |
| value_comp() | Retrieves a copy of the comparison object used to order element values in a hash_multimap |