|< C++ STL Container 10 | Main | C++ STL Container Adapter >|Site Index |Download |

MODULE 29b_1

THE C++ STL CONTAINER PART 11

map, multimap, hash_map, hash_multimap, hash_set,hash_multiset

Member Functions

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

Parameters

• The hash_multiset 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_multiset 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.

• The elements of a hash_multiset may be multiple and serve as their own sort keys, so keys are not unique.

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

• 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() andhash_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.

hash_multiset Constructor

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

• All constructors store a type of allocator object that manages memory storage for the hash_multiset 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_multisets.

• All constructors store a function object of type Traits that is used to establish an order among the keys of the hash_multiset and that can later be returned by calling key_comp().

• The first three constructors specify an empty initial hash_multiset, 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_multiset_Right.

• The last three constructors copy the range [_First, _Last) of a hash_multiset with increasing explicitness in specifying the type of comparison function of class Compare andallocator.

• The actual order of elements in a hash_set container depends on the hash function, the ordering function and the current size of the hash table and cannot, in general, be predicted as it could with the set container, where it was determined by the ordering function alone.

// hash_multiset, constructor, compiled with VC7.0 or .Net, wit a lot of warning messages...

#include <hash_set>

#include <iostream>

using namespace std;

 

int main()

{

   hash_multiset <int>::iterator hms0_Iter, hms1_Iter, hms3_Iter, hms4_Iter, hms5_Iter;

   hash_multiset <int, hash_compare <int, greater<int> > >::iterator hms2_Iter;

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

   hash_multiset<int, hash_compare<int, less<int> > > hms1;

  hms1.insert(12);

   hms1.insert(17);

   hms1.insert(24);

   hms1.insert(17);

   hms1.insert(9);

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

   hash_multiset<int, hash_compare<int, greater<int> > > hms2;

  hms2.insert(21);

   hms2.insert(34);

   hms2.insert(21);

   hms2.insert(17);

   // create a hash_multiset hms3 with the allocator of hash_multiset hms1

   hash_multiset <int>::allocator_type hms1_Alloc;

   hms1_Alloc = hms1.get_allocator();

   hash_multiset <int> hms3(less<int>(), hms1_Alloc);

  hms3.insert(71);

   hms3.insert(52);

   hms3.insert(31);

   // create a hash_multiset hms4 by copying the range hms1[_First, _Last)

   hash_multiset <int>::const_iterator hms1_PIter, hms1_QIter;

   hms1_PIter = hms1.begin();

   hms1_QIter = hms1.begin();

   hms1_QIter++;

   hms1_QIter++;

   hms1_QIter++;

   hash_multiset<int> hms4(hms1_PIter, hms1_QIter);

   // create a hash_multiset hms5 by copying the range hms2[_First, _Last) and with the allocator of hash_multiset hms2

   hash_multiset<int>::allocator_type hms2_Alloc;

   hms2_Alloc = hms2.get_allocator( );

   hash_multiset<int> hms5(hms2.begin(), ++hms2.begin(),less<int>(), hms2_Alloc);

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

   cout<<"Operation: hash_multiset <int> hms0\n";

   cout<<"hms0 data: ";

   for(hms0_Iter = hms0.begin(); hms0_Iter != hms0.end(); hms0_Iter++)

      cout<<*hms0_Iter<<" ";

   cout<<endl;

   cout<<"\nOperation1: hash_multiset<int, \n  hash_compare<int, less<int> > > hms1\n";

   cout<<"Operation2: hms1.insert(12)...\n";

   cout<<"hms1 data: ";

   for(hms1_Iter = hms1.begin(); hms1_Iter != hms1.end(); hms1_Iter++)

      cout<<*hms1_Iter<<" ";

   cout<<endl;

   cout<<"\nOperation1: hash_multiset<int, \n  hash_compare<int, greater<int> > > hms2\n";

   cout<<"Operation2: hms2.insert(21)...\n";

   cout<<"hms2 data: ";

   for(hms2_Iter = hms2.begin(); hms2_Iter != hms2.end(); hms2_Iter++)

      cout<<*hms2_Iter<<" ";

   cout<<endl;

   cout<<"\nOperation1: hash_multiset<int> hms3(less<int>(),hms1_Alloc)\n";

   cout<<"Operation2: hms3.insert(71)...\n";

   cout<<"hms3 data: ";

   for(hms3_Iter = hms3.begin(); hms3_Iter != hms3.end(); hms3_Iter++)

      cout<<*hms3_Iter<<" ";

   cout<<endl;

   cout<<"\nOperation: hash_multiset<int> hms4(hms1_PIter, hms1_QIter)\n";

   cout<<"hms4 data: ";

   for(hms4_Iter = hms4.begin(); hms4_Iter != hms4.end(); hms4_Iter++)

      cout<<*hms4_Iter<<" ";

   cout<<endl;

   cout<<"\nOperation: hash_multiset<int> hms5(hms2.begin(), \n ++hms2.begin(), less<int>(), hms2_Alloc)\n";

   cout<<"hms5 data: ";

   for(hms5_Iter = hms5.begin(); hms5_Iter != hms5.end(); hms5_Iter++)

      cout<<*hms5_Iter<<" ";

   cout<<endl;

   return 0;

}

 

Output:

29.8  Some C++ STL Container Classes Summary

• The following is a program example compiled usingg++ as an illustration.

// ******mapconstructor.cpp********

// map, constructor, compiled with g++ of Linux Fedora Core

#include <map>

#include <iostream>

using namespace std;

int main( )

