CodeCogs

Map and multimap containers are containers that manage key/value pairs as elements.

Definition

The multimap template is defined in the standard header <map>, and in the nonstandard backward-compatibility header <multimap.h>.

#include <map>
namespace std{
       template < class Key, class T,
                 class Compare = less<Key>,
                 class Allocator = allocator<pair<const Key,T> > >
       class multimap;
}

Description

Multimap container, just like map container manage key/value pairs as elements.

The difference between the two is that a multimap allows different elements to have the same key value. (Because there is no limit on the number of elements with the same key multimap is also a Multiple Associative Container.)

Another difference between the two is that multimap does not support the brackets operator ([]) for element access, since there might be several different keys with the same value.

A short example declaring a map is:

map<string, integer> aMap; // associates strings with integer

Performance

Multimap have the important property that gives fast access to stored values of type T that are indexed by keys of type Key. The default operation for key comparison is the < operator.

Multimap supports bidirectional iterators that point to an instance of pair <const Key x, T y> where x is the key and y is the stored value associated with that key. The definition of multimap refers to a typedef to this pair called value_type.

Multimap Operations

Create, Copy, and Destroy Operations

Operation	Effect
map mm	Creates an empty multimap without any elements
map mm(op)	Creates an empty multimap that uses `op` as the sorting criterion
map mm1(mm2)	Creates a copy of another multimap of the same type (all elements are copied)
map mm(beg,end)	Creates a multimap initialized by the elements of the range [beg,end)
map mm(beg,end,op)	Creates a multimap with the sorting criterion op initialized by the elements of the range [beg,end)
mm.~map()	Destroys all elements and frees the memory

Multimap	Effect
multimap<Key,el>	A multimap that sorts keys with `less<>` (operator `<`)
multimap<Key,el,op>	A multimap that sorts keys with op

Nonmodifying Operations of Multimaps

Operation	Effect
mm.size()	Returns the actual number of elements
mm.empty()	Returns if the container is empty
mm.max_size()	Returns the maximum number of elements possible
mm1==mm2	Returns if mm1 is equal to mm2
mm1!=mm2	Returns if mm1 is not equal to mm2 (equivalent to !(mm1==mm2))
mm1<mm2	Returns if mm1 is less than mm2
mm1>mm2	Returns if mm1 is greater than mm2
mm1<=mm2	Returns if mm1 is less than or equal to mm2 (equivalent to !(mm2<mm1))
mm1>=mm2	Returns if mm1 is greater than or equal to mm2 (equivalent to !(mm1<mm2))

Special Search Operations of Multimaps

Operation	Effect
count(key)	Returns the number of elements with key key
find(key)	Returns the position of the first element with key key or end()
lower_bound(key)	Returns the first position where an element with key key would get inserted (the first element with key >= key)
upper_bound(key)	Returns the last position where an element with key key would get inserted (the first element with key > key)
equal_range(key)	Returns the first and last positions where elements with key key would get inserted (the range of elements with key == key)

Assignment Operations of Maps

Operation	Effect
mm1=mm2	Assigns all elements of mm2 to mm1
mm1.swap(mm2)	Swaps the data of mm1 and mm2
swap(c1,c2)	Same (as global function)

Iterator Operations of Multimaps

Operation	Effect
mm.begin()	Returns a bidirectional iterator for the first element (keys are considered `const)`
mm.end()	Returns a bidirectional iterator for the position after the last element (keys are considered `const)`
mm.rbegin()	Returns a reverse iterator for the first element of a reverse iteration
mm.rend()	Returns a reverse iterator for the position after the last element of a reverse iteration

Inserting and Removing Elements of Maps

Operation	Effect
mm.insert(el)	Inserts a copy of el and returns the position of the new element and, for maps, if it succeeded
mm.insert(pos,el)	Inserts a copy of el and returns the position of the new element (pos is used as a hint pointing to where the insert should start the search)
mm.insert(beg,end)	Inserts a copy of all elements of the range [beg,end) (returns nothing)
mm.erase(el)	Removes all elements with value el and returns the number of removed elements
mm.erase(pos)	Removes the element at iterator position pos (returns nothing)
mm.erase(beg,end)	Removes all elements of the range [beg,end) (returns nothing)
mm.clear()	Removes all elements

References

http://stdcxx.apache.org
http://www.sgi.com
Nicolai M. Josuttis: "The C++ Standard Library"

Example 1

Problem

This example of program illustrates how to count keys in a multimap.

Workings

#include <iostream>
using std::cout;
using std::endl;

#include <map>

int main()
{
  std::multimap< int,double,std::less<int> > pairs; // declare the multimap pairs

  cout <<"Now, there are"<<pairs.count(6)<<"pairs with key 15 in the multimap\n";

   // insert three value_type objects in pairs
   pairs.insert(std::multimap< int,double,std::less<int> >::
value_type(6, 1.1));
   pairs.insert(std::multimap< int,double,std::less<int> >::
value_type(6, 23.1));
  pairs.insert(std::multimap< int,double,std::less<int> >::
value_type(6, 4.5));
  pairs.insert(std::multimap< int,double,std::less<int> >::
value_type(6, 55.5));

   cout <<"After inserts,there are "<<pairs.count(6)<<" pairs with key 6\n";

   cout <<endl;
   return 0;
}

Solution

Output:

Now, there are 0 pairs with key 6 in the multimap
After inserts, there are 4 pairs with key 6

References

http://www.java2s.com

Example 2

Problem

This program creates a map of months and the number of days in the month.

Workings

#include <iostream>
#include <map>
#include <string>


typedef std::multimap<int, std::string, std::less<int>,
                      std::allocator<std::pair<const int, 
                                               std::string> > >
        months_type;

inline std::ostream&
operator<< (std::ostream &out, const months_type &mm)
{
    for (months_type::const_iterator it = mm.begin (); 
         it != mm.end (); ++it)
        std::cout << (*it).second << " has " << (*it).first << " days\n";

    return out;
}

int main ()
{

    typedef months_type::value_type value_type;

    // put the months in the multimap with the number of days as the not necessarily unique key
    months.insert (value_type (31, std::string ("January")));
    months.insert (value_type (28, std::string ("February")));
    months.insert (value_type (31, std::string ("March")));
    months.insert (value_type (30, std::string ("April")));
    months.insert (value_type (31, std::string ("May")));
    months.insert (value_type (30, std::string ("June")));
    months.insert (value_type (31, std::string ("July")));
    months.insert (value_type (31, std::string ("August")));
    months.insert (value_type (30, std::string ("September")));
    months.insert (value_type (31, std::string ("October")));
    months.insert (value_type (30, std::string ("November")));
    months.insert (value_type (31, std::string ("December")));

    // print out the months
    std::cout << "Months of the year:\n" << months << std::endl;

    // find all months with 30 days
    std::pair<months_type::iterator, months_type::iterator> pr 
            = months.equal_range (30);

    // print out the 30 day months
    std::cout << "\nMonths with 30 days\n";

    for ( ; pr.first != pr.second; ++pr.first)
        std::cout << (*pr.first).second << '\n';

    return 0;
}

Solution

Output:

Months of the year:
February has 28 days
April has 30 days
June has 30 days
September has 30 days
November has 30 days
January has 31 days
March has 31 days
May has 31 days
July has 31 days
August has 31 days
October has 31 days
December has 31 days

Months with 30 days
April
June
September
November

References

http://stdcxx.apache.org

Example 3

Problem

This program illustrates a phone book in which a person may have more than one phone number.

Workings

#include <iostream>
#include <map>
#include <string>

using namespace std;

// the "key" class for the key/value pairs.
class Name
{
  public:
      Name()         { nameString = ""; }
      Name(string s) { nameString = s; }
      string getName() const { return nameString; }
  private:
      string nameString;
};

// define operator< for Name objects
bool operator<(Name name1, Name name2)
{
  return name1.getName() < name2.getName();
}

// this is the "value" class for the key/value pairs

class PhoneNumber
{
  public:
      PhoneNumber()         { numberString = ""; }
      PhoneNumber(string s) { numberString = s; }
      string getNumber() const { return numberString; }
  private:
      string numberString;
};


int main()
{
  multimap<Name, PhoneNumber> directory;
  directory.insert(pair<Name, PhoneNumber>
    (Name("X"), PhoneNumber("444-3422")));

  directory.insert(pair<Name, PhoneNumber>
    (Name("X"), PhoneNumber("444-1111")));

  directory.insert(pair<Name, PhoneNumber>
    (Name("Y"), PhoneNumber("333-3649")));
 
  directory.insert(pair<Name, PhoneNumber>
    (Name("Z"), PhoneNumber("333-0404")));

  directory.insert(pair<Name, PhoneNumber>
    (Name("Z"), PhoneNumber("333-3764")));

  directory.insert(pair<Name, PhoneNumber>
    (Name("Z"), PhoneNumber("333-6385")));

  cout<<"The names and numbers in the phone book are: \n";
  multimap<Name, PhoneNumber>::iterator it1 = directory.begin();

  while(it1!=directory.end())
  {
     cout<<it1->first.getName()<<" "<<it1->second.getNumber()<< endl;
     ++it1;
  }

  string name;
  cout << "\nEnter a name: ";
  cin >> name;  cin.ignore(80, '\n');
  multimap<Name, PhoneNumber>::iterator it2;
  it2 = directory.find(name);
  if (it2!=directory.end())
  {
    do
      {
        cout<<"Phone number: "<<it2->second.getNumber()<<endl;
        it2++;
      }while (it2 != directory.upper_bound(name));
  }
  else
   cout<<"Not find!\n";

  return 0;
}

Solution

Output:

The names and numbers in the phone book are:
X 444-3422
X 444-1111
Y 333-3649
Z 444-6385
Z 333-0404
Z 333-0404

Enter a name: Z
Phone number: 333-0404
Phone number: 333-3764
Phone number: 333-6385

References

http://www.smu.ca/academic/science/compsci