База знанияИзпитен център
BGБългарски
Избери език13

CKTIS / C++

std::multiset — подреден контейнер с дубликати

std::multiset от <set> съхранява ключове в реда, зададен от компаратора, и допуска еквивалентни ключове. Научете как работят търсенето и броенето и разграничете премахването на един елемент от премахването на всички еквивалентни елементи.

Версия: C++23; repository compiler flag, production runtime not attested

Синтаксис

#include <set>
std::multiset<Key, Compare, Allocator> values;
// Defaults: Compare = std::less<Key>, Allocator = std::allocator<Key>

std::multiset<Key, Compare, Allocator> от <set> е подреден асоциативен контейнер: всеки елемент е и ключ. За разлика от std::set, той допуска множество еквивалентни ключове. Стандартният std::less<Key> задава възходящ ред за числата; обхождането следва реда на компаратора.

Compare трябва да дефинира строго слабо подреждане. Ключовете a и b са еквивалентни, когато е изпълнено !comp(a, b) && !comp(b, a), което не означава непременно a == b. Елементите не могат да се променят чрез итератори. За да промените ключ, можете да изтриете елемента и да вмъкнете нов. Итераторите са двупосочни, а не с произволен достъп.

При N елемента обикновеното вмъкване и find, lower_bound и upper_bound имат сложност O(log N). find връща един съвпадащ елемент или end(); count брои всички еквивалентни елементи, а equal_range определя техния диапазон [first, last). Броенето има сложност O(log N + K), където K е броят на съвпаденията.

Внимание: erase(key) премахва всички еквивалентни елементи и връща броя им. erase(it) премахва само посочения елемент; подаването на end() е невалидно. Вмъкването не обезсилва итератори или препратки, докато изтриването обезсилва само тези, които се отнасят до изтритите елементи.

Примерът е предназначен за компилиране с -std=c++23; поведението при изпълнение в производствена среда не е потвърдено. Източникът е развиващ се работен проект на стандарт, а не окончателна публикация на C++23; този запис не прилага по-новите му декларации constexpr към C++23.

Примери

#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';
}

Резултат

count: 3
after one: 2
removed: 2
remaining: 1 2

Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.

Източници