Стек

Повторение – ссылки и указатели

  • Что такое ссылка?

    Ссылка – это “псевдоним” для существующей переменной. Использование ссылки полностью совпадает с использованием оригинального объекта. Ссылка не занимает и не выделяет память, копирования при создании ссылки не происходит

    T&: например, int& или std::vector<int>&

  • Что такое указатель?

    Это адрес некоторого объекта (другой переменной) в памяти компьютера. Занимает 8 байт на современных системах. Указывает на начало какого-то объекта в памяти

Стек

Стек – структура данных, которая позволяет добавлять элементы только на вершину и доставать элементов только с вершины. Принцип LIFO (“Last in – First out”, то есть “Последним пришел – Первым ушел”).

Операции, которые поддерживает стек:

  • push(elem) – добавляет элемент на вершину стека

  • top() – возвращает элемент с вершины стек

  • pop() – удаляет элемент с вершины стека

  • empty()– возвращает true, если стек пуст. Иначе – false

Есть разные реализации стека: на фиксированном или динамическом массиве, но использование C++ позволяет не задумываться и использование встроенный тип std::stack<T>

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

#include <iostream>
#include <stack>

int main() {
    std::stack<int> stack;

    stack.push(1); // push элемента на вершину стека

    // top -- получение элемента
    std::cout << stack.top() << std::endl;

    stack.pop(); // pop удаление элемента с вершины стека

    // empty -- пуст ли стек
    if (stack.empty()) {
        std::cout << "Stack is empty" << std::endl;
    } else {
        std::cout << "Stack is not empty" << std::endl;
    }

    return 0;
}

Вообще такое ограничение в использовании знакомых конструкций не напрасно:

  • стек – понятная конструкция, использование которой не усложняет программу излишним функционалом

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

  • стек является основой исполнения инструкций процессором (подробнее далее). На нем хранятся данные для организации вызовов функций (в том числе рекурсивных). В IDE в отладчике Call Stack называется так не просто так

  • на стеке хранятся локальные переменные. На самом деле это тесно связано с предыдущим пунктом, но это отдельный, пусть и весьма интересный разговор

Классическая задача на стек – проверка скобочных последовательность на правильность.

Скобочные последовательности

Скобочная последовательность – любая строка, которая состоит из любого количества закрывающих и открывающих скобок.

Формально она называется правильной, если она:

  • пуста

  • равна \(AB\), где \(A\) и \(B\) правильный скобочные по последовательности

  • равна \((A)\), где \(A\) правильная. Вместо круглых может быть любой тип скобок по условию задачи

Примеры правильных: \(((()()()))\), \((()())()()\)

Примеры неправильных: \()(\), \(())()()\), \(((())))\)

Один тип скобок

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

Поскольку у нас только 1 тип скобок, эти условия можно проверить балансом скобок. При открытии скобки \(+1\), при закрытии \(-1\)

Условия на баланс:

  • итоговый баланс равен \(0\)

  • баланс всегда \(\ge 0\)

Соблюдение этих условий на баланс скобок равносильно правильности скобочной последовательности

Несколько типов скобок

Для определенность пусть типов будет 3: \(()\{\}[]\)

Теперь уже недостаточно поддерживать баланс всех скобок или баланс по типам скобок? потому что не отражает зависимости между расстановкой скобок. Например, последовательность \(([)]\) является “правильной” по каждой из скобок (балансы неотрицательны, в конце равны \(0\)), но неправильной по нашему определению

Для решения такой задачи придется использовать стек. Требования:

  • в конце последовательности стек пуст

  • если скобка открывающая, то добавляем ее в стек

  • если скобка закрывающая, то

    • если стек пуст, то последовательность неправльная

    • берем с вершины стека скобку и проверяем, что она совпадает с нашей закрывающей по типу – круглая с круглой, квадратная с квадратной и так далее

Стек минимумов

