Основы программирования на C++: Алгоритмы⁠⁠

Прежде чем читать мою статью - реши для себя, зачем ты это делаешь. Даже если ты просто нормальный человек, лишним не будет.

Если вы настоящий профессионал программирования, то зачем вы тут сидите и читайте статью на пикабу? Если вы ради интереса зашли почитать, то претензий ноль, но если вы просто захотели задушить нового пользователя Пикабу минусами, то немедленно покиньте статью, вам однозначно интересно не будет.

Здравствуйте, мои маленькие любители программирования!

1. Что такое алгоритмы в C++?

Алгоритмы — это готовые функции, которые помогают выполнять типичные задачи с последовательностями элементов, такими как:

• Подсчет элементов.

• Поиск элементов.

• Сортировка данных.

• Модификация последовательностей.

Эти алгоритмы работают с итераторами , которые представляют собой указатели на элементы контейнера (например, vector, list, deque и т.д.).

2. Как работают итераторы?

Итераторы — это объекты, которые позволяют перебирать элементы контейнера. Они похожи на указатели, но могут быть адаптированы для разных типов контейнеров.

Основные правила работы с итераторами:

1. Два итератора задают диапазон :

   • Первый итератор указывает на начало диапазона.

   • Второй итератор указывает за последний элемент диапазона (так называемый "полуинтервал").

   • Например: [first, last) означает, что first включается, а last исключается.

2. Итераторы одного контейнера :

   • Итераторы должны принадлежать одному и тому же контейнеру.

3. Операции с итераторами :

   • Можно двигаться вперед с помощью оператора ++.

   • Можно сравнивать итераторы (iter1 == iter2 или iter1 != iter2).

   • Можно разыменовывать итераторы (*iter) для доступа к значению.

3. Примеры работы с алгоритмами

Подсчет элементов

Функция std::count подсчитывает, сколько раз встречается определенное значение в последовательности.

#include <iostream>

#include <vector>

#include <algorithm>

int main() {

std::vector<int> v = {2, 7, 1, 8, 2, 8};

int count = std::count(v.begin(), v.end(), 8); // Сколько раз встречается число 8

std::cout << "Число 8 встречается " << count << " раз(а).\n";

}

Как это работает?

• Алгоритм проходит по всем элементам в диапазоне [v.begin(), v.end()).

• Если элемент равен заданному значению (в данном случае 8), счетчик увеличивается.

Поиск элемента

Функция std::find ищет первый элемент, равный заданному значению.

#include <iostream>

#include <deque>

#include <algorithm>

int main() {

std::deque<int> d = {3, 14, 15, 92, 6};

auto it = std::find(d.begin(), d.end(), 15); // Ищем число 15

if (it != d.end()) {

std::cout << "Найдено число: " << *it << "\n";

} else {

std::cout << "Число не найдено.\n";

}

}

Как это работает?

• Алгоритм проходит по всем элементам в диапазоне [d.begin(), d.end()).

• Если элемент найден, возвращается итератор на него.

• Если элемент не найден, возвращается d.end().

Сортировка

Функция std::sort сортирует элементы в порядке возрастания.

#include <iostream>

#include <vector>

#include <algorithm>

int main() {

std::vector<int> data = {100, 42, 17, 80, 20, 0};

std::sort(data.begin(), data.end()); // Сортируем все элементы

for (int x : data) {

std::cout << x << " "; // 0 17 20 42 80 100

}

}

Как это работает?

• Алгоритм использует быструю сортировку (quicksort) или другую эффективную стратегию.

• Элементы переставляются так, чтобы они шли в порядке возрастания.

4. Алгоритмы с предикатами

Предикат — это функция, которая возвращает true или false. Алгоритмы с суффиксом _if используют предикаты для выполнения условий.

Пример: std::count_if

Подсчитаем, сколько заглавных букв в строке.

#include <iostream>

#include <string>

#include <algorithm>

int main() {

std::string s = "iPhone SE";

int count = std::count_if(s.begin(), s.end(), [](char c) {

return ('A' <= c && c <= 'Z'); // Проверяем, является ли символ заглавной буквой

});

std::cout << "Заглавных букв: " << count << "\n"; // 3

}

Как это работает?

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

• Алгоритм применяет эту функцию ко всем элементам строки.

5. Модификация последовательности

