std::multiset in C++: Sorted Collections That Allow Duplicates
What is std::multiset in C++: Sorted Collections That Allow Duplicates? std::multiset is an associative container that stores sorted elements where duplicate values are permitted. Calling erase(value) removes ALL occurrences of that...
How does std::multiset differ from std::set, and what happens when erasing duplicate elements?
Explanation & In-Depth Details
```text
MULTISET ORDERED SEQUENCE:
[ 10 ] ──► [ 20 ] ──► [ 20 ] ──► [ 20 ] ──► [ 30 ] ──► [ 40 ]
```
2. Erase Behavior Caution:
- `ms.erase(20)`: Deletes ALL three 20s!
- `ms.erase(ms.find(20))`: Deletes ONLY the first 20 found.
Code Example
#include <iostream>
#include <set>
int main() {
std::multiset<int> scores = {90, 75, 90, 85, 90, 60};
std::cout << "All Scores (Multiset): ";
for (int s : scores) std::cout << s << " ";
std::cout << "\n";
std::cout << "Count of 90s: " << scores.count(90) << "\n";
// 1. Remove ONLY ONE occurrence of 90
auto it = scores.find(90);
if (it != scores.end()) {
scores.erase(it); // Erase by iterator removes 1 item
}
std::cout << "After erasing single 90: ";
for (int s : scores) std::cout << s << " ";
std::cout << "\n";
// 2. Remove ALL occurrences of remaining 90s
scores.erase(90); // Erase by value removes all
std::cout << "After erasing all 90s: ";
for (int s : scores) std::cout << s << " ";
std::cout << "\n";
return 0;
}Interview Question & Tips
A: `erase(val)` removes every matching element with that value and returns the count of removed elements. `erase(iterator)` removes only the specific single node referenced by the iterator.
Q: How is `std::multiset` implemented?
A: Like `std::set`, it is typically implemented as a self-balancing Red-Black Tree where equivalent keys are linked together in the tree structure.
Best Practices
• Use `std::multiset` for tracking dynamic sliding-window medians and frequency counters.
• Use `.equal_range(val)` to iterate over all duplicates of a specific value efficiently.
This study reference for std::multiset in C++: Sorted Collections That Allow Duplicates is curated and verified against recognized curriculum benchmarks, peer-reviewed textbooks, and official technical documentation: