Структуры данных

Строка удобна тем, что управляет хранением последовательности и предоставляет готовые операции: узнать длину, добавить символ, получить подстроку. Но каждая операция имеет свои условия. Если строка содержит три символа, её существующие элементы имеют индексы 0, 1 и 2. Индекс — это смещение от начала (сколько элементов нужно пропустить), поэтому первый элемент получает номер ноль.

Для практики важно различать логическую длину строки, индексы существующих символов и нулевой завершающий символ для совместимости с C. Операции с s[i] и s.at(i) выглядят похоже, но по-разному ведут себя при ошибке.

Для строки "cat" значение size() равно трём, а последний обычный символ находится по индексу size() - 1. Такое вычисление последнего индекса имеет смысл только для непустой строки. Ещё одна полезная оговорка: std::string хранит элементы типа char. В UTF-8 одна русская буква может занимать несколько таких элементов, поэтому длина в байтах не всегда равна числу видимых букв.

Как пройти по строке через for

Если нужен номер символа, используй обычный for (std::size_t i = 0; i < text.size(); ++i). На каждом шаге text[i] обращается к очередному элементу. Условие именно i < text.size(): завершающий ноль в такой обход не входит. Пустая строка просто даст ноль итераций.

Вернитесь после темы ссылок. Для первого решения используйте text[i].

Когда индексы не нужны, запись for (char symbol : text) короче: цикл по диапазону (range-based for) сам перебирает все элементы. Здесь symbol — копия очередного char. Для изменения исходной строки нужна ссылка: for (char& symbol : text). Во вкладках ниже есть оба вида обхода и пример изменения символов.

#include <cstddef>
#include <iostream>
#include <string>

int main() {
    std::string text = "Cat";
    for (std::size_t i = 0; i < text.size(); ++i) {
        char symbol = text[i];
        unsigned int code = static_cast<unsigned char>(symbol);
        std::cout << i << ": " << symbol << " -> " << code << '\n';
    }
}

#include <iostream>
#include <string>

int main() {
    std::string text = "C++17";
    int digits = 0;
    for (char symbol : text) {
        std::cout << symbol << ' ';
        if (symbol >= '0' && symbol <= '9') {
            ++digits;
        }
    }
    std::cout << "\ndigits: " << digits << '\n';
}

#include <iostream>
#include <stdexcept>
#include <string>

int main() {
    std::string text = "C++";
    std::cout << text.at(0) << '\n';
    try {
        std::cout << text.at(10) << '\n';
    } catch (const std::out_of_range&) {
        std::cout << "Index outside string\n";
    }
}

#include <iostream>
#include <string>

int main() {
    std::string text = "hello world";
    for (char& symbol : text) {
        if (symbol == ' ') {
            symbol = '_';
        }
    }
    std::cout << text << '\n';
}

Повседневные операции

std::string s = "abc";
s[1] = 'x';          // "axc"
s.push_back('!');    // "axc!"
s.pop_back();        // "axc"
char first = s.front();
char last  = s.back();
std::size_t n = s.size();

char и таблица ASCII

char хранит одну единицу кодировки размером в один байт C++ (на обычных современных системах это 8 бит). Символ и число — разные способы представить это значение: в ASCII-совместимой кодировке, например UTF-8, 'A' имеет код 65, а '0' — 48, а не ноль. Поэтому std::cout << symbol печатает символ, а преобразование к целому позволяет увидеть его числовой код.

ASCII задаёт 128 кодов: от 0 до 127. Коды 32–126 печатные (включая пробел), остальные — управляющие. Например, '\n' означает перевод строки, а '\0' — нулевой символ. Значения выше 127 зависят от кодировки и не входят в ASCII; для русской буквы в UTF-8 обычно нужны два байта, поэтому один char не всегда равен одной видимой букве.

Чтобы получить неотрицательное значение байта, сначала преобразуй char к unsigned char, затем к целому типу: unsigned int code = static_cast<unsigned char>(symbol);. Это показано во вкладке «for по индексу» выше. Такое преобразование показывает код байта; декодирование букв Unicode — отдельная задача.

Поиск и преобразование подстроки

#include <cstddef>
#include <iostream>
#include <string>
int main() {
    std::string text = "one two";
    const std::size_t position = text.find("two");
    if (position != std::string::npos) {
        std::cout << text.substr(position, 3) << '\n';
        text.erase(position, 3);
        text.insert(position, "three");
    }
    std::cout << text << '\n';
}

