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


 

 

 

 

MODULE 29

THE C++ STL CONTAINER PART 8

map, multimap, hash_map, hash_multimap, hash_set, hash_multiset

 

 

 

 

 

My Training Period: xx hours

 

More program examples on 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. Linux 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 skills that should be acquired for this session:

 

 

What do we have in this session?

  1. map

  2. <map> Header Members – operators, specialized template function & classes

  3. map Template Class Members – typedef, member function & operator

  4. multimap Class

  5. map Constructor

  6. map, constructor program example

  7. Multimap

  8. multimap Members – typedef & member function

  9. multimap Class

  10. multimap Constructor

  11. multimap, constructor or ctor program example

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

29.1  map

  • A map contains elements that are key and value pairs. Each element has a key that is the basis for the sorting criterion and a value.

  • Each key may occur only once, thus duplicate keys are not allowed.

  • A map can also be used as an associative array, which is an array that has an arbitrary index type.  It can be depicted as follow:

C++ STL associative container map

  • The binary tree of the map and multimap structure can be depicted as follow:

C++ STL associative container binary tree of map

  • The iterator provided by the map class is a bidirectional iterator, but the class member functions insert() and map() 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.

  • The different iterator concepts form a family related by refinements in their functionality.  Each iterator concept has its own set of requirements and the algorithms that work with them must limit their assumptions to the requirements provided by that type of iterator.

  • This type of structure is an ordered list of uniquely occurring key words with associated string values. If, instead, the words had more than one correct definition, so that keys were not unique, then a multimap would be the container of choice.

  • If, on the other hand, just the list of words were being stored, then a set would be the correct container. If multiple occurrences of the words were allowed, then a multiset would be the appropriate container structure.

  • The map orders the sequence it controls by calling a stored function object of type key_compare. This stored object is a comparison function that may be accessed by calling the member function key_comp().

  • The general format of the map and multimap operation is shown in the following Table.

Map

Operation

map<Key, Element>

A map that sorts keys with default, less<>(operator <).

map<Key, Element, Operator>

A map that sorts keys with Operator.

multimap<Key, Element>

A multimap that sorts keys with less<>(operator <).

multimap<Key, Element, Operator>

A multimap that sorts keys with Operator.

 

Table 29.1

 

29.2  <map> Header Members

 

map Operators

 

Operators

Description

operator!=

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

operator<

Tests if the map or multimap object on the left side of the operator is less than the map or multimap object on the right side.

operator<=

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

operator==

Tests if the map or multimap object on the left side of the operator is equal to the map or multimap object on the right side.

operator>

Tests if the map or multimap object on the left side of the operator is greater than the map or multimap object on the right side.

operator>=

Tests if the map or multimap object on the left side of the operator is greater than or equal to the map or multimap object on the right side.

 

Table 29.2

 

map Specialized Template Functions

 

Specialized template function

Description

swap()

Exchanges the elements of two maps or multimaps.

 

Table 29.3

 

map Classes

 

Class

Description

value_compare

Provides a function object that can compare the elements of a map by comparing the values of their keys to determine their relative order in the map.

map

Used for the storage and retrieval of data from a collection in which the each of the elements has a unique key with which the data is automatically ordered.

multimap

Used for the storage and retrieval of data from a collection in which the each of the elements has a key with which the data is automatically ordered and the keys do not need to have unique values.

 

Table 29.4

 

map Template Class Members

 

Typedefs

 

Template Class Member

Description

allocator_type

A type that represents the allocator class for the map object.

const_iterator

A type that provides a bidirectional iterator that can read a const element in the map.

const_pointer

A type that provides a pointer to a const element in a map.

const_reference

A type that provides a reference to a const element stored in a 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 map.

difference_type

A signed integer type that can be used to represent the number of elements of a 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 a 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 map.

key_type

A type that describes the sort key object which constitutes each element of the map.

mapped_type

A type that represents the data type stored in a map.

pointer

A type that provides a pointer to a const element in a map.

reference

A type that provides a reference to an element stored in a map.

reverse_iterator

A type that provides a bidirectional iterator that can read or modify an element in a reversed map.

size_type

An unsigned integer type that can represent the number of elements in a 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 map.

 

Table 29.5

 

map Template Class Member Functions

 

Template class member function

Description

begin()

Returns an iterator addressing the first element in the map.

clear()

Erases all the elements of a map.

count()

Returns the number of elements in a map whose key matches a parameter-specified key.

empty()

Tests if a map is empty.

end()

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

equal_range()

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

erase()

Removes an element or a range of elements in a map from specified positions

find()

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

get_allocator()

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

insert()

Inserts an element or a range of elements into the map at a specified position.

key_comp()

Retrieves a copy of the comparison object used to order keys in a map.

lower_bound()

Returns an iterator to the first element in a map that with a key value that is equal to or greater than that of a specified key.

map()

map constructor, 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 map.

max_size()

Returns the maximum length of the map.

rbegin()

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

