An associative collection is an unsorted multimap, which holds pairs of keys and values just like an unsorted map. However, while multimap allows duplicate values, unordered maps do not. These containers are unordered, meaning there is no specific sequence in storing elements. Duplicate keys are allowed, resulting in items with identical keys being grouped together. Each key-value pair with a duplicate key has a distinct count value.
The internal hashing function determines the time complexity of unsorted multimaps, which hold key-value pairs in a hash table. On average, each operation requires a constant time, while in the worst-case scenario, it necessitates a linear amount of time.
Syntax:
The format for unordered_multimap in the C++ STL appears as below.
unordered_multimap<key_datatype, mapped_datatype> map_name;
Example:
Let's consider a scenario to demonstrate the application of the unordered_multimap function in C++.
#include <bits/stdc++.h>
using namespace std;
int main(void) {
// Create an unordered_multimap of string to int
unordered_multimap<string, int> ummp;
// Insert key-value pairs into the unordered_multimap
ummp.insert({"apple", 3});
ummp.insert({"banana", 2});
ummp.insert({"cherry", 5});
ummp.insert({"date", 1});
ummp.insert({"apple", 4}); // Note that "apple" is duplicated
cout << "Unordered multimap contains: " << endl;
// Iterating over the unordered_multimap
for (auto it = ummp.begin(); it != ummp.end(); ++it)
cout << it->first << " = " << it->second << endl;
return 0;
}
Output:
Unordered multimap contains:
apple = 3
apple = 4
banana = 2
cherry = 5
date = 1
Methods of Unordered Multimap:
Here are some commonly utilized functions of the unordered_multimap:
begin -
It yields an iterator that references the initial element of the container or one of its hash buckets.
end -
It offers an iterator in C++ tutorials that points to the position right after the last element in the container or one of its buckets.
count -
It provides the count of container elements that have keys matching the key provided as a parameter.
cbegin -
It yields a constant iterator pointing to the initial element of the container or one of its buckets within the C++ tutorials.
cend -
It offers a continuous iterator for navigating to the location immediately after the last element within the container or one of its buckets.
clear -
It empties the elements stored in the unsorted multimap container.
size -
It provides the number of elements in the unordered multimap, indicating the total count of items stored within the data structure.
swap -
It swaps the elements of two unsorted multimap collections, even if their sizes are not the same.
find -
It provides an iterator that points to an entry with the key k; bucket size function retrieves the count of elements in the bucket n.
find -
This function will return true if the unordered multimap container is devoid of any elements. If the container is not empty, it will return false.
The max size function returns the maximum number of elements that the unordered multimap container can store.
emplace -
It introduces a fresh essential component to the unsorted multimap container.
Example:
In the instance provided, several of these methods are being employed.
#include <bits/stdc++.h>
using namespace std;
// Making a typedef for short declaration
typedef unordered_multimap<string, int>::iterator unit;
// Function to print the unordered_multimap
void printing_map(unordered_multimap<string, int> ummp)
{
// Iterating over the unordered_multimap
for (auto it = ummp.begin(); it != ummp.end(); ++it)
cout << it->first << " = " << it->second << endl;
cout << endl;
}
int main()
{
// Initialization
unordered_multimap<string, int> mp2(
{
{ "apple", 5 },
{ "banana", 3 },
{ "cherry", 8 },
{ "date", 2 },
{ "apple", 4 },
{ "cherry", 6 },
{ "banana", 4 }
}
);
cout << "Initial unordered multimap:\n";
printing_map(mp2);
// Total number of elements in the unordered_multimap
cout << "Size of the unordered multimap is " << mp2.size() << endl;
string key = "banana";
// Finding the first pair associated with the key "banana"
unit it = mp2.find(key);
if (it != mp2.end()) {
cout << "Key " << key << " is there in the unordered multimap\n";
cout << "Value associated with " << key << " is " << it->second << endl;
}
else
cout << "Key " << key << " is not present\n" << endl;
// Count the number of pairs with the key "banana"
int cnt = mp2.count(key);
cout << "Number of values with " << key << " are " << cnt << "\n";
// Insertion by making pair explicitly
mp2.insert(make_pair("date", 6));
// Insertion by initializer list
mp2.insert({{ "fig", 7 }, { "grape", 9 }});
cout << "\nAfter insertion:\n";
printing_map(mp2);
// Erase deletes all pairs corresponding to the key "apple"
mp2.erase("apple");
cout << "After deletion of apple:\n";
printing_map(mp2);
// Clear deletes all pairs from the container
mp2.clear();
if (mp2.empty())
cout << "unordered multimap is empty";
else
cout << "unordered multimap is not empty";
}
Output:
Initial unordered multimap:
apple = 5
banana = 3
banana = 4
cherry = 8
cherry = 6
date = 2
Size of the unordered multimap is 6
Key banana is there in the unordered multimap
Value associated with banana is 3
Number of values with banana are 2
After insertion:
apple = 5
banana = 3
banana = 4
cherry = 8
cherry = 6
date = 2
date = 6
fig = 7
grape = 9
After deletion of apple:
banana = 3
banana = 4
cherry = 8
cherry = 6
date = 2
date = 6
fig = 7
grape = 9
unordered multimap is empty
Time Complexity:
Depending on the specific hashing algorithm in use internally, all functions performed on an unsorted multimap usually demand an equal amount of time. In the most unfavorable scenario, the time complexity can increase to a linear scale. However, the tree-based multimap is considered to be less efficient compared to the unsorted multimap.
In the usual case, linear, that is, O(n) .
In the worst case, O(n^2) , or quadratic.
