C++ Multimap

In C++, multimaps are part of the C++ STL (Standard Template Library) . Multimaps are associative containers like maps that store sorted key-value pairs, but unlike maps, which store only unique keys, multimaps can have duplicate keys. By default, it uses 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

template < class Key,                                     // multimap::key_type  

           class T,                                                     // multimap::mapped_type  

           class Compare = less<Key>,                        // multimap::key_compare  

           class Alloc = allocator<pair<const Key,T> >    // multimap::allocator_type  

           > class multimap;

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> is the default value.
• ✅ alloc: It represents the type of the allocator object. This argument is optional and the default value is allocator.

Creating a multimap

In C++, multimaps can easily be created using the following statement:

multimap<key_type, value_type> mymap;

This syntax declares a multimap named mymap where each key is of type keytype and each value is of type valuetype. In C++, the key of a multimap and corresponding values are always inserted as a pair. We cannot insert only a key or just a value in a multimap.

C++ Example to Create Multimap

Let us take an example to illustrate how we can create a multimap 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 example, we construct a multimap of country-capital pairs with several entries for the same country. After that, it prints the number of total elements with size and then prints all key-value pairs by iterating over the multimap using an iterator.

Basic Operations of Multimap

There are several operations that can be performed on multimap containers in C++ STL. Some of the operations are as follows:

Inserting Elements

In C++, a key-value pair can be inserted into the multimap through the insert function. Insertion through the operator is not supported as there may be several elements with a single key.

C++ Inserting Elements Example

Let us take an example to illustrate how to insert elements in 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 example, we demonstrate how to use a std::multimap in C++ to store key-value pairs with repeating keys. First, we add elements with insert (pairs and initializer lists) and emplace and display all the elements. As multimap stores items in key-sorted order and does not eliminate duplicates, keys like 1, 2, and 3 repeat themselves multiple times with different values.

Accessing Elements

In C++, members of multimaps can be accessed by iterators only. The first member can access the key, and the second member can access the value with the help of the -> operator. Here, the operator is not supported. We can advance the iterators by the next and advance methods.

However, the first and the last element can be addressed directly via begin and end iterators.

C++ Example to Access Elements

Let us take an example to illustrate how to access elements in 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 example, we generate a multimap that maps multiple string values to integer keys. It includes some elements, prints all the key-value pairs, and later finds and prints all values for the key 2 using equal_range.

Updating Elements

In C++, we cannot update the key of an element in multimap. We can update the value with the help of the iterator to that element.

C++ Example to Update Elements

Let us take an example to illustrate how to update elements in 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 example, we create a multimap, insert some key-value pairs, and then print them. After that, it retrieves the value "Banana" with key 2, removes it, and inserts a new pair with the same key but a new value, "Blueberry". After that, it prints the new multimap.

Traversing Elements

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

C++ Example to Traverse Elements

Let us take an example to illustrate how to traverse elements in 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 example, we initialize a multimap, add key-value pairs, and subsequently employ an iterator within a for loop to iterate and output all elements in sorted order by keys.

Identifying Elements

In C++, multimaps provide fast search by key operation using the find method. It returns an iterator to the first element of the given key. It returns the end iterator if the given key is not present.

If we need to search for a particular element from all the elements that contain the same key, we can search for it in the range returned by the equal_range method.

C++ Example to Identify Elements

Let us take an example to illustrate how to identify elements in 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 example, we create a multimap, insert key-value pairs, and use the find function to locate the first value of key 1. If it finds the element in a given, it shows the element and then proceeds to print the rest of the values with the same key.

Removing Elements

In C++, multimap elements can be removed using the erase function either by passing the key or iterator. If we pass the key, all elements with that particular key are removed. If we pass the iterator, the element is removed where the iterator is pointing.

C++ Example to Remove Elements

Let us take an example to illustrate how we can remove the elements in 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 example, we add elements to a multimap and then delete all entries with key 1 by calling erase(1). After that, it erases the first remaining element with an iterator. Finally, it prints the changed contents of the multimap.

Checking the Size of a Multimap

In C++, we can verify whether a multimap is empty or not by using the empty method and find its size by using the size method.

The empty method returns:

• ✅ True: It returns true when the multimap is empty.
• ✅ False: It returns false if the multimap is not empty.

The size method returns the number of elements in the multimap.

C++ Example to Check the Size of Multimap

Let us take an example to illustrate how we can check the size of 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 example, we insert elements into a multimap and print the total number of elements using size. After that, it checks whether the multimap is empty using empty and prints the result accordingly.

Time Complexity:

The below table lists the time complexity of the operations on multimap:

Member Functions

Below is the list of all member functions of multimap:

Constructor/Destructor

The given table shows several constructor/destructor functions that are used in C++ Multimap.

Iterators

The given table shows several iterator functions that are used in C++ Multimap.

Capacity

The given table shows several capacity functions that are used in C++ Multimap.

Modifiers

The given table shows several modifier functions that are used in C++ Multimap.

Observers

The given table shows several observer functions that are used in C++ Multimap.

Operations

The given table shows several operations that are performed in C++ Multimap.

Allocator

The given table shows allocator function that is used in C++ Multimap.

Non-Member Overloaded Functions

The given table shows non-member overloaded functions that are used in C++ Multimap.

Conclusion

In conclusion, C++ multimap is a Standard Template Library (STL) associative container that holds key-value pairs with ordered keys where duplicate keys are allowed. It is implemented over a self-balancing Red-Black Tree and offers several quick operations, including insertion, removal, and lookup in logarithmic time.

In C++, multimap does not support the operator like map but is accessed through functions, including insert, emplace, find, and equal_range. Iterators are utilized for traversal and retrieving elements. It offers a huge collection of member functions to efficiently manage and accommodate popular STL features, such as iterators, capacity tests, and element operations.

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