Стандартная библиотека: обзор контейнеров, алгоритмов, итераторов

Введение

Цикл неоднократно использовал отдельные элементы стандартной библиотеки (std::vector статья 518/542, std::map статья 458/523, std::sort статья 461 алгоритмического цикла) — в этой статье дадим систематический, обзорный взгляд на структуру стандартной библиотеки C++ как целостной экосистемы взаимодействующих контейнеров, алгоритмов и итераторов.

Концепция

Стандартная библиотека C++ организована вокруг трёх взаимодействующих категорий компонентов — контейнеры (хранение данных, как std::vector, std::map, std::list, статьи 456-458 алгоритмического цикла), алгоритмы (операции над данными — сортировка, поиск, преобразование, статьи 461-462 алгоритмического цикла), и итераторы — абстракция, связывающая первые две категории, позволяющая алгоритмам работать с произвольным контейнером единообразно, без необходимости знать конкретный тип контейнера, для которого они вызываются. Эта архитектура (концептуально вдохновлённая исходной STL, Standard Template Library) даёт мощную композицию — один и тот же алгоритм (std::sort, std::find, std::transform) применим к любому контейнеру, предоставляющему итераторы соответствующей категории, без необходимости писать отдельную версию алгоритма для каждого конкретного контейнера.

Пример кода: Стандартная библиотека

#include <vector>
#include <list>
#include <algorithm>
#include <iostream>

template<typename Container>
void printAll(const Container &container)
{
    // Один и тот же код работает для ЛЮБОГО контейнера, поддерживающего begin()/end()
    for (const auto &item : container) {
        std::cout << item << " ";
    }
    std::cout << std::endl;
}

int main()
{
    std::vector<int> vec = {5, 3, 1, 4, 2};
    std::list<int> lst = {5, 3, 1, 4, 2};

    std::sort(vec.begin(), vec.end()); // алгоритм sort работает через ИТЕРАТОРЫ, не зная конкретный тип vector
    printAll(vec); // 1 2 3 4 5

    // std::sort(lst.begin(), lst.end()); // ОШИБКА — list НЕ поддерживает итераторы случайного доступа,
    // нужные std::sort (статья 456 — list не даёт O(1) доступ по индексу, в отличие от vector)
    lst.sort(); // у list ЕСТЬ собственный, специализированный метод sort(), оптимизированный для его структуры
    printAll(lst);

    return 0;
}

// Различные категории алгоритмов стандартной библиотеки
#include <algorithm>
#include <numeric>
#include <vector>
#include <iostream>

int main()
{
    std::vector<int> numbers = {1, 2, 3, 4, 5};

    // Поиск
    auto it = std::find(numbers.begin(), numbers.end(), 3);
    std::cout << "Найдено: " << (it != numbers.end()) << std::endl;

    // Преобразование — применение функции к каждому элементу, результат в НОВЫЙ контейнер
    std::vector<int> squared(numbers.size());
    std::transform(numbers.begin(), numbers.end(), squared.begin(), [](int n) { return n * n; });

    // Накопление/свёртка
    int sum = std::accumulate(numbers.begin(), numbers.end(), 0);
    std::cout << "Сумма: " << sum << std::endl;

    // Подсчёт по условию
    int evenCount = std::count_if(numbers.begin(), numbers.end(), [](int n) { return n % 2 == 0; });
    std::cout << "Чётных: " << evenCount << std::endl;

    return 0;
}

Пояснения к коду

printAll<Container>, работающий идентично для std::vector и std::list, показывает суть единообразного интерфейса через итераторы — функция не знает и не должна знать конкретный тип контейнера, ей достаточно того, что любой подходящий контейнер предоставляет begin()/end(), дающие итераторы, по которым можно пройти стандартным циклом. Сравнение std::sort(vec.begin(), vec.end()) (работающего) и закомментированной попытки std::sort(lst.begin(), lst.end()) (не компилирующейся) демонстрирует важный практический аспект архитектуры итераторов — не все алгоритмы работают с любым видом итератора, и std::sort конкретно требует итераторы произвольного доступа (random access), которые std::vector предоставляет благодаря своей структуре (статья 456), но std::list принципиально не может предоставить эффективно из-за своей связной, а не непрерывной структуры, что и объясняет, почему std::list вместо этого предоставляет собственный, специализированный метод sort(). Набор алгоритмов (std::find, std::transform, std::accumulate, std::count_if) показывает типичное разнообразие категорий стандартных алгоритмов — поиск, преобразование данных, накопление результата через свёртку, и подсчёт по условию — каждый из которых, как и std::sort, работает через единообразный интерфейс итераторов, применимый к широкому спектру различных контейнеров, поддерживающих соответствующую категорию итераторов.

Подводные камни

• Попытка использовать алгоритм с контейнером, не предоставляющим итераторы нужной категории (как явно показано с std::sort и std::list) — это даёт ошибку компиляции, обычно довольно многословную и не всегда сразу понятную (особенно для шаблонного кода стандартной библиотеки, статья 541 про сложность диагностики ошибок шаблонов), и понимание иерархии категорий итераторов (от input/output итераторов с минимальными возможностями до итераторов произвольного доступа с максимальными возможностями) важно для понимания, почему конкретный алгоритм работает с одними контейнерами, но не с другими.
• Игнорирование специализированных, оптимизированных методов конкретных контейнеров в пользу универсальных алгоритмов там, где специализированный метод явно предпочтительнее (как list::sort() вместо попытки применить общий std::sort) — стандартная библиотека часто предоставляет специализированные методы именно потому, что общий, универсальный алгоритм неприменим или неэффективен для конкретной структуры данных, и предпочтение специализированного метода, когда он доступен и подходит для задачи, обычно более правильное решение, чем попытка обойти ограничение через какой-либо более общий, но менее подходящий инструмент.
• Инвалидация итераторов после изменения контейнера во время итерации (статья 456 про инвалидацию итераторов vector после операций, изменяющих емкость) — это особенно частая ошибка при использовании алгоритмов, модифицирующих контейнер во время его обхода (например, попытка удалить элементы внутри цикла, использующего итераторы того же контейнера без явного, корректного обновления этих итераторов после каждого удаления), и стандартная библиотека предоставляет специальные паттерны (идиома «erase-remove» через std::remove в сочетании с методом erase контейнера) для безопасного решения подобных задач, избегающих этой проблемы.
• Создание собственной, «велосипедной» реализации функциональности, уже хорошо реализованной в стандартной библиотеке (собственная сортировка вместо std::sort, собственный поиск вместо std::find) без действительно веской причины — стандартные алгоритмы тщательно протестированы, как правило хорошо оптимизированы (часто значительно лучше, чем наивная, самостоятельно написанная реализация той же логики), и предпочтение стандартных алгоритмов собственным, заново написанным реализациям для типичных, распространённых задач — общепринятая, рекомендуемая практика современного C++, экономящая время разработки и снижающая риск ошибок по сравнению с написанием той же функциональности с нуля.