C++

};

class B : public A {

private:

int y;

public:

void Func2(); // Переопределение функции

void Func3();

};

Основные моменты:

• Класс B включает в себя подобъект класса A.

• Методы и поля класса A доступны в B, за исключением приватных полей.

• Приватное поле x из A хранится внутри объекта типа B, но недоступно напрямую.

Использование:

int main() {

B b;

b.Func1(); // Унаследовано от A

b.Func2(); // Переопределено в B

b.A::Func2(); // Версия из A

b.Func3(); // Определено в B

}

Приведение типов

Объект производного класса может быть приведён к типу базового класса . Это позволяет использовать объекты производного класса там, где ожидается объект базового класса.

void DoSomething(const A&);

int main() {

B b;

DoSomething(b); // OK

}

Жизненный цикл объектов

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

class InheritedLogger : public Logger {

public:

InheritedLogger() { std::cout << "InheritedLogger()\n"; }

~InheritedLogger() { std::cout << "~InheritedLogger()\n"; }

};

int main() {

InheritedLogger x;

}

Вывод программы:

Logger(): 1

InheritedLogger()

~InheritedLogger()

~Logger(): 1

Наследование vs Композиция

Наследование (is-a):

• Класс-наследник является частным случаем базового класса.

• Пример: Car является Vehicle.

Композиция (has-a):

• Класс содержит объект другого класса как поле.

• Пример: Car имеет Engine.

Пример композиции:

class C {

private:

A a; // Композиция

int y;

public:

void Func1() { a.Func1(); } // Обёртка

void Func2();

void Func3();

const A& GetA() const { return a; }

};

Полиморфизм

Полиморфизм позволяет переопределять поведение функций базового класса в производных классах. Для этого используются виртуальные функции .

Пример:

class Animal {

public:

virtual std::string Voice() const { return "Generic voice"; }

};

class Cat : public Animal {

public:

std::string Voice() const override { return "Meow!"; }

};

class Dog : public Animal {

public:

std::string Voice() const override { return "Woof!"; }

};

Виртуальные функции:

• Позволяют выбирать реализацию во время выполнения (позднее связывание ).

• Если функция объявлена как чисто виртуальная , класс становится абстрактным .

class Animal {

public:

virtual std::string Voice() const = 0; // Чисто виртуальная функция

};

• Создать объект абстрактного класса нельзя.

• Производные классы должны реализовать все чисто виртуальные функции.

Полиморфизм и контейнеры

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

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

std::vector<Animal*> zoo;

zoo.push_back(new Cat("Tom"));

zoo.push_back(new Dog("Buffa"));

for (Animal* animal : zoo) {

Process(*animal); // Полиморфное поведение

delete animal; // Освобождение памяти

}

Важно:

• Для корректного удаления объектов деструктор базового класса должен быть виртуальным .

class Animal {

public:

virtual ~Animal() {}

};

Умные указатели

Для безопасного управления памятью лучше использовать умные указатели , такие как std::unique_ptr или std::shared_ptr.

Пример с std::unique_ptr:

std::vector<std::unique_ptr<Animal>> zoo;

zoo.push_back(std::make_unique<Cat>("Tom"));

zoo.push_back(std::make_unique<Dog>("Buffa"));

for (const auto& animal : zoo) {

Process(*animal); // Полиморфное поведение

}

• Умные указатели автоматически освобождают память при выходе из области видимости.

Итог

1. Наследование позволяет создавать иерархии классов и переиспользовать код.

2. Виртуальные функции обеспечивают полиморфное поведение.

3. Для работы с полиморфными объектами в контейнерах используйте указатели или умные указатели .

4. Абстрактные классы помогают определить общий интерфейс для производных классов.

5. Композиция предпочтительна, когда отношение между классами выражается через "имеет", а не "является".

Эти принципы являются основой объектно-ориентированного программирования в C++ и позволяют создавать гибкие, расширяемые и безопасные программы.

Наш класс должен поддерживать работу с разными типами элементов. Поэтому вынесем тип элемента в шаблонные параметры:

template <typename T>

class Matrix;

Теперь решим, будут ли размеры матрицы известны во время компиляции. Если да, их можно сделать шаблонными параметрами, а хранить матрицу можно в двумерном контейнере std::array:

#include <array>

template <typename T, size_t Rows, size_t Columns>

class Matrix {

private:

std::array<std::array<T, Columns>, Rows> data;

};

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

int main() {

Matrix<int, 3, 4> m; // матрица размера 3 x 4

}

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

#include <vector>

template <typename T>

class Matrix {

private:

std::vector<std::vector<T>> data;

public:

size_t GetRows() const {

return data.size();

}

size_t GetColumns() const {

if (data.empty()) {

return 0;

}

return data[0].size();

}

};

Конструкторы

Конструктор из вектора векторов

