|< 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 usingVC++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 inC++ STL Container source code.

The C++ STL containers programming skills that should be acquired for this session:

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

// 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() andmultimap() 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 functionkey_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

multimap Class

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

• The STL multimap class is used for the storage and retrieval of data from a collection in which each element is a pair that has both a data value and a sort key. The value of the key does not need to be unique and is used to order the data automatically.

• The value of an element in a multimap, 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 multimap 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. 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

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

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

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

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

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

tenouk C++ STL tutorial

Further C++ container related 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 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