Open In App

Map in C++ Standard Template Library (STL)

Last Updated : 30 Oct, 2023
Improve
Improve
Like Article
Like
Save
Share
Report

Maps are associative containers that store elements in a mapped fashion. Each element has a key value and a mapped value. No two mapped values can have the same key values.

std::map is the class template for map containers and it is defined inside the <map> header file.

Basic std::map Member Functions

Some basic functions associated with std::map are:

  • begin() – Returns an iterator to the first element in the map.
  • end() – Returns an iterator to the theoretical element that follows the last element in the map.
  • size() – Returns the number of elements in the map.
  • max_size() – Returns the maximum number of elements that the map can hold.
  • empty() – Returns whether the map is empty.
  • pair insert(keyvalue, mapvalue) – Adds a new element to the map.
  • erase(iterator position) – Removes the element at the position pointed by the iterator.
  • erase(const g)– Removes the key-value ‘g’ from the map.
  • clear() – Removes all the elements from the map.

Examples of std::map

The following examples shows how to perform basic operations on map containers.

Example 1: begin() and end() Function

C++




// C++ program to illustrate the begin and end iterator
#include <iostream>
#include <map>
#include <string>
using namespace std;
 
int main()
{
    // Create a map of strings to integers
    map<string, int> mp;
 
    // Insert some values into the map
    mp["one"] = 1;
    mp["two"] = 2;
    mp["three"] = 3;
 
    // Get an iterator pointing to the first element in the
    // map
    map<string, int>::iterator it = mp.begin();
 
    // Iterate through the map and print the elements
    while (it != mp.end()) {
        cout << "Key: " << it->first
             << ", Value: " << it->second << endl;
        ++it;
    }
 
    return 0;
}


Output

Key: one, Value: 1
Key: three, Value: 3
Key: two, Value: 2

Complexity of the above method:

Time complexity: O(n) where n is the size of map.

Auxiliary Space: O(n)

Example 2: size() function

C++




// C++ program to illustrate the size() function
#include <iostream>
#include <map>
#include <string>
using namespace std;
 
int main()
{
    // Create a map of strings to integers
    map<string, int> map;
 
    // Insert some values into the map
    map["one"] = 1;
    map["two"] = 2;
    map["three"] = 3;
 
    // Print the size of the map
    cout << "Size of map: " << map.size() << endl;
 
    return 0;
}


Output

Size of map: 3

Complexity of the above method:

Time complexity: O(1).

Example 3: Implementing Map

CPP




// CPP Program to demonstrate the implementation in Map
// divyansh mishra --> divyanshmishra101010
#include <iostream>
#include <iterator>
#include <map>
using namespace std;
 
int main()
{
 
    // empty map container
    map<int, int> gquiz1;
 
    // insert elements in random order
    gquiz1.insert(pair<int, int>(1, 40));
    gquiz1.insert(pair<int, int>(2, 30));
    gquiz1.insert(pair<int, int>(3, 60));
    gquiz1.insert(pair<int, int>(4, 20));
    gquiz1.insert(pair<int, int>(5, 50));
    gquiz1.insert(pair<int, int>(6, 50));
 
    // another way of inserting a value in a map
    gquiz1[7] = 10;
 
    // printing map gquiz1
    map<int, int>::iterator itr;
    cout << "\nThe map gquiz1 is : \n";
    cout << "\tKEY\tELEMENT\n";
    for (itr = gquiz1.begin(); itr != gquiz1.end(); ++itr) {
        cout << '\t' << itr->first << '\t' << itr->second
             << '\n';
    }
    cout << endl;
 
    // assigning the elements from gquiz1 to gquiz2
    map<int, int> gquiz2(gquiz1.begin(), gquiz1.end());
 
    // print all elements of the map gquiz2
    cout << "\nThe map gquiz2 after"
         << " assign from gquiz1 is : \n";
    cout << "\tKEY\tELEMENT\n";
    for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr) {
        cout << '\t' << itr->first << '\t' << itr->second
             << '\n';
    }
    cout << endl;
 
    // remove all elements up to
    // element with key=3 in gquiz2
    cout << "\ngquiz2 after removal of"
            " elements less than key=3 : \n";
    cout << "\tKEY\tELEMENT\n";
    gquiz2.erase(gquiz2.begin(), gquiz2.find(3));
    for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr) {
        cout << '\t' << itr->first << '\t' << itr->second
             << '\n';
    }
 
    // remove all elements with key = 4
    int num;
    num = gquiz2.erase(4);
    cout << "\ngquiz2.erase(4) : ";
    cout << num << " removed \n";
    cout << "\tKEY\tELEMENT\n";
    for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr) {
        cout << '\t' << itr->first << '\t' << itr->second
             << '\n';
    }
 
    cout << endl;
 
    // lower bound and upper bound for map gquiz1 key = 5
    cout << "gquiz1.lower_bound(5) : "
         << "\tKEY = ";
    cout << gquiz1.lower_bound(5)->first << '\t';
    cout << "\tELEMENT = " << gquiz1.lower_bound(5)->second
         << endl;
    cout << "gquiz1.upper_bound(5) : "
         << "\tKEY = ";
    cout << gquiz1.upper_bound(5)->first << '\t';
    cout << "\tELEMENT = " << gquiz1.upper_bound(5)->second
         << endl;
 
    return 0;
}


Output

The map gquiz1 is : 
    KEY    ELEMENT
    1    40
    2    30
    3    60
    4    20
    5    50
    6    50
    7    10


The map gquiz2 after assign from gquiz1 is : 
    KEY    ELEMENT
    1    40
    2    30
    3    60
    4    20
    5    50
    6    50
    7    10


gquiz2 after remov...

Complexity of the above method:

Time complexity: O(n log(n)) as n is size of the map
Auxiliary space: O(n)

Example 4: Implementing Map of Integers

C++




// C++ program to implement map container
#include <iostream>
#include <map>
#include <string>
 
using namespace std;
 
int main()
{
    // Create a map of strings to integers
    map<string, int> map;
 
    // Insert some values into the map
    map["one"] = 1;
    map["two"] = 2;
    map["three"] = 3;
 
    // Print the values in the map
    cout << "Key: one, Value: " << map["one"] << endl;
    cout << "Key: two, Value: " << map["two"] << endl;
    cout << "Key: three, Value: " << map["three"] << endl;
 
    // Check if a key is in the map
    if (map.count("four") > 0) {
        cout << "Key 'four' is in the map" << endl;
    }
    else {
        cout << "Key 'four' is not in the map" << endl;
    }
 
    return 0;
}


Output

Key: one, Value: 1
Key: two, Value: 2
Key: three, Value: 3
Key 'four' is not in the map

List of all Functions of std::map

The following table contains all the functions defined inside std::map class.

Function

Definition

map::insert()

Insert elements with a particular key in the map container –> O(log n)

map:: count()

Returns the number of matches to element with key-value ‘g’ in the map. –> O(log n)

map equal_range()

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.

map erase()

Used to erase elements from the container –> O(log n)

map rend()

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).

map rbegin()

 

Returns a reverse iterator which points to the last element of the map.

map find()

Returns an iterator to the element with key-value ‘g’ in the map if found, else returns the iterator to end.

map crbegin() and crend() 

crbegin() returns a constant reverse iterator referring to the last element in the map container. crend() returns a constant reverse iterator pointing to the theoretical element before the first element in the map.

map cbegin() and cend()

 cbegin() returns a constant iterator referring to the first element in the map container. cend() returns a constant iterator pointing to the theoretical element that follows the last element in the multimap.

map emplace()

Inserts the key and its element in the map container.

map max_size() 

Returns the maximum number of elements a map container can hold –> O(1)

map upper_bound()

Returns an iterator to the first element that is equivalent to mapped value with key-value ‘g’ or definitely will go after the element with key-value ‘g’ in the map

map operator=

Assigns contents of a container to a different container, replacing its current content.

map lower_bound()

Returns an iterator to the first element that is equivalent to the mapped value with key-value ‘g’ or definitely will not go before the element with key-value ‘g’ in the map –> O(log n)

