Приведи пример, когда следует использовать std::set

Примеры использования std::set

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

Когда выбирать std::set

Требуется:

• Автоматическая уникальность элементов
• Отсортированный порядок
• Быстрый поиск O(log n)
• Итерирование в порядке сортировки

НЕ выбирай, если:

• Нужна максимальная скорость поиска → unordered_set
• Нужен произвольный доступ → vector
• Редко ищешь элементы → vector

Пример 1: Удаление дубликатов

#include <set>
#include <vector>
#include <iostream>

std::vector<int> removeDuplicates(const std::vector<int>& data) {
    std::set<int> uniqueSet(data.begin(), data.end());
    return std::vector<int>(uniqueSet.begin(), uniqueSet.end());
}

int main() {
    std::vector<int> nums = {3, 1, 4, 1, 5, 9, 2, 6, 5};
    auto result = removeDuplicates(nums);
    // Результат: [1, 2, 3, 4, 5, 6, 9] - отсортировано и уникально
    return 0;
}

Пример 2: Поиск пересечения двух массивов

#include <set>
#include <vector>
#include <algorithm>

std::vector<int> intersection(const std::vector<int>& a, 
                               const std::vector<int>& b) {
    std::set<int> setA(a.begin(), a.end());
    std::vector<int> result;
    
    for (int x : b) {
        if (setA.count(x)) {  // O(log n) поиск
            result.push_back(x);
            setA.erase(x);  // Избегаем дубликатов
        }
    }
    
    return result;
}

int main() {
    std::vector<int> nums1 = {1, 2, 2, 1};
    std::vector<int> nums2 = {2, 2};
    auto res = intersection(nums1, nums2);
    // Результат: [2]
    return 0;
}

Пример 3: LRU Кэш с таймаутом

#include <set>
#include <unordered_map>
#include <chrono>

struct CacheEntry {
    std::string key;
    std::string value;
    std::chrono::system_clock::time_point expiry;
    
    bool operator<(const CacheEntry& other) const {
        if (expiry != other.expiry) {
            return expiry < other.expiry;
        }
        return key < other.key;
    }
};

class ExpiringCache {
private:
    std::set<CacheEntry> expiryQueue;  // Отсортировано по времени
    std::unordered_map<std::string, std::string> data;
    
public:
    void set(const std::string& key, const std::string& value, int ttl_seconds) {
        auto expiry = std::chrono::system_clock::now() + 
                      std::chrono::seconds(ttl_seconds);
        data[key] = value;
        expiryQueue.insert({key, value, expiry});
    }
    
    void cleanup() {
        auto now = std::chrono::system_clock::now();
        while (!expiryQueue.empty() && 
               expiryQueue.begin()->expiry <= now) {
            data.erase(expiryQueue.begin()->key);
            expiryQueue.erase(expiryQueue.begin());
        }
    }
    
    std::string get(const std::string& key) {
        cleanup();
        auto it = data.find(key);
        return (it != data.end()) ? it->second : "";
    }
};

Пример 4: Граф конфликтов (для расраскраски)

#include <set>
#include <unordered_map>
#include <string>

class ConflictGraph {
private:
    // Для каждой переменной - set всех переменных, с которыми она конфликтует
    std::unordered_map<std::string, std::set<std::string>> conflicts;
    
public:
    void addConflict(const std::string& var1, const std::string& var2) {
        conflicts[var1].insert(var2);
        conflicts[var2].insert(var1);
    }
    
    bool hasConflict(const std::string& var1, const std::string& var2) {
        return conflicts[var1].count(var2) > 0;  // O(log n)
    }
    
    std::set<std::string> getConflicts(const std::string& var) {
        return conflicts[var];  // Автоматически отсортировано
    }
    
    void removeVariable(const std::string& var) {
        for (const auto& conflicting : conflicts[var]) {
            conflicts[conflicting].erase(var);  // O(log n)
        }
        conflicts.erase(var);
    }
};

int main() {
    ConflictGraph graph;
    graph.addConflict("x", "y");
    graph.addConflict("x", "z");
    graph.addConflict("y", "z");
    
    auto conflicts = graph.getConflicts("x");
    // Результат: отсортированное множество {"y", "z"}
    return 0;
}

Пример 5: Диапазонные запросы

#include <set>
#include <iostream>

int main() {
    std::set<int> scores = {10, 20, 30, 40, 50, 60, 70, 80, 90};
    
    // Найти все оценки в диапазоне [30, 70]
    auto lower = scores.lower_bound(30);  // >= 30
    auto upper = scores.upper_bound(70);  // > 70
    
    std::cout << "Оценки в диапазоне [30, 70]: ";
    for (auto it = lower; it != upper; ++it) {
        std::cout << *it << " ";  // 30 40 50 60 70
    }
    
    // Удалить все scores < 40
    auto it = scores.begin();
    while (it != scores.end() && *it < 40) {
        it = scores.erase(it);
    }
    
    return 0;
}

Производительность std::set

set vs unordered_set vs vector

std::set<int>           // Когда нужна сортировка и быстрый поиск
std::unordered_set<int> // Когда нужна максимальная скорость поиска (O(1))
std::vector<int>        // Когда нужен случайный доступ и итерирование

Практические советы

• Эффективен для small-to-medium data (< 1M элементов)
• Кэш-неэффективен для больших наборов (RB-tree разбросана в памяти)
• Используй reserve() если знаешь размер заранее (unordered_set only)
• Кастомные компараторы для сложного порядка сортировки

std::set — это универсальный инструмент для работы с уникальными отсортированными данными с гарантированной логарифмической сложностью операций.