Knowledge baseExam Center
ENEnglish
Choose language13

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.

Sources