Стек минимумов – структура данных, которая поддерживает операции стека, а также операцию get_min(), которая возвращает минимальный элемент в стеке за \(O(1)\). Для поддержания стека с такой операцией нам нужно использовать дополнительный стек, в котором мы будем хранить минимальные элементы. Логика следующая:

  • при добавлении элемента в основной стек, мы сравниваем его с текущим минимумом (элементом на вершине дополнительного стека). Если новый элемент меньше или равен текущему минимуму, мы также добавляем его в дополнительный стек
  • при удалении элемента из основного стека, если удаляемый элемент равен текущему минимуму (элементу на вершине дополнительного стека), мы также удаляем его из дополнительного стека
  • операция get_min() просто возвращает элемент на вершине дополнительного стека, который всегда будет минимальным элементом в основном стеке

Например:

Операция Основной стек Стек минимумов Результат
push(5) [5] [5]
push(3) [5, 3] [5, 3]
push(7) [5, 3, 7] [5, 3]
get_min() [5, 3, 7] [5, 3] 3
pop() [5, 3] [5, 3]
get_min() [5, 3] [5, 3] 3
pop() [5] [5]
get_min() [5] [5] 5

Аналогично можно реализовать стек максимумов.

Обратная польская нотация

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

Как посчитать арифметическое выражение, записанное в обратной нотации:

  • идем по последовательности слева направо

  • если встретилось число, добавляем в структуру

  • если встретился знак арифметической операции, то

    • выполняем эту арифметическую операцию с 2 числами, которые были добавлены последними – удалем их из структуры

    • добавляем в структуру результат операции

  • по окончании прохода в структуре должно находиться только одно число – это и есть значение всего выражения

  • если одну из операций невозможно выполнить, то это ошибка записи. Например, нужно взять из структуры 2 числа, а там их меньше чем 2. Итог – ошибка записи

Пример:5 15 + 4 7 + 1 - /

  • 5

  • 5 15

  • 5 15 +→ 20

  • 20 4

  • 20 4 7

  • 20 4 7 + → 20 11

  • 20 11 1

  • 20 11 1 - →20 10

  • 20 10 / → 2

  • 2 – результат

Использование памяти

Memory types
  1. Область текста программы содержит машинные инструкции программы (то есть исполняемый код) — именно их мы получаем в результате компиляции.
  2. Глобальные переменные определяются в глобальной области видимости вне любых функций; статические переменные имеют ключевое слово static в их определении. Операционная система обычно выделяет память для хранения глобальных и статических переменных при запуске программы.
  3. (*) В системах с сегментированной памятью выделенная память представлена как единый блок, который остается неиспользуемым до тех пор, пока стек или куча не начнут расти и занимать эту область.
  4. Стек содержит все автоматические (то есть не статические) переменные и служебные данные для вызовов функций (адрес возврата, сохраненные регистры, часть аргументов).
  5. Память выделяется из кучи и возвращается в нее с помощью операторов new и delete, соответственно.

Таким образом, на стеке лежат локальные переменные, а также внутренний контекст выполнения программы: адрес текущей инструкции, адрес возврата из функции (ведь вызов функции — это переход на другую часть кода, а после выполнения функции нужно вернуться обратно), аргументы функции и т. д.

Динамическая память (heap)

Динамическая память — область памяти, которая выделяется и освобождается по запросу программы во время ее выполнения. В C++ для работы с динамической памятью используются операторы new/delete и new[]/delete[]. Она нужна, когда: - размер данных неизвестен на этапе компиляции, - объект должен пережить выход из текущей области видимости, - требуется контроль над временем жизни и размещением, - размер данных слишком велик для стека

Ключевые правила: - Каждому new T(...) должен соответствовать ровно один delete p. - Каждому new T[n] должен соответствовать ровно один delete[] p. - Не удаляйте один и тот же указатель дважды. Не используйте указатель после delete (dangling pointer).

Утечка памяти – ситуация, когда память была выделена, но не освобождена после использования и указатель на нее потерян. В этой ситуации нет способов освободить память, что приводит к постепенному исчерпанию доступной памяти. Такая программа может работать, но считается некорректной.

