#include <iostream>

#include <stack>

int main() {

std::stack<int> s;

s.push(1);

s.push(13);

s.pop(); // Удаляем элемент с вершины (останется только 1)

std::cout << s.top() << "\n"; // Выводим элемент на вершине (1)

if (s.empty()) {

std::cout << "Stack is empty\n";

}

}

Особенности:

• По умолчанию std::stack использует std::deque для хранения данных, но можно заменить его на другой контейнер, например, std::list.

2. std::queue

Очередь реализует принцип FIFO (First In, First Out). Элементы добавляются в конец очереди, а извлекаются из начала.

• Основные операции:

  • push: Добавляет элемент в конец очереди.

  • pop: Удаляет элемент из начала очереди.

  • front: Возвращает первый элемент очереди.

  • back: Возвращает последний элемент очереди.

  • empty: Проверяет, пуста ли очередь.

#include <iostream>

#include <queue>

int main() {

std::queue<int> q;

q.push(1);

q.push(13);

std::cout << q.front() << "\n"; // Выводит первый элемент (1)

std::cout << q.back() << "\n"; // Выводит последний элемент (13)

q.pop(); // Удаляем первый элемент (останется только 13)

if (q.empty()) {

std::cout << "Queue is empty\n";

}

}

Особенности:

• По умолчанию используется std::deque, но можно заменить его на другой контейнер, поддерживающий операции push_back, pop_front и т. д.

3. std::priority_queue

Очередь с приоритетами позволяет быстро получать максимальный (или минимальный) элемент. Она основана на структуре данных "куча".

• Основные операции:

  • push: Добавляет элемент в очередь.

  • pop: Удаляет максимальный элемент.

  • top: Возвращает максимальный элемент без его удаления.

  • empty: Проверяет, пуста ли очередь.

#include <iostream>

#include <queue>

int main() {

std::priority_queue<int> pq;

for (int x : {3, 14, 15, 92, 6, 0, 1, 10}) {

pq.push(x);

}

while (!pq.empty()) {

std::cout << pq.top() << "\n"; // Выводит элементы в порядке убывания

pq.pop();

}

}

Особенности:

• По умолчанию используется std::vector для хранения данных.

• Можно изменить порядок сортировки, передав третий параметр, например, std::greater<int> для получения минимального элемента.

Представления

1. std::string_view

std::string_view — это легковесная обертка над строкой, которая позволяет работать с подстроками без создания их копий. Она не владеет памятью, а лишь ссылается на существующую строку.

• Преимущества:

  • Быстрее, чем создание новой строки (std::string).

  • Экономит память, так как не копирует данные.

#include <iostream>

#include <string>

#include <string_view>

int main() {

std::string s = "Hello, world! How do you do?";

std::string_view sv = s; // Создаем string_view для строки s

auto sub = sv.substr(7, 5); // Выделяем подстроку "world"

std::cout << sub << "\n"; // Выводит "world"

std::cout << s << "\n"; // Исходная строка не изменилась

}

Ограничения:

• std::string_view не позволяет изменять строку.

• Ссылается на исходную строку, поэтому если строка уничтожается, string_view становится невалидным.

2. Пример некорректного использования std::string_view

Если исходная строка выходит из области видимости, string_view теряет доступ к данным:

#include <iostream>

#include <string>

#include <string_view>

#include <vector>

int main() {

std::vector<std::string_view> lines;

for (int i = 0; i < 5; ++i) {

std::string line;

std::getline(std::cin, line);

lines.push_back(line); // string_view ссылается на временную строку

}

for (auto item : lines) {

std::cout << item << "\n"; // Ошибка! Строки уже уничтожены

}

}

Решение: Используйте std::string, если данные должны сохраняться после выхода из области видимости.

3. std::span

std::span — аналог std::string_view, но для массивов или векторов. Он предоставляет доступ к непрерывной последовательности элементов в памяти.

#include <iostream>

#include <vector>

#include <span>

