map

 Overview

The standard library provides map to provide lookup table mechanism.

Details

map is basically a lookup table of unique 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 map;

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

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

New elements can be added or removed or searched in the map. 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
map()	Default Constructor. Example: //v:{} map<int,int> v;
map(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}}; //v:{{1,100},{2,200}, {3,300},{4,400},{5,500}} map<int,int> v(begin(a),end(a));
map(const map& x)	copy constructor.
map(map&& x)	move constructor.
map(initializer_list<value_type> il)	initializer_list constructor. Example: //v:{{1,100},{2,200}, {3,300},{4,400},{5,500}} map<int,int> v({{1,100},{2,200}, {3,300},{4,400},{5,500}});

Iterator

Name	Description
iterator begin() iterator end()	Returns iterator to beginning and end of the map. Example: template<typename T, typename U> ostream& operator << (ostream& os, const pair<T,U>& val) { os << "[" << val.first << "," << val.second << "]"; return os; } map<int,int> v({{1,100},{2,200}, {3,300},{4,400},{5,500}}); //prints [1,100] [2,200] [3,300] [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 map. Example: map<int,int> v({{1,100},{2,200}, {3,300},{4,400},{5,500}}); //prints [5,500] [4,400] [3,300] [2,200] [1,100] for (auto itr=v.rbegin(); itr!=v.rend(); ++itr) cout << *itr << ' ';
const_iterator cbegin() const_iterator cend()	Returns const_iterator to beginning and end of the map. Example: map<int,int> v({{1,100},{2,200}, {3,300},{4,400},{5,500}}); //prints [1,100] [2,200] [3,300] [4,400] [5,500] for (auto itr=v.cbegin(); itr!=v.cend(); ++itr) cout << *itr << ' ';
const_reverse_iterator crbegin() const_reverse_iterator crend()	Return const_reverse_iterator to reverse beginning and reverse end of the map. Example: map<int,int> v({{1,100},{2,200}, {3,300},{4,400},{5,500}}); //prints [5,500] [4,400] [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 map Example: map<int,int> v({{1,100},{2,200}, {3,300},{4,400},{5,500}}); //prints 5 cout << v.size();
size_type max_size()	Returns maximum  possible number of elements possible. A very large number.
bool empty()	Test whether map is empty.

Element Access

Name	Description
mapped_type operator[](const key_type& key)	Returns mapped_type of  the first match of the key  or default value of the mapped_type if not found. Exception is not thrown. Example: map<int,int> v({{1,100},{2,200}, {3,300},{4,400},{5,500}}); //returns 200 auto k = v[2]; //returns 0 k = v[20];
reference  at(const key_type& key)	Returns mapped_type of  the first match of the key  or exception is not thrown if not found.  Example: map<int,int> v({{1,100},{2,200}, {3,300},{4,400},{5,500}}); //returns 200 auto k = v.at(2); //exception thrown k = v.at(20);
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},{4,400},{5,500}} map<int,int> v({{1,100},{2,200}, {3,300},{4,400},{5,500}}); //itr:v.begin()+1 auto itr = v.find(2); //itr:v.end() itr = v.find(200);
size_type count (const value_type& val)	Returns number of elements matching val. Example: map<int,int> v({{1,100},{2,200}, {3,300},{4,400},{5,500}}); //knt:1 auto knt = v.count(2); //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 map.
Example: map<int,int> v({{1,100},{2,200}, {3,300},{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()+4 itr = v.lower_bound(5); //itr = v.end() itr = v.upper_bound(5); //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: map<int,int> v({{1,100},{2,200}, {3,300},{4,400},{5,500}}); //p: {v.begin()+1,v.begin()+2} auto p = v.equal_range(2); //p: {v.begin()+4,v.end()} p = v.equal_range(5); //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) pair<iterator,bool>  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 or existing 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 a pair object containing iterator to the inserted element or existing element and bool with value true if a new value is inserted otherwise false. 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; } map<int,int> v; //(1) //v:{{1,100},{2,200}} v.insert(begin(a),begin(a)+2); //(2) //v:{{1,100},{2,200}, {3,300}} //it=begin(v)+2 auto it = v.insert(v.end(),{3,300}); //(3) //v:{{1,100},{2,200},{3,300},{4,400}} //p=<begin(v)+3,true> auto p = v.insert({4,400}); //(4) //v:{{1,100},{2,200}, {3,300},{4,400},{5,500}} v.insert({5,500});
void erase(const_iterator pos) void  rase(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. Returns number of elements erased.
Example: template<typename T> T operator+ (T it, typename T::difference_type i) { advance(it,i); return it; } map<int,int> v({{1,100},{2,200}, {3,300},{4,400},{5,500}}); //(1) // v:{{2,200}, {3,300},{4,400},{5,500}} //it = begin(v) auto it = v.erase(cbegin(v)); //(2) // v:{{2,200}, {3,300}} //it = begin(v)+2 it = v.erase(begin(v)+2,cend(v)); //(3) // v:{{3,300}} //knt=1 auto knt = v.erase(2);
void swap(map& v)	Swap content with v. Note T has to be same. Example: map<int,int> v({{1,100},{2,200},{3,300}}); map<int,int> v2({{4,400},{5,500}}); //v2:{{1,100},{2,200},{3,300}} //v:{{{4,400},{5,500}} v2.swap(v);
void clear()	Clear contents of map. Example: map<int,int> v({{1,100},{2,200}, {3,300},{4,400},{5,500}}); //v:{} v.clear();
pair<iterator,bool> emplace(Args ...arg)	Constructs and inserts an element using arg. Returns a pair object containing an iterator and a boolean. If insertion succeeded, iterator points to the inserted element and true value. Otherwise, iterator points to the existing element and false. Example: map<int,int> v({{1,100},{2,200}, {3,300},{4,400},{5,500}}); //v:{{1,100},{2,200}, {3,300},{4,400},{5,500}} //p:{v.begin()+1,false} auto p = v.emplace(make_pair(2,200)); //v:{{1,100},{2,200}, {3,300},{4,400},{5,500},{6,600}} //p:{v.begin()+5,true} p = 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. If returns an iterator to the new element or existing 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: map<int,int> v({{1,100},{2,200}, {3,300},{4,400},{5,500}}); //v:{{1,100},{2,200}, {3,300},{4,400},{5,500}} //itr:v.begin()+1 auto itr = v.emplace_hint(v.begin(),make_pair(2,200)); //v:{{1,100},{2,200}, {3,300},{4,400},{5,500},{6,600}} //itr:v.begin()+5 itr = v.emplace_hint(v.end(),make_pair(6,600));