Чтобы детектировать и исправлять утечки памяти и другие ошибки работы с памятью, можно обратиться к санитайзерам памяти. Их можно подключать через флаги компилятора, например, -fsanitize=address для AddressSanitizer в GCC и Clang.

Выделение одного объекта


int main() {
    // создаем локальные переменные a и b на стеке, именно в таком порядке
    int a = 1;
    int b = 2;

    // p -- указатель на динамически выделенный int. Указатель -- локальная переменная на стеке
    // само значение int лежит в динамической памяти (heap)
    int* p = new int(a); // выделение памяти для одного int и инициализация значением a=1
    // использование *p

    std::cout << p << std::endl; // вывод адреса динамически выделенного int
    std::cout << *p << std::endl; // вывод значения динамически выделенного int

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

    return 0;
}
// здесь b и a будут автоматически деаллоцированы при выходе из main, именно в таком порядке из-за LIFO

Реализация стека с помощью динамической памяти

Существует различные подходы к реализации стека. Мы рассмотрим реализацию стека на выделенном массиве фиксированной длины с помощью указателя на вершину стека.

  • выделяем массив фиксированной длины capacity в динамической памяти с помощью new T[capacity]
  • создаем указатель top_ptr, который будет указывать на вершину стека
  • при добавлении элемента push(elem) записываем элемент по адресу top_ptr
  • при удалении элемента pop() просто сдвигаем указатель top_ptr на 1 влево
  • при получении элемента top() возвращаем значение по адресу top_ptr - 1
  • при проверке на пустоту empty() сравниваем top_ptr с началом выделенного массива

Не забудьте освободить выделенную память с помощью delete[] после завершения работы со стеком.

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

#include <iostream>

int main() {
    int max_capacity;
    std::cin >> max_capacity;
    int* stack_begin = new int[max_capacity];
    int* stack_top = stack_begin;

    // some stack operations

    delete[] stack_begin;
    return 0;
}

Функция

Функция – это блок кода, к которому можно обратиться из другого места программы

  • имеет название (как правило)

  • зависит от аргументов

  • возвращает некоторое значение – то есть итогом исполнение функции является некоторый объект, который можно использовать после ее завершения

Например, следующая функция находит сумму двух чисел:

#include <iostream>

int getSum(int a, int b) {
    return a + b;
}

int main() {
    int first, second;
    std::cin >> first >> second;
    int result = getSum(first, second);
    std::cout << "Sum is " << result << '\n';
}

Функция getSum принимает 2 обязательных аргумента, каждый типа int. Тип возвращаемого значения также int.

Ключевое слово return позволяет вернуть значение из функции. После возврата какого-либо значения выполнение функции не продолжится.

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

  • вводятся числа \(n, s, t\)

  • далее вводятся \(n\) целых чисел

  • выведите OK, если их произведение оканчивается на двузначное число \(s\) и последовательность содержит не более \(t\) четных чисел

  • иначе выведите, в чем проблема

#include <iostream>
#include <cstdint>
#include <vector>

void outputVerdict(size_t cnt, size_t t, uint64_t last_digits, uint64_t required_last_digits) {
    if (last_digits != required_last_digits && cnt > t) {
        std::cout << "all checks failed!\n";
    } else if (last_digits != required_last_digits) {
        std::cout << "last digits do not match!\n";
    } else if (cnt > t) {
        std::cout << "too many even numbers!\n";
    } else {
        std::cout << "OK!\n";
    }
}

int main() {
    size_t cnt = 0;
    uint64_t prod = 1;

    size_t n;
    uint64_t required_digits, t;
    std::cin >> n >> required_digits >> t;

    for (size_t i = 0; i < n; ++i) {
        uint32_t current_num;
        std::cin >> current_num;
        prod *= current_num;
        if (current_num % 2 == 0) {
            ++cnt;
        }
    }

    outputVerdict(cnt, t, prod % 100, required_digits);
}

