📚 Увод в стандартната библиотека (STL) и средства за сортиране и търсене от STL

Стандартната библиотека (STL) е основен инструмент в C++ програмирането. Тя предоставя готови реализации на алгоритми, контейнери и итератори, които улесняват разработването на приложения. Един от ключовите аспекти на STL е наличието на мощни средства за сортиране и търсене.

📋 Съдържание

Какво е STL?
- Контейнери
- Итератори
- Алгоритми
Сортиране в STL
- Функция std::sort
- Персонализирано сортиране
Търсене в STL
- Линейно търсене с std::find
- Двоично търсене с std::binary_search
Примери за реални приложения

🔍 Какво е STL?

STL е библиотека, която включва:

📦 Контейнери

Контейнерите представляват структури от данни като масиви, списъци, стекове и опашки. Примери: - std::vector - динамичен масив - std::list - свързан списък - std::map - асоциативен контейнер

#include <vector>
#include <iostream>

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};
    for (int num : numbers) {
        std::cout << num << " ";
    }
    return 0;
}

🔄 Итератори

Итераторите позволяват обхождане на елементите в контейнерите. Пример:

#include <vector>
#include <iostream>

int main() {
    std::vector<int> numbers = {10, 20, 30, 40};
    for (auto it = numbers.begin(); it != numbers.end(); ++it) {
        std::cout << *it << " ";
    }
    return 0;
}

⚙️ Алгоритми

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

🔢 Сортиране в STL

🟢 Функция `std::sort`

std::sort е един от най-използваните алгоритми за сортиране в C++. Той използва бързо сортиране (Quick Sort) и има времева сложност O(n log n).

Пример 1: Сортиране на масив

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> numbers = {5, 2, 9, 1, 5, 6};
    std::sort(numbers.begin(), numbers.end());

    for (int num : numbers) {
        std::cout << num << " ";
    }
    return 0;
}

Пример 2: Персонализирано сортиране

Създаване на собствена функция за сортиране по низходящ ред:

#include <algorithm>
#include <vector>
#include <iostream>

bool descending(int a, int b) {
    return a > b;
}

int main() {
    std::vector<int> numbers = {3, 1, 4, 1, 5, 9};
    std::sort(numbers.begin(), numbers.end(), descending);

    for (int num : numbers) {
        std::cout << num << " ";
    }
    return 0;
}

🔎 Търсене в STL

🟡 Линейно търсене с `std::find`

std::find извършва линейно търсене върху диапазон от елементи.

Пример:

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> numbers = {10, 20, 30, 40, 50};
    auto it = std::find(numbers.begin(), numbers.end(), 30);

    if (it != numbers.end()) {
        std::cout << "Елементът е намерен на позиция: " << (it - numbers.begin()) << std::endl;
    } else {
        std::cout << "Елементът не е намерен." << std::endl;
    }

    return 0;
}

🟢 Двоично търсене с `std::binary_search`

std::binary_search е по-ефективен алгоритъм за търсене, който изисква предварително сортиран контейнер.

Пример:

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5, 6};
    bool found = std::binary_search(numbers.begin(), numbers.end(), 4);

    if (found) {
        std::cout << "Елементът е намерен." << std::endl;
    } else {
        std::cout << "Елементът не е намерен." << std::endl;
    }

    return 0;
}

📈 Примери за реални приложения

1. Сортиране на данни от файл

#include <algorithm>
#include <fstream>
#include <vector>
#include <iostream>

int main() {
    std::ifstream infile("data.txt");
    std::vector<int> numbers;
    int num;

    while (infile >> num) {
        numbers.push_back(num);
    }

    std::sort(numbers.begin(), numbers.end());

    for (int n : numbers) {
        std::cout << n << " ";
    }

    return 0;
}

2. Търсене на специфична стойност в сортирани данни

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> data = {1, 3, 5, 7, 9};
    int target = 5;

    if (std::binary_search(data.begin(), data.end(), target)) {
        std::cout << "Стойността " << target << " е намерена." << std::endl;
    } else {
        std::cout << "Стойността " << target << " не е намерена." << std::endl;
    }

    return 0;
}

🔧 Други полезни алгоритми от STL

1. `std::reverse` - Обръщане на последователност

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

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> nums = {1, 2, 3, 4, 5};
    std::reverse(nums.begin(), nums.end());

    for (int n : nums) {
        std::cout << n << " "; // 5 4 3 2 1
    }
    return 0;
}

2. `std::unique` - Премахване на дубликати

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

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> nums = {1, 1, 2, 2, 3, 3, 3, 4};
    auto it = std::unique(nums.begin(), nums.end());
    nums.erase(it, nums.end()); // Премахваме излишните елементи

    for (int n : nums) {
        std::cout << n << " "; // 1 2 3 4
    }
    return 0;
}

3. `std::lower_bound` и `std::upper_bound`

Търсят позиция за вмъкване в сортиран масив. * lower_bound(x): първия елемент >= x * upper_bound(x): първия елемент > x

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> nums = {1, 2, 4, 4, 4, 7, 9};

    auto lb = std::lower_bound(nums.begin(), nums.end(), 4);
    auto ub = std::upper_bound(nums.begin(), nums.end(), 4);

    std::cout << "Първо срещане на 4 на позиция: " << (lb - nums.begin()) << std::endl; // 2
    std::cout << "Брой срещания на 4: " << (ub - lb) << std::endl; // 3

    return 0;
}

4. `std::next_permutation` - Пермутации

Генерира следващата лексикографска пермутация.

#include <algorithm>
#include <vector>
#include <iostream>

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

    do {
        for (int n : nums) {
            std::cout << n << " ";
        }
        std::cout << std::endl;
    } while (std::next_permutation(nums.begin(), nums.end()));

    // Извежда всички пермутации: 123, 132, 213, 231, 312, 321
    return 0;
}

5. `std::min_element` и `std::max_element`

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

#include <algorithm>
#include <vector>
#include <iostream>

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

    auto minIt = std::min_element(nums.begin(), nums.end());
    auto maxIt = std::max_element(nums.begin(), nums.end());

    std::cout << "Минимум: " << *minIt << std::endl; // 1
    std::cout << "Максимум: " << *maxIt << std::endl; // 9
    std::cout << "Позиция на макс: " << (maxIt - nums.begin()) << std::endl; // 5

    return 0;
}

6. `std::count` и `std::count_if`

Броят срещанията на елемент или елементи, отговарящи на условие.

#include <algorithm>
#include <vector>
#include <iostream>

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

    int countFives = std::count(nums.begin(), nums.end(), 5); // 1

    // Броят четни числа
    int countEven = std::count_if(nums.begin(), nums.end(), [](int x) {
        return x % 2 == 0;
    });

    std::cout << "Четни числа: " << countEven << std::endl; // 4
    return 0;
}

🎲 Ламбда функции (Lambda Expressions)

Ламбда функциите са анонимни функции, които могат да се използват директно в алгоритмите на STL.

Синтаксис

[capture](parameters) -> return_type { body }

Примери

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> nums = {5, 2, 9, 1, 7};

    // Сортиране в низходящ ред с ламбда
    std::sort(nums.begin(), nums.end(), [](int a, int b) {
        return a > b;
    });

    // Филтриране - запазване само на четни числа
    auto it = std::remove_if(nums.begin(), nums.end(), [](int x) {
        return x % 2 != 0;
    });
    nums.erase(it, nums.end());

    for (int n : nums) {
        std::cout << n << " ";
    }

    return 0;
}

📊 Сложност на алгоритмите

Разбирането на времевата сложност е критично за състезателното програмиране.

Алгоритъм	Сложност	Забележки
`std::sort`	O(n log n)	IntroSort (Quick + Heap + Insertion)
`std::stable_sort`	O(n log n)	Запазва реда на еднакви елементи
`std::find`	O(n)	Линейно търсене
`std::binary_search`	O(log n)	Изисква сортиран контейнер
`std::lower_bound`	O(log n)	Двоично търсене
`std::upper_bound`	O(log n)	Двоично търсене
`std::min_element`	O(n)	Обхожда целия контейнер
`std::max_element`	O(n)	Обхожда целия контейнер
`std::reverse`	O(n)	Разменя елементите
`std::unique`	O(n)	Премахва дубликати

💡 Практически съвети за състезания

1. Винаги сортирайте преди `binary_search`

std::vector<int> nums = {5, 2, 9, 1, 7};
std::sort(nums.begin(), nums.end()); // ЗАДЪЛЖИТЕЛНО!
bool found = std::binary_search(nums.begin(), nums.end(), 7);

2. Използвайте `lower_bound` за намиране на позиция

auto it = std::lower_bound(nums.begin(), nums.end(), x);
if (it != nums.end() && *it == x) {
    std::cout << "Намерен на позиция: " << (it - nums.begin()) << std::endl;
}

3. Комбиниране на `sort` + `unique` за премахване на дубликати

std::sort(nums.begin(), nums.end());
nums.erase(std::unique(nums.begin(), nums.end()), nums.end());

4. Персонализирано сортиране на структури

struct Student {
    std::string name;
    int grade;
};

std::vector<Student> students = {{"Иван", 85}, {"Мария", 92}, {"Петър", 78}};

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

🧪 Задачи за практика

Сортиране на думи: Прочетете N думи и ги сортирайте лексикографски.
Медиана: Намерете медианата на масив от числа (използвайте nth_element).
Премахване на дубликати: От несортиран масив (комбинирайте sort + unique).
K-тото най-малко: Намерете K-тото най-малко число в масив за O(n) (използвайте nth_element).
Двоично търсене: Напишете програма, която отговаря на Q запитвания дали дадено число се среща в масив.
Пермутации: Генерирайте всички пермутации на масив от N елемента (N ≤ 8).
Сортиране по модул: Сортирайте масив по абсолютна стойност на елементите.
Брой инверсии: Използвайте merge за броене на инверсии в масив (напреднало).

🎯 Заключение

STL е мощен инструмент, който значително опростява работата с данни. Сортирането и търсенето са основни операции, които благодарение на STL се реализират лесно и ефективно. Разбирането на алгоритмите sort, binary_search, lower_bound, upper_bound и други е от критично значение за успеха в състезателното програмиране. Ламбда функциите предоставят гъвкавост при персонализиране на поведението на алгоритмите. Винаги помнете за времевата сложност на операциите и избирайте правилния алгоритъм за задачата. Практикувайте редовно с различни задачи, за да усвоите напълно възможностите на STL.