I have forgotten
my Password

Or login with:

  • Facebookhttp://facebook.com/
  • Googlehttps://www.google.com/accounts/o8/id
  • Yahoohttps://me.yahoo.com

Hash Multiset

Hash multiset is a hash set that can contain multiple identical values
+ View version details

Key Facts

Gyroscopic Couple: The rate of change of angular momentum (\inline \tau) = \inline I\omega\Omega (In the limit).
  • \inline I = Moment of Inertia.
  • \inline \omega = Angular velocity
  • \inline \Omega = Angular velocity of precession.


Blaise Pascal (1623-1662) was a French mathematician, physicist, inventor, writer and Catholic philosopher.

Definition

Hash_multiset template is defined in the header <hash_set>, and in the backward-compatibility header <hash_set.h>. This class is an SGI extension; it is not part of the C++ standard.

#include <hash_set>
namespace std{
      template < class Key,
                 class Traits = hash_compare<Key, less<Key> >,
                 class Allocator = allocator<Key> > 
      class hash_multiset;
}

Parameters:
Parameter Description
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 de-allocation of memory. This argument is optional, and the default value is allocator<Key>

Description

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.

Hash_multiset 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.

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_multiset:
// Create an empty hash_multiset hms0 of key type integer
hash_multiset <int> hms0;
 
// Create an empty hash_multiset hms1 with the key comparison function of less than
hash_multiset<int, hash_compare<int, less<int> > > hms1;
 
// Create an empty hash_multiset hms2 with the key comparison function of greater than
hash_multiset<int, hash_compare<int, greater<int> > > hms2;

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.

A collision occurs when distinct key values are mapped into the same hashed value.

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 Multiset Header Members

Operators

Operator Description
operator!= Tests if the hash_multiset object on the left side of the operator is not equal to the hash_multiset object on the right side
operator< Tests if the hash_multiset object on the left side of the operator is less than the hash_multiset object on the right side
operator<= Tests if the hash_multiset object on the left side of the operator is less than or equal to the hash_multiset object on the right side
operator== Tests if the hash_multiset object on the left side of the operator is equal to the hash_multiset object on the right side
operator> Tests if the hash_multiset object on the left side of the operator is greater than the hash_multiset object on the right side
operator>= Tests if the hash_multiset object on the left side of the operator is greater than or equal to the hash_multiset object on the right side

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
hash_multiset Used for the storage and fast retrieval of data from a collection in which the values of the elements contained are unique and serve as the key values

Hash Multiset Template Class Members

Typedefs

Typedef Description
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_reverese_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 provides a function object that can compare sort keys to determine the relative order of two elements in the hash_multiset
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

Function Description
hash_multiset() hash_multiset constructor, constructs a hash_multiset that is empty or that is a copy of all or part of some other hash_multiset
begin() Returns an iterator that addresses the first element in the hash_multiset
rbegin() Returns an iterator addressing the first element in a reversed hash_multiset
end() Returns an iterator that addresses the location succeeding the last element in a hash_multiset
rend() Returns an iterator that addresses the location succeeding the last element in a reversed 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
empty() Tests if a hash_multiset is empty
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
find() Returns an iterator addressing the location of an element in a hash_multiset that has a key equivalent to a specified key
insert() Inserts an element or a range of elements into a hash_multiset
erase() Removes an element or a range of elements in a hash_multiset from specified positions or removes elements that match a specified key
get_allocator() Returns a copy of the allocator object used to construct the 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
upper_bound() Returns an iterator to the first element in a hash_set that with a key that is greater than a specified key
size() Returns the number of elements in the hash_multiset
max_size() Returns the maximum length of the hash_multiset
swap() Exchanges the elements of two hash_multisets
value_comp() Retrieves a copy of the hash traits object used to hash and order element key values in a hash_multiset
Example:
Example - hash_multiset methods
Problem
This program illustrates a hash_multiset including a default constructor and the insert(), begin(), erase() member functions of the STL hash_multiset interface.
Workings
#define _DEFINE_DEPRECATED_HASH_CLASSES 0
#include <iostream>
#include <hash_set>
 
using namespace std;
using namespace stdext;
 
int main()
{
  hash_multiset <int> hms1;
  hash_multiset <int>::iterator hms1_Iter;
  hash_multiset <int>::const_iterator hms1_cIter;
 
  hms1.insert( 1 );
  hms1.insert( 2 );
  hms1.insert( 3 );
 
  hms1_Iter = hms1.begin( );
  cout<<"The first element of hms1 is "<<*hms1_Iter<<endl;
 
  hms1_Iter = hms1.begin( );
  hms1.erase( hms1_Iter );
 
  // The following 2 lines would err because the iterator is const
  // hms1_cIter = hms1.begin( );
  // hms1.erase( hms1_cIter );
 
  hms1_cIter = hms1.begin( );
  cout <<"The first element of hms1 is now "<<*hms1_cIter<<endl;
 
  return 0;
}
Solution
Output:

The first element of hms1 is 1
The first element of hms1 is now 2