Здесь стоит обратить внимание, что в функцию передается 4 обязательных аргумента разных типов. Совпадение названий аргументов и переменных несущественно. prod % 100 – это вообще не переменная, а значение, наша функцию принимает именно их (рассмотрим это подробнее в следующем пункте)

Также функция выше ничего не возвращает, поэтому на месте типа возвращаемого значения указан void(перевод с английского “ничто”, “пустота”).

После выполнения return исполнение функции завершится, поэтому вместо каскада условий можно писать вот так:

void outputVerdict(size_t cnt, size_t t, uint64_t last_digits, uint64_t required_last_digits) {
    if (last_digits != required_last_digits && cnt > t) {
        std::cout << "all checks failed!\n";
        return;
    }
    if (last_digits != required_last_digits) {
        std::cout << "last digits do not match!\n";
        return;
    }
    if (cnt > t) {
        std::cout << "too many even numbers!\n";
        return;
    }
    std::cout << "OK!\n";
}

В примере выше стоит отдельно обратить внимание на использование std::cout << "OK!\n"; в конце функции. Действительно, эта строка выполнится только если все условия неверны, иначе выполнился бы один из return

Зачем нужны функции?

Функции полезны для:

  • переиспользования кода в разных частях программы

  • повышения читаемости кода

    • название отражает смысл функции (getEvenSum) или тип (get..., is...)

    • код разбивается на блоки, которые проще понимать. “Основная” программа последовательно вызывает эти функции. Так можно понимать программу без просмотра деталей реализации

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

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

Аргументы функций

Аргументы функции – те переменные, от которых зависит поведение функции. Примеры:

  • сторона квадрата в функции нахождения его площади

  • сообщение в функции красивого вывода на экран

  • std::vector с числами в функции, считающей количество четных элементов

Передача аргументов по значению

Функции выше получали аргументы по значению, то есть происходило следующее:

  • функция получает несколько значений разных типов

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

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

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

  • по завершении функции локальные переменные перестают существовать

Область видимости, жизни этих переменных, их scope – это вся функция. Они локальные, значит, их изменение не повлияет на остальные части программы

#include <iostream>

int getSum(int a, int b) {
    a = 2;
    return a + b;  // 2 + b
}

int main() {
    int first, second;
    std::cin >> first >> second;  // 6 7

    int result = getSum(first, second);

    std::cout << "Sum is " << result << '\n';     // 9
    std::cout << first << ' ' << second << '\n';  // 6 7
}

Важно отметить, что получении аргументов по значению происходит копирование. Если копирование ненужно (не требует локальное изменение аргумента), а передаваемые объекты могут занимать много памяти (std::vector, std::string), то стоит передавать аргументы по ссылке. Ведь C++ – это об эффективности

Передача аргументов по ссылке

При передаче аргументов по ссылке (тип T&):

  • копирования не происходит, новая память не выделяется

  • изменение переменных по ссылке отразиться на внешней программе – ведь изменяться будет “оригинал переменной”

Например, пример с суммой:

#include <iostream>

int getSum(int& a, int& b) {
    a = 2;
    return a + b;  // 2 + b
}

int main() {
    int first, second;
    std::cin >> first >> second;  // 5 1

    int result = getSum(first, second);

    std::cout << "Sum is " << result << '\n';     // 3
    std::cout << first << ' ' << second << '\n';  // 2 1
}

В примере выше изменение переменной a, переданной по ссылке, отражается на “оригинале” – внешней переменной first, которая меняет свое значени на 2.

Таким образом, есть 2 основные причины передавать аргументы по ссылке:

  1. избежать копирования

  2. необходимость менять внешние переменные

Приведем пример на каждую из этих причин:

Аргумент по ссылке – без копирования

Создадим функцию size_t countChar(std::string& line, char chr_to_count). Судя только по названию, что она делает?

  • Ответ

    Эта функция принимает строку по ссылке и символ по значению. Возвращает целое неотрицательное (беззнаковое) число, сколько раз этот символ встречается в переданной строке

