std::vector: от основ до тонкостей реализации

Полное практическое руководство по одному из самых популярных контейнеров в C++

Введение

std::vector — это, пожалуй, самый используемый контейнер STL. Он кажется простым на первый взгляд: динамический массив с автоматическим управлением памятью. Но под капотом скрывается множество тонкостей, знание которых отличает начинающего программиста от профессионала.

В этой статье мы пройдем путь от базового использования до глубокого понимания внутреннего устройства std::vector, рассмотрим все его методы, особенности работы с памятью, исключения, трюки оптимизации и подводные камни. А также рассмотрим альтернативы std::vector и когда их стоит использовать.

Часть 1: Основы

Что такое std::vector?

std::vector — это контейнер последовательности, который инкапсулирует динамический массив. Элементы хранятся непрерывно в памяти, что обеспечивает:

• Константный доступ по индексу O(1)

• Эффективный проход по элементам

• Совместимость с C-style массивами

#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    
    // Доступ по индексу
    std::cout << v[0] << std::endl;  // 1
    
    // Размер и вместимость
    std::cout << "size: " << v.size() << std::endl;      // 5
    std::cout << "capacity: " << v.capacity() << std::endl; // >= 5
    
    return 0;
}

Size vs Capacity: ключевое различие

Это критически важное различие для понимания std::vector:

• size() — количество элементов, которые фактически хранятся в векторе

• capacity() — количество элементов, для которых выделена память (без реаллокации)

std::vector<int> v;
std::cout << "size: " << v.size() << ", capacity: " << v.capacity() << std::endl;
// size: 0, capacity: 0

v.push_back(1);
std::cout << "size: " << v.size() << ", capacity: " << v.capacity() << std::endl;
// size: 1, capacity: 1 (или больше, зависит от реализации)

v.push_back(2);
std::cout << "size: " << v.size() << ", capacity: " << v.capacity() << std::endl;
// size: 2, capacity: 2 (или больше)

Требования к элементам контейнера

std::vector накладывает определенные требования на тип T:

Обязательные требования:

1. Деструктор — должен быть доступен

2. Конструктор перемещения или копирования — для операций вставки/реаллокации

Рекомендуемые требования:

1. Конструктор перемещения помечен noexcept — это критически важно для производительности!

class MyClass {
public:
    MyClass() = default;
    
    // ❌ Плохо: может бросить исключение
    MyClass(MyClass&& other) { /* ... */ }
    
    // ✅ Хорошо: гарантированно не бросит
    MyClass(MyClass&& other) noexcept { /* ... */ }
};

Почему noexcept важен?

При реаллокации памяти std::vector проверяет, помечен ли конструктор перемещения как noexcept:

• Если да → использует перемещение (быстро)

• Если нет → использует копирование (медленно, но безопасно при исключениях)

#include <vector>
#include <iostream>
#include <type_traits>

class WithNoexcept {
public:
    WithNoexcept(WithNoexcept&&) noexcept {}
};

class WithoutNoexcept {
public:
    WithoutNoexcept(WithoutNoexcept&&) {}
};

int main() {
    std::vector<WithNoexcept> v1;
    std::vector<WithoutNoexcept> v2;
    
    // v1 будет использовать move при реаллокации
    // v2 будет использовать copy при реаллокации
    
    std::cout << std::is_nothrow_move_constructible<WithNoexcept>::value << std::endl;     // 1
    std::cout << std::is_nothrow_move_constructible<WithoutNoexcept>::value << std::endl;  // 0
    
    return 0;
}

Часть 2: Управление памятью

reserve(): предварительное выделение памяти

Сигнатура: void reserve(size_type new_cap)

Что делает: Резервирует память для как минимум new_cap элементов. Не создает элементы, только выделяет память.

Когда использовать:

• ✅ Вы знаете заранее, сколько элементов будет

• ✅ Хотите избежать реаллокаций при множественных push_back

• ✅ Оптимизируете производительность

Когда НЕ использовать:

• ❌ Не знаете точное количество элементов

• ❌ Элементов будет мало (1-10)

• ❌ Работаете с огромными объектами и хотите экономить память

std::vector<int> v;

// ❌ Плохо: множественные реаллокации
for (int i = 0; i < 10000; ++i) {
    v.push_back(i);  // может вызвать реаллокацию много раз
}

// ✅ Хорошо: одна реаллокация
std::vector<int> v2;
v2.reserve(10000);  // выделили память заранее
for (int i = 0; i < 10000; ++i) {
    v2.push_back(i);  // без реаллокаций
}

Что возвращает: void — ничего не возвращает.

Может ли бросить исключение: Да

• std::length_error — если new_cap > max_size()

• std::bad_alloc — если не удалось выделить память

• Исключение из конструктора копирования/перемещения элемента при реаллокации

Что происходит, если память уже выделена:

std::vector<int> v;
v.reserve(100);
std::cout << v.capacity() << std::endl;  // >= 100

