std::vector в C++¶

std::vector — это шаблонный класс стандартной библиотеки языка программирования C++, реализующий динамический массив произвольного доступа. Он определён в заголовочном файле <vector> и является одним из наиболее часто используемых контейнеров стандартной библиотеки шаблонов (STL). Основное свойство std::vector — автоматическое управление памятью: он самостоятельно выделяет и освобождает память при добавлении или удалении элементов, обеспечивая непрерывное хранение данных в памяти.

¶История

Контейнер vector появился в первой реализации стандартной библиотеки шаблонов, созданной Александром Степановым и Мэнгом Ли в лаборатории Hewlett-Packard в начале 1990-х годов. В 1994 году STL была включена в проект стандарта C++, а в 1998 году, с принятием международного стандарта ISO/IEC 14882, std::vector стал частью официальной спецификации языка. Название «vector» отражает математическую концепцию вектора как упорядоченного набора чисел, хотя в отличие от математического вектора, контейнер может хранить объекты любого типа.

¶Характеристики и устройство

std::vector хранит элементы в непрерывной области памяти, что обеспечивает быстрый произвольный доступ к любому элементу за константное время O(1). Каждый элемент занимает фиксированный размер памяти, определяемый типом хранимых данных.

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

При добавлении элементов, когда size достигает capacity, вектор выделяет новый, больший буфер (обычно в 1,5–2 раза больше предыдущего), копирует или перемещает существующие элементы в новый буфер и освобождает старую память. Эта операция имеет амортизированную сложность O(1), то есть в среднем добавление элемента в конец занимает постоянное время, несмотря на периодические перераспределения.

¶Основные операции

Базовые операции std::vector включают:

push_back(element) — добавление элемента в конец вектора;
pop_back() — удаление последнего элемента;
insert(iterator, element) — вставка элемента в произвольную позицию;
erase(iterator) — удаление элемента из произвольной позиции;
clear() — удаление всех элементов;
resize(n) — изменение размера вектора;
reserve(n) — предварительное выделение памяти под n элементов;
size() и capacity() — получение текущего размера и ёмкости;
operator[] и at(index) — доступ к элементу по индексу;
front() и back() — доступ к первому и последнему элементам;
begin(), end(), rbegin(), rend() — итераторы для обхода элементов.

Операции вставки и удаления в середине вектора имеют линейную сложность O(n), так как требуют сдвига всех последующих элементов. Это главное отличие от контейнеров list и forward_list, которые поддерживают вставку за константное время, но не обеспечивают произвольный доступ.

¶Итераторы и совместимость

std::vector предоставляет итераторы произвольного доступа (random access iterators), что позволяет использовать его с большинством алгоритмов стандартной библиотеки, включая std::sort, std::find, std::copy и другие. Итераторы vector поддерживают арифметические операции: it + n, it - n, it1 - it2, а также операторы сравнения.

Важная особенность — совместимость с массивами C: данные vector хранятся непрерывно, поэтому указатель на первый элемент (data() или &v[0]) может быть передан функциям, ожидающим обычный массив. Это позволяет использовать vector в качестве современной замены динамических массивов, создаваемых через new[].

¶Управление памятью

В отличие от встроенных массивов, vector автоматически управляет памятью. При создании пустого вектора память не выделяется; она выделяется при первом добавлении элемента. Деструктор vector автоматически вызывает деструкторы всех хранимых элементов и освобождает память.

Метод reserve позволяет заранее выделить память под известное количество элементов, что может существенно повысить производительность при массовом добавлении данных, устраняя многократные перераспределения. Метод shrink_to_fit (доступен с C++11) уменьшает ёмкость до текущего размера, но его выполнение не гарантируется стандартом.

¶Версии стандарта

Стандарт C++11 внёс значительные улучшения в std::vector. Была добавлена поддержка семантики перемещения: vector получил конструктор перемещения и оператор присваивания перемещением, что позволило эффективно возвращать большие векторы из функций без копирования. Метод emplace_back позволяет конструировать элемент непосредственно в памяти вектора, избегая промежуточного копирования или перемещения.

C++11 также добавил методы data() для получения указателя на внутренний буфер и shrink_to_fit(). В C++17 появилась поддержка vector для типов с неполным определением в некоторых контекстах. C++20 добавил методы erase и erase_if в форме свободных функций, а также contains для ассоциативных контейнеров (для vector не применяется). C++23 продолжил развитие, добавив std::vector::resize_and_overwrite и другие усовершенствования.

¶Специализация vector\<bool\>

Стандартная библиотека предоставляет частичную специализацию std::vector<bool>, которая упаковывает логические значения в биты для экономии памяти. Вместо одного байта на элемент используется один бит, что уменьшает потребление памяти в 8 раз. Однако эта специализация имеет существенные отличия от обычного vector: она не предоставляет ссылки на отдельные элементы (возвращает прокси-объект), несовместима с некоторыми алгоритмами и имеет иные гарантии производительности. Из-за этих особенностей многие разработчики предпочитают использовать std::vector<char> или std::bitset вместо std::vector<bool>.

¶Применение

std::vector является универсальным контейнером, применяемым в подавляющем большинстве C++-программ. Он используется как основа для реализации стеков, очередей, буферов и других структур данных. Vector широко применяется в графических приложениях для хранения вершин и текстур, в научных вычислениях для хранения числовых массивов, в игровых движках для управления игровыми объектами, в обработке сигналов и изображений.

Поскольку vector гарантирует непрерывность памяти, он хорошо совместим с SIMD-инструкциями и позволяет эффективно использовать кэш процессора при последовательном обходе элементов. Это делает его предпочтительным выбором по умолчанию при выборе контейнера в C++, если нет специфических требований к вставке в середину или к стабильности ссылок на элементы.

¶Альтернативы

В зависимости от задачи могут использоваться другие контейнеры. std::deque обеспечивает вставку в начало и конец за константное время, но не гарантирует непрерывность памяти. std::list и std::forward_list позволяют вставлять элементы в произвольное место за O(1), но не поддерживают произвольный доступ. std::array — это обёртка над статическим массивом фиксированного размера, не использующая динамическую память. Для строк используется специализированный контейнер std::basic_string.

¶Интересные факты

Вопреки распространённому мнению, std::vector не является «безопасной» заменой массивов в смысле проверки границ: оператор operator[] не выполняет проверок, а метод at() генерирует исключение std::out_of_range при выходе за границы.
Ссылки и итераторы на элементы vector инвалидируются после перераспределения памяти или вставки/удаления элементов в середине, что требует осторожности при написании циклов с модификацией контейнера.
Стандарт не гарантирует точный коэффициент роста ёмкости; на практике большинство реализаций (libstdc++, libc++, MSVC) используют коэффициенты от 1,5 до 2.
С момента появления STL в 1994 году интерфейс std::vector остался практически неизменным, что свидетельствует об удачности его первоначального дизайна.

¶Источники

Страуструп Б. «Язык программирования C++», 4-е издание.
Джосаттис Н. «Стандартная библиотека C++: справочное руководство», 2-е издание.
Международный стандарт ISO/IEC 14882:2020 (C++20).
cppreference.com — справочные материалы по стандартной библиотеке C++.