Map in c++ stl

Map in c++ stl is an associative container. Each element of map container is in associative fashion. Associative fashion means a value is mapped with a key. Inorder to access and perform some operations key is used. There can only be one unique key mapped with an element.

Map is defined in header file < map > and in namespace std

Map is defined by using template class, generic programming paradigm, hence provides flexibility for any kind of data types and it also provides various functions to perform various operations. Map also supports various algorithms defined in header file < algorithm >


Properties of map in c++

  • It is an associative container: elements of C++ map possesses key value paired structure. Data in a map is referenced by a key.
  • Unique Keys: each data item which is mapped with a key, the keys should be unique. There are no repetation in keys.
  • Allocator-aware: container uses an allocator object to handle the memory.
  • Key based Sorting of elements: Elements are arranged on the basis of sorting the keys. This makes the element access effixient.

Simple map example

map example in c++
map example in c++

Basic Functions of a map in c++ to perform basic operations

OperationFunction name
To insertinsert ( ) and pair_insert( )
To removeerase ( )
To Check size of a mapsize ( )
To check maximum sizemax_size ( )
To check whether map is empty or notempty ( )
To clear a mapclear ( )
To get iterator which points to beginbegin ( )
To get iterator which points to endend ( )
Basic Functions of a map in c++ stl

C++ progam which shows usage of various functions of map in c++

//Follow-up comment line
#include <iostream>
#include <map>
#include <iterator>
#include <utility>
#include<algorithm>
using namespace std;
int main(int argc, char const *argv[])
{
	//create an object of map class
	map < int , int > my_map;
	//make a pair and insert an element
	pair < int , int > my_pair(10,20);
	my_map.insert(my_pair);
	//now we use make pair to insert an element
	my_map.insert(make_pair(20,2));
	for( auto i:my_map )
	{
		cout<<i.first<<" -> "<<i.second<<endl;
	}
	//now we insert some random elements and then look at the map container
	cout<<"Inserting some random elements"<<endl;
	for( int i=0 ; i<5 ; i++ )
	{
	 my_map.insert(make_pair(i,i*2));
	}
	for( auto i:my_map )
	{
	 cout<<i.first<<" -> "<<i.second<<endl;
	}
	/*look at the output. You can clearly see that all keys are in sorted fashion.
	lets remove some elements from the map.*/
	//lets remove using erase function by passing some random number
	my_map.erase(2);
	cout<<"After removal of an element"<<endl;
	for( auto i:my_map )
	{
	 cout<<i.first<<" -> "<<i.second<<endl;
	}
	//lets search an element
	cout<<"Search element in map"<<endl;
	
	auto it=my_map.find (3);
	
	if( it!=my_map.end() )
	{
		cout<<"Element with key 3 found"<<endl;
	}
	else
	{
		cout<<"Element with key 3  not found.";
	}
	return 0;
}
map in c++
map in c++ stl

Various pre-defined functions of map in c++ stl

TypeFunction nameDescription
Member FunctionsconstructorConstructs a map.
destructorDestructs map.
operator=It copies one map container to another.
IteratorbeginThis function returns iterator to beginning of that map object.
endThis function returns iterator to end of that map object
rbeginIt returns a reverse iterator. That iterator to end of that map object.
rendIt returns a reverse iterator. That iterator points to beginning of that map object.
cbeginIt returns a constant iterator to beginning of that container object.
cendIt returns a constant iterator to end of that container object.
crbeginIt returns a constant reverse iterator to end of that container object.
crendIt returns a constant reverse iterator to beginning of that container object.
CapacityemptyIt checks if the map object is empty or not.
max_sizeIt returns maximum size of the vector object.
sizeIt returns total size of the map object.
Element accessoperator[]By using operator[] random access to element is possible.
atIt returns the element at position.
ModifiersinsertIt inserts element.
eraseIt erases an element.
swapIt swaps two elements.
clearIt removes all elements.
emplaceIt constructs and inserts the element.
emplace_hintIt constructs and inserts the element with a hint.
Observerskey_compIt returns a key comparisn object.
value_compIt returns value comparisn object.
OperationsfindIt returns an iterator to found element.
countIt counts elements with a specific key.
lower_boundIt returns an iterator to lower bound.
upper_boundIt returns an iterator to upper bound.
equal_rangeIt returns range of equal elements.
Allocatorget_allocatorIt returns an allocator.

Maps are implemented using self-balancing trees. Searching an element is a self balancing tree is log ( n ). Maps can be used efficiently in competetive programming for problems such as repeated numbers in an array, counting distinct numbers in an array, in these problems we are mapping an element with its value.

We can even use map as an array. But this makes the space and computation so costlier.

Elements are not required to sort in Map.


Keypoints about Map in C++

  • Map is an associative container. A unique key is mapped with an element.
  • Map is implemented using self balancing trees.
  • Time complexity of accessing an element is log ( n ).
  • Never forget to make use of map in competetive programming.

Suggestions

  • C++ stl Basics

References