v.reserve(50);  // ❌ НЕ уменьшает capacity!
std::cout << v.capacity() << std::endl;  // >= 100 (не изменилось)

v.reserve(200);  // ✅ Увеличивает capacity
std::cout << v.capacity() << std::endl;  // >= 200

Правило: reserve() никогда не уменьшает capacity().

Что происходит с элементами:

Если reserve(n) больше текущего capacity():

1. Выделяется новый блок памяти размером >= n

2. Все существующие элементы перемещаются (или копируются) в новую память

3. Старая память освобождается

4. Все итераторы, указатели и ссылки на элементы становятся невалидными

std::vector<int> v = {1, 2, 3};
int* ptr = &v[0];  // указатель на первый элемент

v.reserve(1000);   // реаллокация!

// ❌ ptr теперь указывает на освобожденную память!
// Использование ptr — undefined behavior

resize(): изменение размера

Сигнатура:

• void resize(size_type count)

• void resize(size_type count, const T& value)

Что делает: Изменяет количество элементов (size()) в векторе.

std::vector<int> v = {1, 2, 3};

// Увеличение размера
v.resize(5);  // добавляет элементы со значением по умолчанию (0)
// v = {1, 2, 3, 0, 0}

v.resize(7, 42);  // добавляет элементы со значением 42
// v = {1, 2, 3, 0, 0, 42, 42}

// Уменьшение размера
v.resize(2);  // удаляет элементы с конца
// v = {1, 2}

Разница с reserve():

Может ли бросить исключение: Да

• std::length_error — если count > max_size()

• std::bad_alloc — при реаллокации

• Исключение из конструктора T при создании новых элементов

shrink_to_fit(): освобождение лишней памяти

Сигнатура: void shrink_to_fit()

Что делает: "Просьба" уменьшить capacity() до size() — освободить неиспользуемую память.

Важно: Это не обязательная операция! Стандарт не гарантирует, что память будет освобождена.

std::vector<int> v(1000);  // size = 1000, capacity >= 1000
v.resize(10);              // size = 10, capacity >= 1000 (!)

std::cout << "Before: capacity = " << v.capacity() << std::endl;  // >= 1000

v.shrink_to_fit();  // просим освободить лишнюю память

std::cout << "After: capacity = " << v.capacity() << std::endl;   // >= 10 (обычно)

Плюсы:

• ✅ Освобождает неиспользуемую память

• ✅ Полезно после массового удаления элементов

Минусы:

• ❌ Может вызвать реаллокацию (дорого)

• ❌ Инвалидирует все итераторы, указатели и ссылки

• ❌ Не гарантирует освобождение памяти (реализация может проигнорировать)

Может ли бросить исключение: Да (при реаллокации)

Когда использовать:

• После массового удаления элементов

• Когда память критична

• Когда уверены, что вектор больше не будет расти

Стратегии выделения памяти

Как std::vector выделяет память при push_back()?

Когда size() == capacity() и вы вызываете push_back(), вектор:

1. Выделяет новый блок памяти (обычно в 1.5-2 раза больше текущего)

2. Перемещает/копирует все элементы в новую память

3. Вставляет новый элемент

4. Освобождает старую память

Типичные стратегии роста:

• MSVC: capacity × 1.5

• GCC/Clang: capacity × 2

std::vector<int> v;
std::cout << "capacity: " << v.capacity() << std::endl;  // 0

for (int i = 0; i < 10; ++i) {
    v.push_back(i);
    std::cout << "size: " << v.size() 
              << ", capacity: " << v.capacity() << std::endl;
}

// Пример вывода (GCC):
// size: 1, capacity: 1
// size: 2, capacity: 2
// size: 3, capacity: 4
// size: 4, capacity: 4
// size: 5, capacity: 8
// size: 6, capacity: 8
// ...

Амортизированная сложность: push_back() имеет амортизированную константную сложность O(1), несмотря на периодические реаллокации.

Часть 3: Доступ к элементам

operator[] vs at()

operator[]:

• T& operator[](size_type pos)

• const T& operator[](size_type pos) const

at():

• T& at(size_type pos)

• const T& at(size_type pos) const

Ключевое различие: проверка границ

std::vector<int> v = {1, 2, 3};

// operator[] — НЕ проверяет границы
int x = v[10];  // ❌ Undefined behavior! Но компилируется

// at() — проверяет границы
try {
    int y = v.at(10);  // ✅ Бросает std::out_of_range
} catch (const std::out_of_range& e) {
    std::cout << "Error: " << e.what() << std::endl;
}

Когда использовать:

// ✅ Используем operator[] — индекс всегда валиден
for (size_t i = 0; i < v.size(); ++i) {
    std::cout << v[i] << std::endl;
}

// ✅ Используем at() — индекс от пользователя
size_t user_index;
std::cin >> user_index;
try {
    std::cout << v.at(user_index) << std::endl;
} catch (const std::out_of_range&) {
    std::cout << "Invalid index!" << std::endl;
}

Производительность: operator[] быстрее, так как не содержит проверки границ. Разница обычно незначительна, но в tight loops может быть заметна.

front(), back(), data()

std::vector<int> v = {1, 2, 3, 4, 5};

// front() — первый элемент
int first = v.front();  // 1
// Эквивалентно: v[0] или v.at(0)

// back() — последний элемент
int last = v.back();    // 5
// Эквивалентно: v[v.size() - 1]

// data() — указатель на первый элемент (C-style массив)
int* ptr = v.data();
// Можно передать в C API
some_c_function(v.data(), v.size());

⚠️ Важно: front() и back() на пустом векторе — undefined behavior!

std::vector<int> empty;
int x = empty.front();  // ❌ UB!
int y = empty.back();   // ❌ UB!

// ✅ Правильно: проверяйте перед использованием
if (!empty.empty()) {
    int x = empty.front();
}

Часть 4: Модификация элементов

push_back() vs emplace_back()

push_back():

void push_back(const T& value);  // копирование
void push_back(T&& value);       // перемещение

emplace_back() (C++11):

template<class... Args>
void emplace_back(Args&&... args);  // конструирование in-place

Разница:

• push_back создает объект, затем перемещает/копирует его в вектор

• emplace_back создает объект прямо в векторе (без копирования/перемещения)

struct Point {
    int x, y;
    
    Point(int x, int y) : x(x), y(y) {
        std::cout << "Constructor\n";
    }
    
    Point(const Point&) {
        std::cout << "Copy constructor\n";
    }
    
    Point(Point&&) noexcept {
        std::cout << "Move constructor\n";
    }
};

std::vector<Point> v;
v.reserve(10);  // чтобы избежать реаллокаций

// push_back: конструктор + move
v.push_back(Point(1, 2));
// Вывод:
// Constructor
// Move constructor

// emplace_back: только конструктор
v.emplace_back(3, 4);
// Вывод:
// Constructor

Когда использовать emplace_back:

• ✅ Сложные объекты с дорогостоящим перемещением

• ✅ Хотите избежать создания временного объекта

• ✅ Передаете аргументы конструктора напрямую

Может ли бросить исключение: Да (оба метода)

• Исключение при реаллокации

• Исключение из конструктора T

Что возвращают:

• push_back: void (до C++17), reference (C++17+)

• emplace_back: void (до C++17), reference (C++17+)

insert() и emplace()

insert() — вставка в произвольную позицию:

// Вставить один элемент
iterator insert(const_iterator pos, const T& value);
iterator insert(const_iterator pos, T&& value);

// Вставить n копий
iterator insert(const_iterator pos, size_type count, const T& value);

// Вставить диапазон
template<class InputIt>
iterator insert(const_iterator pos, InputIt first, InputIt last);

emplace() — конструирование in-place в произвольной позиции:

template<class... Args>
iterator emplace(const_iterator pos, Args&&... args);

std::vector<int> v = {1, 2, 3, 4, 5};

// Вставка одного элемента
auto it = v.insert(v.begin() + 2, 42);  // {1, 2, 42, 3, 4, 5}

// Вставка нескольких элементов
v.insert(v.begin(), 3, 100);  // {100, 100, 100, 1, 2, 42, 3, 4, 5}

// Вставка диапазона
std::vector<int> other = {7, 8, 9};
v.insert(v.end(), other.begin(), other.end());

⚠️ Важно: Вставка в середину вектора — дорогая операция O(n), так как требует сдвига всех элементов после точки вставки.

Инвалидация итераторов:

• Если вставка вызвала реаллокацию → все итераторы инвалидируются

• Иначе → инвалидируются итераторы после точки вставки

erase() и удаление элементов

erase():

iterator erase(const_iterator pos);
iterator erase(const_iterator first, const_iterator last);

std::vector<int> v = {1, 2, 3, 4, 5};

// Удаление одного элемента
v.erase(v.begin() + 2);  // {1, 2, 4, 5}

// Удаление диапазона
v.erase(v.begin() + 1, v.begin() + 3);  // {1, 5}

pop_back() — удаление последнего элемента:

void pop_back();

std::vector<int> v = {1, 2, 3};
v.pop_back();  // {1, 2}

⚠️ Важно: pop_back() на пустом векторе — undefined behavior!

Может ли бросить исключение: erase() и pop_back() — нет (гарантия no-throw)

Инвалидация итераторов:

• erase() — инвалидируются итераторы после точки удаления

• pop_back() — инвалидируется итератор на последний элемент

clear() — очистка вектора

void clear() noexcept;

Что делает: Удаляет все элементы, size() становится 0.

Что НЕ делает: НЕ освобождает память! capacity() остается прежним.

std::vector<int> v(1000);
std::cout << "size: " << v.size() << ", capacity: " << v.capacity() << std::endl;
// size: 1000, capacity: 1000

v.clear();
std::cout << "size: " << v.size() << ", capacity: " << v.capacity() << std::endl;
// size: 0, capacity: 1000 (!)

Может ли бросить исключение: Нет (гарантия noexcept)

Часть 5: swap() — обмен содержимым

Сигнатура:

void swap(vector& other) noexcept;

Что делает: Обменивает содержимое двух векторов за константное время O(1).

std::vector<int> v1 = {1, 2, 3};
std::vector<int> v2 = {4, 5, 6, 7, 8};

std::cout << "Before swap:\n";
std::cout << "v1.size() = " << v1.size() << ", v1.capacity() = " << v1.capacity() << std::endl;
std::cout << "v2.size() = " << v2.size() << ", v2.capacity() = " << v2.capacity() << std::endl;

v1.swap(v2);  // или std::swap(v1, v2);

std::cout << "After swap:\n";
std::cout << "v1.size() = " << v1.size() << ", v1.capacity() = " << v1.capacity() << std::endl;
std::cout << "v2.size() = " << v2.size() << ", v2.capacity() = " << v2.capacity() << std::endl;

// v1 = {4, 5, 6, 7, 8}
// v2 = {1, 2, 3}

Что происходит с элементами: Элементы не перемещаются и не копируются! Обмениваются только внутренние указатели.

Что происходит с итераторами: Итераторы остаются валидными, но теперь ссылаются на другой вектор!

std::vector<int> v1 = {1, 2, 3};
std::vector<int> v2 = {4, 5, 6};

auto it1 = v1.begin();  // указывает на элемент 1 в v1

v1.swap(v2);

// it1 все еще валиден, но теперь указывает на элемент в v2!
std::cout << *it1 << std::endl;  // 1 (элемент теперь в v2)

Может ли бросить исключение: Нет (гарантия noexcept)

Трюк: освобождение памяти через swap

До C++11 shrink_to_fit() не существовало. Использовался трюк:

std::vector<int> v(1000);
v.resize(10);  // size = 10, capacity = 1000

// ❌ clear() не освобождает память
v.clear();  // size = 0, capacity = 1000

// ✅ Трюк: swap с временным пустым вектором
std::vector<int>().swap(v);  // size = 0, capacity = 0

Как это работает:

1. std::vector() — создается пустой временный вектор

2. .swap(v) — обмен содержимым: v становится пустым, временный получает старые данные

3. Временный вектор уничтожается вместе со старыми данными v

Другой вариант (еще более идиоматичный):

std::vector<int> v(1000);
v.resize(10);

// Освобождение лишней памяти через swap с копией
std::vector<int>(v).swap(v);

Как это работает:

1. std::vector(v) — создается копия v с capacity() == size()

2. .swap(v) — обмен: v получает компактную копию

3. Старый v (с большим capacity()) уничтожается

Сегодня: Используйте shrink_to_fit() вместо этих трюков. Но знать их полезно для работы с legacy-кодом.

Часть 6: std::vector — особый случай

std::vector — это специализация шаблона std::vector, которая не ведет себя как обычный std::vector.

Почему std::vector особенный?

Цель: Экономия памяти. Обычный bool занимает 1 байт, но std::vector хранит каждый bool как 1 бит.

#include <vector>
#include <iostream>

int main() {
    std::vector<bool> vb(100);
    std::vector<int> vi(100);
    
    // vb занимает ~13 байт (100 бит + overhead)
    // vi занимает ~400 байт (100 × 4 байта)
    
    return 0;
}

Проблемы с std::vector

Проблема 1: operator[] возвращает не bool&, а специальный proxy-объект.

std::vector<bool> vb = {true, false, true};

// ❌ Не компилируется!
// bool& ref = vb[0];  // Error: cannot bind non-const lvalue reference

// ✅ Работает (но это proxy, не настоящая ссылка)
auto ref = vb[0];
ref = false;  // изменяет vb[0]

// ❌ Взятие адреса не работает
// bool* ptr = &vb[0];  // Error

Проблема 2: Нарушает ожидания от std::vector.

template<typename T>
void process(std::vector<T>& v) {
    T& first = v[0];  // ✅ Работает для std::vector<int>
                      // ❌ Не работает для std::vector<bool>
}

Проблема 3: Медленнее для поэлементных операций (из-за битовой упаковки).

// std::vector<int> — быстрее
for (auto& elem : vi) {
    elem = 42;  // прямая запись в память
}

// std::vector<bool> — медленнее
for (auto elem : vb) {  // заметьте: не auto&
    elem = true;  // битовые операции
}

Альтернативы std::vector

Если вам нужны реальные bool элементы:

// ✅ Используйте std::vector<char>
std::vector<char> vc = {1, 0, 1};
bool& ref = reinterpret_cast<bool&>(vc[0]);  // теперь работает

