⚙️ Алгоритми в STL

Стандартната библиотека от шаблони (STL) е една от най-мощните функционалности на C++, предоставяща обширна колекция от алгоритми, които всеки състезател по програмиране трябва да овладее. Хедърът <algorithm> съдържа над 100 добре тествани, високо оптимизирани функции за работа с контейнери, правещи вашия код по-чист, по-бърз и по-малко податлив на грешки.

Разбирането и ефективното използване на STL алгоритмите е от решаващо значение за състезателното програмиране, защото: - Производителност: STL алгоритмите са оптимизирани от експерти и често превъзхождат ръчно написания код - Надеждност: Те са основно тествани и по-малко податливи на грешки - Четимост: Кодът, използващ STL алгоритми, е по-изразителен и по-лесен за разбиране - Спестяване на време: Писането на по-малко код означава повече време за решаване на проблеми

🔢 Алгоритми за сортиране и търсене

Функции за сортиране

`std::sort(begin, end, [comparator])`

Основният алгоритъм за сортиране със сложност \(O(N \log N)\) и обикновено използва оптимизирана имплементация на quicksort, heapsort или introsort.

#include <algorithm>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {5, 2, 8, 1, 9};

    // Сортиране във възходящ ред
    sort(v.begin(), v.end());
    // Резултат: {1, 2, 5, 8, 9}

    // Сортиране в низходящ ред с компаратор greater
    sort(v.begin(), v.end(), greater<int>());
    // Резултат: {9, 8, 5, 2, 1}

    // Персонализиран компаратор за двойки - сортиране по втори елемент
    vector<pair<int, int>> pairs = {{1, 5}, {2, 3}, {3, 7}};
    sort(pairs.begin(), pairs.end(), 
         [](const pair<int,int>& a, const pair<int,int>& b) {
             return a.second < b.second;
         });
    // Резултат: {{2,3}, {1,5}, {3,7}}

    return 0;
}

Важни съображения: - Не е стабилна (относителният ред на равните елементи не е гарантиран) - Работи с всеки контейнер с произволен достъп (vector, array, deque) - Изисква елементите да са сравними с оператор < или персонализиран компаратор

`std::stable_sort(begin, end, [comparator])`

Подобна на sort(), но гарантира стабилност - елементите, които са равни, запазват относителния си ред.

struct Student {
    string name;
    int grade;
};

vector<Student> students = {
    {"Alice", 85}, {"Bob", 90}, {"Charlie", 85}, {"David", 90}
};

// Първо сортиране по име
sort(students.begin(), students.end(), 
     [](const Student& a, const Student& b) { return a.name < b.name; });
// Alice, Bob, Charlie, David

// След това stable_sort по оценка - студенти с еднаква оценка запазват реда по име
stable_sort(students.begin(), students.end(),
            [](const Student& a, const Student& b) { return a.grade < b.grade; });
// Резултат: Alice(85), Charlie(85), Bob(90), David(90)
// Забележете Alice преди Charlie, Bob преди David

Времева сложност: \(O(N \log N)\) но може да използва повече памет от обикновеното sort.

`std::partial_sort(begin, middle, end)`

Когато ви трябват само най-малките (или най-големите) K елемента сортирани:

vector<int> v = {9, 5, 7, 1, 3, 8, 2, 6, 4};

// Вземи 3-те най-малки елемента в сортиран ред
partial_sort(v.begin(), v.begin() + 3, v.end());
// Първите 3 елемента: {1, 2, 3}, останалите: неопределен ред

// Времева сложност: O(N log K) където K = 3

Приложение: Намирането на топ K елементи е по-бързо от сортирането на всичко.

`std::nth_element(begin, nth, end)`

Частично сортира така че елементът на позиция nth да е на сортираната си позиция, всички елементи преди него да са по-малки или равни, а всички след него - по-големи или равни.

vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};