#include <iostream>
#include <string>

size_t countChar(std::string& line, char chr_to_count) {
    size_t cnt = 0;
    for (const char& chr : line) {
        if (chr == chr_to_count) {
            ++cnt;
        }
    }
    return cnt;
}

int main() {
    std::string input_line;
    std::getline(std::cin, input_line);
    std::cout << countChar(input_line, 'a') << '\n';
}

Строка здесь передается по ссылке, так как нет смысла ее копировать, а это потенциально высокозатратная операция, ведь строка может быть очень большой.

Этот прием обязательно нужно применять при работе со сложными структурами, динамическими объектами, переменными больших типов. Но это не относится к встроенным типам: int, uint64_t, char, их можно передавать по значению даже если ситуация позволяет воспользоваться ссылками

Аргумент по ссылке – изменение внешних переменных

Например, создадим функцию void addToString(std::string& line, char chr_to_add, size_t num), которая дополняет строку некоторым количеством одинаковых символов:

#include <iostream>
#include <string>

void addToString(std::string& line, char chr_to_fill, size_t num) {
    for (size_t i = 0; i < num; ++i) {
        line += chr_to_fill;
    }
}

int main() {
    std::string line = "";
    size_t n;
    std::cin >> n; // 2
    for (size_t i = 0; i < n; ++i) {
        char chr_to_fill;
        size_t num;
        /*
        a 2
        c 4
        */
        std::cin >> chr_to_fill >> num;
        addToString(line, chr_to_fill, num);
    }

    std::cout << line << '\n'; // "aacccc\n"
}

Ввод и вывод программы выше:

Plain Text 2 a 2 c 4 aacccc

Необязательные аргументы

В С++ все аргументы являются позиционными, то есть стоят порядке, определенном при объявлении функции

Аргументы могут быть:

  • обязательными – они необходимы при каждом вызове функции и стоят в строго установленном порядке

  • необязательные (со значением по умолчанию), их можно опускать при вызове функци, тогда будет использованное значение по умолчанию из объявления функции

Важно, что нельзя “пропустить” какой-то необязательный аргумент, то передать последующие. В следующем примере перечислены все возможные виды вызова объявленной функции в необязательными аргументами:

#include <iostream>
#include <string>

void printMessage(const std::string& message, char border_char = '*', int repeat_count = 3) {
    // верхняя граница
    for (int i = 0; i < repeat_count; ++i) {
        std::cout << border_char;
    }
    std::cout << " " << message << " ";
    // верхняя граница нижняя граница
    for (int i = 0; i < repeat_count; ++i) {
        std::cout << border_char;
    }
    std::cout << '\n';
}

int main() {
    // только обязательный аргумент
    printMessage("Some line of text"); // "*** Some line of text ***\n"

    // обязательный и первый необязательный
    printMessage("Some line of text", '#'); // "### Some line of text ###\n"

    // обязательный и оба необязательных
    printMessage("Some line of text", '=', 5); // "===== Some line of text =====\n"

    // вывод без границы (только пробелы останутся)
    printMessage("Some line of text", 'a', 0); // " Some line of text \n"

    return 0;
}

Функция выше выводит на экран символ borderChar в количестве repeatCount до и после сообщения message, обрамленного пробелами с обеих сторон. В функции main() перечислены все способы вызвать функцию printMessage с разными аргументам, иные виды указания аргументов невозможны.

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

Возвращаемое значение

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

#include <iostream>
#include <string>

uint64_t calcSum(uint64_t a, uint64_t b) {
    uint64_t ret_value = a + b;
    ++ret_value;
    return ret_value;
}

int main() {
    uint64_t a = 15;
    uint64_t b = 42;
    uint64_t result = calcSum(a, b);
    std::cout << result << '\n';
}

В примере выше память для возвращаемого значения функции будет выделено 1 раз – это внешняя переменная uint64_t result

  • выделяем память под ret_value вне функции (не как для обыкновенной локальной переменной)

  • проводим все манипуляции в функции

  • return ret_value;

  • теперь эта память управляется переменной uint64_t result в функции main

  • лишнего копирования не произошло

