Что такое вектор?

Что такое вектор?

Краткий ответ

Вектор (std::vector) — это динамический массив из стандартной библиотеки C++. Это контейнер, который может автоматически растить свой размер при добавлении элементов, в отличие от обычного массива фиксированного размера.

Основные характеристики

1. Динамический размер

std::vector<int> v;  // Пустой вектор
v.push_back(10);     // Добавляем элемент
v.push_back(20);
v.push_back(30);
// v содержит: [10, 20, 30]

2. Связная память

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

std::vector<int> v = {1, 2, 3, 4, 5};
int x = v[2];       // = 3, O(1) доступ
int y = v.at(2);    // = 3, с проверкой границ

3. Автоматическое управление памятью

std::vector<int> v;
v.push_back(10);  // Выделяется память
v.push_back(20);
v.clear();        // Удаляются элементы
v.shrink_to_fit(); // Освобождается неиспользуемая память
// При уничтожении v всё автоматически освобождается

Как работает внутри: Capacity vs Size

Size — количество элементов в векторе Capacity — выделенное место в памяти

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

v.push_back(10);
std::cout << v.size();     // 1
std::cout << v.capacity(); // 1 (может быть больше)

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

v.push_back(30);
std::cout << v.size();     // 3
std::cout << v.capacity(); // 4 (вырос при добавлении!

Стратегия роста

Когда вектор переполняется (size == capacity), он выделяет новый блок памяти большего размера и копирует туда все элементы:

Добавляем 1-й элемент:  capacity = 1
Добавляем 2-й элемент:  capacity = 2 (перераспределение!)
Добавляем 3-й элемент:  capacity = 4 (перераспределение!)
Добавляем 5-й элемент:  capacity = 8 (перераспределение!)

Стандартная стратегия — умножение на 1.5 или 2 (зависит от реализации). Это гарантирует амортизированную сложность O(1) для push_back.

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

Добавление элементов:

std::vector<int> v = {1, 2, 3};
v.push_back(4);           // Добавить в конец: [1, 2, 3, 4]
v.insert(v.begin() + 1, 99);  // Вставить 99 на позицию 1: [1, 99, 2, 3, 4]
v.emplace_back(5);        // Создать элемент в конце (более эффективно)

Удаление элементов:

v.pop_back();             // Удалить последний
v.erase(v.begin() + 1);   // Удалить элемент на позиции 1
v.clear();                // Удалить все элементы

Доступ:

int x = v[0];             // Доступ без проверки (быстро)
int y = v.at(0);          // Доступ с проверкой (безопасно)
int first = v.front();    // Первый элемент
int last = v.back();      // Последний элемент

Информация:

size_t n = v.size();      // Количество элементов
bool empty = v.empty();   // Пустой ли?
size_t cap = v.capacity(); // Выделенное место
v.resize(10);             // Изменить размер (добавить или удалить)
v.reserve(100);           // Зарезервировать место без добавления элементов

Итерирование

Традиционный цикл:

for (int i = 0; i < v.size(); ++i) {
    std::cout << v[i];
}

Итератор:

for (auto it = v.begin(); it != v.end(); ++it) {
    std::cout << *it;
}

Range-based for (C++11):

for (int x : v) {
    std::cout << x;
}

// С ссылкой (чтобы изменять):
for (int& x : v) {
    x *= 2;  // Удвоить каждый элемент
}

Производительность

Сложность операций:

Сравнение с другими контейнерами

std::vector<int> v;    // Динамический массив, быстрый доступ
std::list<int> l;      // Двусвязный список, медленный доступ, быстрая вставка
std::deque<int> d;     // Двусторонняя очередь, быстро с обеих сторон
std::set<int> s;       // Отсортированное множество, автоматическая сортировка
std::map<string, int>; // Словарь, быстрый поиск по ключу

Практические примеры

1. Динамический массив вместо обычного:

// Плохо — размер заранее неизвестен
int arr[1000];  // Если нужно 500, память впустую

// Хорошо — вектор растёт по мере надобности
std::vector<int> v;
for (int i = 0; i < n; ++i) {
    v.push_back(i);
}

2. Копирование вектора:

std::vector<int> v1 = {1, 2, 3};
std::vector<int> v2 = v1;        // Копирование (медленно для больших)
std::vector<int> v3 = std::move(v1);  // Перемещение (быстро!)

3. Передача в функцию:

// Копирование (неэффективно для больших)
void process(std::vector<int> v) { ... }

// Ссылка (эффективно)
void process(const std::vector<int>& v) { ... }

// Изменение вектора
void modify(std::vector<int>& v) { ... }

4. Фильтрация элементов:

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

for (int n : numbers) {
    if (n % 2 == 0) {
        evens.push_back(n);
    }
}
// evens = {2, 4, 6}

5. Использование std::remove и erase:

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

// Удалить все 2
v.erase(std::remove(v.begin(), v.end(), 2), v.end());
// v = {1, 3, 4}

Когда использовать вектор

• Часто нужен доступ по индексу — вектор O(1)
• Много добавлений в конец — push_back быстро
• Размер заранее неизвестен — вектор растёт автоматически
• Нужна обычная динамическая коллекция — вектор по умолчанию

Когда не использовать вектор:

• Если часто вставляете/удаляете в середину → используйте list
• Если нужны быстрые операции с обеих сторон → используйте deque
• Если нужна отсортированность → используйте set или map

Заключение

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

• Автоматически растёт при добавлении элементов
• Хранит данные линейно в памяти для быстрого доступа
• Управляет памятью автоматически (RAII)
• Имеет удобный API с большим количеством полезных методов
• Является основой большинства C++ программ

Это один из самых важных контейнеров в STL!