// ✅ Используйте std::deque<bool> (не специализирован)
std::deque<bool> db = {true, false, true};
bool& ref2 = db[0];  // настоящая ссылка

// ✅ Используйте std::bitset (если размер известен на компиляции)
std::bitset<100> bs;
bs[0] = true;

Когда использовать std::vector:

• Нужна экономия памяти

• Много элементов (тысячи, миллионы)

• Редко нужны ссылки на отдельные элементы

Часть 7: Исключения в std::vector

Какие методы могут бросить исключения?

Гарантии безопасности исключений

std::vector предоставляет строгую гарантию (strong exception guarantee) для большинства операций:

• Если операция бросает исключение, вектор остается в исходном состоянии

• НО: только если конструктор перемещения T помечен noexcept!

struct ThrowingType {
    ThrowingType() = default;
    ThrowingType(const ThrowingType&) = default;
    
    // ❌ Может бросить исключение
    ThrowingType(ThrowingType&&) {
        throw std::runtime_error("Move failed!");
    }
};

std::vector<ThrowingType> v(10);
try {
    v.reserve(20);  // может привести к неконсистентному состоянию!
} catch (...) {
    // v может быть поврежден
}

Правило: Всегда помечайте конструктор перемещения как noexcept!

Часть 8: Итераторы и их инвалидация

Типы итераторов

std::vector<int> v = {1, 2, 3, 4, 5};

// Iterator
std::vector<int>::iterator it = v.begin();

// Const iterator
std::vector<int>::const_iterator cit = v.cbegin();

// Reverse iterator
std::vector<int>::reverse_iterator rit = v.rbegin();

// Const reverse iterator
std::vector<int>::const_reverse_iterator crit = v.crbegin();

Когда итераторы инвалидируются?

Пример инвалидации:

std::vector<int> v = {1, 2, 3};
auto it = v.begin();

v.push_back(4);  // может вызвать реаллокацию

// ❌ it может быть инвалидирован!
std::cout << *it << std::endl;  // undefined behavior, если была реаллокация

Правильно:

std::vector<int> v = {1, 2, 3};
v.reserve(10);  // гарантируем, что не будет реаллокаций

auto it = v.begin();
v.push_back(4);  // реаллокации не будет

std::cout << *it << std::endl;  // ✅ OK

Часть 9: Альтернативы std::vector

Хотя std::vector является универсальным выбором для большинства случаев, существуют ситуации, когда альтернативные контейнеры могут быть более эффективными. Рассмотрим основные альтернативы.

C-style массивы (T array[N])

Что это: Классические массивы в стиле C.

int arr[100];  // стек
int* arr2 = new int[100];  // куча

Плюсы:

• ✅ Минимальный overhead

• ✅ Очень быстрая работа (особенно на стеке)

• ✅ Совместимость с C API

Минусы:

• ❌ Фиксированный размер (для стековых)

• ❌ Нет автоматического управления памятью (для кучных)

• ❌ Нет проверки границ

• ❌ Не поддерживают STL алгоритмы напрямую

• ❌ Легко ошибиться с размером

Когда использовать:

• Фиксированный размер известен на компиляции

• Критична производительность

• Маленький размер (< 100 элементов)

• Работа с C API

Производительность: По результатам бенчмарков, C-style массивы на стеке (~1.0x) быстрее std::vector без reserve() (2-3x), но практически идентичны std::vector с предварительным reserve() и выделением памяти (1.1x).

std::array (C++11)

Что это: Обертка над C-style массивом с STL интерфейсом.

#include <array>

std::array<int, 100> arr = {1, 2, 3};  // остальные инициализируются 0

Плюсы:

• ✅ Безопасность: at() с проверкой границ

• ✅ STL совместимость (итераторы, алгоритмы)

• ✅ Нет heap аллокаций (стек)

• ✅ Знает свой размер (size())

• ✅ Такая же производительность как C-style массив

Минусы:

• ❌ Фиксированный размер на компиляции

• ❌ Не может расти динамически

• ❌ Занимает место на стеке (ограничение ~1-2 МБ)

Когда использовать:

• Размер известен на компиляции

• Размер небольшой (< 10,000 элементов)

• Не нужно динамическое изменение размера

• Хотите STL совместимость

std::array<int, 5> arr = {1, 2, 3, 4, 5};

// ✅ STL алгоритмы работают
std::sort(arr.begin(), arr.end());

// ✅ Безопасный доступ
try {
    int x = arr.at(10);  // бросит std::out_of_range
} catch (...) {}

// ✅ Знает размер
std::cout << arr.size() << std::endl;  // 5

Сравнение с vector:

std::valarray

Что это: Контейнер для математических операций над массивами.

#include <valarray>

std::valarray<double> v1 = {1.0, 2.0, 3.0};
std::valarray<double> v2 = {4.0, 5.0, 6.0};

std::valarray<double> result = v1 + v2;  // поэлементное сложение
// result = {5.0, 7.0, 9.0}

