Multimap in C++

Learn via video course
FREE
View all courses
C++ Course: Learn the Essentials
C++ Course: Learn the Essentials
by Prateek Narang
1000
5
Start Learning
C++ Course: Learn the Essentials
C++ Course: Learn the Essentials
by Prateek Narang
1000
5
Start Learning

Overview

Multimap is an associative container that stores elements in sorted key-value pairs as a tuple. Multimap can store more than one value against a key. It is quite similar to the map, but the difference is that it can also contain duplicate keys that are not unique. By default, it uses the < operator to compare the keys.

We can declare a Multimap in C++ as:

What is Multimap in C++?

Multimap in C++ is an associative container where elements are stored in sorted key-value pairs as a tuple. Key values are used to sort and uniquely identify the elements and mapped values store the content associated with that key. In a map, keys must be unique, but in a multimap, keys can be duplicated or unique.r By default, the multimap class uses the < operator to compare and sort the keys.

Properties of Multimap in C++

  • In map and set in C++, each key must be unique, whereas, in the case of multimap in C++, we do not have this restriction.
  • The key-value pair of multimap in C++ can be of any data type. We can also use user-defined data types for keys and values of the multimap. Also, key and mapped values can have different or the same data types in C++.
  • Inserting a new element into a multimap does not invalidate iterators that point to existing elements. Similarly, erasing an element from a multimap does not invalidate any iterators, except for iterators that point to the element that is being erased.
  • Multimaps in C++ have certain runtime complexity of O(log n) for the inserting operation.

Syntax of Multimap in C++

There are four template parameters used in the syntax of multimap in C++ that we will study later as we move through this article.

Creating a Multimap in C++

One important thing to remember in the case of multimap in C++ is that the key of a multimap and corresponding values associated with it is always inserted as a pair, and we can't just insert only a key or the value at a time.

creating a multimap in c++

Declaring a Multimap in C++

Here, we have declared a multimap in C++ with keys of character type that can hold values of integer type.

Methods of Initializing a Multimap in C++

1. Initializing with initializer list: Here, we have initialized a multimap in C++ using the initializer list during multimap declaration.

2. Inserting using make_pair: We can also insert a key-value pair in multimap in C++ using the insert() member function.

3. Inserting using pair:

4. Constructing a multimap n from another multimap m1: Here, we have a multimap m1, and we assign the values of m1 to a new multimap n by specifying the start and end iterator.

Iterating over the multimap in C++

1. Using Range-based for Loop Here, we have implemented a range-based for loop to traverse on key-value pair of multimap m1; hence, this will print the resultant values.

2. Using Iterator Here, we are using multimap iterator itr over multimap m1 that will traverse over multimap from start to end and print the resultant key-value pair as an output.

Member Functions of Multimap in C++

Constructor / Destructor

FunctionsDescription
ConstructorConstruct multimap
DestructorDestruct and destroy multimap
Operator=Copy elements of multimap to another multimap

Iterators

FunctionsDescription
beginReturns an iterator pointing to the first element of the multimap
cbeginReturns a constant iterator pointing to the first element of the multimap
endReturns an iterator pointing to the end of multimap
rbeginReturns a reverse iterator pointing to the end
rendReturns a reverse iterator pointing to the beginning of the multimap

Capacity

FunctionsDescription
emptyReturns true if multimap is empty
sizeReturns the number of elements in a multimap
max_sizeReturns the maximum size of multimap

Modifiers

FunctionsDescription
insertInsert elements in the multimap
eraseErase elements from the multimap
clearDelete all the elements from the multimap
emplaceConstruct and insert the new elements into the multimap
swapExchange and swap the content of multimap

Operations

FunctionsDescription
findSearch for an element with a given key
countGet the no. of elements matching with the given key
lower_boundReturns an iterator to lower bound
upper_boundReturns an iterator to upper bound
equal_range()Returns the range of elements that match with the given key

Allocator

FunctionsDescription
get_allocatorReturns an allocator object that is used to construct the multimap

Examples to Illustrate Multimap in C++

In this C++ example code, we have declared and initialized multimap simultaneously with the key of character type that contains integer type data.

After that, we inserted some additional key-value pairs using the insert() function, and then we used a for-each loop to traverse through & print the key-value pair of multimap m1. To explore STL, we have also used the size() and clear() functions at the end.

Example 1

Output:

We can observe that the output will display multimap key-value pair in each line, and in the end, we have displayed the multimap's size before and after clearing it.

Example 2

In this C++ example code, firstly, we have declared multimap m1 of key-value pair of integer type and then inserted some pair type data. After printing the multimap values of m1, we have also created another multimap m2 of the same type as that of m1 using m1.begin() and m1.end() as parameters.

Then we have also tried to erase the key-value pair from multimap m2 having a key value less than 3. After each operation, we also print the map key-value pair as on the output console. In the end, we have explored the STL function lower_bound to print key-value pair having the lower bound value as 5.

Output:

We can see that the output console window displays multimap m1 values first, and then after inserting two more key-value pairs, we have again displayed the m1 key-value pair in each line.

Also, next, it will display m2 elements after removing the key-value pair having a key-value less than 3. In the end, we have displayed key-value pair having lower_bound 5.

Template Parameters of Multimap in C++

We have seen above the syntax of the multimap class and how everything works internally for multimap in C++, and now, we will study in detail all four template parameters:

1. Key (multimap::key_type) As every element in the multimap is identified using a key value, the key can be of different types. The data type of key is stored in a multimap container. It is aliased as member-type multimap::key_type.

2. Type (multimap::mapped_type) The data type of value associated or mapped with the key is stored in a multimap container. It is aliased as member-type multimap::mapped_type.

3. Traits (multimap::key_compare) The trait keyword is similar to Compare keyword, and they both have the same functionality. It takes two parameter keys as arguments and returns a boolean value. It provides results after comparing two element values, and by default, multimap uses the < operator to compare two keys. It is aliased as member-type multimap::key_compare.

4. Allocator (multimap::allocator_type) It represents the object stored in the allocator, which is used to define the storage allocation model. This argument is optional, and the default value is allocator. It is aliased as member-type multimap::allocator_type.

Conclusion

  • Multimaps in C++ are part of the C++ STL (Standard Template Library). Elements are stored in a tuple as key-value pairs in a sorted manner in accordance with the keys. By default, they use the < operator to compare the keys.
  • Unlike maps in C++, multimaps in C++ can contain duplicate keys.
  • We can declare a multimap in C++ as: multimap <Key_type,Value_type> map_name;
  • There are four template parameters in multimap in C++, and they are: key, type, trait, and allocator.
  • Multimaps in C++ have certain runtime complexity of O(log n) for the inserting operation.

Read More: