How to Find All Occurrences of an Element in a Multiset in C++?
In C++, a multiset is a container similar to a set but it allows multiple occurrences of its elements i.e. duplicate values. In this article, we will learn how to find all occurrences of a specific element in a multiset in C++.
Example:
Input:
myMultiset = {1, 2, 2, 3, 3, 3, 4, 4, 4, 4};
target = 3
Output:
The element 3 occurred at position: 3 4 5
Finding All Occurrences of an Element in a Multiset in C++
To find all occurrences of an element in a std::multiset in C++, we can use the std::set::equal_range() function that returns the pair that contains the iterator to the range of set elements containing our target elements. We can then use the std::distance() function to get the position of these elements.
C++ Program To Find All Occurrences of an Element in a Multiset
The below example demonstrates how we can find all occurrences of an element in a multiset in C++.
// C++ Program to illustrate how to find all occurrences of
// an element in a multiset
#include <iostream>
#include <set>
using namespace std;
int main()
{
// Initialize a multiset with multiple occurrences of
// some elements
multiset<int> myMultiset
= { 1, 2, 2, 3, 3, 3, 4, 4, 4, 4 };
// The element to find
int target = 3;
cout << "The element " << target
<< " occurred at indices: ";
// getting iterator to the range that contains the
// matching elements
auto it = myMultiset.equal_range(3);
for (auto i = it.first; i != it.second; i++) {
cout << distance(myMultiset.begin(), i) << " ";
}
return 0;
}
Output
The element 3 occurred at indices: 3 4 5
Time Complexity: O(K + logN), here N is the number of elements in the multiset and K is the number of occurences.
Auxilliary Space: O(1)
Contact Us