Плюсы:

• ✅ Оптимизирован для математических операций

• ✅ Поэлементные операции (+, -, *, /)

• ✅ Математические функции (sin, cos, exp, log)

• ✅ Срезы (slices) для работы с подмассивами

Минусы:

• ❌ Не стандартизирован для общего использования

• ❌ Хуже документирован

• ❌ Менее популярен

• ❌ Не все компиляторы оптимизируют хорошо

Когда использовать:

• Численные вычисления

• Линейная алгебра

• Поэлементные математические операции

std::valarray<double> v = {1.0, 2.0, 3.0, 4.0};

// Поэлементные операции
v *= 2.0;  // {2.0, 4.0, 6.0, 8.0}
v += 1.0;  // {3.0, 5.0, 7.0, 9.0}

// Математические функции
std::valarray<double> result = std::sin(v);

// Срезы
std::valarray<double> slice = v[std::slice(0, 2, 2)];  // каждый 2-й элемент

Важно: std::valarray не рекомендуется для нового кода. Используйте специализированные библиотеки (Eigen, Armadillo).

Boost.Container alternatives

Boost предоставляет несколько альтернатив std::vector для специфических случаев.

boost::container::vector

Что это: Улучшенная версия std::vector.

#include <boost/container/vector.hpp>

boost::container::vector<int> v = {1, 2, 3};

Отличия от std::vector:

• ✅ Нет специализации для bool (ведет себя как обычный вектор)

• ✅ Более гибкая работа с аллокаторами

• ✅ Поддержка рекурсивных контейнеров

• ✅ Одинаковая реализация на всех платформах

• ✅ Настраиваемая стратегия роста

// Настройка стратегии роста на 50% вместо 100%
typedef boost::container::vector_options< 
    boost::container::growth_factor<boost::container::growth_factor_50>
>::type growth_50_option_t;

boost::container::vector<int, boost::container::new_allocator<int>, growth_50_option_t> v;

Когда использовать:

• Проблемы с std::vector

• Нужна кастомизация стратегии роста

• Работа с нестандартными аллокаторами

boost::container::small_vector

Что это: Вектор с оптимизацией для малого количества элементов (Small Buffer Optimization).

#include <boost/container/small_vector.hpp>

// Вмещает до 10 элементов без heap аллокации
boost::container::small_vector<int, 10> v;

v.push_back(1);  // на стеке
v.push_back(2);  // на стеке
// ... до 10 элементов на стеке

v.push_back(11);  // переход на heap

Плюсы:

• ✅ Первые N элементов хранятся на стеке (быстро)

• ✅ Автоматически переходит на кучу при превышении N

• ✅ Совместим с std::vector API

• ✅ Избегает аллокаций для маленьких размеров

Минусы:

• ❌ Больший размер объекта (на стеке)

• ❌ Копирование дороже (если < N элементов)

Когда использовать:

• Обычно мало элементов (< 10-20)

• Хотите избежать heap аллокаций

• Критична производительность аллокации

// Типичный use case: путь из нескольких компонентов
boost::container::small_vector<std::string, 4> path_components;
path_components.push_back("home");
path_components.push_back("user");
path_components.push_back("documents");
// Все на стеке, нет аллокаций!

boost::container::static_vector

Что это: Вектор с фиксированной максимальной capacity, хранящийся на стеке.

#include <boost/container/static_vector.hpp>

boost::container::static_vector<int, 100> v;

v.push_back(1);  // OK
v.push_back(2);  // OK
// ... максимум 100 элементов

// v.push_back(101);  // ❌ Exception или UB, если capacity превышена

Плюсы:

• ✅ Нет heap аллокаций вообще

• ✅ Предсказуемая производительность

• ✅ Можно менять размер (в отличие от std::array)

• ✅ Совместим с std::vector API (почти)

Минусы:

• ❌ Максимальный размер фиксирован на компиляции

• ❌ Занимает место на стеке

• ❌ Нельзя вырасти за пределы capacity

Когда использовать:

• Embedded системы

• Real-time системы (предсказуемость)

• Известен максимальный размер

• Heap аллокации недопустимы

// Embedded: буфер для UART
boost::container::static_vector<uint8_t, 256> uart_buffer;

void receive_byte(uint8_t byte) {
    if (uart_buffer.size() < uart_buffer.capacity()) {
        uart_buffer.push_back(byte);
    }
}

boost::container::stable_vector

Что это: Вектор, где итераторы и ссылки не инвалидируются при вставке/удалении.

#include <boost/container/stable_vector.hpp>

boost::container::stable_vector<int> v = {1, 2, 3};

int& ref = v[1];  // ссылка на элемент
auto it = v.begin() + 1;

v.push_back(4);  // реаллокация!
v.insert(v.begin(), 0);

// ✅ ref и it все еще валидны!
std::cout << ref << std::endl;  // 2
std::cout << *it << std::endl;  // 2

