C++ Multimap

In C++, multimaps are a component of the C++ STL (Standard Template Library). Multimaps function as associative containers similar to maps, organizing sorted key-value pairs. However, unlike maps that permit only unique keys, multimaps allow for the storage of duplicate keys. By default, it utilizes the (<) operator to compare the keys.

For example: A multimap of Employees where employee age is the key and name is the value can be represented as:

Multimap employee has duplicate keys age.

Syntax

It has the following syntax

_PRESERVE0__

Parameters

• ✅ key: The key data type to be stored in the multimap.
• ✅ type: The data type of value to be stored in the multimap.
• ✅ 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> as the default value.
• ✅ alloc: This parameter denotes the allocator object's type. While this argument is not mandatory, the default value assigned is allocator.

Creating a multimap

In C++, you can effortlessly generate multimaps by utilizing the subsequent statement:

multimap<key_type, value_type> mymap;

This code snippet defines a multimap named mymap, where every key is of keytype and each value is of valuetype. In C++, a multimap requires key-value pairs to be inserted together, preventing the insertion of only a key or a value independently.

C++ Example to Create Multimap

Let's consider an instance to demonstrate how a multimap can be created in C++.

Example

#include <iostream>  

#include <map>  

#include <string>  

  

using namespace std;   //using standard namespace

  

int main()   //main function

{  

    multimap<string, string> m = {  

            {"India","New Delhi"},  

            {"India", "Hyderabad"},  

            {"United Kingdom", "London"},  

            {"United States", "Washington D.C"}  

    };  

      

    cout << "Size of map m: " << m.size() <<endl;      

    cout << "Elements in m: " << endl;  

      

    for (multimap<string, string>::iterator it = m.begin(); it != m.end(); ++it)  

    {  

       cout << "  [" << (*it).first << ", " << (*it).second << "]" << endl;  

    }  

  

    return 0;  

}

Output:

Size of map m: 4

Elements in m: 

  [India, New Delhi]

  [India, Hyderabad]

  [United Kingdom, London]

  [United States, Washington D.C]

Explanation:

In this instance, we are creating a multimap that stores pairs of countries and their corresponding capitals, allowing multiple entries for the same country. Following this, it displays the total number of elements in the multimap using the size function and proceeds to output all the key-value pairs by iterating through the multimap with an iterator.

Basic Operations of Multimap

There exist numerous actions that can be executed on multimap containers within C++ STL. A selection of these operations includes:

Inserting Elements

In C++, you can add a key-value pair to the multimap using the insert method. The operator is not suitable for insertion because multiple elements could have the same key in the multimap.

C++ Inserting Elements Example

Let's consider an instance to demonstrate the process of adding elements in a C++ multimap.

Example

#include <iostream>

#include <map>

int main() {   //main function

    std::multimap<int, std::string> mm;

    mm.insert(std::pair<int, std::string>(1, "Apple"));

    mm.insert(std::pair<int, std::string>(2, "Banana"));

    mm.insert(std::pair<int, std::string>(1, "Avocado")); 

    

    mm.insert({3, "Cherry"});

    mm.insert({2, "Blueberry"}); 

    

    mm.emplace(4, "Date");

    mm.emplace(3, "Cranberry");  

    std::cout << "Multimap contents:\n";

    for (const auto& pair : mm) {

        std::cout << "Key: " << pair.first << ", Value: " << pair.second << '\n';

    }

    return 0;

}

Output:

Multimap contents:

Key: 1, Value: Apple

Key: 1, Value: Avocado

Key: 2, Value: Banana

Key: 2, Value: Blueberry

Key: 3, Value: Cherry

Key: 3, Value: Cranberry

Key: 4, Value: Date

Explanation:

In this illustration, we showcase the utilization of a std::multimap in C++ for managing key-value pairs where keys can be repeated. Initially, we populate the multimap using insert (pairs and initializer lists) and emplace methods, followed by showcasing all the stored elements. Since a multimap organizes entries in a sorted order based on keys and allows duplicates, keys such as 1, 2, and 3 are presented multiple times with varying corresponding values.

Accessing Elements

In C++, multimaps allow access to their members solely through iterators. The initial iterator grants access to the key, while the subsequent iterator grants access to the value using the -> operator. It's important to note that the operator is not enabled for multimaps. To move the iterators forward, the next and advance methods can be utilized.

Nevertheless, the initial and final element can be specifically accessed using the begin and end iterators.

C++ Example to Access Elements

Let's consider an instance to demonstrate the process of retrieving elements in a C++ multimap.

Example

#include <iostream>

#include <map>

int main() {  //main function

    std::multimap<int, std::string> mm;

    mm.insert({1, "Apple"});

    mm.insert({2, "Banana"});

    mm.insert({1, "Avocado"});

    mm.insert({3, "Cherry"});

    std::cout << "All elements:\n";

    for (const auto& pair : mm) {

        std::cout << "Key: " << pair.first << ", Value: " << pair.second << '\n';

    }

    std::cout << "\nValues for key 2:\n";

    auto range = mm.equal_range(2);

    for (auto it = range.first; it != range.second; ++it) {

        std::cout << it->second << '\n';

    }

    return 0;

}

Output:

All elements:

Key: 1, Value: Apple

Key: 1, Value: Avocado

Key: 2, Value: Banana

Key: 3, Value: Cherry

Values for key 2:

Banana

Explanation:

In this instance, we create a multimap that associates numerous string values with integer keys. The multimap is populated with various elements, displays all the key-value pairs, and subsequently retrieves and displays all values corresponding to the key 2 utilizing the equal_range function.

Updating Elements

In C++, modifying the key of an entry in a multimap is not allowed. However, it is possible to update the value using the iterator pointing to that specific entry.

C++ Example to Update Elements

Let's consider a scenario to demonstrate the process of modifying elements in a C++ multimap.

Example

#include <iostream>

#include <map>

int main() {   //main function

    std::multimap<int, std::string> mm;

    mm.insert({1, "Apple"});

    mm.insert({2, "Banana"});

    mm.insert({1, "Avocado"});

    std::cout << "Before update:\n";

    for (const auto& pair : mm) {

        std::cout << "Key: " << pair.first << ", Value: " << pair.second << '\n';

    }

    auto range = mm.equal_range(2);

    for (auto it = range.first; it != range.second; ++it) {

        if (it->second == "Banana") {

            mm.erase(it);

            mm.insert({2, "Blueberry"});

            break; 

        }

    }

    std::cout << "\nAfter update:\n";

    for (const auto& pair : mm) {

        std::cout << "Key: " << pair.first << ", Value: " << pair.second << '\n';

    }

    return 0;

}

Output:

Before update:

Key: 1, Value: Apple

Key: 1, Value: Avocado

Key: 2, Value: Banana

After update:

Key: 1, Value: Apple

Key: 1, Value: Avocado

Key: 2, Value: Blueberry

Explanation:

In this instance, we instantiate a multimap, add various key-value pairs, and subsequently display them. Following that, we extract the value "Banana" associated with key 2, delete it, and add a new pair with the identical key but a different value, "Blueberry". Finally, the updated multimap is printed.

Traversing Elements

In C++, a multimap can be traversed using either a range-based for loop or by using begin and end iterators within a loop.

C++ Example to Traverse Elements

Let's consider a scenario to demonstrate the process of iterating through elements in a C++ multimap.

Example

#include <iostream>

#include <map>

int main() {  //main function

    std::multimap<int, std::string> mm;

    mm.insert({1, "Apple"});

    mm.insert({2, "Banana"});

    mm.insert({1, "Avocado"});

    mm.insert({3, "Cherry"});

    std::cout << "Traversal using iterator:\n";

    for (std::multimap<int, std::string>::iterator it = mm.begin(); it != mm.end(); ++it) {

        std::cout << "Key: " << it->first << ", Value: " << it->second << '\n';

    }

    return 0;

}

Output:

Traversal using iterator:

Key: 1, Value: Apple

Key: 1, Value: Avocado

Key: 2, Value: Banana

Key: 3, Value: Cherry

Explanation:

In this instance, we create a multimap, insert key-value pairs, and then utilize an iterator in a for loop to traverse and display all items in ascending order based on keys.

Identifying Elements

In C++, multimaps offer efficient key-based search functionality through the find function. The find method returns an iterator pointing to the initial element of the specified key. If the key is not found, it returns the end iterator instead.

If there is a necessity to locate a specific element among all the elements sharing a common key, we can carry out the search within the range provided by the equal_range function.

C++ Example to Identify Elements

Let's consider an instance to demonstrate the process of recognizing elements in a C++ multimap.

Example

#include <iostream>

#include <map>

int main() {    //main function

    std::multimap<int, std::string> mm;

// insert key-value pair

    mm.insert({1, "Apple"});

    mm.insert({2, "Banana"});

    mm.insert({1, "Avocado"});

    mm.insert({3, "Cherry"});

//define the key to search

    int keyToFind = 1;

    auto it = mm.find(keyToFind);

    if (it != mm.end()) {

        std::cout << "First occurrence of key " << keyToFind << ": " << it->second << '\n';

        std::cout << "All values for key " << keyToFind << ":\n";

        for (auto rangeIt = it; rangeIt != mm.end() && rangeIt->first == keyToFind; ++rangeIt) {

            std::cout << rangeIt->second << '\n';

        }

    } else {

        std::cout << "Key " << keyToFind << " not found.\n";

    }

    return 0;

}

Output:

First occurrence of key 1: Apple

All values for key 1:

Apple

Avocado

Explanation:

In this illustration, we instantiate a multimap, add key-value pairs, and employ the find method to search for the initial value associated with key 1. Upon locating the element within the specified range, it displays the element and subsequently outputs the remaining values corresponding to the same key.

Removing Elements

In C++, elements in a multimap can be deleted using the erase method by either providing the key or the iterator. When the key is specified, all elements associated with that specific key are eliminated. Alternatively, if the iterator is supplied, the element at the iterator's position is deleted.

C++ Example to Remove Elements

Let's consider an example to demonstrate the process of deleting elements in a C++ multimap.

Example

#include <iostream>

#include <map>

int main() {   //main function

    std::multimap<int, std::string> mm;

    mm.insert({1, "Apple"});

    mm.insert({2, "Banana"});

    mm.insert({1, "Avocado"});

    mm.insert({3, "Cherry"});

    mm.

erase(1);

    auto it = mm.begin(); 

    mm.erase(it);

    std::cout << "After removal:\n";

    for (const auto& pair : mm) {

        std::cout << "Key: " << pair.first << ", Value: " << pair.second << '\n';

    }

    return 0;

}

Output:

After removal:

Key: 3, Value: Cherry

Explanation:

In this illustration, we insert elements into a multimap and subsequently remove all records associated with key 1 using the erase(1) function. Following that, it removes the initial remaining element using an iterator. Lastly, it displays the updated contents of the multimap.

Checking the Size of a Multimap

In C++, we can determine if a multimap is empty by utilizing the empty function and obtain its size by using the size method.

The empty function provides the following outcomes:

• ✅ True: This result is generated when the multimap has no elements.
• ✅ False: It is the outcome when the multimap contains one or more elements.

The size function provides the count of elements stored in the multimap.

C++ Example to Check the Size of Multimap

Let's consider an example to demonstrate how we can verify the size of a multimap in C++.

Example

#include <iostream>

#include <map>

int main() {   //main function

    std::multimap<int, std::string> mm;

    mm.insert({1, "Apple"});

    mm.insert({2, "Banana"});

    mm.insert({1, "Avocado"});

    mm.insert({3, "Cherry"});

    std::cout << "The multimap contains " << mm.size() << " elements.\n";

    if (mm.empty()) {

        std::cout << "The multimap is empty.\n";

    } else {

        std::cout << "The multimap is not empty.\n";

    }

    return 0;

}

Output:

The multimap contains 4 elements.

The multimap is not empty.

Explanation:

In this instance, we add elements to a multimap and display the overall count of elements by utilizing the size method. Following this, we verify if the multimap is devoid of elements by employing empty and output the corresponding outcome.

Time Complexity:

The following table outlines the time complexity of the operations on multimap:

Member Functions

Below is the compilation of all member functions of multimap:

Constructor/Destructor

The provided table displays various constructor and destructor functions employed in C++ Multimap implementations.

Iterators

The provided table displays various iterator functions commonly utilized in C++ Multimap.

Capacity

The provided table displays various capacity functions utilized in C++ Multimap.

Modifiers

The provided table displays various modifier functions utilized in C++ Multimap.

Observers

The provided table displays a variety of observer functions utilized in C++ Multimap.

Operations

The provided table illustrates various operations carried out in C++ Multimap.

Allocator

The provided table displays the allocator function utilized in C++ Multimap.

Non-Member Overloaded Functions

The provided table displays non-member overloaded functions utilized in C++ Multimap.

Conclusion

In summary, the C++ multimap represents an associative container within the Standard Template Library (STL) that stores key-value pairs with sorted keys while permitting duplicate keys. This container is built on a self-adjusting Red-Black Tree structure and provides efficient functionalities such as insertion, deletion, and retrieval in logarithmic time complexity.

In C++, the multimap container does not have the operator similar to map. Instead, it is interacted with using methods like insert, emplace, find, and equal_range. Traversal and element retrieval are done using iterators. This container provides a wide array of member functions to effectively handle and support various key STL functionalities, such as iterators, capacity checks, and element manipulations.

C++ Multimap MCQs

1) Which of the following options is true about multimap in C++?

• ✅ It stores key-value pairs in an unordered fashion
• ✅ It allows duplicate keys
• ✅ It does not use any internal data structure
• ✅ Keys and values are stored separately

2) Which of the following methods is used to insert elements in a C++ multimap?

• ✅ add
• ✅ push
• ✅ insert
• ✅ put

3) Which of the following function returns the range of elements matching a specific key in a multimap?

• ✅ equal_range
• ✅ find_range
• ✅ range
• ✅ get_range

4) What is the time complexity for inserting an element in a C++ multimap?

• ✅ O(1)
• ✅ O(n)
• ✅ O(n log n)
• ✅ O(log n)

5) Which of the following methods cannot be used to access multimap elements directly?

• ✅ begin
• ✅ find
• ✅ operator
• ✅ equal_range