// Намери медиана
nth_element(v.begin(), v.begin() + v.size()/2, v.end());
int median = v[v.size()/2];

// Времева сложност: O(N) средно - много по-бързо от пълно сортиране!

Приложения: - Намиране на медиана в \(O(N)\) - Намиране на k-ти най-малък елемент - Разделяне на данни около пивот

Функции за двоично търсене

Всички функции за двоично търсене изискват диапазонът да е сортиран първо!

`std::binary_search(begin, end, value)`

Връща true ако стойността съществува в диапазона, false в противен случай.

vector<int> v = {1, 2, 3, 5, 8, 13, 21};

bool exists = binary_search(v.begin(), v.end(), 5);    // true
bool missing = binary_search(v.begin(), v.end(), 7);   // false

// Времева сложност: O(log N)

Ограничение: Само казва дали елементът съществува, но не и позицията му.

`std::lower_bound(begin, end, value)`

Връща итератор към първия елемент, който НЕ Е по-малък от стойността (т.е. \(\ge\) value).

vector<int> v = {1, 2, 2, 2, 5, 8, 8, 13};

auto it = lower_bound(v.begin(), v.end(), 2);
// Сочи към първата 2 на индекс 1

int index = it - v.begin();  // Вземи индекс: 1

auto it2 = lower_bound(v.begin(), v.end(), 7);
// Сочи към 8 (първи елемент >= 7)

Често използвани случаи:

// Брой срещания на стойност в сортиран масив
auto lb = lower_bound(v.begin(), v.end(), value);
auto ub = upper_bound(v.begin(), v.end(), value);
int count = ub - lb;

// Вмъкни стойност, запазвайки сортирания ред
v.insert(lower_bound(v.begin(), v.end(), value), value);

// Провери дали стойността съществува и вземи позиция
auto it = lower_bound(v.begin(), v.end(), value);
if (it != v.end() && *it == value) {
    // Намерена на позиция (it - v.begin())
}

`std::upper_bound(begin, end, value)`

Връща итератор към първия елемент, който е по-голям от стойността (т.е. \(>\) value).

vector<int> v = {1, 2, 2, 2, 5, 8, 8, 13};

auto it = upper_bound(v.begin(), v.end(), 2);
// Сочи към 5 (първи елемент > 2)

// Намери диапазон на равни елементи
auto lb = lower_bound(v.begin(), v.end(), 2);
auto ub = upper_bound(v.begin(), v.end(), 2);
// Диапазонът [lb, ub) съдържа всички 2-ки

`std::equal_range(begin, end, value)`

Връща двойка итератори [lower_bound, upper_bound) за дадената стойност.

vector<int> v = {1, 2, 2, 2, 5, 8};

auto range = equal_range(v.begin(), v.end(), 2);
// range.first = lower_bound, range.second = upper_bound
int count = range.second - range.first;  // 3 срещания

🛠️ Алгоритми за манипулация на данни

Модифициращи последователности

`std::reverse(begin, end)`

Обръща реда на елементите в диапазона.

vector<int> v = {1, 2, 3, 4, 5};
reverse(v.begin(), v.end());
// Резултат: {5, 4, 3, 2, 1}

string s = "hello";
reverse(s.begin(), s.end());
// Резултат: "olleh"

// Времева сложност: O(N)

`std::rotate(begin, middle, end)`

Ротира елементите така че middle да стане първи елемент.

vector<int> v = {1, 2, 3, 4, 5};
rotate(v.begin(), v.begin() + 2, v.end());
// Резултат: {3, 4, 5, 1, 2}

// Полезно за циклични измествания
// Ляво изместване с k позиции:
rotate(v.begin(), v.begin() + k, v.end());

// Дясно изместване с k позиции:
rotate(v.rbegin(), v.rbegin() + k, v.rend());

`std::unique(begin, end)`

Премахва последователни дублиращи се елементи. Връща итератор към нов край.

