multimap

Overview

The standard library provides multimap, a lookup table  to store key value pairs that can have duplicate keys.

Details

multimap is basically a lookup table of duplicate keys associated with a value that can be used to search and retrieve elements. Sorting is done by the Compare function provided in the template. 

Syntax

The syntax is as below. Template parameter T represents the datatype to store, Compare represents comparison function to compare elements and Alloc represents the allocator used for storage.

template <class Key, class Value, class Compare, class Alloc = allocator<Key> > 
class multimap;

Members

 It defines following types

Name	Description
key_type	The first template parameter (Key)
mapped_type	The second template parameter (Value)
value_type	pair<key_type,mapped_type>
key_compare	The third template parameter (Compare)
value_compare	map::value_compare  function object
allocator_type	The third template parameter (Alloc)
reference	value_type&
const_reference	const value_type&
pointer	allocator_traits<allocator_type>::pointer
const_pointer	allocator_traits<allocator_type>::const_pointer
iterator	a bidirectional iterator to value_type convertible to const_iterator
const_iterator	a bidirectional iterator to const value_type
reverse_iterator	reverse_iterator<iterator>
const_reverse_iterator	reverse_iterator<const_iterator>
difference_type	a signed integral type
size_type	an unsigned integral type

Operation

multimap can be graphically represented as below. It's basically a AVL tree. It holds value pairs [{1,100},{2,200}, {3,300},{4,400},{5,500},{3,350}].

New elements can be added or removed or searched in the multimap. The default comparison function is less.

Complexity

The cost of Insertion or removal or search is O(Log(n)).

Functionality

Constructors

In following constructors use default allocator. Custom compare operations can be supplied. Custom allocators can be used by passing them as an additional argument. 

Name	Description
multimap ()	Default Constructor. Example: //v:{} multimap<int,int> v;
multimap (InputIterator first, InputIterator last)	Constructs a set and copies the elements in the range. Example: pair<int,int> a[]{{1,100},{2,200},{3,300},{4,400},{5,500},{3,350}}; //v:{{1,100},{2,200},{3,300},{3,350},{4,400},{5,500}} multimap<int,int> v(begin(a),end(a));
multimap (const multimap & x)	copy constructor.
multimap (multimap && x)	move constructor.
multimap (initializer_list<value_type> il)	initializer_list constructor. Example: //v:{{1,100},{2,200}, {3,300},{3,350},{4,400},{5,500}} multimap<int,int> v({{1,100},{2,200}, {3,300},{4,400},{5,500},{3,350}});

Iterator