map emplace_hint()

Inserts the key and its element in the map container with a given hint.

map value_comp() 

Returns the object that determines how the elements in the map are ordered (‘<‘ by default).

map key_comp() 

Returns the object that determines how the elements in the map are ordered (‘<‘ by default).

map::size()

Returns the number of elements in the map.

map::empty()

Returns whether the map is empty

map::begin() and end()

begin() returns an iterator to the first element in the map. end() returns an iterator to the theoretical element that follows the last element in the map

map::operator[]

This operator is used to reference the element present at the position given inside the operator.

map::clear() 

Removes all the elements from the map.

map::at() and map::swap()

at() function is used to return the reference to the element associated with the key k. swap() function is used to exchange the contents of two maps but the maps must be of the same type, although sizes may differ.



Similar Reads

The C++ Standard Template Library (STL)
The Standard Template Library (STL) is a set of C++ template classes to provide common programming data structures and functions such as lists, stacks, arrays, etc. It is a library of container classes, algorithms, and iterators. It is a generalized library and so, its components are parameterized. Working knowledge of template classes is a prerequ
5 min read
Sort in C++ Standard Template Library (STL)
Sorting is one of the most basic functions applied to data. It means arranging the data in a particular fashion, which can be increasing or decreasing. There is a builtin function in C++ STL by the name of sort(). This function internally uses IntroSort. In more details it is implemented using hybrid of QuickSort, HeapSort and InsertionSort.By defa
6 min read
Set in C++ Standard Template Library (STL)
Sets are a type of associative container in which each element has to be unique because the value of the element identifies it. The values are stored in a specific sorted order i.e. either ascending or descending. The std::set class is the part of C++ Standard Template Library (STL) and it is defined inside the &lt;set&gt; header file. Syntax: std:
7 min read
Priority Queue in C++ Standard Template Library (STL)
A C++ priority queue is a type of container adapter, specifically designed such that the first element of the queue is either the greatest or the smallest of all elements in the queue, and elements are in non-increasing or non-decreasing order (hence we can see that each element of the queue has a priority {fixed order}). In C++ STL, the top elemen
11 min read
Containers in C++ STL (Standard Template Library)
A container is a holder object that stores a collection of other objects (its elements). They are implemented as class templates, which allows great flexibility in the types supported as elements. The container manages the storage space for its elements and provides member functions to access them, either directly or through iterators (reference ob
2 min read
Binary Search in C++ Standard Template Library (STL)
Binary search is a widely used searching algorithm that requires the array to be sorted before search is applied. The main idea behind this algorithm is to keep dividing the array in half (divide and conquer) until the element is found, or all the elements are exhausted.It works by comparing the middle item of the array with our target, if it match
3 min read
Multimap in C++ Standard Template Library (STL)
Multimap is similar to a map with the addition that multiple elements can have the same keys. Also, it is NOT required that the key-value and mapped value pair have to be unique in this case. One important thing to note about multimap is that multimap keeps all the keys in sorted order always. These properties of multimap make it very much useful i
6 min read
Multiset in C++ Standard Template Library (STL)
Multisets are a type of associative containers similar to the set, with the exception that multiple elements can have the same values. Some Basic Functions associated with multiset: begin() - Returns an iterator to the first element in the multiset --&gt; O(1)end() - Returns an iterator to the theoretical element that follows the last element in th
6 min read
Queue in C++ Standard Template Library (STL)
Queues are a type of container adaptors that operate in a first in first out (FIFO) type of arrangement. Elements are inserted at the back (end) and are deleted from the front. Queues use an encapsulated object of deque or list (sequential container class) as its underlying container, providing a specific set of member functions to access its eleme
3 min read
Deque in C++ Standard Template Library (STL)
Double-ended queues are sequence containers with the feature of expansion and contraction on both ends. They are similar to vectors, but are more efficient in case of insertion and deletion of elements. Unlike vectors, contiguous storage allocation may not be guaranteed. Double Ended Queues are basically an implementation of the data structure doub
4 min read
Practice Tags :