int main() {

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

std::span<int> span(v); // Создаем span для вектора

for (int x : span) {

std::cout << x << " "; // Выводит элементы вектора

}

}

Особенности:

• Не владеет данными.

• Может использоваться для работы с подмассивами.

Заключение

Адаптеры и представления позволяют работать с данными более эффективно:

• Адаптеры (std::stack, std::queue, std::priority_queue) предоставляют специализированный интерфейс для работы с контейнерами.

• Представления (std::string_view, std::span) позволяют избежать ненужных копирований данных, но требуют осторожности при работе с временными объектами.

Задачи на std::stack

1. Обратный порядок слов
   Напишите программу, которая принимает строку текста и выводит слова в обратном порядке, используя std::stack.
   Пример:
   Ввод: "Hello world from C++"
   Вывод: "C++ from world Hello"

2. Проверка правильности скобок
   Напишите программу, которая проверяет, правильно ли расставлены скобки в строке (круглые, квадратные и фигурные). Используйте std::stack.
   Пример:
   Ввод: "{[()()]}" → Вывод: "Правильно"
   Ввод: "{[(])}" → Вывод: "Неправильно"

3. Калькулятор с обратной польской записью
   Реализуйте калькулятор, который вычисляет выражения в обратной польской записи (RPN). Например:
   Ввод: "3 4 + 2 * 7 /" → Вывод: 2

Задачи на std::queue

1. Симуляция очереди в банке
   Напишите программу, которая моделирует очередь клиентов в банке. Каждый клиент имеет номер. Программа должна позволять добавлять новых клиентов в очередь и обслуживать их по принципу FIFO.
   Пример:
   Ввод:

   add 1

   add 2

   serve

   Вывод: "Client 1 served"

2. Поиск минимального элемента в очереди
   Напишите программу, которая находит минимальный элемент в очереди за один проход. Используйте только операции push, pop и front.

3. Симуляция круговой очереди
   Реализуйте круговую очередь (например, карусель), где после обслуживания последнего клиента очередь начинается заново. Программа должна позволять добавлять новых клиентов и обслуживать их.

Задачи на std::priority_queue

1. Топ-N самых больших чисел
   Напишите программу, которая находит N самых больших чисел из потока данных. Используйте std::priority_queue.
   Пример:
   Ввод: N = 3, данные = {5, 1, 9, 2, 8, 3} → Вывод: {9, 8, 5}

2. Сортировка задач по приоритету
   У вас есть список задач с приоритетами. Напишите программу, которая обрабатывает задачи в порядке убывания приоритета.
   Пример:
   Ввод:

   Task1 Priority=3

   Task2 Priority=1

   Task3 Priority=2

   Вывод:

   Task1

   Task3

   Task2

3. Минимальная куча
   Реализуйте минимальную кучу с помощью std::priority_queue и напишите программу, которая выводит элементы в порядке возрастания.

Задачи на std::string_view

1. Подсчет подстрок
   Напишите программу, которая подсчитывает количество вхождений заданной подстроки в строку, используя std::string_view.
   Пример:
   Ввод: "Hello world", "o" → Вывод: 2

2. Разбиение строки на слова
   Напишите программу, которая разбивает строку на слова, используя std::string_view.
   Пример:
   Ввод: "Hello world from C++" → Вывод:

   Hello

   world

   from

   C++

3. Проверка префикса и суффикса
   Напишите программу, которая проверяет, начинается ли строка с заданного префикса и заканчивается ли заданным суффиксом, используя std::string_view.
   Пример:
   Ввод: "Hello world", prefix="Hello", suffix="world" → Вывод: "Да"

Задачи на std::span

1. Сумма элементов массива
   Напишите программу, которая вычисляет сумму элементов массива или вектора, используя std::span.
   Пример:
   Ввод: {1, 2, 3, 4, 5} → Вывод: 15

2. Поиск максимального элемента
   Напишите программу, которая находит максимальный элемент в массиве или векторе, используя std::span.