Алгоритмы могут изменять порядок или значения элементов.

Пример: std::reverse

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

#include <iostream>

#include <string>

#include <algorithm>

int main() {

std::string s = "No lemon, no melon!";

std::reverse(s.begin(), s.end()); // Переворачиваем строку

std::cout << s << "\n"; // !nolem on ,nomel oN

}

Как это работает?

• Алгоритм меняет местами первый и последний элементы, второй и предпоследний, и так далее.

6. Копирование данных

Функция std::copy копирует элементы из одной последовательности в другую.

#include <iostream>

#include <vector>

#include <list>

#include <algorithm>

int main() {

std::vector<int> v = {3, 14, 15, 92, 6};

std::list<int> l(v.size()); // Создаем список того же размера

std::copy(v.begin(), v.end(), l.begin()); // Копируем данные

for (int x : l) {

std::cout << x << " "; // 3 14 15 92 6

}

}

Как это работает?

• Алгоритм берет каждый элемент из входной последовательности и записывает его в выходную.

7. Теоретико-множественные операции

Если последовательности отсортированы, можно выполнять операции над множествами.

Пример: std::set_union

Объединяет два множества.

#include <iostream>

#include <vector>

#include <algorithm>

int main() {

std::vector<int> a = {1, 3, 5, 7};

std::vector<int> b = {2, 3, 6};

std::vector<int> result;

std::set_union(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(result));

for (int x : result) {

std::cout << x << " "; // 1 2 3 5 6 7

}

}

Как это работает?

• Алгоритм объединяет два отсортированных множества, сохраняя порядок.

8. Бинарный поиск

Для отсортированных последовательностей можно использовать бинарный поиск.

Пример: std::binary_search

Проверяет, есть ли элемент в последовательности.

#include <iostream>

#include <vector>

#include <algorithm>

int main() {

std::vector<int> data = {1, 4, 5, 9, 9, 13, 47};

bool found = std::binary_search(data.begin(), data.end(), 5); // Ищем число 5

std::cout << (found ? "Найдено" : "Не найдено") << "\n";

}

Как это работает?

• Алгоритм делит последовательность пополам и проверяет, находится ли элемент в левой или правой части.

Заключение

Алгоритмы стандартной библиотеки C++ — это мощный инструмент для работы с данными. Они универсальны, эффективны и легко интегрируются в код. Чтобы использовать их правильно:

1. Убедитесь, что вы понимаете, как работают итераторы.

2. Выбирайте подходящий алгоритм для вашей задачи.

3. Используйте предикаты для сложных условий.

Теперь вы знаете основы работы с алгоритмами и можете применять их в своих программах!

Вот несколько задач для закрепления материала по алгоритмам C++:

Подсчет и поиск:

• Напишите программу, которая считает количество четных чисел в векторе

• Найдите первое отрицательное число в списке или выведите сообщение, что их нет

  Сортировка:

• Отсортируйте массив строк по длине (от коротких к длинным)

• Создайте вектор чисел и отсортируйте его в обратном порядке

  Алгоритмы с предикатами:

• Посчитайте количество гласных букв в строке

• Найдите первое слово в векторе строк, начинающееся на заданную букву

  Модификация последовательностей:

• Переверните порядок слов в строке

• Удалите все повторяющиеся элементы из вектора

  Копирование данных:

• Скопируйте только положительные числа из одного вектора в другой

• Создайте копию строки, преобразовав все буквы в верхний регистр

  Теоретико-множественные операции:

• Найдите общие элементы двух отсортированных массивов

• Объедините два отсортированных списка уникальных чисел

  Бинарный поиск:

• Проверьте, содержит ли отсортированный массив заданное число

• Найдите первое число, большее заданного, в отсортированном векторе

  Комбинированные задачи:

• Отсортируйте список слов и подсчитайте количество уникальных

• Найдите все числа в диапазоне [a, b] в отсортированном массиве

• Удалите все четные числа из вектора и отсортируйте оставшиеся

  Работа с пользовательским вводом:

• Запросите у пользователя набор чисел, отсортируйте их и найдите медиану

• Создайте телефонный справочник (вектор пар имя-телефон) и реализуйте поиск по имени

  Обработка текста:

• Посчитайте частоту встречаемости каждой буквы в тексте

• Разбейте текст на слова и выведите только те, что длиннее 5 символов