rend()

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

size()

Specifies a new size for a map.

swap()

Exchanges the elements of two maps.

upper_bound()

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

 

Table 29.6

 

map Template Class Operator

 

Operator

Description

operator[ ]

Inserts an element into a map with a specified key value.

 

Table 29.7

multimap Class

template < class Key, class Type, class Traits = less<Key>, class Allocator = allocator<pair <const Key, Type> > >

 

Parameters

 

Parameter

Description

Key

The key data type to be stored in the map.

Type

The element data type to be stored in the map.

Traits

The type that provides a function object that can compare two element values as sort keys to determine their relative order in the map. This argument is optional and the binary predicate less<Key> is the default value.

Allocator

The type that represents the stored allocator object that encapsulates details about the map's allocation and de-allocation of memory. This argument is optional and the default value is allocator<pair <const Key, Type> >.

 

Table 29.8

  1. An associative container, which a variable size container that supports the efficient retrieval of element values based on an associated key value.

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

  3. Sorted, because its elements are ordered by key values within the container in accordance with a specified comparison function.

  4. Unique in the sense that each of its elements must have a unique key.

  5. A pair associative container, because its element data values are distinct from its key values.

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

map Constructor

 

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

  • All constructors store a type of allocator object that manages memory storage for the map and that can later be returned by calling get_allocator().  The allocator parameter is often omitted in the class declarations and preprocessing macros used to substitute alternative allocators.

  • All constructors initialize their map.

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

  • The first three constructors specify an empty initial map, 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 map _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 and allocator.

 

// map, constructor, compiled with VC++ 7.0 or .Net

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

}

 

Output:

 

C++ STL associative container map constructor

 

-----------------------------------------------------End of map------------------------------------------------

---www.tenouk.com---

 

 

29.3  multimap

C++ STL Associative container multimap

 

29.4  multimap Members

 

Typedefs

 

Typedef

Description

allocator_type

A type that represents the allocator class for the multimap object.

const_iterator

A type that provides a bidirectional iterator that can read a const element in the multimap.

const_pointer

A type that provides a pointer to a const element in a multimap.

const_reference

A type that provides a reference to a const element stored in a 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 multimap.

difference_type

A signed integer type that can be used to represent the number of elements of a multimap in a range between elements pointed to by iterators.

iterator

A type that provides the difference between two iterators those refer to elements within the same 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 multimap.

key_type

A type that describes the sort key object that constitutes each element of the multimap.

mapped_type

A type that represents the data type stored in a multimap.

pointer

A type that provides a pointer to a const element in a multimap.

reference

A type that provides a reference to an element stored in a multimap.

reverse_iterator

A type that provides a bidirectional iterator that can read or modify an element in a reversed multimap.

size_type

An unsigned integer type that provides a pointer to a const element in a 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 multimap

 

Table 29.9

 

Member Functions

 

Member function

Description

begin()

Returns an iterator addressing the first element in the multimap.

clear()

Erases all the elements of a multimap.

count()

Returns the number of elements in a multimap whose key matches a parameter-specified key.

empty()

Tests if a multimap is empty.

end()

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

equal_range()

Returns a pair of iterators respectively to the first element in a multimap with a key that is greater than a specified key and to the first element in the multimap with a key that is equal to or greater than the key.

erase()

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

find()

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

get_allocator()

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

insert()

Inserts an element or a range of elements into a multimap.

key_comp()

Retrieves a copy of the comparison object used to order keys in a multimap.

lower_bound()

Returns an iterator to the first element in a multimap that with a key that is equal to or greater than a specified key.

max_size()

Returns the maximum length of the multimap.

multimap()

multimap constructor constructs a multimap that is empty or that is a copy of all or part of some other multimap.

rbegin()

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

rend()

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

size()

Returns the number of elements in the multimap.

swap()

Exchanges the elements of two multimaps.

upper_bound()

Returns an iterator to the first element in a multimap that with a key that is greater than a specified key.

value_comp()

The member function returns a function object that determines the order of elements in a multimap by comparing their key values.

 

Table 29.10

 

multimap Class

template < class Key, class Type, class Traits=less<Key>, class Allocator=allocator<pair <const Key, Type> > >

 

 

Parameters

 

Parameter

Description

Key

The key data type to be stored in the multimap.

Type

The element data type to be stored in the multimap.

Traits

The type that provides a function object that can compare two element values as sort keys to determine their relative order in the multimap. The binary predicate less<Key> is the default value.

Allocator

The type that represents the stored allocator object that encapsulates details about the map's allocation and de-allocation of memory. This argument is optional and the default value is allocator<pair <const Key, Type> >.

 

Table 29.11

  1. An associative container, which a variable size container that supports the efficient retrieval of element values based on an associated key value.

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

  3. Sorted, because its elements are ordered by key values within the container in accordance with a specified comparison function.

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

  5. A pair associative container, because its element data values are distinct from its key values.

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

multimap Constructor