3. Реверс части массива
   Напишите программу, которая переворачивает часть массива, используя std::span.
   Пример:
   Ввод: {1, 2, 3, 4, 5}, start=1, end=4 → Вывод: {1, 4, 3, 2, 5}

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

1. Очередь с приоритетом задач
   Реализуйте систему управления задачами, где каждая задача имеет приоритет и описание. Используйте std::priority_queue для хранения задач и std::string_view для работы с описанием.

2. Стек с поддержкой минимума
   Реализуйте стек, который поддерживает операцию получения минимального элемента за O(1). Используйте два std::stack.

3. Анализ логов
   Напишите программу, которая анализирует лог-файл и выводит топ-N самых частых сообщений. Используйте std::unordered_map для подсчета частот и std::priority_queue для выбора топ-N.

4. Работа с подстроками
   Напишите программу, которая находит самую длинную подстроку без повторяющихся символов, используя std::string_view.

5. Многомерные массивы
   Реализуйте функцию, которая работает с двумерным массивом через std::span. Например, найдите сумму всех элементов или максимальный элемент.

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 символов

Если вам нужен массив фиксированного размера, известного на этапе компиляции, используйте std::array. Вот пример объявления array из трёх элементов:

#include <array>

int main() {

std::array<int, 3> point = {1, 2, -3};

}

std::array является обёрткой над низкоуровневым массивом T[N], предоставляя интерфейс стандартного контейнера: он знает свой размер, умеет присваиваться, предоставляет итераторы и т.д. Как и у вектора, элементы array располагаются в памяти непрерывно, но хранятся не в динамической памяти, а на стеке. Размер array должен быть задан на этапе компиляции и не может изменяться во время выполнения программы.

Контейнер std::deque

Deque расшифровывается как double-ended queue (двусторонняя очередь). В отличие от вектора, который размещает элементы в памяти непрерывно, std::deque размещает их кусочно-непрерывно, в отдельных страницах (непрерывных блоках) памяти фиксированного размера. Даже для одного элемента в деке будет выделена целая страница. Сами страницы не обязательно расположены в памяти подряд. Отдельно поддерживается список указателей на начала страниц. Размеры страниц зависят от sizeof(T) и от конкретной реализации дека.

Дек эффективно добавляет и удаляет элементы в начале и в конце без необходимости реаллокации и копирования старых элементов. Вставка по краям в деке эффективнее, чем в векторе. Однако вставка в середину и удаление из неё требуют сдвига элементов. Обращение к элементу по индексу происходит за O(1), но требует двух разыменований указателей, в то время как вектору достаточно одного.

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

#include <deque>

#include <iostream>

int main() {

std::deque<int> d = {1, 2, 3, 4};

d.push_back(5); // добавление в конец

d.push_back(6);

d.pop_back(); // удаление из конца

d.push_front(0); // добавление в начало

d.push_front(-1);

d.pop_front(); // удаление из начала

for (size_t i = 0; i != d.size(); ++i) {

std::cout << d[i] << "\n";

}

for (int x : d) {

std::cout << x << "\n";

}

}

Контейнер std::list

Двусвязный список std::list хранит элементы в отдельных узлах, которые могут располагаться в разных местах памяти. Узлы содержат указатели на предыдущий и следующий узлы. Пройтись по списку можно только с помощью range-based for или итераторов.

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

#include <list>

#include <iostream>

int main() {

std::list<int> l = {10, 15, 20};

l.push_front(5);

l.push_front(0);

l.push_back(25);

l.push_back(30);

l.pop_front();

l.pop_back();

for (int x : l) {

std::cout << x << "\n"; // 5 10 15 20 25

}

}

Итераторы списка

Итераторы — это объекты для навигации по контейнеру. Они позволяют обращаться к текущему элементу и сдвигаться к соседним. Функция begin возвращает итератор, указывающий на начальный элемент контейнера.

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

#include <list>

#include <iostream>

