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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

My Training Period:        xx 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_multiset Members- typedefs & member functions

  2. hash_multiset Class

  3. hash_multiset Constructor

  4. hash_multiset, constructor program example

  5. Strings

  6. Ordinary Arrays

  7. C++ STL Container Classes Summary

  8. map, constructor program example compiled with g++

 

29.5.4  hash_multiset 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_reverse_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.

 

Table 29.28

 

 

Member Functions

 

Member function

Description

begin()

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

end()

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

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.

erase()

Removes an element or a range of elements in a hash_multiset from specified positions or removes elements that match a specified key.

find()

Returns an iterator addressing the location of an element in a hash_multiset that has a key equivalent to a specified key.

get_allocator()

Returns a copy of the allocator object used to construct the hash_multiset.

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.

insert()

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

max_size()

Returns the maximum length of the hash_multiset.

rbegin()

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

rend()

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

size()

Returns the number of elements in the hash_multiset.

swap()

Exchanges the elements of two hash_multisets.

upper_bound()

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

 

Table 29.29

 

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

 

Table 29.30

  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.

hash_multiset Constructor

// 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:

C++ STL Associative container hash_multiset constructor

 

29.6  Strings

  • You can also use strings as STL containers. By strings that mean objects of the C++ string classes, basic_string<>, string, and wstring. Strings are similar to vectors except that their elements are characters.  This has been discussed extensively in Module 25 and 26.

29.7  Ordinary Arrays

  • An ordinary C and C++ language array type that has static or dynamic size is a container.  However, ordinary arrays are not STL containers because they don't provide member functions such as size() and empty().

  • However, the STL's design allows you to call algorithms for these ordinary arrays.  This is especially useful when you process static arrays of values as an initializer list.

  • You should have familiar with this traditional array, what is new in STL is using algorithms for them.

  • Note that in C++ it is no longer necessary to program dynamic arrays directly. Vectors provide all properties of dynamic arrays with a safer and more convenient interface.

 

29.8  Some C++ STL Container Classes Summary

 

No

Sequences container

Summary

1

vector

A sequence that supports random access to elements, constant time insertion and removal of elements at the end, and linear time insertion and removal of elements at the beginning or in the middle. The number of elements in a vector may vary dynamically; memory management is automatic.  vector is the simplest of the STL container classes, and in many cases the most efficient.

2

deque

Like a vector with extra features that deque does not have any member functions analogous to vector's capacity() and reserve(), and does not provide any of the guarantees on iterator validity that are associated with those member functions.

The Standard Template Library (STL) sequence container deque arranges elements of a given type in a linear arrangement and, like vectors, allow fast random access to any element and efficient insertion and deletion at the back of the container. However, unlike a vector, the deque class also supports efficient insertion and deletion at the front of the container.

4

list

A doubly linked list. It is a sequence that supports both forward and backward traversal, and (amortized) constant time insertion and removal of elements at the beginning or the end, or in the middle. Lists have the important property that insertion and splicing do not invalidate iterators to list elements, and that even removal invalidates only the iterators that point to the elements that are removed. The ordering of iterators may be changed (that is, list<Type>::iterator might have a different predecessor or successor after a list operation than it did before), but the iterators themselves will not be invalidated or made to point to different elements unless that invalidation or mutation is explicit.

 

Associative container

Summary

6

set

A sorted associative container that stores objects of type Key. Set is a simple associative container, meaning that its value type, as well as its key type, is Key. It is also a unique associative container, meaning that no two elements are the same.  The set algorithms require their arguments to be sorted ranges, and, since set and multiset are sorted associative containers, their elements are always sorted in ascending order.  The output range of these algorithms is always sorted, and inserting a sorted range into a set or multiset is a fast operation: the unique sorted associative container and multiple sorted associative container requirements guarantee that inserting a range takes only linear time if the range is already sorted. Set has the important property that inserting a new element into a set does not invalidate iterators that point to existing elements. Erasing an element from a set also does not invalidate any iterators, except, of course, for iterators that actually point to the element that is being erased.

