Приведи пример использования multiset

Приведи пример использования multiset

std::multiset — это контейнер, который хранит отсортированные элементы и разрешает дубликаты. Это критичный инструмент для многих backend задач, где нужна упорядоченность и возможность повторений.

Основное отличие от set

#include <set>
#include <multiset>
#include <iostream>

int main() {
    // std::set — уникальные элементы
    std::set<int> unique_nums;
    unique_nums.insert(5);
    unique_nums.insert(5);  // Дубликат не добавляется
    std::cout << unique_nums.size() << std::endl;  // Выведет: 1
    
    // std::multiset — разрешены дубликаты
    std::multiset<int> all_nums;
    all_nums.insert(5);
    all_nums.insert(5);  // Добавляется
    std::cout << all_nums.size() << std::endl;  // Выведет: 2
    
    return 0;
}

Практический пример 1: Система рейтинга

В высоконагруженной системе множество пользователей имеют одинаковый рейтинг. Нам нужно быстро найти пользователей в определённом диапазоне рейтингов:

#include <multiset>
#include <string>
#include <iostream>

struct Player {
    std::string name;
    int rating;
    
    // Оператор сравнения для автоматической сортировки
    bool operator<(const Player& other) const {
        if (rating != other.rating) {
            return rating > other.rating;  // По убыванию рейтинга
        }
        return name < other.name;  // При равном рейтинге - по имени
    }
    
    bool operator==(const Player& other) const {
        return name == other.name && rating == other.rating;
    }
};

int main() {
    std::multiset<Player> leaderboard;
    
    // Добавляем игроков (многие имеют одинаковый рейтинг)
    leaderboard.insert({"Alice", 3500});
    leaderboard.insert({"Bob", 3500});
    leaderboard.insert({"Charlie", 3200});
    leaderboard.insert({"David", 3200});
    leaderboard.insert({"Eve", 3200});
    leaderboard.insert({"Frank", 2800});
    
    // Быстрый поиск: находим всех игроков с рейтингом 3200
    Player search_key{"Dummy", 3200};
    auto range = leaderboard.equal_range(search_key);
    
    std::cout << "Players with rating 3200:\n";
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << "  " << it->name << " (" << it->rating << ")\n";
    }
    
    // Быстрое удаление всех игроков с рейтингом 3200
    leaderboard.erase(range.first, range.second);
    
    std::cout << "\nRemaining players: " << leaderboard.size() << std::endl;
    
    return 0;
}

Output:

Players with rating 3200:
  Charlie (3200)
  David (3200)
  Eve (3200)

Remaining players: 3

Практический пример 2: Приоритетная очередь с дубликатами

В backend системе приходят события разной важности. Нужно обработать важные события раньше, но при равной важности - в порядке прихода:

#include <multiset>
#include <chrono>
#include <iostream>
#include <iomanip>

struct Event {
    int priority;  // 1 = высокий, 10 = низкий
    long timestamp;  // Время события
    std::string description;
    
    // Сортировка: сначала по приоритету, потом по времени
    bool operator<(const Event& other) const {
        if (priority != other.priority) {
            return priority < other.priority;  // Меньший номер = выше приоритет
        }
        return timestamp < other.timestamp;  // Раньше по времени
    }
};

class EventQueue {
private:
    std::multiset<Event> events;
    
public:
    void add_event(const Event& event) {
        events.insert(event);
        std::cout << "Event added: " << event.description << std::endl;
    }
    
    Event get_next_event() {
        if (events.empty()) {
            throw std::runtime_error("Queue is empty");
        }
        Event next = *events.begin();  // Первый элемент - наивысший приоритет
        events.erase(events.begin());
        return next;
    }
    
    size_t size() const {
        return events.size();
    }
};

int main() {
    EventQueue queue;
    
    long t1 = 1000, t2 = 2000, t3 = 3000;
    
    queue.add_event({5, t1, "Database backup"});
    queue.add_event({1, t2, "Critical error - server down"});
    queue.add_event({5, t3, "Log rotation"});
    queue.add_event({1, t1, "Authentication failure"});  // Раньше, но всё равно высокий приоритет
    
    std::cout << "\nProcessing events in priority order:\n";
    while (queue.size() > 0) {
        Event e = queue.get_next_event();
        std::cout << "[Priority " << e.priority << "] " << e.description << std::endl;
    }
    
    return 0;
}

Output:

Event added: Database backup
Event added: Critical error - server down
Event added: Log rotation
Event added: Authentication failure

