CKTIS / C++
std::multiset — an ordered container with duplicates
std::multiset from <set> stores keys in comparator-defined order and permits equivalent keys. Learn how lookup and counting work, and distinguish removing one element from removing every equivalent element.
Version: C++23; repository compiler flag, production runtime not attested
Syntax
#include <set>
std::multiset<Key, Compare, Allocator> values;
// Defaults: Compare = std::less<Key>, Allocator = std::allocator<Key>std::multiset<Key, Compare, Allocator> from <set> is an ordered associative container: each element is itself a key. Unlike std::set, it permits multiple equivalent keys. The default std::less<Key> gives ascending order for numbers; iteration visits elements in comparator order.
Compare must define a strict weak ordering. Keys a and b are equivalent when !comp(a, b) && !comp(b, a), which need not mean a == b. Elements cannot be modified through iterators. To change a key, you can erase the element and insert a new one. Iterators are bidirectional, not random access.
For N elements, ordinary insertion and find, lower_bound, and upper_bound take O(log N). find returns one matching element or end(); count counts all equivalents, and equal_range identifies their range [first, last). Counting takes O(log N + K), where K is the number of matches.
Warning: erase(key) removes all equivalent elements and returns their count. erase(it) removes only the indicated element; passing end() is invalid. Insertion does not invalidate iterators or references, while erasure invalidates only those referring to erased elements.
The example targets compilation with -std=c++23; production runtime behavior is not attested. The source is an evolving working draft, not a frozen C++23 publication; this entry does not apply its newer constexpr declarations to C++23.
Examples
#include <iostream>
#include <set>
int main() {
std::multiset<int> values{3, 1, 3, 2};
values.insert(3);
std::cout << "count: " << values.count(3) << '\n';
auto it = values.find(3);
if (it != values.end()) {
values.erase(it);
}
std::cout << "after one: " << values.count(3) << '\n';
auto removed = values.erase(3);
std::cout << "removed: " << removed << '\n';
std::cout << "remaining:";
for (int value : values) {
std::cout << ' ' << value;
}
std::cout << '\n';
}
Result
count: 3 after one: 2 removed: 2 remaining: 1 2
The displayed code and declared result were verified in an isolated environment using the method recorded in the verification evidence for this exact version.