Критично: Трябва първо да сортирате, за да премахнете ВСИЧКИ дубликати!

vector<int> v = {1, 2, 2, 3, 2, 4, 4, 5};

// ГРЕШНО: Без сортиране
auto new_end = unique(v.begin(), v.end());
// Премахва само последователни дубликати: {1, 2, 3, 2, 4, 5}

// ПРАВИЛНО: Със сортиране
sort(v.begin(), v.end());
// {1, 2, 2, 2, 3, 4, 4, 5}
new_end = unique(v.begin(), v.end());
v.erase(new_end, v.end());  // Действително премахни елементите
// Резултат: {1, 2, 3, 4, 5}

// Идиома на един ред:
v.erase(unique(v.begin(), v.end()), v.end());

`std::fill(begin, end, value)` и `std::fill_n(begin, count, value)`

Присвоява стойност на всички елементи в диапазона.

vector<int> v(5);
fill(v.begin(), v.end(), 42);
// Резултат: {42, 42, 42, 42, 42}

int arr[10];
fill_n(arr, 10, -1);
// Всички елементи зададени на -1

`std::copy(begin, end, dest_begin)`

Копира елементи от един диапазон в друг.

vector<int> src = {1, 2, 3, 4, 5};
vector<int> dest(5);

copy(src.begin(), src.end(), dest.begin());
// dest = {1, 2, 3, 4, 5}

// Копирай на изход
copy(src.begin(), src.end(), ostream_iterator<int>(cout, " "));
// Отпечатва: 1 2 3 4 5

Алгоритми за пермутации

`std::next_permutation(begin, end)`

Трансформира диапазона в следващата лексикографски по-голяма пермутация. Връща true ако е успешно, false ако е вече на последната пермутация.

vector<int> v = {1, 2, 3};

do {
    for(int x : v) cout << x << " ";
    cout << "\n";
} while(next_permutation(v.begin(), v.end()));

// Изход:
// 1 2 3
// 1 3 2
// 2 1 3
// 2 3 1
// 3 1 2
// 3 2 1

Важно за състезателно програмиране:

// Генерирай всички пермутации на низ
string s = "ABC";
sort(s.begin(), s.end());  // Трябва да започнете сортирани!
do {
    cout << s << "\n";
} while(next_permutation(s.begin(), s.end()));

// Брой пермутации до изпълнение на условие
int count = 0;
do {
    count++;
    // Провери някакво условие...
} while(next_permutation(v.begin(), v.end()));

`std::prev_permutation(begin, end)`

Подобна на next_permutation, но генерира предишна пермутация.

vector<int> v = {3, 2, 1};  // Започни от най-голямата

do {
    for(int x : v) cout << x << " ";
    cout << "\n";
} while(prev_permutation(v.begin(), v.end()));

📊 Математически и числови алгоритми

Намиране на екстремуми

`std::max_element(begin, end)` / `std::min_element(begin, end)`

Връща итератор към максималния/минималния елемент.

vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};

auto max_it = max_element(v.begin(), v.end());
cout << "Максимум: " << *max_it << "\n";           // 9
cout << "Позиция: " << (max_it - v.begin()) << "\n";  // 5

auto min_it = min_element(v.begin(), v.end());
cout << "Минимум: " << *min_it << "\n";           // 1

// Персонализиран компаратор за сложни типове
struct Point { int x, y; };
vector<Point> points = {{1, 2}, {3, 1}, {2, 5}};

auto furthest = max_element(points.begin(), points.end(),
    [](const Point& a, const Point& b) {
        return (a.x*a.x + a.y*a.y) < (b.x*b.x + b.y*b.y);
    });

`std::minmax_element(begin, end)`

Връща и минимум и максимум в един проход (по-ефективно).

vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};

auto [min_it, max_it] = minmax_element(v.begin(), v.end());
cout << "Мин: " << *min_it << ", Макс: " << *max_it << "\n";
// Мин: 1, Макс: 9

Числови операции (от `<numeric>`)

`std::accumulate(begin, end, init, [binary_op])`

Изчислява сума или персонализирана операция на свиване.

#include <numeric>

vector<int> v = {1, 2, 3, 4, 5};

// Сумирай всички елементи
int sum = accumulate(v.begin(), v.end(), 0);
// Резултат: 15

// Произведение на всички елементи
int product = accumulate(v.begin(), v.end(), 1, multiplies<int>());
// Резултат: 120

// Персонализирана операция - конкатенирай низове
vector<string> words = {"Hello", " ", "World"};
string sentence = accumulate(words.begin(), words.end(), string(""));
// Резултат: "Hello World"

// Сума на квадрати
int sum_of_squares = accumulate(v.begin(), v.end(), 0,
    [](int acc, int x) { return acc + x * x; });
// Резултат: 55

`std::partial_sum(begin, end, dest_begin)`

Изчислява префиксни суми (кумулативна сума).

vector<int> v = {1, 2, 3, 4, 5};
vector<int> prefix(5);

partial_sum(v.begin(), v.end(), prefix.begin());
// prefix = {1, 3, 6, 10, 15}

// Може и на място
partial_sum(v.begin(), v.end(), v.begin());

`std::iota(begin, end, start_value)`

Запълва диапазон с нарастващи стойности, започвайки от start_value.

vector<int> v(10);
iota(v.begin(), v.end(), 1);
// Резултат: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

// Създай масив от индекси
vector<int> indices(n);
iota(indices.begin(), indices.end(), 0);
// indices = {0, 1, 2, ..., n-1}

🔍 Алгоритми за търсене и заявки

`std::find(begin, end, value)`

Линейно търсене за стойност. Връща итератор към първото срещане или end ако не е намерена.

vector<int> v = {1, 2, 3, 4, 5};

auto it = find(v.begin(), v.end(), 3);
if (it != v.end()) {
    cout << "Намерена на позиция: " << (it - v.begin()) << "\n";
}

// Времева сложност: O(N) - използвайте binary_search за сортирани масиви!

`std::find_if(begin, end, predicate)`

Намира първия елемент, удовлетворяващ предиката.

vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8};

// Намери първо четно число
auto it = find_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; });
// Сочи към 2

// Намери първо число > 5
auto it2 = find_if(v.begin(), v.end(), [](int x) { return x > 5; });
// Сочи към 6

`std::count(begin, end, value)` / `std::count_if(begin, end, predicate)`

Брои срещанията на стойност или елементи, удовлетворяващи предиката.

vector<int> v = {1, 2, 2, 3, 2, 4, 5};

int count = count(v.begin(), v.end(), 2);
// Резултат: 3

int even_count = count_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; });
// Резултат: 4 (елементи: 2, 2, 2, 4)

`std::all_of`, `std::any_of`, `std::none_of`

Проверява дали предикатът е истина за всички/някои/никой от елементите.

vector<int> v = {2, 4, 6, 8, 10};

bool all_even = all_of(v.begin(), v.end(), [](int x) { return x % 2 == 0; });
// true

bool has_negative = any_of(v.begin(), v.end(), [](int x) { return x < 0; });
// false

bool no_odds = none_of(v.begin(), v.end(), [](int x) { return x % 2 == 1; });
// true

🎯 Операции с множества (върху сортирани диапазони)

Всички операции с множества изискват сортирани входни диапазони!

`std::set_union`, `std::set_intersection`, `std::set_difference`

vector<int> a = {1, 2, 3, 4, 5};
vector<int> b = {3, 4, 5, 6, 7};
vector<int> result;

// Обединение: всички елементи от двете (без дубликати)
set_union(a.begin(), a.end(), b.begin(), b.end(), back_inserter(result));
// result = {1, 2, 3, 4, 5, 6, 7}

result.clear();

// Сечение: общи елементи
set_intersection(a.begin(), a.end(), b.begin(), b.end(), back_inserter(result));
// result = {3, 4, 5}

result.clear();

// Разлика: елементи в a, но не в b
set_difference(a.begin(), a.end(), b.begin(), b.end(), back_inserter(result));
// result = {1, 2}

🚀 Разширени алгоритми

`std::partition(begin, end, predicate)`

Пренарежда елементите така че тези, удовлетворяващи предиката, да дойдат първи. Връща итератор към първия елемент, неудовлетворяващ предиката.

vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8};

auto pivot = partition(v.begin(), v.end(), [](int x) { return x % 2 == 0; });
// Възможен резултат: {2, 4, 6, 8, 1, 3, 5, 7}
// pivot сочи към 1

// Времева сложност: O(N)
// Не е стабилна - използвайте stable_partition за запазване на относителния ред

`std::transform(begin, end, dest_begin, unary_op)`

Прилага операция към всеки елемент и съхранява резултата.

vector<int> v = {1, 2, 3, 4, 5};
vector<int> squares(5);

transform(v.begin(), v.end(), squares.begin(), 
          [](int x) { return x * x; });
// squares = {1, 4, 9, 16, 25}

// Трансформация на място
transform(v.begin(), v.end(), v.begin(),
          [](int x) { return x * 2; });
// v = {2, 4, 6, 8, 10}

`std::remove(begin, end, value)` и `std::remove_if(begin, end, predicate)`

"Премахва" елементи като ги премества към края. Трябва да извикате erase() за действително изтриване!

vector<int> v = {1, 2, 3, 2, 4, 2, 5};

// Премахни всички 2-ки
auto new_end = remove(v.begin(), v.end(), 2);
v.erase(new_end, v.end());
// v = {1, 3, 4, 5}

// Идиома erase-remove (един ред):
v.erase(remove(v.begin(), v.end(), value), v.end());

// Премахни четни числа
v.erase(remove_if(v.begin(), v.end(), 
                  [](int x) { return x % 2 == 0; }), 
        v.end());

💡 Съвети за производителност и добри практики

1. Изберете правилния алгоритъм

// ЛОШО: O(N) линейно търсене в сортиран масив
vector<int> v = {1, 2, 3, ..., 1000000};  // сортиран
auto it = find(v.begin(), v.end(), target);  // O(N)

// ДОБРО: O(log N) двоично търсене
bool found = binary_search(v.begin(), v.end(), target);  // O(log N)

2. Избягвайте ненужни копия

// ЛОШО: Множество проходи
sort(v.begin(), v.end());
auto new_end = unique(v.begin(), v.end());
v.erase(new_end, v.end());

// ДОБРО: Комбинирани операции
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());

3. Използвайте подходящи контейнери

// Ако имате нужда от чести търсения: използвайте set/unordered_set вместо vector+sort
set<int> s;  // Автоматично сортиране, O(log N) търсене
unordered_set<int> us;  // O(1) средно търсене

4. Ламбда изрази за персонализирана логика

// Чисто и четимо
sort(students.begin(), students.end(),
     [](const Student& a, const Student& b) {
         return a.grade > b.grade;  // Сортирай по оценка низходящо
     });

🎓 Често срещани шаблони в състезателно програмиране

Шаблон 1: Сортиране + Двоично търсене

// Задача: Брой елементи в диапазон [L, R]
sort(v.begin(), v.end());
auto left = lower_bound(v.begin(), v.end(), L);
auto right = upper_bound(v.begin(), v.end(), R);
int count = right - left;

Шаблон 2: Сортиране + Уникални (Премахване на дубликати)

// Задача: Брой различни елементи
sort(v.begin(), v.end());
int distinct = unique(v.begin(), v.end()) - v.begin();

Шаблон 3: Сортиране + Два показалеца

