Login
Hash Set
Hash set is a set that uses a hash table to provide faster searching functionnality
Contents
Key Facts
Gyroscopic Couple: The rate of change of angular momentum (= Moment of Inertia.
= Angular velocity
= Angular velocity of precession.
Blaise Pascal (1623-1662) was a French mathematician, physicist, inventor, writer and Catholic philosopher.
Definition
Hash_set 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_set; }Parameters:
| Parameter | Description |
|---|---|
| Key | The element data type to be stored in the hash_set |
| 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_set's allocation and de-allocation of memory. This argument is optional, and the default value is allocator<Key> |
Description:
Hash_set is an extension of the STL and helps to storage and to find quickly data from a collection in which the values of the elements contained are unique and serve as the key values. Hash_set 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 Reversible, because it provides a bidirectional iterator to access its elements. Hash_set is also an Unique Associative Container meaning that each of its elements must have a unique key. Further, it is a Simple Associative Container because its elements are also unique. Examples of declaring a hash_set:// Create an empty hash_set hst0 of key type integer hash_set <int> hst0; // Create an empty hash_set hst1 with the key comparison function of less than hash_set <int, hash_compare<int, less<int> > > hst1; // Create an empty hash_set hst2 with the key comparison function of greater than hash_set<int, hash_compare<int, greater<int> > > hst2;
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 set may not be changed directly. Instead, you must delete old values and insert elements with new values.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 Set Header Members
Operators| Operator | Description |
|---|---|
| operator!= | Tests if the hash_set object on the left side of the operator is not equal to the hash_set object on the right side |
| operator< | Tests if the hash_set object on the left side of the operator is less than the hash_set object on the right side |
| operator<= | Tests if the hash_set object on the left side of the operator is less than or equal to the hash_set object on the right side |
| operator== | Tests if the hash_set object on the left side of the operator is equal to the hash_set object on the right side |
| operator> | Tests if the hash_set object on the left side of the operator is greater than the hash_set object on the right side |
| operator>= | Tests if the hash_set or hash_multiset object on the left side of the operator is greater than or equal to the hash_set or hash_multiset object on the right side |
| 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_set | 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 Set Template Class Members
Typedefs| Typedef | Description |
|---|---|
| allocator_type | A type that represents the allocator class for the hash_set object |
| const_iterator | A type that provides a bidirectional iterator that can read a const element in the hash_set |
| const_pointer | A type that provides a pointer to a const element in a hash_set |
| const_reference | A type that provides a reference to a const element stored in a hash_set 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_set |
| difference_type | A signed integer type that can be used to represent the number of elements of a hash_set 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_set |
| 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_set |
| 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_set |
| reference | A type that provides a reference to an element stored in a hash_set |
| reverse_iterator | A type that provides a bidirectional iterator that can read or modify an element in a reversed hash_set |
| size_type | An unsigned integer type that can represent the number of elements in a hash_set |
| value_compare | A type that provides two function objects, a binary predicate of class compare that can compare two element values of a hash_set 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_set in its capacity as a value |
| Function | Description |
|---|---|
| hash_set() | Constructs a hash_set that is empty or that is a copy of all or part of some other hash_set |
| begin() | Returns an iterator that addresses the first element in the hash_set |
| rbegin() | Returns an iterator addressing the first element in a reversed hash_set |
| end() | Returns an iterator that addresses the location succeeding the last element in a hash_set |
| rend() | Returns an iterator that addresses the location succeeding the last element in a reversed hash_set |
| clear() | Erases all the elements of a hash_set |
| count() | Returns the number of elements in a hash_set whose key matches a parameter-specified key |
| empty() | Tests if a hash_set is empty |
| equal_range() | Returns a pair of iterators respectively to the first element in a hash_set with a key that is greater than a specified key and to the first element in the hash_set with a key that is equal to or greater than the key |
| insert() | Inserts an element or a range of elements into a hash_set |
| erase() | Removes an element or a range of elements in a hash_set from specified positions or removes elements that match a specified key |
| find() | Returns an iterator addressing the location of an element in a hash_set that has a key equivalent to a specified key |
| get_allocator() | Returns a copy of the allocator object used to construct the hash_set |
| key_comp() | Retrieves a copy of the comparison object used to order keys in a hash_set |
| lower_bound() | Returns an iterator to the first element in a hash_set 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_set |
| max_size() | Returns the maximum length of the hash_set |
| swap() | Exchanges the elements of two hash_sets |
| value_comp() | Retrieves a copy of the hash traits object used to hash and order element key values in a hash_set |
Example:
Example - hash_set methods
Problem
This program illustrates a hash_set including a default constructor and the insert(), begin(), erase() member functions of the STL hash_set interface.
Workings
#define _DEFINE_DEPRECATED_HASH_CLASSES 0 #include <iostream> #include <hash_set> using namespace std; using namespace stdext; int main { hash_set <int> hs1; hash_set <int>::iterator hs1_Iter; hash_set <int>::const_iterator hs1_cIter; hs1.insert( 1 ); hs1.insert( 2 ); hs1.insert( 3 ); hs1_Iter = hs1.begin( ); cout <<"The first element of hs1 is "<<*hs1_Iter<<endl; hs1_Iter = hs1.begin( ); hs1.erase( hs1_Iter ); // The following 2 lines would err because the iterator is const // hs1_cIter = hs1.begin( ); // hs1.erase( hs1_cIter ); hs1_cIter = hs1.begin( ); cout <<"The first element of hs1 is now "<<*hs1_cIter<<endl; return 0; }
Solution
Output:
The first element of hs1 is 1
The first element of hs1 is now 2
The first element of hs1 is now 2