C++

Классы не только задают тип данных, но и определяют их поведение. Переменные такого типа называются объектами.

Объявление класса

Рассмотрим пример простой структуры, которая хранит время в часах, минутах и секундах:

struct Time {

int hours = 0;

int minutes = 0;

int seconds = 0;

};

Эта структура удобна, но она не проверяет корректность значений. Например, можно присвоить часам значение 42, а минутам — -5. Чтобы избежать таких ошибок, объявим класс Time.

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

class Time {

private:

int hours;

int minutes;

int seconds;

public:

Time(int h, int m, int s); // Конструктор

int GetHours() const; // Метод для получения часов

int GetMinutes() const; // Метод для получения минут

int GetSeconds() const; // Метод для получения секунд

};

Здесь конструктор отвечает за начальную инициализацию объекта, а методы GetHours, GetMinutes и GetSeconds объявлены как константные (с пометкой const), что означает их невозможность изменять состояние объекта.

Реализация функций

Теперь реализуем объявленные функции. Для этого можно написать их тела внутри класса или отдельно. При внешнем определении используется префикс с именем класса и двоеточием:

Time::Time(int h, int m, int s) {

if (s < 0 || s > 59) {

// Обработка ошибочных секунд

}

if (m < 0 || m > 59) {

// Обработка ошибочных минут

}

if (h < 0 || h > 23) {

// Обработка ошибочных часов

}

hours = h;

minutes = m;

seconds = s;

}

int Time::GetHours() const {

return hours;

}

int Time::GetMinutes() const {

return minutes;

}

int Time::GetSeconds() const {

return seconds;

}

Обратите внимание, что каждая функция класса работает с текущим объектом, который передаётся неявно. Этот объект доступен через указатель this.

Обработка ошибок в конструкторе

Если конструктор получает некорректные значения, он может либо сгенерировать исключение, либо скорректировать данные. Рассмотрим второй вариант:

Time::Time(int h, int m, int s) {

m += s / 60;

s %= 60;

if (s < 0) {

m -= 1;

s += 60;

}

h += m / 60;

m %= 60;

if (m < 0) {

h -= 1;

m += 60;

}

h %= 24;

if (h < 0) {

h += 24;

}

hours = h;

minutes = m;

seconds = s;

}

Теперь объекты класса Time всегда будут содержать корректное время.

Перегрузка конструкторов

Можно добавить несколько конструкторов для удобства. Например, конструктор без параметров и конструктор, принимающий общее количество секунд:

class Time {

private:

int hours = 0;

int minutes = 0;

int seconds = 0;

public:

Time() = default; // Конструктор по умолчанию

Time(int h, int m, int s); // Основной конструктор

Time(int s): Time(0, 0, s) {} // Делегирующий конструктор

};

Изменение состояния объекта

Чтобы позволить изменять объект после создания, добавим метод AddSeconds:

void AddSeconds(int s) {

seconds += s;

Normalize(); // Корректировка времени

}

Этот метод нельзя вызвать для константного объекта, так как он изменяет состояние.

Перегрузка операторов

Для удобства можно перегрузить операторы, такие как += и +. Например:

Time& operator += (int s) {

seconds += s;

Normalize();

return *this;

}

Time operator + (int s) const {

return Time(hours, minutes, seconds + s);

}

Теперь можно писать t += 40 или t + 20.

Ввод и вывод

Операторы << и >> можно перегрузить для работы с потоками:

std::ostream& operator << (std::ostream& out, const Time& t) {

out << t.GetHours() << ":" << t.GetMinutes() << ":" << t.GetSeconds();

return out;

}

std::istream& operator >> (std::istream& in, Time& t) {

int h, m, s;

char dummy;

in >> h >> dummy >> m >> dummy >> s;

t = Time(h, m, s);

return in;

}

Теперь можно легко читать и выводить время.

Модификация реализации

Интерфейс класса остаётся неизменным, даже если внутренняя реализация меняется. Например, вместо трёх полей (hours, minutes, seconds) можно хранить только одно поле totalSeconds:

class Time {

private:

int totalSeconds;

void Normalize() {

const int secondsInDay = 24 * 60 * 60;

totalSeconds %= secondsInDay;

if (totalSeconds < 0) {

totalSeconds += secondsInDay;

}

}

public:

Time(int h, int m, int s) {

totalSeconds = h * 60 * 60 + m * 60 + s;

Normalize();

}

int GetHours() const {

return totalSeconds / (60 * 60);

}

int GetMinutes() const {

return (totalSeconds / 60) % 60;

}

int GetSeconds() const {

return totalSeconds % 60;

}

};

Это упрощает код, сохраняя совместимость с существующими программами.

Таким образом, классы позволяют создавать надёжные и гибкие типы данных, которые легко модифицировать и расширять.

Задание 1: Класс Point

Создайте класс Point, который представляет точку в двумерном пространстве с координатами (x, y). Реализуйте следующие функциональности:

1. Приватные поля x и y.

2. Конструкторы :

   • Конструктор без параметров (инициализирует координаты нулями).

   • Конструктор с двумя параметрами для установки значений x и y.

3. Методы доступа :

   • GetX() и GetY() для получения значений координат.

   • SetX(int x) и SetY(int y) для изменения значений координат.

4. Перегрузка операторов :

   • Перегрузите оператор + для сложения двух точек (координаты складываются поэлементно).

   • Перегрузите оператор - для вычитания двух точек.

