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

 

C++ STL containers abilities that should be acquired:

 

▪         Able to understand and use map associative container.

▪         Able to understand and use multimap associative container.

▪         Able to understand and use hash_map associative container.

▪         Able to understand and use hash_multimap associative container.

▪         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 page?

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: The binary tree of the map and multimap structure can be depicted as follow: 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

 

 

map Specialized Template Functions

 

 

map Classes

 

 

map Template Class Members

 

Typedefs

 

 

map Template Class Member Functions

 

 

map Template Class Operator

 

multimap Class

• The STL map class is used for the storage and retrieval of data from a collection in which the each element is a pair that has both a data value and a sort key.

• The value of the key is unique and is used to order the data is automatically.  The value of an element in a map, but not its associated key value, may be changed directly.  Instead, key values associated with old elements must be deleted and new key values associated with new elements inserted.

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

 

Parameters

 

• The STL map class is:

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:

 

------------------------------------------------------------------------------------------------------

 

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

---www.tenouk.com---

 

 

29.3  multimap

• A multimap is the same as a map except that duplicates are allowed.  Thus, a multimap may contain multiple elements that have the same key.  A multimap can also be used as dictionary.  It can be depicted as follows:

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

• The multimap 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 (key, value) pairs are stored in a multimap as objects of type pair.  The pair class requires the header <utility>, which is automatically included by <map>.

 

29.4  multimap Members

 

Typedefs

 

 

Member Functions