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, так сделать не удастся. Поэтому, происходит следующее:

1. capacity увеличивается примерно в 2 раза.
2. Выделяется область памяти, вмещающая capacity элементов.
3. Элементы из старой области памяти копируются в новую.
4. Старая область памяти освобождается.

Поймём, почему амортизированное время работы 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