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
Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.