Multimap in C++
FREE
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.
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
| Functions | Description |
|---|---|
| Constructor | Construct multimap |
| Destructor | Destruct and destroy multimap |
| Operator= | Copy elements of multimap to another multimap |
Iterators
| Functions | Description |
|---|---|
| begin | Returns an iterator pointing to the first element of the multimap |
| cbegin | Returns a constant iterator pointing to the first element of the multimap |
| end | Returns an iterator pointing to the end of multimap |
| rbegin | Returns a reverse iterator pointing to the end |
| rend | Returns a reverse iterator pointing to the beginning of the multimap |
Capacity
| Functions | Description |
|---|---|
| empty | Returns true if multimap is empty |
| size | Returns the number of elements in a multimap |
| max_size | Returns the maximum size of multimap |
Modifiers
| Functions | Description |
|---|---|
| insert | Insert elements in the multimap |
| erase | Erase elements from the multimap |
| clear | Delete all the elements from the multimap |
| emplace | Construct and insert the new elements into the multimap |
| swap | Exchange and swap the content of multimap |
Operations
| Functions | Description |
|---|---|
| find | Search for an element with a given key |
| count | Get the no. of elements matching with the given key |
| lower_bound | Returns an iterator to lower bound |
| upper_bound | Returns an iterator to upper bound |
| equal_range() | Returns the range of elements that match with the given key |
Allocator
| Functions | Description |
|---|---|
| get_allocator | Returns 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.