Name	Description
iterator begin() iterator end()	Returns iterator to beginning and end of the multimap . Example: template<typename T, typename U> ostream& operator << (ostream& os, const pair<T,U>& val) { os << "[" << val.first << "," << val.second << "]"; return os; } multimap<int,int> v{{1,100},{2,200}, {3,300},{3,350},{4,400},{5,500}}; //prints [1,100] [2,200] [3,300] [3,350] [4,400] [5,500] for (auto itr=v.begin(); itr!=v.end(); ++itr) cout << *itr << ' ';
reverse_iterator  rbegin() reverse_iterator  rend()	Returns reverse_iterator   to reverse beginning and reverse end of the multimap. Example: multimap<int,int> v{{1,100},{2,200}, {3,300},{3,350},{4,400},{5,500}}; //prints [1,100] [2,200] [3,300] [3,350] [4,400] [5,500] for (auto itr=v.cbegin(); itr!=v.cend(); ++itr) cout << *itr << ' ';
const_iterator cbegin() const_iterator cend()	Returns const_iterator to beginning and end of the multimap. Example: multimap<int,int> v{{1,100},{2,200}, {3,300},{3,350},{4,400},{5,500}}; //prints [5,500] [4,400] [3,350] [3,300] [2,200] [1,100] for (auto itr=v.crbegin(); itr!=v.crend(); ++itr) cout << *itr << ' ';
const_reverse_iterator crbegin() const_reverse_iterator crend()	Return const_reverse_iterator to reverse beginning and reverse end of the multimap. Example: multimap<int,int> v{{1,100},{2,200}, {3,300},{3,350},{4,400},{{5,500}}; //prints [5,500] [4,400] [3,350] [3,300] [2,200] [1,100] for (auto itr=v.crbegin(); itr!=v.crend(); ++itr) cout << *itr << ' ';

Capacity

Name	Description
size_type size()	Returns the number of elements in the multimap. Example: //v:{{1,100},{2,200}, {3,300},{3,350},{4,400},{5,500}} multimap<int,int> v{{1,100},{2,200}, {3,300},{3,350},{4,400},{5,500}}; //prints 6 cout << v.size();
size_type max_size()	Returns maximum  possible number of elements possible. A very large number.
bool empty()	Test whether multimap is empty.

Element Access

Name	Description
iterator find(const value_type& val)	Returns iterator to the first element or end if not found. Example: //v:{{1,100},{2,200}, {3,300},{3,350},{4,400},{5,500}} multimap<int,int> v{{1,100},{2,200}, {3,300},{3,350},{4,400},{5,500}}; //itr:v.begin()+2 auto itr = v.find(3); //itr:v.end() itr = v.find(200);
size_type count (const value_type& val)	Returns number of elements matching val. Example: //v:{{1,100},{2,200}, {3,300},{3,350},{4,400},{5,500}} multimap<int,int> v{{1,100},{2,200},{3,300},{3,350},{4,400},{5,500}}; //knt:1 auto knt = v.count(2); //knt:2 knt = v.count(3); //knt:0 knt = v.count(200);
iterator lower_bound(const value_type& val) iterator upper_bound(const value_type& val)	Returns iterator to the first element matching val or end Returns iterator next to the last  element matching val or end. Note that end will be returned if matching element is the last in the multimap.
Example: //v:{{1,100},{2,200}, {3,300},{3,350},{4,400},{5,500}} multimap<int,int> v{{1,100},{2,200},{3,300},{3,350},{4,400},{5,500}}; //itr = v.begin()+1 auto itr = v.lower_bound(2); //itr = v.begin()+2 itr = v.upper_bound(2); //itr = v.begin()+2 itr = v.lower_bound(3); //itr = v.begin()+4 itr = v.upper_bound(3); //itr = v.end() itr = v.lower_bound(6); //itr = v.end() itr = v.upper_bound(6);
pair<iterator,iterator>  equal_range (const value_type&  val)	Returns a pair object containing lower_bound and upper_bound iterators matching value val. Example: //v:{{1,100},{2,200}, {3,300},{3,350},{4,400},{5,500}} map<int,int> v({{1,100},{2,200},{3,300},{3,350},{4,400},{5,500}}); //p: {v.begin()+1,v.begin()+2} auto p = v.equal_range(2); //p: {v.begin()+2,v.begin()+4} p = v.equal_range(3); //p: {v.end(),v.end()} p = v.equal_range(6);

Modifiers

Name	Description
void insert(InputIterator first, InputIterator last) iterator insert(const_iterator hintpos, const value_type& val) iterator   insert(const value_type& val) void insert(initializer_list<value_type> il)	Inserts the  elements in the range. Inserts an element initialized with val. hintpos, is used to scout for location.  Returns an iterator to the inserted element. Note that the hintpos is used as starting point to scout to add new element. It  will go round robin if the scout is exhausted. Insert an element initialized with with val.  Returns an iterator to the inserted element. Insert elements with the contents of il.
Example: template<typename T> T operator+ (T it, typename T::difference_type i) { advance(it,i); return it; } pair<int,int> a[]{{1,100},{2,200},{3,300},{4,400},{5,500}}; multimap<int,int> v; //(1) //v:{{1,100},{2,200},{3,300}} v.insert(begin(a),begin(a)+3); //(2) //v:{{1,100},{2,200},{3,300},{3,350}} //it=begin(v)+3 auto it = v.insert(v.end(),{3,350}); //(3) //v:{{1,100},{2,200},{3,300},{3,350},{4,400}} //it=begin(v)+4 it = v.insert({4,400}); //(4) //v:{{1,100},{2,200},{3,300},{3,350},{4,400},{5,500}} v.insert({5,500});
void erase(const_iterator pos) void  erase(const_iterator first, const_iterator last) size_type erase( const value_type& val)	Erases element at pos.  Erases elements in the range.  Erases the elements of value val. Also returns number of elements erased.
Example: template<typename T> T operator+ (T it, typename T::difference_type i) { advance(it,i); return it; } multimap<int,int> v({{1,100},{2,200},{3,300},{3,350},{4,400},{5,500}}); //(1) // v:{{2,200},{3,300},{3,350},{4,400},{5,500}} //it = begin(v) auto it = v.erase(cbegin(v)); //(2) // v:{{2,200}, {3,300}, {3,350}} //it = begin(v)+3 it = v.erase(begin(v)+3,cend(v)); //(3) // v:{{2,200}} //knt=2 auto knt = v.erase(3);
void swap(set& v)	Swap content with v. Note T has to be same. Example: multimap<int,int> v({{1,100},{2,200},{3,300},{3,350}}); multimap<int,int> v2({{4,400},{5,500}}); //v2:{{1,100},{2,200},{3,300},{3,350}} //v:{{{4,400},{5,500}} v2.swap(v);
void clear()	Clear contents of multimap . Example: multimap<int,int> v({{1,100},{2,200},{3,300},{3,350},{4,400},{5,500}}); //v:{} v.clear();
iterator emplace(Args ...arg)	Constructs and inserts an element using arg. Returns an iterator to the inserted element.  Example: multimap<int,int> v({{1,100},{2,200},{3,300},{4,400},{5,500}}); //v:{{1,100},{2,200},{3,300},{3,350},{4,400},{5,500}} //itr:v.begin()+3 auto itr = v.emplace(make_pair(3,350)); //v:{{1,100},{2,200},{3,300},{3,350},{4,400},{5,500},{6,600}} //itr:v.begin()+6 itr = v.emplace(make_pair(6,600));
iterator emplace_hint(iterator hintpos, Args ...arg)	Constructs and attempts to insert an element at the hintpos using arg. After insertion, it returns an iterator to the new element. Note that the hintpos is used as starting point to scout to add new element. It  will go round robin if the scout is exhausted. Example: multimap<int,int> v({{1,100},{2,200},{3,300},{4,400},{5,500}}); //v:{{1,100},{2,200},{3,350},{3,300},{4,400},{5,500}} //itr:v.begin()+2 auto itr = v.emplace_hint(begin(v),make_pair(3,350)); //v:{{1,100},{2,200},{3,350},{3,300},{4,400},{5,500},{6,600}} //itr:v.begin()+6 itr = v.emplace_hint(end(v),make_pair(6,600));