int main() {

std::list<int> l = {10, 15, 20};

auto iter = l.begin();

std::cout << *iter << "\n"; // печатаем начальный элемент

++iter; // сдвигаемся к следующему элементу

--iter; // возвращаемся назад

}

Функция end возвращает итератор, указывающий за последний элемент контейнера. Этот итератор нельзя разыменовывать, но можно сравнивать с ним.

Пример прохода по списку:

#include <list>

#include <iostream>

int main() {

std::list<int> l = {10, 15, 20};

for (auto iter = l.begin(); iter != l.end(); ++iter) {

std::cout << *iter << "\n"; // печатаем элементы списка через итератор

}

for (auto iter = l.rbegin(); iter != l.rend(); ++iter) {

std::cout << *iter << "\n"; // проход по списку в обратном порядке

}

}

С итераторами можно вставлять или удалять элементы в любом месте списка.

Пример вставки и удаления элементов:

#include <list>

#include <iostream>

int main() {

std::list<int> l = {0, 10, 15, 20};

auto iter = l.begin();

++iter;

l.insert(iter, 5); // вставляем на эту позицию элемент

for (auto iter = l.begin(); iter != l.end(); ) {

if (*iter % 2 == 0) {

iter = l.erase(iter); // возвращается итератор на элемент, следующий за удалённым

} else {

++iter;

}

}

}

Контейнер std::forward_list

Односвязный список std::forward_list используется там, где требуется экономия памяти на хранении ссылок на предыдущий узел. По такому контейнеру можно пройтись только вперёд, а вставка разрешена только в начало или после указанного итератора.

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

#include <forward_list>

#include <iostream>

int main() {

std::forward_list<int> fl = {3, 42, 5};

fl.push_front(2);

auto iter = std::next(fl.begin());

iter = fl.erase_after(iter);

fl.insert_after(iter, 4);

for (int x : fl) {

std::cout << x << "\n"; // 2 3 5 4

}

}

Инвалидация итераторов и ссылок

При изменении контейнера итераторы и ссылки на элементы могут стать невалидными. Например, если у вектора произошла реаллокация, все итераторы и ссылки инвалидируются. В std::array ничего вставить нельзя, его размер фиксирован. В std::deque инвалидируются итераторы, но не инвалидируются ссылки и указатели. В std::list и std::forward_list ни итераторы, ни ссылки не инвалидируются.

Пример инвалидации итераторов:

#include <vector>

#include <iostream>

int main() {

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

auto iter = v.begin(); // итератор

int* ptr = &v.front(); // указатель

int& ref = v.front(); // ссылка

std::cout << *iter << " " << *ptr << " " << ref << "\n"; // 1 1 1

v.push_back(5); // происходит реаллокация

// обращаться к старым итераторам, указателям и ссылкам больше нельзя:

std::cout << *iter << " " << *ptr << " " << ref << "\n"; // неопределённое поведение!

}

Ассоциативные контейнеры в C++

Ассоциативные контейнеры в C++ позволяют хранить данные в виде пар "ключ-значение". Они обеспечивают быстрый доступ к значениям по ключу. В стандартной библиотеке C++ есть два основных типа ассоциативных контейнеров:

1. Контейнеры на основе сбалансированных деревьев:

- `std::map` — хранит пары "ключ-значение" в отсортированном порядке.

- `std::set` — хранит только уникальные ключи в отсортированном порядке.

2. Контейнеры на основе хеш-таблиц:

- `std::unordered_map` — хранит пары "ключ-значение" без гарантии порядка.

- `std::unordered_set` — хранит только уникальные ключи без гарантии порядка.

Также существуют "мульти" версии этих контейнеров (`multimap`, `multiset`, `unordered_multimap`, `unordered_multiset`), которые позволяют хранить несколько значений для одного ключа.

---

Контейнер `std::map`

`std::map` — это ассоциативный контейнер, который хранит пары "ключ-значение" в отсортированном порядке. Он реализован как красно-чёрное дерево, что обеспечивает логарифмическое время выполнения операций поиска, вставки и удаления.

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

