C++ Multimap

In C++, a multimap is an associative container available in the Standard Template Library (STL) that stores elements in the form of key-value pairs. Unlike a map, a multimap allows duplicate keys, which means multiple values can be associated with the same key. By default, the elements in a multimap are stored in ascending order of keys.

Declaration of a C++ Multimap

In C++, a multimap can be declared using the multimap container available in the STL.

The syntax for declaring a multimap is given below:

In this syntax,

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

We can create a multimap using the following syntax:

Initialization of a C++ Multimap

A multimap can be initialized using key-value pairs during declaration.

The following example shows how to initialize a multimap:

In the above example, the multimap stores multiple values for the same key.

C++ Multimap Example

Let us take an example to understand how to create and use a multimap in C++.

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 create a multimap of country-capital pairs where duplicate keys are allowed. After that, the size() function is used to display the total number of elements, and all key-value pairs are printed 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:

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

Example

Let us take an example to illustrate how to insert elements in C++ multimap.

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.

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

Example

Let us take an example to illustrate how to access elements in C++ multimap.

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.

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

Example

Let us take an example to illustrate how to update elements in C++ multimap.

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.

4. Traversing Elements

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

Example

Let us take an example to illustrate how to traverse elements in C++ multimap.

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.

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

Example

Let us take an example to illustrate how to identify elements in C++ multimap.

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.

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

Example

Let us take an example to illustrate how we can remove the elements in C++ multimap.

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.

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

Example

Let us take an example to illustrate how we can check the size of multimap in C++.

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:

Multimap Member Functions

Below is the list of all member functions of multimap:

1. Constructor/Destructor

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

2. Iterators

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

3. Capacity

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

4. Modifiers

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

5. Observers

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

6. Operations

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

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