📦 STL Контейнери: Пълно ръководство

Standard Template Library (STL) в C++ предоставя мощни структури от данни, които са оптимизирани, тествани и готови за употреба. Познаването на техните характеристики и сложност е задължително за всеки състезател.

1. Последователни контейнери (Sequence Containers)

1.1. `std::vector` (Динамичен масив)

Най-използваният контейнер. Пази елементите последователно в паметта. * Достъп: \(O(1)\) чрез v[i]. * Push Back: \(O(1)\) амортизирано (понякога преалокира памет). * Insert/Erase (по средата): \(O(N)\) (бавно!). * Размер: v.size(), v.empty().

vector<int> v = {1, 2, 3};
v.push_back(4);
v.pop_back(); // Маха последния
sort(v.begin(), v.end()); // Сортиране

1.2. `std::deque` (Double Ended Queue)

Позволява добавяне/махане и от двата края за \(O(1)\). * Не гарантира последователност в паметта (състои се от чанки). * Малко по-бавен достъп [] от vector, но по-бърз push_front.

deque<int> d;
d.push_front(1);
d.push_back(2);

1.3. `std::list` (Двойно свързан списък)

Позволява \(O(1)\) insert/erase навсякъде, ако имате итератор. * Бавен достъп: \(O(N)\) за стигане до k-тия елемент. * Рядко се ползва в състезания, освен за специфични задачи (напр. LRU Cache).

2. Асоциативни контейнери (Sorted Associative Containers)

Поддържат елементите сортирани. Реализирани са чрез Червено-черни дървета (Self-balancing BST).

2.1. `std::set` (Множество)

Пази уникални елементи в сортиран ред. * Insert/Erase/Find: \(O(\log N)\). * Iterate: В сортиран ред.

set<int> s;
s.insert(5);
s.insert(3);
s.insert(5); // Няма ефект, 5 вече го има
if (s.count(3)) cout << "Found";

2.2. `std::map` (Речник / Асоциативен масив)

Пази двойки (key, value), сортирани по ключ. * Достъп: m[key] връща референция към стойността (създава я, ако я няма, с default стойност 0/empty). * Сложност: \(O(\log N)\) за всички операции.

map<string, int> scores;
scores["Ivan"] = 100;
scores["Ana"] = 95;
for (auto& p : scores) {
    cout << p.first << ": " << p.second << endl; // Ana: 95, Ivan: 100
}

2.3. `multiset` / `multimap`

Позволяват дублиращи се ключове. * s.erase(val) изтрива всички инстанции на val. * s.erase(s.find(val)) изтрива само една инстанция.

3. Неподредени контейнери (Unordered Associative Containers)

Базирани на Хеш таблици. Елементите са в произволен ред.

3.1. `std::unordered_set` / `std::unordered_map`

Сложност: \(O(1)\) средно, но \(O(N)\) в най-лошия случай (колизии).
Важно: В Codeforces има "анти-хеш" тестове, които правят тези контейнери бавни (\(O(N^2)\) общо). Използвайте custom hash функция (виж Тема 09b).

4. Адаптери (Container Adapters)

4.1. `std::stack` (Стек - LIFO)

push(), pop(), top(). Всичко е \(O(1)\).
Ползва се за DFS, проверка на скоби, Shunting-yard.

4.2. `std::queue` (Опашка - FIFO)

push(), pop(), front(). Всичко е \(O(1)\).
Ползва се за BFS.

4.3. `std::priority_queue` (Приоритетна опашка / Heap)

Винаги дава най-големия елемент (top()). * Push/Pop: \(O(\log N)\). * Top: \(O(1)\). * За Min-Heap: priority_queue<int, vector<int>, greater<int>> pq;

5. Специални контейнери

5.1. `std::bitset`

Оптимизиран масив от битове. Заема 1 бит на елемент (8 пъти по-малко от bool или vector<bool>). * Поддържа побитови операции (&, |, ^, ~, <<, >>) върху целия масив. * Изключително бърз за задачи с множество (Knapsack, subset sum). * Размерът трябва да е константа при компилация: bitset<1000> b;.