// multimap, constructor or ctor compiled with VC++ 7.0 or .Net

// notice the duplicate key and data element

#include <map>

#include <iostream>

using namespace std;

 

int main()

{

   typedef pair<int, int> Int_Pair;

   multimap<int, int>::iterator mmp0Iter, mmp1Iter, mmp3Iter, mmp4Iter, mmp5Iter, mmp6Iter;

   multimap<int, int, greater<int> >::iterator mmp2Iter;

   // create an empty multimap mmp0 of key type integer

   multimap <int, int> mmp0;

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

   multimap<int, int, less<int> > mmp1;

   mmp1.insert(Int_Pair(2, 2));

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

   mmp1.insert(Int_Pair(1, 5));

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

   mmp1.insert(Int_Pair(5, 32));

   mmp1.insert(Int_Pair(4, 21));

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

   multimap <int, int, greater<int> > mmp2;

   mmp2.insert(Int_Pair(1, 11));

   mmp2.insert(Int_Pair(2, 10));

   mmp2.insert(Int_Pair(2, 11));

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

   // create a multimap mmp3 with the allocator of multimap mmp1

   multimap <int, int>::allocator_type mmp1_Alloc;

   mmp1_Alloc = mmp1.get_allocator();

   multimap <int, int> mmp3(less<int>(), mmp1_Alloc);

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

   mmp3.insert(Int_Pair(1, 21));

   // multimap mmp4, a copy of multimap mmp1

   multimap <int, int> mmp4(mmp1);

   // create a multimap mmp5 by copying the range mmp1[_First, _Last)

   multimap <int, int>::const_iterator mmp1_PIter, mmp1_QIter;

   mmp1_PIter = mmp1.begin();

   mmp1_QIter = mmp1.begin();

   mmp1_QIter++;

   mmp1_QIter++;

   multimap <int, int> mmp5(mmp1_PIter, mmp1_QIter);

   // create a multimap mmp6 by copying the range mmp4[_First, _Last) and with the allocator of multimap mmp2

   multimap <int, int>::allocator_type mmp2_Alloc;

   mmp2_Alloc = mmp2.get_allocator();

   multimap <int, int> mmp6(mmp4.begin(), ++mmp4.begin(), less<int>(), mmp2_Alloc);

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

   cout<<"Operation: multimap <int, int> mmp0\n";

   cout<<"mmp0 data: ";

   for(mmp0Iter = mmp0.begin(); mmp0Iter != mmp0.end(); mmp0Iter++)

      cout<<" "<<mmp0Iter->second;

   cout<<endl;

   cout<<"\nOperation1: multimap<int, int, less<int> > mmp1\n";

   cout<<"Operation2: mmp1.insert(Int_Pair(2, 2))...\n";

   cout<<"mmp1 data: ";

   for(mmp1Iter = mmp1.begin(); mmp1Iter != mmp1.end(); mmp1Iter++)

      cout<<" "<<mmp1Iter->second;

   cout<<endl;

   cout<<"\nOperation1: multimap <int, int, greater<int> > mmp2\n";

   cout<<"Operation2:  mmp2.insert(Int_Pair(1, 11))...\n";

   cout<<"mmp2 data: ";

   for(mmp2Iter = mmp2.begin(); mmp2Iter != mmp2.end(); mmp2Iter++)

      cout<<" "<<mmp2Iter->second;

   cout<<endl;

   cout<<"\nOperation1: multimap <int, int> mmp3(less<int>(), mmp1_Alloc)\n";

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

   cout<<"mmp3 data: ";

   for(mmp3Iter = mmp3.begin(); mmp3Iter != mmp3.end(); mmp3Iter++)

      cout<<" "<<mmp3Iter->second;

   cout<<endl;

   cout<<"\nOperation: multimap <int, int> mmp4(mmp1)\n";

   cout<<"mmp4 data: ";

   for(mmp4Iter = mmp4.begin(); mmp4Iter != mmp4.end(); mmp4Iter++)

      cout<<" "<<mmp4Iter->second;

   cout << endl;

   cout<<"\nOperation: multimap <int, int> mmp5(mmp1_PIter, mmp1_QIter)\n";

   cout<<"mmp5 data: ";

   for(mmp5Iter = mmp5.begin(); mmp5Iter != mmp5.end(); mmp5Iter++)

      cout<<" "<<mmp5Iter->second;

   cout<<endl;

   cout<<"\nOperation: multimap <int, int> mmp6(mmp4.begin(), \n++mmp4.begin(), less<int>(), mmp2_Alloc)\n";

   cout<<"mmp6 data: ";

   for(mmp6Iter = mmp6.begin(); mmp6Iter != mmp6.end(); mmp6Iter++)

      cout<<" "<<mmp6Iter->second;

   cout<<endl;

       return 0;

}

 

Output:

 

C++ STL Associative container multimap constructor/ctor

 

tenouk C++ STL tutorial

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Further C++ container related 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 7 | Main | C++ STL Container 9 >| 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