7

multiset

Multiset is a sorted associative container that stores objects of type Key. Multiset is a simple associative container, meaning that its value type, as well as its key type, is Key. It is also a multiple associative container, meaning that two or more elements may be identical. The set algorithms require their arguments to be sorted ranges, and, since set and multiset are sorted associative containers, their elements are always sorted in ascending order. The output range of these algorithms is always sorted, and inserting a sorted range into a set or multiset is a fast operation: the unique sorted associative container and multiple sorted associative container requirements guarantee that inserting a range takes only linear time if the range is already sorted. Multiset has the important property that inserting a new element into a multiset does not invalidate iterators that point to existing elements. Erasing an element from a multiset also does not invalidate any iterators, except, of course, for iterators that actually point to the element that is being erased.

8

map

Map is a sorted associative container that associates objects of type Key with objects of type Data. Map is a pair associative container, meaning that its value type is pair<const Key, Data>. It is also a unique associative container, meaning that no two elements have the same key.

Map has the important property that inserting a new element into a map does not invalidate iterators that point to existing elements. Erasing an element from a map also does not invalidate any iterators, except, of course, for iterators that actually point to the element that is being erased.

9

multimap

Multimap is a sorted associative container that associates objects of type Key with objects of type Data. multimap is a pair associative container, meaning that its value type is pair<const Key, Data>. It is also a multiple associative container, meaning that there is no limit on the number of elements with the same key.

Multimap has the important property that inserting a new element into a multimap does not invalidate iterators that point to existing elements. Erasing an element from a multimap also does not invalidate any iterators, except, of course, for iterators that actually point to the element that is being erased.

Implementation dependent, non ANSI C++ (ISO/IEC C++)

10

hash

The function object hash<Type> is a Hash Function; it is used as the default hash function by all of the Hashed Associative Containers that are included in the STL.   The hash<Type> template is only defined for template arguments of type char*, const char*, crope, wrope, and the built-in integral types.  If you need a Hash Function with a different argument type, you must either provide your own template specialization or else use a different Hash Function.  This is implementation extension, not the ANSI C++ standard.

11

hash_set

Hash_set is a hashed associative container that stores objects of type Key. Hash_set is a simple associative container, meaning that its value type, as well as its key type, is Key. It is also a unique associative container, meaning that no two elements compare equal using the binary predicate EqualKey.

Hash_set is useful in applications where it is important to be able to search for an element quickly. If it is important for the elements to be in a particular order, however, then set is more appropriate.

12

hash_multiset

hash_multiset is a hashed associative container that stores objects of type Key. hash_multiset is a simple associative container, meaning that its value type, as well as its key type, is Key. It is also a multiple associative container, meaning that two or more elements may compare equal using the binary predicate EqualKey.

hash_multiset is useful in applications where it is important to be able to search for an element quickly. If it is important for the elements to be in a particular order, however, then multiset is more appropriate.

13

hash_map

Hash_map is a hashed associative container that associates objects of type Key with objects of type Data. Hash_map is a pair associative container, meaning that its value type is pair<const Key, Data>. It is also a unique associative container, meaning that no two elements have keys that compare equal using EqualKey.

Looking up an element in a hash_map by its key is efficient, so hash_map is useful for "dictionaries" where the order of elements is irrelevant. If it is important for the elements to be in a particular order, however, then map is more appropriate.

14

hash_multimap

Hash_multimap is a hashed associative container that associates objects of type Key with objects of type Data. Hash_multimap is a pair associative container, meaning that its value type is pair<const Key, Data>. It is also a multiple associative container, meaning that there is no limit on the number of elements whose keys may compare equal using EqualKey.

Looking up an element in a hash_multimap by its key is efficient, so hash_multimap is useful for "dictionaries" where the order of elements is irrelevant. If it is important for the elements to be in a particular order, however, then multimap is more appropriate.

 

Table 29.31

// ******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 in C++ STL Container source code.

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

 

 

 

 

 

 

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