Задание: замените слово cat в строке на dog. Проверьте начало, конец и отсутствие слова. Чтение строки с пробелами выполняйте через getline; после числового ввода учитывайте оставшийся перевод строки.

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

Когда значений несколько, удобно хранить их в одной последовательности. Вектор grades содержит пять оценок. У каждого существующего элемента есть индекс: первый имеет номер ноль, последний — на единицу меньше размера. Метод size сообщает число элементов. Обращение grades[i] позволяет прочитать или изменить конкретную оценку, если индекс допустим. Цикл в примере проходит именно существующие элементы и накапливает их сумму. Начальный ноль важен: до первого шага ни одна оценка ещё не учтена. Для среднего деление должно быть вещественным, поэтому размер явно преобразован к double. Пустая последовательность не имеет среднего: этот случай проверяется до деления. Добавление через push_back создаёт ещё один элемент в конце. Пока нам достаточно этих операций. Запас памяти, перенос буфера и сохранённые адреса разберём после того, как научимся уверенно обрабатывать значения и проверять границы.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> grades{5, 4, 3, 5, 4};
    if (grades.empty()) {
        std::cout << "No grades\n";
        return 0;
    }
    int sum = 0;
    for (int grade : grades) {
        sum += grade;
    }
    const double average = sum / static_cast<double>(grades.size());
    std::cout << sum << ' ' << average << '\n';
}

Выбирай вектор по умолчанию, когда нужен изменяемый массив с быстрым индексированием. Сейчас нужны size(), push_back() и доступ по допустимому индексу. Остальные методы разобраны ниже.

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

#include <iostream>
#include <vector>

int main() {
    std::vector<int> values;
    values.reserve(8);
    std::cout << values.size() << '\n';
    values.resize(3, 7);
    std::cout << values.size() << ' ' << values.at(0) << '\n';
}

#include <cstddef>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> values{2, 4, 6};
    const std::size_t original_size = values.size();
    for (std::size_t i = 0; i < original_size; ++i) {
        const int doubled = values[i] * 2;
        values.push_back(doubled);
    }
    for (int value : values) {
        std::cout << value << ' ';
    }
    std::cout << '\n';
}

#include <iostream>
#include <vector>

int main() {
    std::vector<int> values{10, 20, 30};
    if (!values.empty()) {
        std::cout << values.front() << ' ' << values.back() << '\n';
        values.front() = 11;
        values.back() = 33;
    }
    std::cout << values[1] << ' ' << values.at(1) << '\n';
    values.push_back(40);
    std::cout << values.size() << ' ' << values.back() << '\n';
    values.pop_back();
    std::cout << values.size() << ' ' << values.back() << '\n';
}

std::vector<int> v = {1, 2, 3};
v.reserve(10);       // capacity() >= 10, size() == 3
v.push_back(4);      // size() == 4
v.resize(6, 7);     // {1, 2, 3, 4, 7, 7}
v.clear();          // size() == 0
// capacity() может остаться прежней

Методы и обращение к элементам std::vector

В примерах ниже v — объект std::vector<int>. front() возвращает первый элемент, back() — последний, а v[i] позволяет выбрать элемент по индексу. Это обращения к самим элементам (полученное значение можно читать или менять), а не удаление из контейнера.

Итератор — это позиция в контейнере (его можно передвигать и разыменовывать, как указатель). После перераспределения памяти все прежние указатели, ссылки и итераторы на элементы недействительны. Даже без перераспределения вставка или удаление может сделать недействительными позиции от места изменения и дальше; после push_back прежний end() тоже меняется.

v.reserve(10);
v[9] = 42; // UB, если size < 10

v.resize(10);
v[9] = 42; // элемент существует

std::vector<int> v = {2, 4, 6};
int x = v[1];       // 4
int y = v.at(1);    // 4
// v.at(3);         // std::out_of_range
// v[3];            // UB: за пределами size()

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

Для первых задач достаточно: текст — std::string; изменяемая последовательность — std::vector. Остальные строки таблицы пригодятся после практики обхода и поиска. Не требуется запоминать устройство всех контейнеров на этом занятии.

Обозначения O(1), O(log n) и O(n) описывают, как растёт объём работы при увеличении числа элементов, а не точное время в секундах. Например, линейный поиск может проверить все записи, тогда как индексирование вектора не требует обходить предыдущие элементы. Для небольшой учебной задачи понятный vector часто удобнее сложной комбинации структур; усложнять хранение стоит под конкретную потребность.

