How to traverse through all values for a given key in multimap?
Given a multimap and a key of the multimap, our task is to simply display the (key – value) pairs of the given key. In multimap we can have multiple (key – value) pair for the same key. Suppose our multimap contains
key value
1 10
2 20
2 30
2 40
3 50
4 60
4 70
key : 2
key value
2 20
2 30
2 40
Like in unordered_map in C++ STL we cant fetch values like
int key = 2;
multimap map;
// insert values in map
cout << "Key : " << key;
cout << "Value : " < second;
Output :
Key : 2
Value : 20
Because the above method will only return the first occurrence of the key present, This method fails if there are multiple (key – value) pairs for the same key.
There are two ways by which we can achieve the expected results :
Method 1 (Simple Traversal) Traverse through whole map and whenever the key is equal to given key we display the key-value pair.
// CPP program to find all values for a
// given key.
#include <bits/stdc++.h>
using namespace std;
int main()
{
multimap <int, int> map;
// insert the values in multimap
map.insert(make_pair(1, 10));
map.insert(make_pair(2, 20));
map.insert(make_pair(2, 30));
map.insert(make_pair(2, 40));
map.insert(make_pair(3, 50));
map.insert(make_pair(4, 60));
map.insert(make_pair(4, 70));
int key = 2;
for (auto itr = map.begin(); itr != map.end(); itr++)
if (itr -> first == key)
cout << itr -> first << " "
<< itr -> second << endl;
return 0;
}
// JAVA program to find all values for a
// given key.
import java.util.*;
class GFG
{
static class pair
{
int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
public static void main(String[] args)
{
HashSet <pair> map = new LinkedHashSet<>();
// add the values in multimap
map.add(new pair(1, 10));
map.add(new pair(2, 20));
map.add(new pair(2, 30));
map.add(new pair(2, 40));
map.add(new pair(3, 50));
map.add(new pair(4, 60));
map.add(new pair(4, 70));
int key = 2;
for (pair itr : map)
if (itr.first == key)
System.out.println(itr.first+ " "
+ itr.second);
}
}
// This code is contributed by 29AjayKumar
# Python program to find all values for a
# given key.
map = []
# insert the values in multimap
map.append((1, 10));
map.append((2, 20));
map.append((2, 30));
map.append((2, 40));
map.append((3, 50));
map.append((4, 60));
map.append((4, 70));
key = 2;
for i in map:
if i[0] == key:
print(i[0],i[1])
# This code is contributed by shubhamsingh10
// C# program to find all values for a
// given key.
using System;
using System.Collections.Generic;
class GFG
{
class pair
{
public int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Driver code
public static void Main(String[] args)
{
HashSet<pair> map = new HashSet<pair>();
//.Add the values in multimap
map.Add(new pair(1, 10));
map.Add(new pair(2, 20));
map.Add(new pair(2, 30));
map.Add(new pair(2, 40));
map.Add(new pair(3, 50));
map.Add(new pair(4, 60));
map.Add(new pair(4, 70));
int key = 2;
foreach (pair itr in map)
if (itr.first == key)
Console.WriteLine(itr.first+ " "
+ itr.second);
}
}
// This code is contributed by Rajput-Ji
<script>
class pair
{
constructor(first,second)
{
this.first=first;
this.second=second;
}
}
let map = new Set();
// add the values in multimap
map.add(new pair(1, 10));
map.add(new pair(2, 20));
map.add(new pair(2, 30));
map.add(new pair(2, 40));
map.add(new pair(3, 50));
map.add(new pair(4, 60));
map.add(new pair(4, 70));
let key = 2;
for (let itr of map.values())
if (itr.first == key)
document.write(itr.first+ " "
+ itr.second+"<br>");
// This code is contributed by rag2127
</script>
Output:
2 20
2 30
2 40
Method 2(Using Binary Search)Find the lower_bound and upper_bound for the given key and traverse between them.
lower_bound(key) : returns the iterator pointing to the first element which is greater than or
equal to key.
upper_bound(key) : returns the iterator pointing to the first element which is greater than key.
key value
1 10
2 20 <-- lower_bound(2)
2 30
2 40
3 50 <-- upper_bound(2)
4 60
4 70
#include <bits/stdc++.h>
using namespace std;
int main()
{
multimap <int, int> map;
// insert the values in multimap
map.insert(make_pair(1, 10));
map.insert(make_pair(2, 20));
map.insert(make_pair(2, 30));
map.insert(make_pair(2, 40));
map.insert(make_pair(3, 50));
map.insert(make_pair(4, 60));
map.insert(make_pair(4, 70));
int key = 2;
auto itr1 = map.lower_bound(key);
auto itr2 = map.upper_bound(key);
while (itr1 != itr2)
{
if (itr1 -> first == key)
cout << itr1 -> first << " "
<< itr1 -> second << endl;
itr1++;
}
return 0;
}
import java.util.*;
public class Main {
public static void main(String[] args) {
Map<Integer, List<Integer>> map = new HashMap<>();
// Insert the values in the map
map.put(1, Arrays.asList(10));
map.put(2, Arrays.asList(20, 30, 40));
map.put(3, Arrays.asList(50));
map.put(4, Arrays.asList(60, 70));
int key = 2;
// Print the values for the specific key
if (map.containsKey(key)) {
for (int value : map.get(key)) {
System.out.println(key + " " + value);
}
}
}
}
from collections import defaultdict
# Create a defaultdict with int as the default factory
map = defaultdict(list)
# insert the values in the multimap
map[1].append(10)
map[2].extend([20, 30, 40])
map[3].append(50)
map[4].extend([60, 70])
key = 2
itr1 = map[key]
for val in itr1:
print(key, val)
using System;
using System.Collections.Generic;
class MainClass {
public static void Main (string[] args) {
Dictionary<int, List<int>> map = new Dictionary<int, List<int>>();
// Insert the values in the map
map.Add(1, new List<int> { 10 });
map.Add(2, new List<int> { 20, 30, 40 });
map.Add(3, new List<int> { 50 });
map.Add(4, new List<int> { 60, 70 });
int key = 2;
// Print the values for the specific key
if (map.ContainsKey(key)) {
foreach (int value in map[key]) {
Console.WriteLine(key + " " + value);
}
}
}
}
// Create a JavaScript object to store the values
const map = {
1: [10],
2: [20, 30, 40],
3: [50],
4: [60, 70]
};
const key = 2;
// Check if the key exists in the map
if (map.hasOwnProperty(key)) {
// Print the values for the specific key
map[key].forEach(value => {
console.log(key + " " + value);
});
}
Output:
2 20
2 30
2 40
Time complexity: O(logn) where n is size of given multimap
Auxiliary Space: O(n)
Contact Us