bitset<8> b("10101010");
b[0] = 0; // Променя най-десния бит (индексиране отзад напред!)
cout << b.count(); // Брой единици

5.2. `std::pair` и `std::tuple`

Удобни за групиране на данни без създаване на struct. * Сравняват се лексикографски автоматично.

pair<int, int> p = {1, 2};
vector<pair<int, int>> v; // Често ползвано за графи (съсед, тегло)

6. Итератори

Итераторите са "умни указатели", които позволяват обхождане на контейнери. * begin(): сочи към първия елемент. * end(): сочи след последния елемент. * rbegin(), rend(): за обратно обхождане.

vector<int>::iterator it = v.begin();
auto it2 = v.find(x); // За set/map
if (it2 != v.end()) { /* намерено */ }

7. Практически примери и задачи

7.1. Задача: Брой уникални думи в текст

Използвайте set за автоматично премахване на дубликати.

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

int main() {
    std::set<std::string> uniqueWords;
    std::string word;

    while (std::cin >> word) {
        uniqueWords.insert(word);
    }

    std::cout << "Брой уникални думи: " << uniqueWords.size() << std::endl;

    return 0;
}

7.2. Задача: Честота на думи

Използвайте map за броене на срещанията.

#include <iostream>
#include <map>
#include <string>

int main() {
    std::map<std::string, int> wordCount;
    std::string word;

    while (std::cin >> word) {
        wordCount[word]++;
    }

    // Намиране на най-честата дума
    std::string mostFrequent;
    int maxCount = 0;

    for (const auto& p : wordCount) {
        if (p.second > maxCount) {
            maxCount = p.second;
            mostFrequent = p.first;
        }
    }

    std::cout << "Най-честа дума: " << mostFrequent << " (" << maxCount << " пъти)" << std::endl;

    return 0;
}

7.3. Задача: Проверка за анаграми

Две думи са анаграми, ако съдържат едни и същи букви с еднаква честота.

#include <iostream>
#include <map>
#include <string>

bool areAnagrams(const std::string& s1, const std::string& s2) {
    if (s1.length() != s2.length()) return false;

    std::map<char, int> freq1, freq2;

    for (char c : s1) freq1[c]++;
    for (char c : s2) freq2[c]++;

    return freq1 == freq2;
}

int main() {
    std::string word1 = "listen";
    std::string word2 = "silent";

    if (areAnagrams(word1, word2)) {
        std::cout << "Думите са анаграми" << std::endl;
    } else {
        std::cout << "Думите не са анаграми" << std::endl;
    }

    return 0;
}

7.4. Задача: K-тото най-голямо число

Използвайте priority_queue за ефективно намиране.

#include <iostream>
#include <queue>
#include <vector>

int findKthLargest(std::vector<int>& nums, int k) {
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

    for (int num : nums) {
        minHeap.push(num);
        if (minHeap.size() > k) {
            minHeap.pop();
        }
    }

    return minHeap.top();
}

int main() {
    std::vector<int> nums = {3, 2, 1, 5, 6, 4};
    int k = 2;

    std::cout << k << "-то най-голямо число е: " << findKthLargest(nums, k) << std::endl; // 5

    return 0;
}

7.5. Задача: Проверка за балансирани скоби

Използвайте stack за проверка дали скобите са балансирани.

#include <iostream>
#include <stack>
#include <string>

