hash_multiset Class

Article
07/29/2015

Note

This API is obsolete. The alternative is unordered_multiset Class.

The container class hash_multiset is an extension of the Standard Template Library and is used for the storage and fast retrieval of data from a collection in which the values of the elements contained serve as the key values and are not required to be unique.

template < 
   class Key,  
   class Traits=hash_compare<Key, less<Key> >,  
   class Allocator=allocator<Key>  
> 
class hash_multiset

Parameters

Key
The element data type to be stored in the hash_multiset.
Traits
The type which includes two function objects, one of class compare 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_multiset's allocation and deallocation of memory. This argument is optional, and the default value is allocator*<Key>.*

Remarks

The hash_multiset is:

An associative container, which a variable size container that supports the efficient retrieval of element values based on an associated key value. Further, it is a simple associative container because its element values are its key values.
Reversible, because it provides a bidirectional iterator to access its elements.
Hashed, because its elements are grouped into buckets based on the value of a hash function applied to the key values of the elements.
Unique in the sense that each of its elements must have a unique key. Because hash_multiset is also a simple associative container, its elements are also unique.
A template class because the functionality it provides is generic and so independent of the specific type of data contained as elements or keys. The data types to be used for elements and keys are, instead, specified as parameters in the class template along with the comparison function and allocator.

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 set may not be changed directly. Instead, you must delete old values and insert elements with new values.

The choice of container type should be based in general on the type of searching and inserting required by the application. 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, where a collision is said to occur when distinct key values are mapped into the same hashed value. 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).

The hash_multiset should be the associative container of choice when the conditions associating the values with their keys are satisfies by the application. The elements of a hash_multiset may be multiple and serve as their own sort keys, so keys are not unique. A model for this type of structure is an ordered list of, say, words in which the words may occur more than once. Had multiple occurrences of the words not been allowed, then a hash_set would have been the appropriate container structure. If unique definitions were attached as values to the list of unique keywords, then a hash_map would be an appropriate structure to contain this data. If instead the definitions were not unique, then a hash_multimap would be the container of choice.

The hash_multiset orders the sequence it controls by calling a stored hash traits object of type value_compare. This stored object may be accessed by calling the member function key_comp. Such a function object must behave the same as an object of class hash_compare*<Key,* less*<Key> >.* Specifically, for all values Key of type Key, the call Trait(Key) yields a distribution of values of type size_t.

In general, the elements need be merely less than comparable to establish this order: so that, given any two elements, it may be determined either that they are equivalent (in the sense that neither is less than the other) or that one is less than the other. This results in an ordering between the nonequivalent elements. On a more technical note, the comparison function is a binary predicate that induces a strict weak ordering in the standard mathematical sense. A binary predicate f(x,y) is a function object that has two argument objects x and y and a return value of true or false. An ordering imposed on a hash_multiset is a strict weak ordering if the binary predicate is irreflexive, antisymmetric, and transitive and if equivalence is transitive, where two objects x and y are defined to be equivalent when both f(x,y) and f(y,x) are false. If the stronger condition of equality between keys replaces that of equivalence, then the ordering becomes total (in the sense that all the elements are ordered with respect to each other) and the keys matched will be indiscernible from each other.

The actual order of elements in the controlled sequence depends on the hash function, the ordering function, and the current size of the hash table stored in the container object. You cannot determine the current size of the hash table, so you cannot in general predict the order of elements in the controlled sequence. Inserting elements invalidates no iterators, and removing elements invalidates only those iterators that had specifically pointed at the removed elements.

The iterator provided by the hash_multiset class is a bidirectional iterator, but the class member functions insert and hash_multiset have versions that take as template parameters a weaker input iterator, whose functionality requirements are more minimal than those guaranteed by the class of bidirectional iterators. The different iterator concepts form a family related by refinements in their functionality. Each iterator concept has its own hash_multiset of requirements, and the algorithms that work with them must limit their assumptions to the requirements provided by that type of iterator. It may be assumed that an input iterator may be dereferenced to refer to some object and that it may be incremented to the next iterator in the sequence. This is a minimal hash_multiset of functionality, but it is enough to be able to talk meaningfully about a range of iterators [_First, _Last) in the context of the class member functions.