// Задача: Намери двойка със сума равна на цел
sort(v.begin(), v.end());
int left = 0, right = n - 1;
while (left < right) {
    int sum = v[left] + v[right];
    if (sum == target) {
        // Намерена двойка
        break;
    } else if (sum < target) {
        left++;
    } else {
        right--;
    }
}

Шаблон 4: Префиксни суми

// Задача: Заявки за сума на диапазон
vector<int> prefix(n + 1, 0);
partial_sum(v.begin(), v.end(), prefix.begin() + 1);

// Сума на диапазон [L, R]
int range_sum = prefix[R + 1] - prefix[L];

Шаблон 5: Генериране и тестване на пермутации

// Задача: Намери пермутация, удовлетворяваща условие
sort(v.begin(), v.end());
do {
    if (check_condition(v)) {
        return true;
    }
} while(next_permutation(v.begin(), v.end()));

⚠️ Чести грешки

1. Забравяне на сортиране преди двоично търсене

vector<int> v = {5, 2, 8, 1, 9};
binary_search(v.begin(), v.end(), 5);  // ГРЕШНО! Недефинирано поведение!

sort(v.begin(), v.end());
binary_search(v.begin(), v.end(), 5);  // ПРАВИЛНО

2. Неизползване на erase след remove

remove(v.begin(), v.end(), value);  // Елементите все още са във вектора!
v.erase(remove(v.begin(), v.end(), value), v.end());  // ПРАВИЛНО

3. Модифициране на контейнер при итериране

// ГРЕШНО
for (auto it = v.begin(); it != v.end(); ++it) {
    if (*it == value) v.erase(it);  // Итераторът е невалиден!
}

// ПРАВИЛНО
v.erase(remove(v.begin(), v.end(), value), v.end());

🏁 Заключение

STL алгоритмите са основен инструмент в арсенала на всеки състезател по програмиране. Ключови изводи:

Не преоткривайте колелото: STL алгоритмите са тествани, оптимизирани и по-малко податливи на грешки от персонализирани имплементации
Знайте сложностите си: Разбирането на временната сложност помага да изберете правилния алгоритъм
Сортирайте първо: Много алгоритми изискват сортирани данни (двоично търсене, unique, операции с множества)
Използвайте ламбди: Те правят кода по-четим и позволяват персонализирана логика
Практикувайте често срещани шаблони: Сортиране+двоично търсене, идиома erase-remove, префиксни суми и др.

Овладейте тези алгоритми и ще пишете по-чист, по-бърз и по-надежден код в състезания. Спестеното време от избягване на грешки и имплементиране на оптимизирани решения може да бъде разликата между решаването на още една задача или не!

Бърза справочна таблица

Алгоритъм	Времева сложност	Изисква сортиране	Приложение
`sort`	\(O(N \log N)\)	Не	Общо сортиране
`binary_search`	\(O(\log N)\)	Да	Проверка за съществуване
`lower_bound`	\(O(\log N)\)	Да	Намиране на позиция
`unique`	\(O(N)\)	Да	Премахване на дубликати
`reverse`	\(O(N)\)	Не	Обръщане на реда
`next_permutation`	\(O(N)\)	Не	Генериране на пермутации
`max_element`	\(O(N)\)	Не	Намиране на максимум
`accumulate`	\(O(N)\)	Не	Сума/свиване
`partial_sum`	\(O(N)\)	Не	Префиксни суми

Не забравяйте: STL алгоритмите спестяват време, намаляват грешките и правят кода ви по-професионален!

⚙️ Алгоритми в STL

🔢 Алгоритми за сортиране и търсене

Функции за сортиране

std::sort(begin, end, [comparator])

std::stable_sort(begin, end, [comparator])

std::partial_sort(begin, middle, end)

std::nth_element(begin, nth, end)

Функции за двоично търсене

std::binary_search(begin, end, value)

std::lower_bound(begin, end, value)

std::upper_bound(begin, end, value)

std::equal_range(begin, end, value)