#include <iostream>

#include <map>

#include <string>

int main() {

std::map<std::string, int> years = {

{"Moscow", 1147},

{"Rome", -753},

{"London", 47},

};

// Добавление элемента

years["Paris"] = 52;

// Итерация по элементам

for (const auto& [city, year] : years) {

std::cout << city << ": " << year << "\n";

}

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

if (auto it = years.find("Rome"); it != years.end()) {

std::cout << "Found: " << it->first << " -> " << it->second << "\n";

}

// Удаление элемента

years.erase("London");

}

Основные операции:

- Вставка: `years[key] = value` или `years.insert({key, value})`.

- Поиск: `years.find(key)`.

- Удаление: `years.erase(key)`.

Контейнер `std::unordered_map`

`std::unordered_map` — это ассоциативный контейнер, основанный на хеш-таблицах. Он обеспечивает среднее время выполнения операций O(1), но не гарантирует порядок элементов.

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

#include <iostream>

#include <unordered_map>

#include <string>

int main() {

std::unordered_map<std::string, int> freqs;

std::string word;

// Подсчёт частот слов

while (std::cin >> word) {

++freqs[word];

}

// Вывод результатов

for (const auto& [word, freq] : freqs) {

std::cout << word << ": " << freq << "\n";

}

}

Основные операции:

- Вставка: `freqs[key] = value` или `freqs.insert({key, value})`.

- Поиск: `freqs.find(key)`.

- Удаление: `freqs.erase(key)`.

Контейнеры `std::set` и `std::unordered_set`

Эти контейнеры хранят только уникальные ключи. Они полезны, когда нужно проверить наличие элемента в коллекции.

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

#include <iostream>

#include <set>

#include <string>

int main() {

std::set<std::string> unique_words;

std::string word;

// Сбор уникальных слов

while (std::cin >> word) {

unique_words.insert(word);

}

// Вывод уникальных слов

for (const auto& word : unique_words) {

std::cout << word << "\n";

}

}

Мультиконтейнеры (`multimap`, `multiset`, `unordered_multimap`, `unordered_multiset`) позволяют хранить несколько значений для одного ключа.

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

#include <iostream>

#include <map>

#include <string>

int main() {

std::multimap<std::string, int> positions;

std::string word;

int position = 0;

// Сохранение позиций слов

while (std::cin >> word) {

positions.insert({word, position});

++position;

}

// Вывод всех позиций для слова "hello"

auto range = positions.equal_range("hello");

for (auto it = range.first; it != range.second; ++it) {

std::cout << "Position: " << it->second << "\n";

}

}

Итераторы ассоциативных контейнеров

Итераторы позволяют обходить элементы контейнера. Для `map` и `set` итераторы двусторонние, а для `unordered_map` и `unordered_set` — однонаправленные.

Пример работы с итераторами:

#include <iostream>

#include <map>

int main() {

std::map<int, std::string> numbers = {

{1, "one"},

{2, "two"},

{3, "three"},

};

auto it = numbers.find(2);

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

std::cout << "Found: " << it->first << " -> " << it->second << "\n";

}

}

Ассоциативные контейнеры в C++ — это мощный инструмент для работы с данными, организованными по принципу "ключ-значение". Выбор между `map` и `unordered_map` зависит от требований к порядку элементов и производительности. Для хранения уникальных ключей используйте `set` или `unordered_set`, а для работы с дубликатами — мультиконтейнеры.

# Список исходных файлов

SRCS = $(wildcard *.cpp)

OBJS = $(SRCS:.cpp=.o)

# Основная цель

all: $(TARGET)

# Как собирать программу

$(TARGET): $(OBJS)

$(CXX) $(OBJS) $(LDFLAGS) -o $(TARGET)

# Правило для объектных файлов

%.o: %.cpp

$(CXX) $(CXXFLAGS) -c $< -o $@

# Очистка

clean:

rm -f $(OBJS) $(TARGET)

Здесь используется функция wildcard, которая автоматически находит все .cpp файлы в директории. Это делает Makefile более гибким.

