Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
Reading time: 35 minutes
Map is a dictionary like data structure. It is a sequence of (key, value) pair, where only single value is associated with each unique key. It is often referred as associative array.
In map, key values are generally used to sort the elements.In Maps each key is unique and cannot be changed, and it can be inserted or deleted but cannot be altered. Value associated with keys can be altered. We can search, remove and insert in a map within O(n) time complexity.
Maps are typically implemented as Binary Search Tree.
Zero sized maps are also valid. In that case map.begin() and map.end() points to same location.
Maps are part of the C++ STL (Standard Template Library).
For example:
A map of Employees where employee ID is the key and name is the value can be represented as:
| Keys | Values |
|---|---|
| 101 | Robin |
| 102 | Reem |
| 103 | Nisha |
| 104 | Neeta |
Creating a Map in C++ STL
Syntax :
template < class Key, // map::key_type
class T, // map::mapped_type
class Compare = less<Key>, // map::key_compare
class Alloc = allocator<pair<const Key,T> > // map::allocator_type
> class map;
Parameter
key: The key data type to be stored in the map.type: The data type of value to be stored in the map.compare: A comparison class that takes two arguments of the same type bool and returns a value. This argument is optional and the binary predicate less<"key"> is the default value.alloc: Type of the allocator object. This argument is optional and the default value is allocator .
Maps can easily be created using the following statement :
map<key_type , value_type> map_name;
This will create a map with key of type Key_type and value of type value_type. One thing which is to remembered is that key of a map and corresponding values are always inserted as a pair, you cannot insert only key or just a value in a map.
Example 1 :
#include <string.h>
#include <iostream>
#include <map>
#include <utility>
using namespace std;
int main()
{
map<int, string> Employees;
// 1) Assignment using array index notation
Employees[101] = "Nikita";
Employees[105] = "John";
Employees[103] = "Dolly";
Employees[104] = "Deep";
Employees[102] = "Aman";
cout << "Employees[104]=" << Employees[104] << endl << endl; cout << "Map size: " << Employees.size()<< endl;
cout << endl << "Natural Order:" << endl;
for( map<int,string>::iterator ii=Employees.begin(); ii!=Employees.end();++ii)
{
cout << (*ii).first << ": "<< (*ii).second<< endl;
}
cout << endl << "Reverse Order:" << endl;
for( map<int,string>::reverse_iterator ii=Employees.rbegin(); ii!=Employees.rend(); ++ii)
{
cout << (*ii).first << ": " << (*ii).second << endl;
}
}
Output :
Employees[104]=Deep
Map size: 5
Natural Order:
101: Nikita
102: Aman
103: Dolly
104: Deep
105: John
Reverse Order:
105: John
104: Deep
103: Dolly
102: Aman
101: Nikita
Example 2 :
#include <iostream>
#include <map>
using namespace std;
int main ()
{
map<int,int> m{ {1,2} , {2,3} , {3,4} };
/* creates a map m with keys 1,2,3 and
their corresponding values 2,3,4 */
map<string,int> map1;
/* creates a map with keys of type character and
values of type integer */
map1["abc"]=100; // inserts key = "abc" with value = 100
map1["b"]=200; // inserts key = "b" with value = 200
map1["c"]=300; // inserts key = "c" with value = 300
map1["def"]=400; // inserts key = "def" with value = 400
map<char,int> map2 (map1.begin(), map1.end());
/* creates a map map2 which have entries copied
from map1.begin() to map1.end() */
map<char,int> map3 (m);
/* creates map map3 which is a copy of map m */
}
Member Functions of Map in C++ STL:
Following are some of the commonly used basic functions of Map container in STL:
1. at and [ ] :
Both at and [ ] are used for accessing the elements in the map. The only difference between them is that at throws an exception if the accessed key is not present in the map, on the other hand operator [ ] inserts the key in the map if the key is not present already in the map.
Example :
#include <iostream>
#include <map>
using namespace std;
int main ()
{
map <int,string> m{ {1,”nikhilesh”} , {2,”shrikant”} , {3,”ashish”} };
cout << m.at(1) ; // prints value associated with key 1 ,i.e nikhilesh
cout << m.at(2) ; // prints value associated with key 2 ,i.e shrikant
/* note that the parameters in the above at() are the keys not the index */
cout << m[3] ; // prints value associated with key 3 , i.e ashish
m.at(1) = "vikas"; // changes the value associated with key 1 to vikas
m[2] = "navneet"; // changes the value associated with key 2 to navneet
m[4] = "doodrah";
/* since there is no key with value 4 in the map,
it insert a key-value pair in map with key=4 and value = doodrah */
m.at(5) = "umeshwa";
/* since there is no key with value 5 in the map ,
it throws an exception */
}
2. empty, size and max_size :
empty() returns boolean true if the map is empty, else it returns Boolean false. size() returns number of entries in the map, an entry consist of a key and a value.
max_size() returns the upper bound of the entries that a map can contain (maximum possible entries) based on the memory allocated to the map.
Example :
#include <iostream>
#include <map>
using namespace std;
int main()
{
map<char, int> mymap;
mymap['a'] = 1;
mymap['b'] = 2;
if (mymap.empty()) {
cout << "True";
}
else {
cout << "False";
}
return 0;
}
Output :
False
3. insert and insert_or_assign :
insert() is used to insert entries in the map. Since keys are unique in a map, it first checks that whether the given key is already present in the map or not, if it is present the entry is not inserted in the map and the iterator to the existing key is returned otherwise new entry is inserted in the map.
There are two variations of insert():
- insert(pair) : In this variation, a pair of key and value is inserted in the map. The inserted pair is always inserted at the appropriate position as keys are arranged in sorted order.
- insert(start_itr , end_itr): This variation inserts the entries in range defined by start_itr and end_itr of another map.
The insert_or_assing() works exactly as insert() except that if the given key is already present in the map then its value is modified.
Example :
#include <iostream>
#include <map>
using namespace std;
int main ()
{
map<int,int> m{{1,2} , {2,3} , {3,4} };
m.insert( pair<int,int> (4,5));
/* inserts a new entry of key = 4 and value = 5 in map m */
/* make_pair() can also be used for creating a pair */
m.insert( make_pair(5, 6));
/* inserts a new entry of key = 5 and value = 6 */
map::iterator i , j;
i = m.find(2); // points to entry having key =2
j = m.find(5); // points to entry having key =5
map<int,int> new_m;
new_m.insert(i,j);
/* insert all the entries which are pointed
by iterator i to iterator j*/
m.insert( make_pair(3,6));
// do not insert the pair as map m already contain key = 3 */
m.insert_or_assign( make_pair(3,6)); // assign value = 6 to key =3
}
4. erase and clear :
erase() removes the entry from the map pointed by the iterator (which is passed as parameter), however if we want to remove all the elements from the map, we can use clear(), it clears the map and sets its size to 0.
There are two variations of erase :
- erase(iterator_itr) : This removes entry from the map pointed by iterator iterator_itr, reducing the size of map by 1.
- erase(start_iterator, end_iterator) : It removes the elements in range specified by the start_iterator and end_iterator.
Example of Clear() :
#include <bits/stdc++.h>
using namespace std;
int main()
{
// Take any two maps
map<int, string> map1, map2;
// Inserting values
map1[1] = "India";
map1[2] = "Nepal";
map1[3] = "Sri Lanka";
map1[4] = "Myanmar";
// Print the size of map
cout<< "Map size before running function: \n";
cout << "map1 size = " << map1.size() << endl;
cout << "map2 size = " << map2.size() << endl;;
// Deleting the map elements
map1.clear();
map2.clear();
// Print the size of map
cout<< "Map size after running function: \n";
cout << "map1 size = " << map1.size() << endl;
cout << "map2 size = " << map2.size();
return 0;
}
Example of erase() :
#include <bits/stdc++.h>
using namespace std;
int main()
{
// initialize container
map<int, int> mp;
// insert elements in random order
mp.insert({ 2, 30 });
mp.insert({ 1, 40 });
mp.insert({ 3, 60 });
mp.insert({ 5, 50 });
// prints the elements
cout << "The map before using erase() is : \n";
cout << "KEY\tELEMENT\n";
for (auto itr = mp.begin(); itr != mp.end(); ++itr) {
cout << itr->first
<< '\t' << itr->second << '\n';
}
// function to erase given keys
mp.erase(1);
mp.erase(2);
// prints the elements
cout << "\nThe map after applying erase() is : \n";
cout << "KEY\tELEMENT\n";
for (auto itr = mp.begin(); itr != mp.end(); ++itr) {
cout << itr->first
<< '\t' << itr->second << '\n';
}
return 0;
}
output :
The map before using erase() is :
KEY ELEMENT
1 40
2 30
3 60
5 50
The map after applying erase() is :
KEY ELEMENT
3 60
5 50
5. begin, end and find :
begin, end and find returns an iterator.
begin() returns the iterator to the starting entry of the map
end() returns the iterator next to the last entry in the map
find() returns the iterator to the entry having key equal to given key (passed as parameter).
Example of begin() and end() :
#include <iostream>
#include <map>
using namespace std;
int main()
{
// declaration of map container
map<char, int> mymap;
mymap['a'] = 1;
mymap['b'] = 2;
mymap['c'] = 3;
// using begin() to print map
for (auto it = mymap.begin();
it != mymap.end(); ++it)
cout << it->first << " = "
<< it->second << '\n';
return 0;
}
Example of find() :
#include <bits/stdc++.h>
using namespace std;
int main()
{
// initialize container
multimap<int, int> mp;
// insert elements in random order
mp.insert({ 2, 30 });
mp.insert({ 1, 40 });
mp.insert({ 3, 20 });
mp.insert({ 4, 50 });
cout << "The elements from position 3 in map are : \n";
cout << "KEY\tELEMENT\n";
// find() function finds the position at which 3 is
for (auto itr = mp.find(3); itr != mp.end(); itr++)
cout << itr->first
<< '\t' << itr->second << '\n';
return 0;
}
output :
The elements from position 3 in map are :
KEY ELEMENT
3 20
4 50
6. count() :
count() is a built-in function in C++ STL which returns 1 if the element with key K is present in the map container. It returns 0 if the element with key K is not present in the container.
Example :
#include <bits/stdc++.h>
using namespace std;
int main()
{
// initialize container
map<int, int> mp;
// insert elements in random order
mp.insert({ 2, 30 });
mp.insert({ 1, 40 });
mp.insert({ 3, 60 });
mp.insert({ 4, 20 });
mp.insert({ 5, 50 });
// checks if key 1 is present or not
if (mp.count(1))
cout << "The key 1 is present\n";
else
cout << "The key 1 is not present\n";
// checks if key 100 is present or not
if (mp.count(100))
cout << "The key 100 is present\n";
else
cout << "The key 100 is not present\n";
return 0;
}
7. equal_range() :
equal_range() is a built-in function in C++ STL which returns an iterator of pairs. The pair refers to the bounds of a range that includes all the elements in the container which have a key equivalent to k. Since the map container only contains unique key, hence the first iterator in the pair returned thus points to the element and the second iterator in the pair points to the next key which comes after key K. If there are no matches with key K, the range returned is of length 1 with both iterators pointing to the an element which has a key denoting the size of map and elements as 0.
Example :
#include <bits/stdc++.h>
using namespace std;
int main()
{
// initialize container
map<int, int> mp;
// insert elements in random order
mp.insert({ 4, 30 });
mp.insert({ 1, 40 });
mp.insert({ 6, 60 });
pair<map<int, int>::iterator, map<int, int>::iterator> it;
// iterator of pairs
it = mp.equal_range(1);
cout << "The lower bound is " <<
it.first->first << ":" << it.first->second;
cout << "\nThe upper bound is " <<
it.second->first << ":" << it.second->second;
return 0;
}
Output :
The lower bound is 1:40
The upper bound is 4:30
8. rend() :
The rend() function is an inbuilt function in C++ STL which returns a reverse iterator pointing to the theoretical element right before the first key-value pair in the map(which is considered its reverse end).
Example of rend() :
#include <iostream>
#include <map>
using namespace std;
int main()
{
map<char, int> mymap;
// Insert pairs in the multimap
mymap.insert(make_pair('a', 1));
mymap.insert(make_pair('b', 3));
mymap.insert(make_pair('c', 5));
// Get the iterator pointing to
// the preceding position of
// 1st element of the map
auto it = mymap.rend();
// Get the iterator pointing to
// the 1st element of the multimap
it--;
cout << it->first
<< " = "
<< it->second;
return 0;
}
Output :
a = 1
9. crbegin() and crend() :
crbegin() is a built-in function in C++ STL which returns a constant reverse iterator referring to the last element in the map container. Since map container contains the element in an ordered way, crbegin() will point to that element that will come last according to the container’s sorting criterion.
crend() is a built-in function in C++ STL which returns a constant reverse iterator pointing to the theoretical element before the first element in the map. Since map container contains the element in an ordered way, crend() will point to the element theoretically before the first element according to the container’s sorting criterion.
example of crbegin() :
#include <bits/stdc++.h>
using namespace std;
int main()
{
// initialize container
map<int, int> mp;
// insert elements in random order
mp.insert({ 2, 30 });
mp.insert({ 1, 40 });
mp.insert({ 3, 60 });
mp.insert({ 4, 20 });
mp.insert({ 5, 50 });
auto ite = mp.crbegin();
cout << "The last element is {" << ite->first
<< ", " << ite->second << "}\n";
// prints the elements
cout << "\nThe map in reverse order is: \n";
cout << "KEY\tELEMENT\n";
for (auto itr = mp.crbegin(); itr != mp.crend(); ++itr) {
cout << itr->first
<< '\t' << itr->second << '\n';
}
return 0;
}
Output:
The last element is {5, 50}
The map in reverse order is:
KEY ELEMENT
5 50
4 20
3 60
2 30
1 40
example of crend() :
#include <bits/stdc++.h>
using namespace std;
int main()
{
// initialize container
map<int, int> mp;
// insert elements in random order
mp.insert({ 2, 30 });
mp.insert({ 1, 40 });
mp.insert({ 3, 60 });
mp.insert({ 4, 20 });
mp.insert({ 5, 50 });
// prints the elements
cout << "\nThe map in reverse order is : \n";
cout << "KEY\tELEMENT\n";
for (auto itr = mp.crbegin(); itr != mp.crend(); ++itr) {
cout << itr->first
<< '\t' << itr->second << '\n';
}
return 0;
}
Output:
The map in reverse order is :
KEY ELEMENT
5 50
4 20
3 60
2 30
1 40
10. emplace() :
emplace() is a built-in function in C++ STL which inserts the key and its element in the map container. It effectively increases the container size by one. If the same key is emplaced more than once, the map stores the first element only as the map is a container which does not store multiple keys of the same value.
Example of emplace() :
#include <bits/stdc++.h>
using namespace std;
int main()
{
// initialize container
map<int, int> mp;
// insert elements in random order
mp.emplace(2, 30);
mp.emplace(1, 40);
mp.emplace(2, 20);
mp.emplace(1, 50);
mp.emplace(4, 50);
// prints the elements
cout << "\nThe map is : \n";
cout << "KEY\tELEMENT\n";
for (auto itr = mp.begin(); itr != mp.end(); itr++)
cout << itr->first << "\t" << itr->second << endl;
return 0;
}
Output:
The map is :
KEY ELEMENT
1 40
2 30
4 50