In Visual C++ .NET 2003, members of the <hash_map> and <hash_set> header files are no longer in the std namespace, but rather have been moved into the stdext namespace. See The stdext Namespace for more information.

Constructors

hash_multiset

Constructs a hash_multiset that is empty or that is a copy of all or part of some other hash_multiset.

Typedefs

allocator_type	A type that represents the allocator class for the hash_multiset object.
const_iterator	A type that provides a bidirectional iterator that can read a const element in the hash_multiset.
const_pointer	A type that provides a pointer to a const element in a hash_multiset.
const_reference	A type that provides a reference to a const element stored in a hash_multiset 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_multiset.
difference_type	A signed integer type that provides the difference between two iterators that address elements within the same hash_multiset.
iterator	A type that provides a bidirectional iterator that can read or modify any element in a hash_multiset.
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_multiset.
key_type	A type that describes an object stored as an element of a hash_set in its capacity as sort key.
pointer	A type that provides a pointer to an element in a hash_multiset.
reference	A type that provides a reference to an element stored in a hash_multiset.
reverse_iterator	A type that provides a bidirectional iterator that can read or modify an element in a reversed hash_multiset.
size_type	An unsigned integer type that can represent the number of elements in a hash_multiset.
value_compare	A type that provides two function objects, a binary predicate of class compare that can compare two element values of a hash_multiset to determine their relative order and a unary predicate that hashes the elements.
value_type	A type that describes an object stored as an element of a hash_multiset in its capacity as a value.

Member Functions

begin	Returns an iterator that addresses the first element in the hash_multiset.
hash_multiset::cbegin	Returns a const iterator addressing the first element in the hash_multiset.
hash_multiset::cend	Returns a const iterator that addresses the location succeeding the last element in a hash_multiset.
clear	Erases all the elements of a hash_multiset.
count	Returns the number of elements in a hash_multiset whose key matches a parameter-specified key
hash_multiset::crbegin	Returns a const iterator addressing the first element in a reversed hash_multiset.
hash_multiset::crend	Returns a const iterator that addresses the location succeeding the last element in a reversed hash_multiset.
hash_multiset::emplace	Inserts an element constructed in place into a hash_multiset.
hash_multiset::emplace_hint	Inserts an element constructed in place into a hash_multiset, with a placement hint.
empty	Tests if a hash_multiset is empty.
end	Returns an iterator that addresses the location succeeding the last element in a hash_multiset.
equal_range	Returns a pair of iterators respectively to the first element in a hash_multiset with a key that is greater than a specified key and to the first element in the hash_multiset with a key that is equal to or greater than the key.
erase	Removes an element or a range of elements in a hash_multiset from specified positions or removes elements that match a specified key.
find	Returns an iterator addressing the location of an element in a hash_multiset that has a key equivalent to a specified key.
get_allocator	Returns a copy of the allocator object used to construct the hash_multiset.
insert	Inserts an element or a range of elements into a hash_multiset.
key_comp	Retrieves a copy of the comparison object used to order keys in a hash_multiset.
lower_bound	Returns an iterator to the first element in a hash_multiset with a key that is equal to or greater than a specified key.
max_size	Returns the maximum length of the hash_multiset.
rbegin	Returns an iterator addressing the first element in a reversed hash_multiset.
rend	Returns an iterator that addresses the location succeeding the last element in a reversed hash_multiset.
size	Returns the number of elements in the hash_multiset.
swap	Exchanges the elements of two hash_multisets.
upper_bound	Returns an iterator to the first element in a hash_multiset that with a key that is equal to or greater than a specified key.
value_comp	Retrieves a copy of the hash traits object used to hash and order element key values in a hash_multiset.

Operators

hash_multiset::operator=

Replaces the elements of the hash_multiset with a copy of another hash_multiset.

Requirements

Header: <hash_set>

Namespace: stdext

Share via