Перегрузки функций

Перегрузки функций (function overloading) – это определение функций с одинаковым названием, но разным набором аргументов. Для успешной компиляции перегрузки функции

Например:

#include <iostream>
#include <string>

// Overload 1: Log with a simple message
void logger(const std::string& message) {
    std::cout << "[INFO]: " << message << std::endl;
}

// Overload 2: Log with an error code and message

void logger(int errorCode, const std::string& message) {
    std::cout << "[ERROR " << errorCode << "]: " << message << std::endl;
}

// Overload 3: Log with a message and a severity level (e.g., INFO, WARNING, ERROR)
void logger(const std::string& message, const std::string& severity) {
    std::cout << "[" << severity << "]: " << message << std::endl;
}

int main() {
    logger("System started successfully.");
    logger(404, "Resource not found.");
    logger("Disk space running low", "WARNING");

    return 0;
}

Вывод примера:

[INFO]: System started successfully.
[ERROR 404]: Resource not found.
[WARNING]: Disk space running low

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

Перегрузка функций позволяет понятно и легко использовать одну конструкцию в различных ситуациях, что упрощает написание и чтение высокоуровневой программы (в данном случае функции main())

Лямбда функции

Лямбда функция – функция без имени, которую можно сохранить “как переменную”. В C++ существую переменные – функции определенного типа.

Синтаксис:

[= or &](T1 arg_1, T2 arg_2){
        // some code
        // some return statement
    };

  • [] – все переменные, которые видны в текущем скоупе, в lambda функции недоступны

  • [=] – все переменные, которые видны в текущем скоупе, доступны в lambda функции по значению

  • [&] – – все переменные, которые видны в текущем скоупе, доступны в lambda функции по ссылке

Например:

#include <iostream>

int getSum(int a, int b) {
    return a + b;
}

int main() {
    int first, second;
    std::cin >> first >> second;
    auto adder = [](int a, int b){
        return a + b;
    };
    int result = adder(first, second);
    std::cout << "Sum is " << result << '\n';
}

Что происходит при выполнении такой строки: [](){}();?

Получения контекста (capture)

#include <iostream>

int getSum(int a, int b) {
    return a + b;
}

int main() {
    int increment_by = 15;
    auto ref_incrementer = [&](int num){ // захват по ссылке
        return num + increment_by;
    };
    std::cout << ref_incrementer(15) << '\n'; // 30
    increment_by = 10; // это изменение повлияет на лямбда функцию
    std::cout << ref_incrementer(15) << '\n'; // 25

}
#include <iostream>

int getSum(int a, int b) {
    return a + b;
}

int main() {
    int increment_by = 15;
    auto ref_incrementer = [=](int num){ // захват по значению
        return num + increment_by;
    };
    std::cout << ref_incrementer(15) << '\n'; // 30
    increment_by = 10; // это изменение НЕ повлияет на лямбда функцию
    std::cout << ref_incrementer(15) << '\n'; // 30

}

Функции высшего порядка

Так называют функции, которые принимают или возвращают другие функции. Как и для любого другого аргумента, для этих операций необходимо явно указывать значение функции Здесь нам на помощь приходит std::function<F>, где F для лямбда-функции определяется как return_type(arg_1_type, arg_2_type, ...)

Пример:

#include <iostream>
#include <functional>

void outputVerdict(int number, std::function<bool(int)> checker) {
    if (checker(number)) {
        std::cout  << "Checker returned true for this value!" << std::endl;
    } else {
        std::cout  << "Checker returned false for this value!" << std::endl;
    }
}

int main() {
    int a = 1;
    int b = 2;
    std::function<bool(int)> is_even = [](int number) {
        return number % 2 == 0;
    };

    exampleFunc(a, is_even); // "Checker return false for this value!"
    exampleFunc(b, is_even); // "Checker return true for this value!"
}