The multiset in the C++ Standard Template Library (STL) is an associative container that stores elements in a sorted order, allowing multiple identical elements.
Unlike set, which enforces unique elements, multiset permits duplicates, making it useful for applications where multiple identical items need to be managed in sorted order.
Key Features of multiset
- Sorted Order: Elements are automatically stored in ascending order by default.
- Duplicate Elements Allowed: Unlike set, multiset allows multiple occurrences of the same value.
- Efficient Operations: Provides efficient insertion, deletion, and search operations.
- No Direct Access by Index: Elements cannot be accessed by index; only by iterator.
Basic Syntax
#include <set> using namespace std; multiset<int> ms;
Let’s explore multiset with various examples.
1. Initializing and Inserting Elements
You can initialize a multiset and insert elements using the insert function. Duplicate elements are allowed and automatically sorted.
#include <iostream>
#include <set>
using namespace std;
int main() {
// Initialize an empty multiset
multiset<int> ms;
// Insert elements
ms.insert(10);
ms.insert(20);
ms.insert(10); // Duplicate
ms.insert(15);
// Display elements
cout << "Elements in the multiset: ";
for (const auto &val : ms) {
cout << val << " ";
}
cout << endl;
return 0;
}
Output:
Elements in the multiset: 10 10 15 20
2. Counting Elements
The count function returns the number of occurrences of a specific element in the multiset.
#include <iostream>
#include <set>
using namespace std;
int main() {
multiset<int> ms = {10, 20, 10, 15, 20, 20};
// Count occurrences of an element
cout << "Count of 10: " << ms.count(10) << endl;
cout << "Count of 20: " << ms.count(20) << endl;
return 0;
}
Output:
Count of 10: 2 Count of 20: 3
3. Removing Elements
You can remove elements from a multiset using erase. It can either remove all occurrences of a specific value or a specific element at an iterator position.
#include <iostream>
#include <set>
using namespace std;
int main() {
multiset<int> ms = {10, 20, 10, 15, 20, 20};
// Remove all occurrences of 20
ms.erase(20);
// Display remaining elements
cout << "Elements after removing 20: ";
for (const auto &val : ms) {
cout << val << " ";
}
cout << endl;
return 0;
}
Output:
Elements after removing 20: 10 10 15
4. Inserting Multiple Elements with Duplicates
Since multiset allows duplicates, you can insert identical elements multiple times, and they will be stored in sorted order.
#include <iostream>
#include <set>
using namespace std;
int main() {
multiset<int> ms;
// Insert multiple identical elements
ms.insert(5);
ms.insert(5);
ms.insert(5);
cout << "Elements after inserting duplicates: ";
for (const auto &val : ms) {
cout << val << " ";
}
cout << endl;
return 0;
}
Output:
Elements after inserting duplicates: 5 5 5
5. Finding Elements
The find function returns an iterator to the first occurrence of a specific element in the multiset.
#include <iostream>
#include <set>
using namespace std;
int main() {
multiset<int> ms = {10, 20, 10, 15};
// Finding an element
auto it = ms.find(10);
if (it != ms.end()) {
cout << "Found element 10 in the multiset." << endl;
} else {
cout << "Element 10 not found in the multiset." << endl;
}
return 0;
}
Output:
Found element 10 in the multiset.
6. Using equal_range to Access All Occurrences of an Element
The equal_range function returns a pair of iterators that represent the range of elements with a specific value.
#include <iostream>
#include <set>
using namespace std;
int main() {
multiset<int> ms = {10, 20, 10, 15, 20, 20};
// Using equal_range to get all occurrences of 20
auto range = ms.equal_range(20);
cout << "All occurrences of 20: ";
for (auto it = range.first; it != range.second; ++it) {
cout << *it << " ";
}
cout << endl;
return 0;
}
Output:
All occurrences of 20: 20 20 20
7. Iterating Over Elements
You can use a range-based for loop or an iterator to iterate over elements in a multiset.
#include <iostream>
#include <set>
using namespace std;
int main() {
multiset<int> ms = {10, 20, 10, 15};
cout << "Elements in the multiset: ";
for (auto it = ms.begin(); it != ms.end(); ++it) {
cout << *it << " ";
}
cout << endl;
return 0;
}
Output:
Elements in the multiset: 10 10 15 20
8. Using lower_bound and upper_bound
The lower_bound function returns an iterator to the first element that is not less than a given value, while upper_bound returns an iterator to the first element greater than the given value.
#include <iostream>
#include <set>
using namespace std;
int main() {
multiset<int> ms = {10, 20, 10, 15, 20, 20};
// Lower bound of 15
auto lb = ms.lower_bound(15);
if (lb != ms.end()) {
cout << "Lower bound of 15: " << *lb << endl;
}
// Upper bound of 15
auto ub = ms.upper_bound(15);
if (ub != ms.end()) {
cout << "Upper bound of 15: " << *ub << endl;
}
return 0;
}
Output:
Lower bound of 15: 15 Upper bound of 15: 20
9. Using multiset with a Custom Comparator
You can specify a custom comparator to define the order of elements in the multiset.
#include <iostream>
#include <set>
using namespace std;
struct DescendingOrder {
bool operator()(const int &a, const int &b) const {
return a > b;
}
};
int main() {
multiset<int, DescendingOrder> ms = {10, 20, 15, 5};
cout << "Elements in descending order: ";
for (const auto &val : ms) {
cout << val << " ";
}
cout << endl;
return 0;
}
Output:
Elements in descending order: 20 15 10 5
10. Clearing the Multiset
The clear function removes all elements from the multiset, making it empty.
#include <iostream>
#include <set>
using namespace std;
int main() {
multiset<int> ms = {10, 20, 10, 15};
cout << "Size before clear: " << ms.size() << endl;
// Clear the multiset
ms.clear();
cout << "Size after clear: " << ms.size() << endl;
return 0;
}
Output:
Size before clear: 4 Size after clear: 0
Summary Table of multiset Operations
| Operation | Code Example | Description |
|---|---|---|
| Initialize | multiset<int> ms = {10, 20}; | Creates a multiset with initial values |
| Insert element | ms.insert(10); | Inserts an element (allows duplicates) |
| Count elements | ms.count(10); | Counts occurrences of a specific value |
| Remove element | ms.erase(10); | Removes all occurrences of a specific value |
| Find element | ms.find(10); | Finds the first occurrence of a specific value |
| Equal range | auto range = ms.equal_range(10); | Accesses all occurrences of a specific value |
| Lower bound | ms.lower_bound(15); | Returns the first element not less than the given value |
| Upper bound | ms.upper_bound(15); | Returns the first element greater than the given value |
| Custom comparator | multiset<int, CustomComparator> ms; | Creates a multiset with custom sorting order |
| Clear | ms.clear(); | Removes all elements from the multiset |
Complete Example
This example demonstrates initializing a multiset, inserting elements with duplicates, accessing and removing elements, counting occurrences, and iterating over elements.
#include <iostream>
#include <set>
using namespace std;
int main() {
multiset<int> ms;
// Insert elements with duplicates
ms.insert(10);
ms.insert(20);
ms.insert(10);
ms.insert(15);
ms.insert(20);
// Count occurrences of 10 and 20
cout << "Count of 10: " << ms.count(10) << endl;
cout << "Count of 20: " << ms.count(20) << endl;
// Access all occurrences of 20
auto range = ms.equal_range(20);
cout << "All occurrences of 20: ";
for (auto it = range.first; it != range.second; ++it) {
cout << *it << " ";
}
cout << endl;
// Remove all occurrences of 10
ms.erase(10);
// Display remaining elements
cout << "Elements after removing 10: ";
for (const auto &val : ms) {
cout << val << " ";
}
cout << endl;
return 0;
}
Sample Output:
Count of 10: 2 Count of 20: 2 All occurrences of 20: 20 20 Elements after removing 10: 15 20 20
Key Takeaways
- multiset is an associative container that stores elements in sorted order and allows duplicates.
- Use insert, count, erase, find, equal_range, and lower_bound / upper_bound for common operations.
- Custom comparators allow for custom sorting orders, while iterators provide flexible traversal.
- Ideal for cases where you need sorted data that permits duplicates, like managing collections of repeated values.