{

   typedef pair<int, int> Int_Pair;

   map<int, int>::iterator mp0_Iter, mp1_Iter, mp3_Iter, mp4_Iter, mp5_Iter, mp6_Iter;

   map<int, int, greater<int> >::iterator mp2_Iter;

   // create an empty map mp0 of key type integer

   map <int, int> mp0;

   // create an empty map mp1 with the key comparison function of less than, then insert 6 elements

   map <int, int, less<int> > mp1;

   mp1.insert(Int_Pair(1, 13));

   mp1.insert(Int_Pair(3, 23));

   mp1.insert(Int_Pair(3, 31));

   mp1.insert(Int_Pair(2, 23));

   mp1.insert(Int_Pair(6, 15));

   mp1.insert(Int_Pair(9, 25));

   // create an empty map mp2 with the key comparison function of greater than, then insert 3 elements

   map <int, int, greater<int> > mp2;

   mp2.insert(Int_Pair(3, 12));

   mp2.insert(Int_Pair(1, 31));

   mp2.insert(Int_Pair(2, 21));

   // create a map mp3 with the allocator of map mp1

   map <int, int>::allocator_type mp1_Alloc;

   mp1_Alloc = mp1.get_allocator();

   map <int, int> mp3(less<int>(), mp1_Alloc);

   mp3.insert(Int_Pair(1, 10));

   mp3.insert(Int_Pair(2, 12));

   // create a copy, map mp4, of map mp1

   map <int, int> mp4(mp1);

   // create a map mp5 by copying the range mp1[_First, _Last)

   map <int, int>::const_iterator mp1_PIter, mp1_QIter;

   mp1_PIter = mp1.begin();

   mp1_QIter = mp1.begin();

   mp1_QIter++;

   mp1_QIter++;

   map <int, int> mp5(mp1_PIter, mp1_QIter);

   // create a map mp6 by copying the range mp4[_First, _Last) and with the allocator of map mp2

   map <int, int>::allocator_type mp2_Alloc;

   mp2_Alloc = mp2.get_allocator();

   map <int, int> mp6(mp4.begin(), ++mp4.begin(), less<int>(), mp2_Alloc);

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

   cout<<"Operation: map <int, int> mp0\n";

   cout<<"mp0 data: ";

   for(mp0_Iter = mp0.begin(); mp0_Iter != mp0.end(); mp0_Iter++)

      cout<<" "<<mp0_Iter->second;

   cout<<endl;

   cout<<"\nOperation1: map <int, int, less<int> > mp1\n";

   cout<<"Operation2: mp1.insert(Int_Pair(1, 13))...\n";

   cout<<"mp1 data: ";

   for(mp1_Iter = mp1.begin(); mp1_Iter != mp1.end(); mp1_Iter++)

      cout<<" "<<mp1_Iter->second;

   cout<<endl;

   cout<<"\nOperation1: map <int, int, greater<int> > mp2\n";

   cout<<"Operation2: mp2.insert(Int_Pair(3, 12))...\n";

   cout<<"mp2 data: ";

   for(mp2_Iter = mp2.begin(); mp2_Iter != mp2.end(); mp2_Iter++)

      cout<<" "<<mp2_Iter->second;

   cout<<endl;

   cout<<"\nOperation1:  map <int, int> mp3(less<int>(), mp1_Alloc)\n";

   cout<<"Operation2: mp3.insert(Int_Pair(1, 10))...\n";

   cout<<"mp3 data: ";

   for(mp3_Iter = mp3.begin(); mp3_Iter != mp3.end(); mp3_Iter++)

      cout<<" "<<mp3_Iter->second;

   cout<<endl;

   cout<<"\nOperation: map <int, int> mp4(mp1)\n";

     cout<<"mp4 data: ";

   for(mp4_Iter = mp4.begin(); mp4_Iter != mp4.end(); mp4_Iter++)

      cout<<" "<<mp4_Iter->second;

   cout<<endl;

   cout<<"\nOperation: map <int, int> mp5(mp1_PIter, mp1_QIter)\n";

   cout<<"mp5 data: ";

   for(mp5_Iter = mp5.begin(); mp5_Iter != mp5.end(); mp5_Iter++)

      cout<<" "<<mp5_Iter->second;

   cout<<endl;

   cout<<"\nOperation: map <int, int> mp6(mp4.begin(), \n++mp4.begin(), less<int>(), mp2_Alloc);\n";

   cout<<"mp6 data: ";

   for(mp6_Iter = mp6.begin(); mp6_Iter != mp6.end(); mp6_Iter++)

      cout<<" "<<mp6_Iter->second;

   cout<<endl;

   return 0;

}

[bodo@bakawali ~]$ g++ mapconstructor.cpp -o mapconstructor

[bodo@bakawali ~]$ ./mapconstructor

Operation: map <int, int> mp0

mp0 data:

Operation1: map <int, int, less<int> > mp1

Operation2: mp1.insert(Int_Pair(1, 13))...

mp1 data:  13 23 23 15 25

Operation1: map <int, int, greater<int> > mp2

Operation2: mp2.insert(Int_Pair(3, 12))...

mp2 data:  12 21 31

Operation1:  map <int, int> mp3(less<int>(), mp1_Alloc)

Operation2: mp3.insert(Int_Pair(1, 10))...

mp3 data:  10 12

Operation: map <int, int> mp4(mp1)

mp4 data:  13 23 23 15 25

Operation: map <int, int> mp5(mp1_PIter, mp1_QIter)

mp5 data:  13 23

Operation: map <int, int> mp6(mp4.begin(),

++mp4.begin(), less<int>(), mp2_Alloc);

mp6 data:  13

----------------------------End of container-----------------------

tenouk C++ STL tutorial

Further C++ STL container classes reading:

1. Source code is available inC++ STL Container source code.

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

3. Acomplete C Standard Library.

4. Acomplete C++ Standard Library documentation that includes STL.

|< C++ STL Container 10 | Main | C++ STL Container Adapter >|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