bool isBalanced(const std::string& str) {
    std::stack<char> s;

    for (char c : str) {
        if (c == '(' || c == '[' || c == '{') {
            s.push(c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (s.empty()) return false;

            char top = s.top();
            s.pop();

            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{')) {
                return false;
            }
        }
    }

    return s.empty();
}

int main() {
    std::string expr = "{[()]}";

    if (isBalanced(expr)) {
        std::cout << "Скобите са балансирани" << std::endl;
    } else {
        std::cout << "Скобите НЕ са балансирани" << std::endl;
    }

    return 0;
}

7.6. Задача: Sliding Window Maximum

Намерете максимума във всеки прозорец от размер K.

#include <iostream>
#include <deque>
#include <vector>

std::vector<int> maxSlidingWindow(const std::vector<int>& nums, int k) {
    std::deque<int> dq; // Съхранява индекси
    std::vector<int> result;

    for (int i = 0; i < nums.size(); i++) {
        // Премахва елементи извън прозореца
        if (!dq.empty() && dq.front() <= i - k) {
            dq.pop_front();
        }

        // Премахва по-малки елементи от края
        while (!dq.empty() && nums[dq.back()] < nums[i]) {
            dq.pop_back();
        }

        dq.push_back(i);

        // Добавя резултат след първите k-1 елемента
        if (i >= k - 1) {
            result.push_back(nums[dq.front()]);
        }
    }

    return result;
}

int main() {
    std::vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;

    std::vector<int> result = maxSlidingWindow(nums, k);

    std::cout << "Максимуми в прозорци: ";
    for (int num : result) {
        std::cout << num << " "; // 3 3 5 5 6 7
    }
    std::cout << std::endl;

    return 0;
}

8. Допълнителни съвети за състезателно програмиране

8.1. Избор на правилния контейнер

Операция	Препоръчителен контейнер	Сложност
Бърз достъп по индекс	`vector`	O(1)
Добавяне/махане от двата края	`deque`	O(1)
Уникални елементи, сортирани	`set`	O(log n)
Ключ-стойност, сортирани	`map`	O(log n)
Бързо търсене (несортирани)	`unordered_set`	O(1) средно
Приоритетна опашка	`priority_queue`	O(log n)
LIFO операции	`stack`	O(1)
FIFO операции	`queue`	O(1)

8.2. Често срещани грешки

Грешка 1: Модификация по време на итерация

// ГРЕШНО!
for (auto x : s) {
    s.erase(x); // Undefined behavior!
}

// ПРАВИЛНО
while (!s.empty()) {
    s.erase(s.begin());
}

Грешка 2: Достъп до несъществуващ ключ в `map`

std::map<std::string, int> m;
// m["Ivan"] създава елемент със стойност 0, ако не съществува!

// По-безопасно:
if (m.count("Ivan")) {
    std::cout << m["Ivan"];
} else {
    std::cout << "Няма такъв ключ";
}

// Или използвайте find:
auto it = m.find("Ivan");
if (it != m.end()) {
    std::cout << it->second;
}

Грешка 3: Използване на `unordered_map` без custom hash

В състезания може да има специално създадени тестове, които водят до колизии.

// По-безопасно е да използвате обикновен map
std::map<long long, int> m; // Винаги работи добре

// Или добавете custom hash:
struct CustomHash {
    size_t operator()(long long x) const {
        return x ^ (x >> 16);
    }
};
std::unordered_map<long long, int, CustomHash> m;

8.3. Оптимизации

Резервиране на памет за `vector`

std::vector<int> v;
v.reserve(1000000); // Избягва множество реалокации
for (int i = 0; i < 1000000; i++) {
    v.push_back(i);
}

Използване на `emplace` вместо `push`

std::vector<std::pair<int, int>> v;
v.emplace_back(1, 2); // По-бързо от v.push_back({1, 2})

🏁 Заключение

За масив с фиксиран размер/индексиране -> vector.
За търсене/уникалност -> set или unordered_set.
За ключове/стойности -> map.
За BFS -> queue.
За DFS/проверка на скоби -> stack.
За Dijkstra/Prim -> priority_queue.
За битови маски -> bitset.

Познаването на STL контейнерите и тяхната сложност е задължително за всеки състезател. Практикувайте редовно с различни задачи, за да развиете интуиция кой контейнер да използвате в различни ситуации. Винаги помнете за времевата и паметовата сложност на операциите. Комбинирайте различни контейнери, за да решавате сложни задачи ефективно.

📦 STL Контейнери: Пълно ръководство

1. Последователни контейнери (Sequence Containers)

1.1. std::vector (Динамичен масив)

1.2. std::deque (Double Ended Queue)

1.3. std::list (Двойно свързан списък)