Что такое multiset?

Что такое multiset?

std::multiset — это упорядоченный ассоциативный контейнер STL, похожий на std::set, но с одним ключевым отличием: он позволяет хранить несколько элементов с одинаковыми значениями. Элементы автоматически хранятся в отсортированном порядке.

Основные характеристики

1. Упорядоченность

Все элементы автоматически хранятся в отсортированном порядке в соответствии с компаратором (по умолчанию — оператор <).

2. Дубликаты допускаются

В отличие от set, multiset позволяет иметь несколько элементов с одинаковыми значениями.

3. Внутренняя реализация

Обычно реализуется как красно-чёрное дерево (Red-Black Tree), что даёт:

• Вставка: O(log n)
• Удаление: O(log n)
• Поиск: O(log n)
• Итерация: O(n)

4. Итераторы

Двусторонние итераторы (bidirectional), позволяют двигаться вперёд и назад, но не поддерживают случайный доступ.

Синтаксис создания

#include <set>

// Пустой multiset с дефолтным компаратором (operator<)
std::multiset<int> ms;

// С инициализацией
std::multiset<int> ms = {5, 3, 8, 3, 1, 8};

// С кастомным компаратором (убывающий порядок)
std::multiset<int, std::greater<int>> ms_desc = {5, 3, 8};

// С кастомной функцией сравнения
auto cmp = [](int a, int b) { return a > b; };
std::multiset<int, decltype(cmp)> ms_lambda(cmp);

Основные операции

1. Вставка элементов

std::multiset<int> ms;

// Вставка одного элемента
ms.insert(10);
ms.insert(5);
ms.insert(10);  // Дубликат разрешён!
ms.insert(15);

// Вставка диапазона
std::vector<int> vec = {7, 3, 7};
ms.insert(vec.begin(), vec.end());

// Результат: {3, 5, 7, 7, 10, 10, 15}

2. Поиск и подсчёт

std::multiset<int> ms = {1, 2, 2, 3, 3, 3, 4};

// find() — возвращает итератор на первое вхождение
auto it = ms.find(3);
if (it != ms.end()) {
    std::cout << "Found: " << *it << "\n";  // 3
}

// count() — количество элементов с заданным значением
size_t count = ms.count(3);
std::cout << "Count of 3: " << count << "\n";  // 3

// count() для 2
std::cout << "Count of 2: " << ms.count(2) << "\n";  // 2

// count() для несуществующего элемента
std::cout << "Count of 5: " << ms.count(5) << "\n";  // 0

3. Диапазонные операции

std::multiset<int> ms = {1, 2, 2, 3, 3, 3, 4, 5};

// equal_range() — пара итераторов [begin, end) для всех элементов со значением
auto range = ms.equal_range(3);
std::cout << "Elements with value 3: ";
for (auto it = range.first; it != range.second; ++it) {
    std::cout << *it << " ";
}
std::cout << "\n";  // 3 3 3

// lower_bound() — итератор на первый элемент >= value
auto lower = ms.lower_bound(3);
std::cout << "Lower bound of 3: " << *lower << "\n";  // 3

// upper_bound() — итератор на первый элемент > value
auto upper = ms.upper_bound(3);
std::cout << "Upper bound of 3: " << *upper << "\n";  // 4

4. Удаление элементов

std::multiset<int> ms = {1, 2, 2, 3, 3, 3, 4};

// Удалить одно вхождение по итератору
ms.erase(ms.find(2));  // Удаляет только первое 2
// Результат: {1, 2, 3, 3, 3, 4}

// Удалить все элементы со значением
size_t removed = ms.erase(3);  // Удаляет все 3
std::cout << "Removed " << removed << " elements\n";  // 3
// Результат: {1, 2, 4}

// Удалить диапазон
ms.erase(ms.begin(), ms.end());  // Очистить весь multiset

5. Итерация

std::multiset<int> ms = {1, 2, 2, 3, 3, 3, 4};

// Прямая итерация (в порядке возрастания)
std::cout << "Forward: ";
for (int val : ms) {
    std::cout << val << " ";
}
std::cout << "\n";  // 1 2 2 3 3 3 4

// Обратная итерация (с reverse_iterator)
std::cout << "Reverse: ";
for (auto it = ms.rbegin(); it != ms.rend(); ++it) {
    std::cout << *it << " ";
}
std::cout << "\n";  // 4 3 3 3 2 2 1

Практические примеры использования

Пример 1: Подсчёт частоты элементов

#include <iostream>
#include <set>
#include <string>

int main() {
    std::multiset<std::string> words;
    
    std::string text[] = {"hello", "world", "hello", "cpp", "world", "hello"};
    for (const auto& word : text) {
        words.insert(word);
    }
    
    std::cout << "Word frequencies:\n";
    for (const auto& word : words) {
        std::cout << word << ": " << words.count(word) << "\n";
    }
    
    // Вывод:
    // cpp: 1
    // hello: 3
    // world: 2
    
    return 0;
}

Пример 2: Топ-10 худших ошибок

struct ErrorLog {
    int error_code;
    int frequency;
    
    bool operator<(const ErrorLog& other) const {
        // Сортируем по частоте (по убыванию), затем по коду
        if (frequency != other.frequency) {
            return frequency > other.frequency;
        }
        return error_code < other.error_code;
    }
};

int main() {
    std::multiset<ErrorLog> errors;
    
    errors.insert({404, 150});
    errors.insert({500, 45});
    errors.insert({403, 120});
    errors.insert({502, 30});
    
    int rank = 1;
    for (const auto& err : errors) {
        std::cout << rank++ << ". Error " << err.error_code 
                  << " (" << err.frequency << " times)\n";
    }
    
    // Вывод (по убыванию частоты):
    // 1. Error 404 (150 times)
    // 2. Error 403 (120 times)
    // 3. Error 500 (45 times)
    // 4. Error 502 (30 times)
    
    return 0;
}

Пример 3: Скользящее окно для вычисления медианы

#include <iostream>
#include <set>
#include <deque>

class MedianFinder {
    std::multiset<int> window;
    std::deque<int> data;
    int window_size;
    
public:
    MedianFinder(int size) : window_size(size) {}
    
    double add_and_get_median(int value) {
        data.push_back(value);
        window.insert(value);
        
        if (window.size() > window_size) {
            window.erase(window.find(data.front()));
            data.pop_front();
        }
        
        // Вычислить медиану
        auto it = window.begin();
        std::advance(it, window.size() / 2);
        
        if (window.size() % 2 == 1) {
            return *it;
        } else {
            --it;
            double median = *it;
            ++it;
            median = (median + *it) / 2.0;
            return median;
        }
    }
};

int main() {
    MedianFinder mf(3);  // Размер окна = 3
    
    std::cout << "Medians: ";
    for (int val : {1, 2, 3, 4, 5}) {
        std::cout << mf.add_and_get_median(val) << " ";
    }
    std::cout << "\n";  // 1 1.5 2 3 4
    
    return 0;
}

Отличие multiset от set

Когда использовать multiset

• Подсчёт частоты элементов без дополнительных структур
• Лидерборды и рейтинги с возможными дубликатами
• Топ-N элементов в отсортированном виде
• Медиана и квантили скользящего окна
• Логирование и аналитика с дубликатами
• Приоритетные очереди с возможностью нескольких элементов одного приоритета

Резюме: multiset — это мощный контейнер STL для работы с упорядоченными коллекциями элементов, где допускаются дубликаты, предоставляющий O(log n) операции поиска, вставки и удаления.