Контейнер vector в C++

В C++,vectorЭто один из наиболее часто используемых контейнеров STL.

vectorПо сути, этодинамический массив, который может автоматически расширяться.По сравнению с традиционными массивами, vector не требует ручного управления памятью и может автоматически расширяться в соответствии с количеством элементов.

Поскольку vector имеет:

• Непрерывное хранение в памяти
• Быстрый произвольный доступ
• Полная экосистема STL
• Дружественный к кэшу

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

Основные особенности vector

• Динамический размер:vector может автоматически расширяться и сжиматься.
• Непрерывная память:Элементы хранятся в памяти непрерывно, поэтому эффективность доступа очень высока.
• Произвольный доступ:Поддерживается быстрый доступ к элементам по индексу с временной сложностью O(1).
• Автоматическое управление памятью:Нет необходимости вручную вызывать malloc/free.
• Поддерживает итераторы:Его можно легко использовать вместе с алгоритмами STL.

Почему vector быстр?

Элементы vector расположены в памяти непрерывно:

[1][2][3][4][5]

Такое расположение очень благоприятно для кэша процессора.

Когда процессор читает первый элемент, он обычно заранее предзагружает следующие данные в кэш, поэтому итерация по vector обычно очень быстрая.

Это также объясняет, почему во многих случаях:

vector 比 list 更快

Хотя list имеет теоретически более низкую сложность удаления.

Использование vector

Перед использованием vector нужно подключить заголовочный файл:

#include <vector>

Создание vector

Создать пустой vector:

std::vector<int>vec;

Указать начальный размер:

std::vector<int>vec(5);

Приведённый выше код создаёт 5 элементов со значением по умолчанию 0.

Укажите начальное значение:

std::vector<int>vec(5, 10);

Результат создания:

[10, 10, 10, 10, 10]

Использование списка инициализации:

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

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

Использованиеpush_back()Добавление элементов в конец:

vec.push_back(100);

Средняя временная сложность добавления элемента в конец vector равна:

O(1)

Доступ к элементам

Доступ с помощью индексов:

int x = vec[0];

Использованиеat()：

int y = vec.at(1);

Разница:

• []Проверка границ не выполняется, быстрее.
• at()Проверка границ выполняется, безопаснее.

Получение size

vec.size();

Возвращает текущее количество элементов.

Разница между size и capacity

Это одна из самых важных концепций vector.

std::vector<int>vec;

vec.push_back(1);
vec.push_back(2);

std::cout << vec.size() << std::endl;
std::cout << vec.capacity() << std::endl;

Вывод может быть:

2
4

• size：Текущее количество элементов.
• capacity：Текущая выделенная ёмкость памяти.

capacity обычно не меньше size.

Это потому, что vector запрашивает больше места заранее, чтобы уменьшить частые перераспределения.

Механизм расширения vector

Когда capacity у vector недостаточно, происходит перераспределение:

1. Выделить больше памяти
2. Скопировать старые элементы
3. Освобождение старой памяти

Этот процесс относительно затратен.

Например:

std::vector<int>vec;

for (int i = 0; i < 1000000; i++) {
    vec.push_back(i);
}

Может произойти несколько перераспределений памяти.

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

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

std::vector<int>vec;

vec.reserve(1000000);

Это позволяет сократить:

• Перераспределение памяти
• Копирование элементов
• Накладные расходы на производительность

Это очень важный приём оптимизации при разработке программного обеспечения.

Обход vector

Использование индексации

for (size_t i = 0; i < vec.size(); i++) {
    std::cout << vec[i] << " ";
}

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

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

Цикл for по диапазону

for (int element : vec) {
    std::cout << element << " ";
}

Удаление элемента

Удалить третий элемент:

vec.erase(vec.begin() + 2);

Примечание:

Когда vector удаляет элемент в середине, последующие элементы сдвигаются вперёд целиком.

Например:

1 2 3 4 5

删除 2 后：

1 3 4 5

Где:

3 4 5

Все нужно переместить.

Следовательно:

erase() 的时间复杂度为 O(n)

Сценарии, в которых vector не подходит

• Частая вставка в начало
• Частое удаление из середины
• Частое расширение с объектами слишком большого размера

Например:

vec.insert(vec.begin(), 100);

Это относительно медленная операция.

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

После перераспределения vector исходные адреса памяти могут стать недействительными.

Например:

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

auto it = vec.begin();

vec.push_back(4);

std::cout << *it;

здесьitМогут быть аннулированы.

Потому что push_back() может вызвать перераспределение памяти.

Это одна из самых распространённых ловушек vector.

Замечания о clear()

vec.clear();

clear() очищает только элементы:

• size становится 0
• Ёмкость может по-прежнему сохраняться.

То есть:

clear() 不一定释放内存

Если вы хотите освободить память:

std::vector<int>().swap(vec);

Или:

vec.shrink_to_fit();

push_back и emplace_back

Современный C++ рекомендует использовать:

emplace_back()

Например:

vec.push_back(Person("Tom", 20));

Могут создаваться временные объекты.

И:

vec.emplace_back("Tom", 20);

Он конструирует объект непосредственно на месте внутри vector.

Обычно более эффективно.

Различия между vector и array

Сложность типичных операций с vector

Пример: управление оценками студентов

Результат вывода следующий:

所有成绩: 85 90 78 92 88 
平均成绩: 86.6
删除后成绩: 85 90 92 88 

Итог

vector — одна из самых важных и часто используемых структур данных в современном C++.

Его ключевые преимущества:

• Динамическое изменение размера
• Непрерывная память
• Быстрый произвольный доступ
• Кэш-дружественный
• Полная экосистема STL

Но в то же время обратите внимание, что:

• Затраты производительности при расширении
• Низкая эффективность удаления из середины
• Проблема инвалидации итераторов

Для подавляющего большинства сценариев последовательного хранения:

vector 通常都是默认首选容器