|< C++ STL Container 9 | Main | C++ STL Container 11 >| Site Index | Download |


 

 

 

 

 

MODULE 29b

THE C++ STL CONTAINER PART 10

map, multimap, hash_map, hash_multimap, hash_set, hash_multiset

 

 

 

 

 

 

 

 

 

 

 

 

 

My Training Period:        hours

 

This is a continuation from previous C++ STL Container, compiled using VC++7.0/.Net, win32 empty console mode application.  Be careful with the source codes than span more than one line. g++ compilation examples are given at the end of this Module. Source code is available in C++ STL Container source code.

 

The C++ STL containers programming abilities that supposed to be acquired:

 

  • Able to understand and use hash_set associative container.

  • Able to understand and use hash_multiset container.

  • Some useful summary.

 

What do we have in this session?

  1. hash_set

  2. <hash_set> Header Members – operators, specialized template functions & classes

  3. hash_set Template Class Members – typedefs & class member functions

  4. hash_set Class

  5. hash_set Constructor

  6. hash_set, constructor program example

 

29.5.3  hash_set

 

  • The elements of a hash_set are unique and serve as their own sort keys.  A model for this type of structure is an ordered list of, say, words in which the words may occur only once.

  • If multiple occurrences of the words were allowed, then a hash_multiset would be the appropriate container structure.  If unique definitions were attached as values to the list of 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_set 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.

  • The iterator provided by the hash_set class is a bidirectional iterator.

<hash_set> Header Members

 

Operators

 

Operator

Description

operator!=

Tests if the hash_set or hash_multiset object on the left side of the operator is not equal to the hash_set or hash_multiset object on the right side.

operator<

Tests if the hash_set or hash_multiset object on the left side of the operator is less than the hash_set or hash_multiset object on the right side.

operator<=

Tests if the hash_set or hash_multiset object on the left side of the operator is less than or equal to the hash_set or hash_multiset object on the right side.

operator==

Tests if the hash_set or hash_multiset object on the left side of the operator is equal to the hash_set or hash_multiset 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 the hash_set or hash_multiset 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.

 

Table 29.22

 

Specialized Template Functions

 

Specialized template function

Description

swap()

Exchanges the elements of two hash_sets or hash_multisets.

 

Table 29.23

 

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

 

Table 29.24

 

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.

 

Table 29.25

 

hash_set Template Class Member Functions

 

Member function

Description

begin()

Returns an iterator that addresses the first element in the 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.

end()

Returns an iterator that addresses the location succeeding the last element in a hash_set.

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.

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.

hash_set()

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

insert()

Inserts an element or a range of elements into a 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.

max_size()

Returns the maximum length of the hash_set.

rbegin()

Returns an iterator addressing the first element in a reversed hash_set.

rend()

Returns an iterator that addresses the location succeeding the last element in a reversed hash_set.

size()

Returns the number of elements in the hash_set.

swap()

Exchanges the elements of two hash_sets.

upper_bound()

Returns an iterator to the first element in a hash_set 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_set.

 

Table 29.26

 

hash_set Class

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

 

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

 

Table 29.27

 

  • The hash_set is:

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

  2. Reversible, because it provides a bidirectional iterator to access its elements.

  3. Hashed, because its elements are grouped into buckets based on the value of a hash function applied to the key values of the elements.

  4. Unique in the sense that each of its elements must have a unique key.  Because hash_set is also a simple associative container, its elements are also unique.

  5. 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_set Constructor

// hash_set, constructor, compiled with VC7.0/.Net with some warnings

#include <hash_set>

#include <iostream>

using namespace std;

 

int main()

