Continue from the previous Module, compiled usingVC++7.0 / .Net, win32 empty console mode application. Be careful with the source codes than span more than one line. Linux g++ compilation examples are given at the end of this Module. Source code is available inC++ STL Container source code.
| 29.5 Hash Tables
29.5.1 hash_map
<hash_map> Header Members
Operators
|
Specialized template function | Description |
swap() | Exchanges the elements of twohash_maps or hash_multimaps. |
Table 29.13 |
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 Traitsparameter object to order and hash the elements they contain. |
value_compare | Provides a function object that can compare the elements of a hash_map by comparing the values of their keys to determine their relative order in the hash_map. |
hash_map | 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 is unique and an associated data value. |
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. |
Table 29.14 |
Typedef | Description |
allocator_type | A type that represents the allocator class for the hash_map object. |
const_iterator | A type that provides a bidirectional iterator that can read a const element in the hash_map. |
const_pointer | A type that provides a pointer to aconst element in a hash_map. |
const_reference | A type that provides a reference to a const element stored in a hash_map 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_map. |
difference_type | A signed integer type that can be used to represent the number of elements of a hash_map 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 ahash_map. |
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_map. |
key_type | A type describes the sort key object that constitutes each element of the hash_map. |
mapped_type | A type that represents the data type stored in a hash_map. |
pointer | A type that provides a pointer to an element in a hash_map. |
reference | A type that provides a reference to an element stored in a hash_map. |
reverse_iterator | A type that provides a bidirectional iterator that can read or modify an element in a reversedhash_map. |
size_type | An unsigned integer type that can represent the number of elements in a hash_map. |
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_map. |
table 29.15 |
Member function | Description |
begin() | Returns an iterator addressing the first element in the hash_map. |
clear() | Erases all the elements of a hash_map. |
count() | Returns the number of elements in a hash_map whose key matches a parameter-specified key. |
empty() | Tests if a hash_map is empty. |
end() | Returns an iterator that addresses the location succeeding the last element in a hash_map. |
equal_range() | Returns a pair of iterators, respectively, to the first element in a hash_map with a key that is greater than a specified key and to the first element in the hash_map with a key that is equal to or greater than the key. |
erase() | Removes an element or a range of elements in a hash_map from specified positions |
find() | Returns an iterator addressing the location of an element in a hash_map that has a key equivalent to a specified key. |
get_allocator() | Returns a copy of the allocator object used to construct the hash_map. |
hash_map() | Constructs a hash_map that is empty or that is a copy of all or part of some other hash_map. |
insert() | Inserts an element or a range of elements into a hash_map. |
key_comp() | Returns an iterator to the first element in a hash_map with a key value that is equal to or greater than that of a specified key. |
lower_bound() | Returns an iterator to the first element in a hash_map with a key value that is equal to or greater than that of a specified key. |
max_size() | Returns the maximum length of the hash_map. |
rbegin() | Returns an iterator addressing the first element in a reversed hash_map. |
rend() | Returns an iterator that addresses the location succeeding the last element in a reversed hash_map. |
size() | Specifies a new size for a hash_map. |
swap() | Exchanges the elements of two hash_maps. |
upper_bound() | Returns an iterator to the first element in a hash_map that with a key value that is greater than that of a specified key. |
value_comp() | Retrieves a copy of the comparison object used to order element values in a hash_map. |
Table 29.16 |
Operator | Description |
operator[ ] | Inserts an element into ahash_map with a specified key value. |
Table 29.17 |
Stores and retrieves data quickly from a collection in which each element is a pair that has a sort key whose value is unique and an associated data value.
template < class Key, class Type, class Traits=hash_compare<Key, less<Key> >, class Allocator=allocator<pair <const Key, Type> > >
Parameter | Description |
Key | The element data type to be stored in the hash_map. |
Type | The element data type to be stored in the hash_map. |
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 hash_compare<Key, less<Key> >is the default value. |
Allocator | The type that represents the stored allocator object that encapsulates details about thehash_map's allocation and de-allocation of memory. This argument is optional, and the default value isallocator<pair <const Key, Type> >. |
Table 29.18 |
Thehash_map is:
An associative container, which a variable size container that supports the efficient retrieval of element values based on an associated key value.
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.
A pair associative container, because its element data values are distinct from its key values.
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.
|
// hash_map, constructor, compiled with visual C++ 7.0 or VC.Net, with some warnings
#include <hash_map>
#include <iostream>
using namespace std;
int main()
{
typedef pair <int, int> Int_Pair;
hash_map <int, int>::iterator hmp0_Iter, hmp1_Iter, hmp3_Iter, hmp4_Iter, hmp5_Iter, hmp6_Iter;
hash_map <int, int, hash_compare<int, greater<int> > >::iterator hmp2_Iter;
// create an empty hash_map hmp0 of key type integer
hash_map <int, int> hmp0;
// create an empty hash_map hmp1 with the key comparison function of less than, then insert 4 elements
hash_map <int, int, hash_compare <int, less<int> > > hmp1;
hmp1.insert(Int_Pair(1, 13));
hmp1.insert(Int_Pair(3, 51));
hmp1.insert(Int_Pair(7, 22));
hmp1.insert(Int_Pair(2, 31));
// create an empty hash_map hmp2 with the key comparison function of greater than, then insert 4 elements no duplicate key...
hash_map <int, int, hash_compare <int, greater<int> > > hmp2;
hmp2.insert(Int_Pair(1, 17));
hmp2.insert(Int_Pair(2, 20));
hmp2.insert(Int_Pair(4, 13));
hmp2.insert(Int_Pair(3, 34));
// create a hash_map hmp3 with the hash_map hmp1 allocator notice the duplicate key...
hash_map <int, int>::allocator_type hmp1_Alloc;
hmp1_Alloc = hmp1.get_allocator();
hash_map <int, int> hmp3(less<int>(), hmp1_Alloc);
hmp3.insert(Int_Pair(2, 17));
hmp3.insert(Int_Pair(1, 12));
hmp3.insert(Int_Pair(2, 15));
hmp3.insert(Int_Pair(1, 22));
// create a hash_map hm5 by copying the range hm1[_First, _Last)
hash_map <int, int>::const_iterator hmp1_PIter, hmp1_QIter;
hmp1_PIter = hmp1.begin( );
hmp1_QIter = hmp1.begin( );
hmp1_QIter++;
hmp1_QIter++;
hash_map <int, int> hmp5(hmp1_PIter, hmp1_QIter);
// create a hash_map hm6 by copying the range hm2[_First, _Last) and with the allocator of hash_map hm2
hash_map <int, int>::allocator_type hmp2_Alloc;
hmp2_Alloc = hmp2.get_allocator();
hash_map <int, int> hmp6(hmp2.begin(), ++hmp2.begin(), less<int>(), hmp2_Alloc);
// ---------------------------------------------------------------
cout<<"Operation: hash_map <int, int> hmp0\n";
cout<<"hmp0 data: ";
for(hmp0_Iter = hmp0.begin(); hmp0_Iter != hmp0.end(); hmp0_Iter++)
cout<<hmp0_Iter->second<<" ";
cout<<endl;
cout<<"\nOperation1: hash_map<int, int, \nhash_compare<int, less<int> > > hmp1\n";
cout<<"Operation2: hmp1.insert(Int_Pair(1, 13))...\n";
cout<<"hmp1 data: ";
for(hmp1_Iter = hmp1.begin(); hmp1_Iter != hmp1.end(); hmp1_Iter++)
cout<<hmp1_Iter->second<<" ";
cout<<endl;
cout<<"\nOperation1: hash_map<int, int, \nhash_compare<int, greater<int> > > hmp2\n";
cout<<"Operation2: hmp2.insert(Int_Pair(1, 17))...\n";
cout<<"hmp2 data: ";
for(hmp2_Iter = hmp2.begin(); hmp2_Iter != hmp2.end(); hmp2_Iter++)
cout<<hmp2_Iter->second<<" ";
cout<<endl;
cout<<"\nOperation1: hash_map<int, int> hmp3(less<int>(), hmp1_Alloc)\n";
cout<<"Operation2: hmp3.insert(Int_Pair(2, 17))...\n";
cout<<"hmp3 data: ";
for(hmp3_Iter = hmp3.begin(); hmp3_Iter != hmp3.end(); hmp3_Iter++)
cout<<hmp3_Iter->second<<" ";
cout<<endl;
cout<<"\nOperation: hash_map<int, int> hmp5(hmp1_PIter, hmp1_QIter)\n";
cout<<"hmp5 data: ";
for(hmp5_Iter = hmp5.begin(); hmp5_Iter != hmp5.end(); hmp5_Iter++)
cout<<hmp5_Iter->second<<" ";
cout<<endl;
cout<<"\nOperation: hash_map<int, int> hmp6(hmp2.begin(), \n++hmp2.begin(), less<int>(), hmp2_Alloc);\n";
cout<<"hmp6 data: ";
for(hmp6_Iter = hmp6.begin(); hmp6_Iter != hmp6.end(); hmp6_Iter++)
cout<<hmp6_Iter->second <<" ";
cout<<endl;
return 0;
}
Output:
---------------------------------------------End of hash_map---------------------------------------
---www.tenouk.com---
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 aconst 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. |
Table 29.19 |
Member function | Description |
begin() | Returns an iterator addressing the first element in the 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. |
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_multimapconstructor, 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. |
max_size() | Returns the maximum length of the hash_multimap. |
rbegin() | Returns an iterator addressing the first element in a reversed hash_multimap. |
rend() | Returns an iterator that addresses the location succeeding the last element in a reversed hash_multimap. |
size() | Specifies a new size for a hash_multimap. |
swap() | Exchanges the elements of two hash_multimaps. |
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. |
value_comp() | Retrieves a copy of the comparison object used to order element values in a hash_multimap. |
Table 29.20 |
The container class hash_multimap is an extension of the STL 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.
template <class Key, class Type, class Traits = hash_compare<Key, less<Key> >, class Allocator = allocator<pair <const Key, Type> > >
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 typesize_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> >. |
Table 29.21 |
The hash_multimap is:
An associative container, which a variable size container that supports the efficient retrieval of element values based on an associated key value.
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.
Multiple, because its elements do not need to have a unique keys, so that one key value may have many element data values associated with it.
A pair associative container, because its element values are distinct from its key values.
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 hash_multimap 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 functionkey_comp().
Such a function object must behave the same as an object of classhash_compare<Key, less<Key> >. Specifically, for all values _Key of typeKey, the call Traits(_Key) yields a distribution of values of type size_t.
The iterator provided by the hash_multimap class is a bidirectional iterator, but the class member functions insert() andhash_multimap() 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.
Constructs a hash_multimap that is empty or that is a copy of all or part of some other hash_multimap.
All constructors store a type of allocator object that manages memory storage for the hash_multimap and that can later be returned by callingget_allocator(). The allocator parameter is often omitted in the class declarations and preprocessing macros used to substitute alternative allocators.
All constructors initialize their hash_multimap.
All constructors store a function object of type Traits that is used to establish an order among the keys of the hash_multimap and that can later be returned by calling key_comp().
The first three constructors specify an empty initial hash_multimap, the second specifying the type of comparison function (_Comp) to be used in establishing the order of the elements and the third explicitly specifying the allocator type (_Al) to be used. The keyword explicit suppresses certain kinds of automatic type conversion.
The fourth constructor specifies a copy of the hash_multimap_Right.
The last three constructors copy the range [_First, _Last) of a map with increasing explicitness in specifying the type of comparison function of class Traits andallocator.
// hash_multimap, constructor compiled with VC7.0 or .Net, a lot of warning messages:-)
#include <hash_map>
#include <iostream>
using namespace std;
int main()
{
typedef pair <int, int> Int_Pair;
hash_multimap <int, int>::iterator hmp0_Iter, hmp1_Iter, hmp3_Iter, hmp4_Iter, hmp5_Iter;
hash_multimap <int, int, hash_compare <int, greater<int> > >::iterator hmp2_Iter;
// 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, then insert 6 elements
hash_multimap <int, int, hash_compare <int, less<int> > > hmp1;
hmp1.insert(Int_Pair(3, 12));
hmp1.insert(Int_Pair(2, 30));
hmp1.insert(Int_Pair(1, 22));
hmp1.insert(Int_Pair(7, 41));
hmp1.insert(Int_Pair(4, 9));
hmp1.insert(Int_Pair(7, 30));
// create an empty hash_multimap hmp2 with the key comparison function of greater than, then insert 2 elements
hash_multimap <int, int, hash_compare <int, greater<int> > > hmp2;
hmp2.insert(Int_Pair(2, 13));
hmp2.insert(Int_Pair(1, 17));
// create a hash_multimap hmp3 with the allocator of hash_multimap hmp1
hash_multimap <int, int>::allocator_type hmp1_Alloc;
hmp1_Alloc = hmp1.get_allocator();
hash_multimap <int, int> hmp3(less<int>(),hmp1_Alloc);
hmp3.insert(Int_Pair(2, 13));
hmp3.insert(Int_Pair(4, 10));
// create a hash_multimap hmp4 by copying the range hmp1[_First, _Last)
hash_multimap <int, int>::const_iterator hmp1_PIter, hmp1_QIter;
hmp1_PIter = hmp1.begin();
hmp1_QIter = hmp1.begin();
hmp1_QIter++;
hmp1_QIter++;
hmp1_QIter++;
hash_multimap <int, int> hmp4(hmp1_PIter, hmp1_QIter);
// create a hash_multimap hmp5 by copying the range hmp2[_First, _Last) and with the allocator of hash_multimap hmp2
hash_multimap <int, int>::allocator_type hmp2_Alloc;
hmp2_Alloc = hmp2.get_allocator();
hash_multimap <int, int> hmp5(hmp2.begin(), ++hmp2.begin(), less<int>(), hmp2_Alloc);
// ----------------------------------------------------------------------------------------------
cout<<"Operation: hash_multimap <int, int> hmp0\n";
cout<<"hmp0 data: ";
for(hmp0_Iter = hmp0.begin(); hmp0_Iter != hmp0.end(); hmp0_Iter++)
cout<<hmp0_Iter->second<<" ";
cout<<endl;
cout<<"\nOperation1: hash_multimap<int, int, \n hash_compare<int, less<int> > > hmp1\n";
cout<<"Operation2: hmp1.insert(Int_Pair(3, 12))...\n";
cout<<"hmp1 data: ";
for(hmp1_Iter = hmp1.begin(); hmp1_Iter != hmp1.end(); hmp1_Iter++)
cout<<hmp1_Iter->second<<" ";
cout<<endl;
cout<<"\nOperation1: hash_multimap<int, int, \n hash_compare<int, greater<int> > > hmp2\n";
cout<<"Operation2: hmp2.insert(Int_Pair(2, 13))...\n";
cout<<"hmp2 data: ";
for(hmp2_Iter = hmp2.begin(); hmp2_Iter != hmp2.end(); hmp2_Iter++)
cout<<hmp2_Iter->second<<" ";
cout<<endl;
cout<<"\nOperation1: hash_multimap<int, int> hmp3(less<int>(), hmp1_Alloc)\n";
cout<<"Operation2: hmp3.insert(Int_Pair(2, 13))...\n";
cout<<"hmp3 data: ";
for(hmp3_Iter = hmp3.begin(); hmp3_Iter != hmp3.end(); hmp3_Iter++)
cout<<hmp3_Iter->second<<" ";
cout<<endl;
cout<<"\nOperation: hash_multimap<int, int> hmp4(hmp1_PIter, hmp1_QIter)\n";
cout<<"hmp4 data: ";
for(hmp4_Iter = hmp4.begin(); hmp4_Iter != hmp4.end(); hmp4_Iter++)
cout<<hmp4_Iter->second<<" ";
cout<<endl;
cout<<"\nOperation: hash_multimap<int, int> hmp5(hmp2.begin(), \n ++hmp2.begin(), less<int>(), hmp2_Alloc);\n";
cout<<"hmp5 data: ";
for(hmp5_Iter = hmp5.begin(); hmp5_Iter != hmp5.end(); hmp5_Iter++)
cout<<hmp5_Iter->second<<" ";
cout<<endl;
return 0;
}
Output:
-------------------------------------------End of hash_multimap------------------------------------
Source code is available inC++ STL Container source code.
Acomplete C++ Standard Library documentation that includes STL.