Как это работает: Каждый элемент хранится в отдельном узле (как в list), но есть массив указателей для быстрого доступа.

Плюсы:

• ✅ Стабильность итераторов и ссылок

• ✅ Random access O(1) (как у vector)

• ✅ Не инвалидируются итераторы при вставке

Минусы:

• ❌ Больший overhead памяти (~2 указателя на элемент)

• ❌ Медленнее обход (не cache-friendly)

• ❌ Нет contiguous storage

Когда использовать:

• Нужна стабильность итераторов

• Много вставок/удалений в середине

• Долгоживущие ссылки на элементы

boost::container::devector

Что это: Гибрид vector и deque — быстрая вставка с обоих концов.

#include <boost/container/devector.hpp>

boost::container::devector<int> v = {3, 4, 5};

v.push_front(2);  // O(1) amortized - быстро!
v.push_front(1);  // O(1) amortized
v.push_back(6);   // O(1) amortized
v.push_back(7);   // O(1) amortized

// v = {1, 2, 3, 4, 5, 6, 7}

Плюсы:

• ✅ Быстрая вставка с обоих концов O(1)

• ✅ Contiguous storage (как vector)

• ✅ Random access O(1)

Минусы:

• ❌ Больший overhead (4 указателя вместо 3)

• ❌ capacity() имеет другую семантику

• ❌ size() может быть > capacity()

Когда использовать:

• Нужна вставка с обоих концов

• Важна contiguous storage (в отличие от deque)

• FIFO/LIFO паттерны

// Use case: скользящее окно
boost::container::devector<int> window;

void add_value(int value) {
    window.push_back(value);
    if (window.size() > 100) {
        window.pop_front();  // O(1)!
    }
}

Сравнение производительности

* амортизированная сложность

⚡ — cache-friendly (contiguous memory)
? — не cache-friendly

Рекомендации по выбору

Используйте std::vector когда:

• ✅ Это ваш выбор по умолчанию (90% случаев)

• ✅ Нужна динамическая размерность

• ✅ Много элементов

• ✅ Вставка только в конец

Используйте std::array когда:

• ✅ Размер известен на компиляции

• ✅ Размер небольшой (< 10,000)

• ✅ Хотите избежать heap аллокаций

Используйте C array когда:

• ✅ Работа с C API

• ✅ Критична производительность

• ✅ Очень маленький размер

Используйте boost::small_vector когда:

• ✅ Обычно мало элементов (< 20)

• ✅ Хотите избежать аллокаций

• ✅ Может вырасти за пределы N

Используйте boost::static_vector когда:

• ✅ Embedded/real-time

• ✅ Heap недоступен

• ✅ Максимальный размер известен

Используйте boost::stable_vector когда:

• ✅ Критична стабильность итераторов

• ✅ Долгоживущие ссылки

• ✅ Много вставок в середину

Используйте boost::devector когда:

• ✅ Нужна вставка с обоих концов

• ✅ Важна contiguous storage

• ✅ Скользящее окно, FIFO/LIFO

НЕ используйте std::valarray:

• ❌ Используйте Eigen, Armadillo для численных вычислений

Часть 10: Эволюция std::vector по стандартам

C++98/03: Основа

• Базовая функциональность

• push_back(), insert(), erase()

• Проблемы с производительностью при вставке сложных объектов

C++11: Революция

1. Move semantics

std::vector<std::string> v1 = {"hello", "world"};
std::vector<std::string> v2 = std::move(v1);  // перемещение, не копирование

2. emplace_back() и emplace()

v.emplace_back(arg1, arg2);  // конструирование in-place

3. Initializer lists

std::vector<int> v = {1, 2, 3, 4, 5};

4. noexcept

void swap(vector& other) noexcept;

5. shrink_to_fit()

v.shrink_to_fit();  // до этого использовали swap-трюк

C++17: Улучшения

1. Возвращаемое значение из emplace_back()

auto& ref = v.emplace_back(42);  // теперь возвращает ссылку

2. Вывод типов при конструировании (CTAD)

std::vector v = {1, 2, 3};  // std::vector<int>

C++20: Дополнительные улучшения

1. erase() и erase_if()

std::erase(v, 42);  // удалить все элементы == 42
std::erase_if(v, [](int x) { return x % 2 == 0; });  // удалить четные

2. Ranges

auto result = v | std::views::filter([](int x) { return x > 0; })
                | std::views::transform([](int x) { return x * 2; });

C++23: Дальнейшие улучшения

1. append_range()

v.append_range(some_range);  // вставка диапазона в конец

2. insert_range()

v.insert_range(v.begin(), some_range);

Часть 11: Трюки и оптимизации

1. Избегайте ненужных копирований

// ❌ Плохо: копирование при каждой вставке
std::vector<std::string> v;
for (const auto& s : data) {
    v.push_back(s);  // копирование
}

