Vector
vector
- это динамический массив. Его размер может меняться во время исполнения программы, вы можете добавлять элементы в конец и так далее. Чтобы объявить пустой vector
, способный содержать в себе целые числа типа T
, необходимо воспользоваться следующей конструкцией:
vector<T> vector_name;
Здесь T
— это тип элементов, которые будут содержаться в vector, а vector_name
— имя самого vector
. Как и другие контейнеры C++, vector
не может содержать элементы разных типов!
Чтобы добавить элемент в конец вектора, необходимо воспользоваться функцией push_back
. Эта функция работает в среднем за $O(1)$.
Существуют два способа обращения к vector
:
vector<int> a;
cout << a[5];
cout << a.at(5);
Кроме этого вам также могут потребоваться следующие методы:
vector<int> a;
a.push_back(x); // вставляет x в конец a
a.size(); // возращает размер вектора а
a.resize(x) // сделать размер вектора = x, либо удаляются последние элементы, либо добавляются нули
a.resize(x, y) // сделать размер вектора = x, добавляются y
// Также можно изначально задать размер и элементы массива
vector<int> a(10); // Размер вектора - 10 элементов, каждый из которых равен 0
vector<int> b(5, 123); // Размер - 5 элементов, каждый из которых равен 123
vector<int> c = {1, 2, 3}; // явная инициализация
Как работает vector?
Как уже было сказано, добавление в конец вектора работает в среднем за $O(1)$. Это означает, что, если вы сделаете $n$ операций push_back
, они будут в сумме работать за $O(n)$. Но при этом некоторые из них могли работать и за линейное время!
У vector
есть 2 важные величины: size
и capacity
— размер и вместимость. Размер — это то, сколько элементов сейчас находится в векторе. Вместимость — то, под сколько элементов памяти выделено. Когда size
< capacity
, push_back
просто добавляет новый элемент в первую свободную ячейку уже выделенной памяти, поэтому работает за $O(1)$. Когда size
= capacity
, так сделать не удастся. Поэтому, происходит следующее: capacity
увеличивается примерно в 2 раза.
Выделяется область памяти, вмещающая capacity
элементов.
Элементы из старой области памяти копируются в новую.
Старая область памяти освобождается.
Поймём, почему амортизированное время работы push_back
действительно равно $O(1)$. Пусть сейчас capacity
= $n$. Тогда мы выделяли n+n2+n4+⋯<2n
памяти. На копирование также ушло не более 2n операций. Следовательно, так как операций push_back было хотя бы n2 , каждая операция в среднем работала за O(1) .
Получить capacity у vector можно с помощью одноимённой функции. Рассмотрим пример того, как изменяется capacity.
$$TBC$$