5. Дополнительно : добавьте метод DistanceTo(const Point& other), который вычисляет расстояние между текущей точкой и другой точкой.

Задание 2: Класс Fraction

Реализуйте класс Fraction, представляющий дробь вида a/b (где a — числитель, b — знаменатель). Добавьте следующие возможности:

1. Приватные поля numerator и denominator.

2. Конструкторы :

   • Конструктор с двумя параметрами для инициализации числителя и знаменателя.

   • Конструктор с одним параметром (знаменатель по умолчанию равен 1).

3. Методы доступа :

   • GetNumerator() и GetDenominator().

   • Метод Simplify(), который сокращает дробь до несократимой формы (например, 4/8 → 1/2).

4. Перегрузка операторов :

   • Перегрузите операторы +, -, *, / для выполнения арифметических операций с дробями.

   • Перегрузите операторы сравнения (==, !=, <, >, <=, >=).

5. Дополнительно : добавьте метод ToDouble(), который возвращает значение дроби как число типа double.

Задание 3: Класс BankAccount

Создайте класс BankAccount, моделирующий банковский счёт. Реализуйте следующие функциональности:

1. Приватные поля :

   • balance (баланс счёта).

   • accountNumber (номер счёта, строка или целое число).

2. Конструкторы :

   • Конструктор с начальным балансом и номером счёта.

   • Конструктор без параметров (начальный баланс = 0, номер счёта генерируется автоматически).

3. Методы :

   • Deposit(double amount) для пополнения счёта.

   • Withdraw(double amount) для снятия денег (с проверкой на достаточность средств).

   • GetBalance() для получения текущего баланса.

4. Перегрузка операторов :

   • Перегрузите оператор += для пополнения счёта.

   • Перегрузите оператор -= для снятия денег.

5. Дополнительно : добавьте метод Transfer(BankAccount& other, double amount), который переводит деньги с одного счёта на другой.

Задание 4: Класс Date

Реализуйте класс Date, представляющий дату в формате день-месяц-год. Добавьте следующие возможности:

1. Приватные поля :

   • day, month, year.

2. Конструкторы :

   • Конструктор с тремя параметрами для инициализации дня, месяца и года.

   • Конструктор без параметров (текущая дата по умолчанию).

3. Методы :

   • GetDay(), GetMonth(), GetYear() для получения значений.

   • SetDate(int day, int month, int year) для изменения даты.

   • IsValid() для проверки корректности даты (например, 31 февраля недопустимо).

4. Перегрузка операторов :

   • Перегрузите оператор ++ для увеличения даты на один день.

   • Перегрузите оператор -- для уменьшения даты на один день.

5. Дополнительно : добавьте метод DaysBetween(const Date& other), который возвращает количество дней между текущей датой и другой датой.

Задание 5: Класс Matrix

Создайте класс Matrix, представляющий матрицу чисел. Реализуйте следующие функциональности:

1. Приватные поля :

   • Двумерный массив для хранения элементов матрицы.

   • Размеры матрицы (rows, columns).

2. Конструкторы :

   • Конструктор с размерами матрицы и начальными значениями элементов.

   • Конструктор без параметров (матрица размером 1x1 с нулевым элементом).

3. Методы :

   • GetElement(int row, int col) и SetElement(int row, int col, int value) для доступа к элементам.

   • Print() для вывода матрицы на экран.

4. Перегрузка операторов :

   • Перегрузите оператор + для сложения двух матриц.

   • Перегрузите оператор * для умножения матриц (проверьте совместимость размеров).

5. Дополнительно : добавьте метод Transpose(), который возвращает транспонированную матрицу.

Задание 6: Класс Student

Создайте класс Student, представляющий студента с информацией о его имени, возрасте и оценках. Реализуйте следующие функциональности:

1. Приватные поля :

   • name (имя студента).

   • age (возраст студента).

   • grades (массив оценок).

2. Конструкторы :

   • Конструктор с именем, возрастом и массивом оценок.

   • Конструктор только с именем (остальные поля по умолчанию).

3. Методы :

   • GetName(), GetAge(), GetGrades() для получения данных.

   • AddGrade(int grade) для добавления новой оценки.

   • AverageGrade() для вычисления средней оценки.

4. Перегрузка операторов :

   • Перегрузите оператор << для вывода информации о студенте в поток.

   • Перегрузите оператор >> для ввода данных о студенте из потока.

5. Дополнительно : добавьте метод IsExcellentStudent(), который возвращает true, если средняя оценка >= 4.5.

Задание 7: Класс String

Реализуйте свой собственный класс String, аналогичный стандартному std::string. Добавьте следующие возможности:

1. Приватные поля :

   • Указатель на массив символов (char*).

   • Длина строки.

2. Конструкторы :

   • Конструктор с C-style строкой (например, "Hello").

   • Конструктор без параметров (пустая строка).

3. Методы :

   • Length() для получения длины строки.

   • Concat(const String& other) для конкатенации строк.

   • Substring(int start, int length) для получения подстроки.

4. Перегрузка операторов :

   • Перегрузите оператор + для конкатенации строк.

   • Перегрузите оператор == для сравнения строк.

5. Дополнительно : реализуйте метод Find(char c), который возвращает индекс первого вхождения символа в строку.

#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`, а для работы с дубликатами — мультиконтейнеры.