3. Работа с зависимостями

3.1. Установка библиотек через пакетный менеджер

Это самый простой способ, но он имеет ограничения:

• Разные дистрибутивы Linux могут использовать разные пакетные менеджеры (apt, yum, pacman).

• Версии библиотек в репозиториях могут быть устаревшими.

Пример установки libcurl:

sudo apt-get install libcurl4-openssl-dev

3.2. Локальная компиляция библиотек

Если вы хотите избежать проблем с версиями библиотек, лучше скомпилировать их локально. Например, для libcurl:

wget https://curl.se/download/curl-8.11.1.tar.bz2

tar -jxf curl-8.11.1.tar.bz2

cd curl-8.11.1

./configure --with-openssl

make

Теперь используйте локальные пути при компиляции:

g++ curlexample.cpp -o curlexample \

-I ./curl-8.11.1/include \

-L ./curl-8.11.1/lib/.libs \

-l curl

4. Продвинутые инструменты сборки

4.1. CMake

CMake — это мощный инструмент, который поддерживает кроссплатформенную сборку. Вот пример CMakeLists.txt для проекта с зависимостью от libcurl:

cmake_minimum_required(VERSION 3.10)

project(CurlExample LANGUAGES CXX)

set(CMAKE_CXX_STANDARD 17)

set(CMAKE_CXX_STANDARD_REQUIRED ON)

find_package(CURL REQUIRED)

add_executable(CurlExample curlexample.cpp)

target_link_libraries(CurlExample PRIVATE CURL::libcurl)

Чтобы собрать проект:

mkdir build

cd build

cmake ..

make

4.2. Meson

Meson — это современный инструмент, который генерирует файлы для Ninja. Пример meson.build:

project('CurlExample', 'cpp')

# Поиск libcurl

dependency('libcurl')

executable('curlexample', 'curlexample.cpp', dependencies: ['libcurl'])

Сборка:

meson setup build

cd build

ninja

4.3. SCons

SCons использует Python для написания рецептов. Пример SConstruct:

env = Environment()

env.Append(LIBS=['curl'])

env.Program(target='curlexample', source='curlexample.cpp')

Сборка:

scons

5. Docker для изоляции сборки

Docker позволяет создавать изолированные контейнеры с нужной версией ОС и библиотек. Это особенно полезно для старых проектов или CI/CD.

Пример Dockerfile:

FROM ubuntu:20.04

RUN apt-get update && apt-get install -y \

build-essential cmake git libcurl4-openssl-dev

WORKDIR /app

COPY . .

RUN mkdir build && cd build && cmake .. && make

Сборка и запуск:

docker build -t myproject .

docker run -it --rm -v $(pwd):/app myproject

6. Советы по оптимизации сборки

1. Инкрементальная сборка: Не пересобирайте весь проект, если изменился только один файл. Инструменты вроде make и ninja поддерживают это "из коробки".

2. Параллельная сборка: Используйте флаг -j для ускорения сборки на многоядерных процессорах:

   make -j$(nproc)

3. Кэширование зависимостей: Если вы используете Docker, сохраняйте зависимости в кэше, чтобы не скачивать их заново при каждой сборке.

4. Статическая vs Динамическая линковка: Выбирайте подходящий метод в зависимости от ваших целей:

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

   • Динамическая линковка делает файл меньше, но требует наличия библиотек на целевой системе.

7. Заключение

Настройка сборки проекта — это инвестиция в будущее. Чем раньше вы потратите время на её автоматизацию, тем проще будет развивать проект. Вот несколько рекомендаций:

• Для небольших проектов используйте Makefile.

• Для средних и больших проектов выбирайте CMake или Meson.

• Если вам нужно тестировать сборку в разных окружениях, используйте Docker.

• Всегда документируйте процесс сборки, чтобы другие разработчики могли легко подключиться к проекту.

Помните: хороший процесс сборки — это залог стабильности и успеха вашего проекта!