Processing events in priority order:
[Priority 1] Authentication failure
[Priority 1] Critical error - server down
[Priority 5] Database backup
[Priority 5] Log rotation

Практический пример 3: Отслеживание задержек в сети

Система мониторинга отслеживает задержки между миллионами пакетов. Нужна быстрая статистика:

#include <multiset>
#include <vector>
#include <iostream>
#include <numeric>

class LatencyMonitor {
private:
    std::multiset<int> latencies;  // Миллисекунды
    const int MAX_SAMPLES = 10000;
    
public:
    void record_latency(int ms) {
        latencies.insert(ms);
        
        // Ограничиваем размер (sliding window)
        if (latencies.size() > MAX_SAMPLES) {
            latencies.erase(latencies.begin());
        }
    }
    
    // Быстрый поиск медианы (контейнер отсортирован!)
    double get_median() const {
        if (latencies.empty()) return 0;
        
        auto it = latencies.begin();
        std::advance(it, latencies.size() / 2);
        
        if (latencies.size() % 2 == 1) {
            return *it;
        }
        
        // Среднее двух средних элементов
        int mid1 = *it;
        --it;
        int mid2 = *it;
        return (mid1 + mid2) / 2.0;
    }
    
    // Процентиль (p95, p99)
    int get_percentile(double p) const {
        if (latencies.empty()) return 0;
        
        int index = (latencies.size() * p) / 100.0;
        auto it = latencies.begin();
        std::advance(it, index);
        return *it;
    }
    
    void print_stats() const {
        if (latencies.empty()) {
            std::cout << "No data\n";
            return;
        }
        
        std::cout << "Latency Statistics:\n";
        std::cout << "  Min: " << *latencies.begin() << " ms\n";
        std::cout << "  Max: " << *latencies.rbegin() << " ms\n";
        std::cout << "  Median: " << get_median() << " ms\n";
        std::cout << "  P95: " << get_percentile(95) << " ms\n";
        std::cout << "  P99: " << get_percentile(99) << " ms\n";
    }
};

int main() {
    LatencyMonitor monitor;
    
    // Симулируем данные
    std::vector<int> sample_latencies = {
        10, 12, 11, 15, 14, 20, 18, 25, 30, 50,
        12, 14, 16, 100, 45, 35, 22, 18, 19, 21
    };
    
    for (int lat : sample_latencies) {
        monitor.record_latency(lat);
    }
    
    monitor.print_stats();
    
    return 0;
}

Практический пример 4: Система кэширования LRU

Кэш с вытеснением наименее используемых элементов:

#include <multiset>
#include <unordered_map>
#include <string>

struct CacheEntry {
    std::string key;
    int access_count;
    long last_access_time;
    
    bool operator<(const CacheEntry& other) const {
        // Сортируем по редкости использования
        if (access_count != other.access_count) {
            return access_count < other.access_count;  // Реже используемые первыми
        }
        return last_access_time < other.last_access_time;  // Потом по времени
    }
};

class LRUCache {
private:
    std::multiset<CacheEntry> usage_tracker;
    std::unordered_map<std::string, std::string> cache;
    const size_t MAX_SIZE = 1000;
    
public:
    void put(const std::string& key, const std::string& value) {
        cache[key] = value;
        
        // Добавляем в tracker
        usage_tracker.insert({
            key,
            1,  // access_count
            std::chrono::duration_cast<std::chrono::milliseconds>(
                std::chrono::system_clock::now().time_since_epoch()
            ).count()
        });
        
        // Если превышен размер, удаляем наименее используемый
        if (cache.size() > MAX_SIZE) {
            std::string lru_key = usage_tracker.begin()->key;
            cache.erase(lru_key);
            usage_tracker.erase(usage_tracker.begin());
        }
    }
    
    std::string get(const std::string& key) {
        if (cache.find(key) != cache.end()) {
            // Обновляем счётчик (симплифицировано для примера)
            return cache[key];
        }
        throw std::runtime_error("Key not found");
    }
};

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

Используйте multiset когда:

• Нужны отсортированные элементы с дубликатами
• Часто нужны операции поиска/удаления по значению
• Нужна сложная сортировка с несколькими критериями
• Нужны операции вроде lower_bound/upper_bound

Альтернативы:

• multimap — для пар ключ-значение с дубликатами ключей
• priority_queue — если нужна только очередь с приоритетом
• std::vector + std::sort — если нужна модификация (быстрее для малых наборов)

Сложность операций

std::multiset — мощный инструмент для backend разработки, обеспечивающий эффективность и удобство работы с отсортированными наборами данных с дубликатами.