Напишем конструктор, который принимает двумерный вектор и соблюдает инвариант «в строках матрицы одинаковое количество элементов»:

template <typename T>

class Matrix {

private:

std::vector<std::vector<T>> data;

void MakeRectangle() {

size_t maxSize = 0;

for (const auto& row : data) {

if (row.size() > maxSize) {

maxSize = row.size();

}

}

for (auto& row : data) {

row.resize(maxSize);

}

}

public:

Matrix(const std::vector<std::vector<T>>& d) : data(d) {

MakeRectangle();

}

};

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

int main() {

Matrix<int> m({

{1, 2, 3},

{4, 5, 6},

});

std::cout << m.GetRows() << "\n"; // 2

std::cout << m.GetColumns() << "\n"; // 3

}

Конструктор для нулевой матрицы

Добавим конструктор для создания нулевой матрицы заданных размеров:

template <typename T>

class Matrix {

private:

std::vector<std::vector<T>> data;

public:

Matrix(size_t rows, size_t columns) {

data.resize(rows);

for (auto& row : data) {

row.resize(columns);

}

}

};

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

int main() {

Matrix<int> m(3, 4); // создаём нулевую матрицу из 3 строк и 4 столбцов

}

Обращение к элементам и перегрузка по константности

Хочется обращаться к элементам матрицы так же, как и с двумерным массивом:

int main() {

Matrix<int> m(3, 4);

int element = m[0][0];

m[1][1] = 1;

m[2][3] = 5;

}

Для этого перегрузим оператор []. Однако нужно учесть два случая: чтение и запись. Для этого перегрузим оператор по константности:

template <typename T>

class Matrix {

private:

std::vector<std::vector<T>> data;

public:

const std::vector<T>& operator[](size_t i) const {

return data[i];

}

std::vector<T>& operator[](size_t i) {

return data[i];

}

};

Теперь первая версия будет применяться к константным матрицам, а вторая — к неконстантным.

Итерация по матрице

Чтобы можно было писать цикл range-based for по строкам матрицы, добавим функции begin и end:

template <typename T>

class Matrix {

private:

std::vector<std::vector<T>> data;

public:

using const_iterator = typename std::vector<std::vector<T>>::const_iterator;

const_iterator begin() const {

return data.cbegin();

}

const_iterator end() const {

return data.cend();

}

};

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

int main() {

Matrix<int> m(3, 4);

for (const auto& row : m) {

// обрабатываем строку row

}

}

Потоковый ввод и вывод

Перегрузим операторы << и >> для удобства работы с потоками:

template <typename T>

std::ostream& operator<<(std::ostream& out, const Matrix<T>& matrix) {

const size_t rows = matrix.GetRows();

const size_t columns = matrix.GetColumns();

for (size_t i = 0; i != rows; ++i) {

for (size_t j = 0; j != columns; ++j) {

if (j > 0) {

out << "\t";

}

out << matrix(i, j);

}

out << "\n";

}

return out;

}

template <typename T>

std::istream& operator>>(std::istream& in, Matrix<T>& matrix) {

const size_t rows = matrix.GetRows();

const size_t columns = matrix.GetColumns();

for (size_t i = 0; i != rows; ++i) {

for (size_t j = 0; j != columns; ++j) {

in >> matrix(i, j);

}

}

return in;

}

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

int main() {

Matrix<int> m(3, 4);

std::cin >> m;

std::cout << m;

}

Арифметические операции

Оператор +=

Реализуем оператор += для сложения матриц одинакового размера:

template <typename T>

Matrix<T>& operator+=(const Matrix<T>& other) {

const size_t rows = GetRows();

const size_t columns = GetColumns();

if (rows != other.GetRows() || columns != other.GetColumns()) {

throw std::invalid_argument("Matrices have different size!");

}

for (size_t i = 0; i != rows; ++i) {

for (size_t j = 0; j != columns; ++j) {

data[i][j] += other.data[i][j];

}

}

return *this;

}

Оператор +

Реализуем оператор +, используя уже написанный оператор +=:

template <typename T>

Matrix<T> operator+(const Matrix<T>& m1, const Matrix<T>& m2) {

auto tmp = m1;

tmp += m2;

return tmp;

}

Сравнение матриц

Напишем операторы == и != для сравнения двух матриц:

template <typename T>

bool operator==(const Matrix<T>& other) const {

const size_t rows = GetRows();

const size_t columns = GetColumns();

if (rows != other.GetRows() || columns != other.GetColumns()) {

return false;

}

for (size_t i = 0; i != rows; ++i) {

for (size_t j = 0; j != columns; ++j) {

if (!((*this)(i, j) == other(i, j))) {

return false;

}

}

}

return true;

}

template <typename T>

bool operator!=(const Matrix<T>& m1, const Matrix<T>& m2) {

return !(m1 == m2);

}

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

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

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

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

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