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 + \frac{n}{2} + \frac{n}{4} + ⋯ < 2n$ памяти. На копирование также ушло не более $2n$ операций. Следовательно, так как операций push_back
было хотя бы $\frac{n}{2}$, каждая операция в среднем работала за $O(1)$.
Получить capacity
у vector
можно с помощью одноимённой функции. Рассмотрим пример того, как изменяется capacity
.
vector<int> a;
for (int i = 0; i < 10; i++) {
a.push_back(i);
cout << "Size: " << a.size() << ", capacity " << a.capacity() << "\n";
}
/* Будет выведено:
Size: 1, capacity 1
Size: 2, capacity 2
Size: 3, capacity 4
Size: 4, capacity 4
Size: 5, capacity 8
Size: 6, capacity 8
Size: 7, capacity 8
Size: 8, capacity 8
Size: 9, capacity 16
Size: 10, capacity 16
*/
Автор конспекта: Егор Гутров
По всем вопросам пишите в telegram @Egor_Gutrov