Иногда важно не место элемента в массиве, а правило, по которому его разрешено забрать. Стек похож на историю отмены действий: первым отменяется последнее действие. Очередь подходит для обработки заявок в порядке поступления. Эти структуры намеренно предоставляют ограниченный набор операций (помогают выразить нужный порядок работы, а не дают произвольный доступ к любому элементу).

Положите числа 1, 2 и 3 в стек и в очередь. У стека первым доступно 3 через top(), у очереди — 1 через front(). Метод pop() только удаляет этот элемент: если значение понадобится дальше, его следует сохранить до удаления. Перед чтением и удалением проверьте empty(), потому что у пустой структуры нет элемента для такой операции.

#include <iostream>
#include <queue>
#include <stack>

int main() {
    std::stack<int> stack;
    std::queue<int> queue;
    for (int value : {1, 2, 3}) {
        stack.push(value);
        queue.push(value);
    }
    while (!stack.empty()) {
        std::cout << stack.top();
        stack.pop();
    }
    std::cout << '\n';
    while (!queue.empty()) {
        std::cout << queue.front();
        queue.pop();
    }
    std::cout << '\n';
}

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> tasks;
    for (int priority : {4, 9, 2}) {
        tasks.push(priority);
    }
    while (!tasks.empty()) {
        std::cout << tasks.top() << ' ';
        tasks.pop();
    }
    std::cout << '\n';
}

std::stack<int> s;
s.push(5); s.push(8);
int top = s.top();       // 8
s.pop();

std::queue<int> q;
q.push(5); q.push(8);
int first = q.front();   // 5
q.pop();

Очередь с приоритетом

В обычной очереди порядок определяется временем добавления, а в priority_queue — приоритетом. Стандартная реализация по умолчанию выдаёт наибольшее значение через top().

std::priority_queue<int> pq;
pq.push(4); pq.push(9); pq.push(2);
int mx = pq.top();      // 9
pq.pop();               // удалит 9

При поиске по индексу мы спрашиваем: «Что лежит на третьем месте?». При поиске по ключу вопрос другой: «Какое значение связано с этим именем?». Например, в словаре можно хранить название товара и количество на складе. Ключ определяет, какую запись искать, а значение содержит связанные с ним данные. Множество решает более узкую задачу — хранит сами уникальные ключи без отдельного значения.

Если нужно считать слова, выражение ++counts[word] удобно: отсутствующему слову сначала создаётся счётчик со значением ноль, а затем он увеличивается. Но при обычной проверке наличия такая вставка может оказаться неожиданной. Метод find позволяет спросить, есть ли ключ, не добавляя его. Возвращённый end() означает «совпадение не найдено» (это специальная позиция за последним элементом, а не найденная запись).

#include <iostream>
#include <map>
#include <sstream>
#include <string>

int main() {
    std::istringstream input{"red blue red"};
    std::map<std::string, int> counts;
    std::string word;
    while (input >> word) {
        ++counts[word];
    }
    for (const auto& [key, count] : counts) {
        std::cout << key << ": " << count << '\n';
    }
}

#include <iostream>
#include <set>

int main() {
    std::set<int> values{3, 1, 3, 2};
    const auto [position, inserted] = values.insert(2);
    std::cout << std::boolalpha << inserted << ' ' << *position << '\n';
    for (int value : values) {
        std::cout << value << ' ';
    }
    std::cout << '\n';
}

std::map<std::string, int> m;
m["abc"] = 1;       // создаёт пару
m["abc"] = 5;       // обновляет значение
m.size();            // 1
m.erase("abc");      // удаляет пару

std::set<int> s;
s.insert(3);
s.insert(3);     // дубликата не будет
s.size();        // 1
bool found = s.count(3) != 0;
s.erase(3);

А если ключи повторяются?

multimap и multiset разрешают дубликаты. У multimap нет operator[]; lower_bound(k) и upper_bound(k) позволяют получить диапазон одинаковых ключей.

std::multimap<int, char> m;
m.insert({2, 'a'});
m.insert({2, 'b'});
auto first = m.lower_bound(2); // первый >= 2
auto last = m.upper_bound(2);  // первый > 2
// [first, last) — все пары с ключом 2

std::unordered_map<int, int> m;
m[10] = 1;
m[3] = 8;
// Обход НЕ гарантирует сортировку по ключам
// find / insert / erase: O(1) в среднем