// ✅ Хорошо: перемещение
std::vector<std::string> v;
for (auto&& s : data) {
    v.push_back(std::move(s));  // перемещение
}

// ✅ Еще лучше: emplace_back (если подходит)
std::vector<std::string> v;
for (const auto& s : data) {
    v.emplace_back(s);
}

2. reserve() для известного размера

// ❌ Плохо: множественные реаллокации
std::vector<int> v;
for (int i = 0; i < 10000; ++i) {
    v.push_back(i);
}

// ✅ Хорошо: одна аллокация
std::vector<int> v;
v.reserve(10000);
for (int i = 0; i < 10000; ++i) {
    v.push_back(i);
}

3. Удаление элементов по условию: erase-remove idiom

std::vector<int> v = {1, 2, 3, 4, 5, 6};

// ❌ Плохо: O(n²)
for (auto it = v.begin(); it != v.end(); ) {
    if (*it % 2 == 0) {
        it = v.erase(it);
    } else {
        ++it;
    }
}

// ✅ Хорошо: erase-remove idiom, O(n)
v.erase(
    std::remove_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; }),
    v.end()
);

// ✅ Еще лучше (C++20):
std::erase_if(v, [](int x) { return x % 2 == 0; });

4. Избегайте bool как типа элемента

// ❌ Плохо: std::vector<bool> — не настоящий вектор
std::vector<bool> vb;

// ✅ Хорошо: используйте char или int
std::vector<char> vc;

// ✅ Или std::deque<bool>
std::deque<bool> db;

5. Используйте data() для взаимодействия с C API

std::vector<int> v = {1, 2, 3, 4, 5};

// ✅ Передача в C функцию
some_c_function(v.data(), v.size());

// ✅ Эквивалентно:
some_c_function(&v[0], v.size());

// ⚠️ Но data() безопаснее для пустого вектора

6. Предпочитайте range-based for

std::vector<int> v = {1, 2, 3, 4, 5};

// ❌ Старый стиль
for (size_t i = 0; i < v.size(); ++i) {
    std::cout << v[i] << std::endl;
}

// ✅ Современный стиль
for (const auto& elem : v) {
    std::cout << elem << std::endl;
}

// ✅ С изменением
for (auto& elem : v) {
    elem *= 2;
}

7. Освобождение памяти

std::vector<int> v(1000000);
v.clear();  // size = 0, но capacity = 1000000!

// ✅ C++11+: shrink_to_fit
v.shrink_to_fit();

// ✅ Legacy: swap trick
std::vector<int>().swap(v);

// ✅ Или
std::vector<int>(v).swap(v);

8. Предпочитайте emplace_back для сложных типов

struct BigObject {
    BigObject(int a, double b, std::string c) { /* ... */ }
};

std::vector<BigObject> v;
v.reserve(100);

// ❌ Плохо: создание временного + move
v.push_back(BigObject(1, 2.0, "hello"));

// ✅ Хорошо: конструирование in-place
v.emplace_back(1, 2.0, "hello");

9. Используйте resize() вместо множественных push_back()

// ❌ Плохо
std::vector<int> v;
for (int i = 0; i < 1000; ++i) {
    v.push_back(0);
}

// ✅ Хорошо
std::vector<int> v(1000);  // или v.resize(1000);

10. Будьте осторожны с вложенными векторами

// ❌ Плохо: фрагментация памяти
std::vector<std::vector<int>> matrix;

// ✅ Лучше: плоский массив с индексацией
std::vector<int> flat_matrix(rows * cols);
auto& elem = flat_matrix[row * cols + col];

Заключение

std::vector — это мощный, но тонкий инструмент. Основные выводы:

Всегда помните:

1. size() ≠ capacity()

2. Реаллокация инвалидирует итераторы

3. reserve() для известного размера

4. noexcept на move конструкторе критичен

5. operator[] не проверяет границы, at() проверяет

6. std::vector — не настоящий std::vector

7. emplace_back() может быть быстрее push_back()

8. Используйте erase-remove idiom для удаления по условию

Избегайте:

• Множественных реаллокаций

• std::vector если нужны настоящие ссылки

• Вставки в середину вектора (когда можно избежать)

• Ненужных копирований

Используйте:

• reserve() когда знаете размер

• emplace_back() для сложных типов

• shrink_to_fit() для освобождения памяти

• Range-based for loops

• data() для C API

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

• std::array для фиксированного размера

• boost::small_vector для малого числа элементов

• boost::static_vector для embedded

• boost::stable_vector для стабильности итераторов

• boost::devector для вставки с обоих концов

Знание этих деталей поможет вам писать более эффективный и безопасный код. std::vector — это не просто динамический массив, это сложный контейнер с множеством нюансов, понимание которых отличает профессионала.

---

Полезные ссылки:

• cppreference: std::vector

• Boost.Container documentation

• C++ Core Guidelines

• Effective Modern C++ by Scott Meyers

Остались вопросы? Задавайте в комментариях!