Ответ
std::multiset — это ассоциативный контейнер из стандартной библиотеки C++, который хранит элементы в отсортированном порядке и допускает дубликаты ключей. Он обычно реализован на основе самобалансирующегося бинарного дерева поиска (например, красно-черного дерева).
Ключевые характеристики:
- Дубликаты: В отличие от
std::set, может содержать несколько экземпляров одного и того же значения. - Автоматическая сортировка: Элементы всегда хранятся в порядке, заданном функцией сравнения (по умолчанию —
std::less<Key>). - Сложность операций: Вставка, удаление и поиск выполняются за логарифмическое время — O(log n).
- Изменение элементов: Нельзя напрямую модифицировать значение через итератор, так как это может нарушить порядок. Нужно удалить старый элемент и вставить новый.
Пример использования:
#include <iostream>
#include <set>
int main() {
// Создание и инициализация multiset
std::multiset<int> numbers = {5, 2, 8, 2, 5, 3};
// Вставка новых элементов (дубликаты разрешены)
numbers.insert(8);
numbers.insert(1);
// Вывод всех элементов (будут отсортированы)
for (const auto& num : numbers) {
std::cout << num << ' '; // 1 2 2 3 5 5 8 8
}
std::cout << 'n';
// Подсчёт количества вхождений конкретного значения
std::cout << "Count of 5: " << numbers.count(5) << 'n'; // 2
// Нахождение диапазона элементов с заданным ключом
auto [lower, upper] = numbers.equal_range(2);
std::cout << "Range for value 2: ";
for (auto it = lower; it != upper; ++it) {
std::cout << *it << ' '; // 2 2
}
return 0;
}Типичные сценарии применения: хранение отсортированных данных с повторениями, реализация приоритетных очередей с возможностью одинаковых приоритетов, сбор статистики (например, частоты встречаемости значений).