{

    hash_set <int>::iterator hst0_Iter, hst1_Iter, hst3_Iter, hst4_Iter, hst5_Iter;

    hash_set <int, hash_compare <int, greater<int> > >::iterator hst2_Iter;

    // 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, then insert 5 elements

    hash_set <int, hash_compare<int, less<int> > > hst1;

    hst1.insert(7);

    hst1.insert(3);

    hst1.insert(12);

    hst1.insert(51);

    hst1.insert(10);

    // create an empty hash_set hst2 with the key comparison function of greater than, then insert 4 elements

    hash_set<int, hash_compare<int, greater<int> > > hst2;

    hst2.insert(71);

    hst2.insert(68);

    hst2.insert(68);

    hst2.insert(55);

    // create a hash_set hst3 with the hash_set hst1 allocator

    hash_set<int>::allocator_type hst1_Alloc;

    hst1_Alloc = hst1.get_allocator();

    hash_set<int> hst3(less<int>(),hst1_Alloc);

    hst3.insert(12);

    hst3.insert(13);

    hst3.insert(12);

    // create a hash_set hst4 by copying the range hst1[_First, _Last)

    hash_set <int>::const_iterator hst1_PIter, hst1_QIter;

    hst1_PIter = hst1.begin();

    hst1_QIter = hst1.begin();

    hst1_QIter++;

    hst1_QIter++;

    hash_set<int> hst4(hst1_PIter, hst1_QIter);

    // create a hash_set hst5 by copying the range hst4[_First, _Last) and with the allocator of hash_set hst2

    hash_set <int>::allocator_type hst2_Alloc;

    hst2_Alloc = hst2.get_allocator();

    hash_set <int> hst5(hst1.begin(), ++hst1.begin(), less<int>(), hst2_Alloc);

    // --------------------------------------------------------------

    cout<<"Operation: hash_set <int> hst0\n";

    cout<<"hst0 data: ";

    for(hst0_Iter = hst0.begin(); hst0_Iter != hst0.end(); hst0_Iter++)

        cout<<*hst0_Iter<<" ";

    cout<<endl;

    cout<<"\nOperation: hash_set <int, hash_compare<int, \nless<int> > > hst1\n";

    cout<<"Operation: hst1.insert(7)...\n";

    cout<< "hst1 data: ";

    for(hst1_Iter = hst1.begin(); hst1_Iter != hst1.end(); hst1_Iter++)

        cout<<*hst1_Iter << " ";

    cout<<endl;

    cout<<"\nOperation: hash_set <int, hash_compare<int, \ngreater<int> > > hst2\n";

    cout<<"Operation: hst2.insert(71)...\n";

    cout<<"hst2 data: ";

    for(hst2_Iter = hst2.begin(); hst2_Iter != hst2.end(); hst2_Iter++)

        cout<<*hst2_Iter<<" ";

    cout<<endl;

    cout<<"\nOperation: hash_set<int> hst3(less<int>(),hst1_Alloc)\n";

    cout<<"Operation: hst3.insert(12)...\n";

    cout<<"hst3 data: ";

    for(hst3_Iter = hst3.begin(); hst3_Iter != hst3.end(); hst3_Iter++)

        cout<<*hst3_Iter<<" ";

    cout<<endl;

    cout<<"\nOperation: hash_set<int> hst4(hst1_PIter, hst1_QIter)\n";

    cout<<"hst4 data: ";

    for(hst4_Iter = hst4.begin(); hst4_Iter != hst4.end(); hst4_Iter++)

        cout<<*hst4_Iter<<" ";

    cout<<endl;

    cout<<"\nOperation: hash_set <int> hst5(hst1.begin(), \n++hst1.begin(), less<int>(), hst2_Alloc)\n";

    cout<<"hst5 data: ";

    for(hst5_Iter = hst5.begin(); hst5_Iter != hst5.end(); hst5_Iter++)

        cout<<*hst5_Iter<<" ";

    cout<<endl;

    return 0;

}

 

Output:

 

C++ STL Associative container hash_set constructor

 

---------------------------------------------End of the hash_set----------------------------------------

tenouk C++ STL tutorial

 

 

 

 

 

 

 

 

 

 

 

 

Further C++ STL container classes reading:

 

  1. Source code is available in C++ STL Container source code.

  2. Check the best selling C / C++ and STL books at Amazon.com.

 

 

 

 

 

|< C++ STL Container 9 | Main | C++ STL Container 11 >| Site Index | Download |


C++ STL Container Classes:  Part 1 | Part 2 | Part 3 | Part 4 | Part 5 | Part 6 | Part 7 | Part 8 | Part 9 | Part 10 | Part 11