Мы уже знаем, что такое std::vector в языке С++ и как его можно использовать в качестве динамического массива, который запоминает свою длину и длина которого может быть динамически изменена по мере необходимости. Хотя использование std::vector в качестве динамического массива — это самая полезная и наиболее часто применяемая его особенность, но он также имеет и некоторые другие способности, которые также могут быть полезными.
Длина vs. Ёмкость
Рассмотрим следующий пример:
1 |
int *array = new int[12] { 1, 2, 3, 4, 5, 6, 7 }; |
Мы можем сказать, что длина массива равна 12, но используется только 7 элементов (которые мы, собственно, выделили).
А что, если мы хотим выполнять итерации только с элементами, которые мы инициализировали, оставляя в резерве неиспользованные элементы для будущего применения? В таком случае нам потребуется отдельно отслеживать, сколько элементов было «использовано» из общего количества выделенных элементов. В отличие от фиксированного массива или std::array, которые запоминают только свою длину, std::vector имеет два отдельных свойства:
Длина в std::vector — это количество фактически используемых элементов.
Ёмкость (или «вместимость») в std::vector — это количество выделенных элементов.
Рассмотрим пример из урока о std::vector:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
#include <iostream> #include <vector> int main() { std::vector<int> array { 0, 1, 2, 3 }; array.resize(6); // устанавливаем длину, равную 6 std::cout << "The length is: " << array.size() << '\n'; for (auto const &element: array) std::cout << element << ' '; return 0; } |
Результат выполнения программы:
The length is: 6
0 1 2 3 0 0
В примере, приведенном выше, мы использовали функцию resize() для изменения длины вектора до 6 элементов. Это сообщает массиву, что мы намереваемся использовать только первые 6 элементов, поэтому он должен их учитывать, как активные (те, которые фактически используются). Следует вопрос: «Какова ёмкость этого массива?».
Мы можем спросить std::vector о его ёмкости, используя функцию capacity():
1 2 3 4 5 6 7 8 9 10 11 |
#include <iostream> #include <vector> int main() { std::vector<int> array { 0, 1, 2, 3}; array.resize(6); // устанавливаем длину, равную 6 std::cout << "The length is: " << array.size() << '\n'; std::cout << "The capacity is: " << array.capacity() << '\n'; } |
Результат на моем компьютере:
The length is: 6
The capacity is: 6
В этом случае функция resize() заставила std::vector изменить как свою длину, так и ёмкость. Обратите внимание, ёмкость всегда должна быть не меньше длины массива (но может быть и больше), иначе доступ к элементам в конце массива будет за пределами выделенной памяти!
Зачем вообще нужны длина и ёмкость? std::vector может перераспределить свою память, если это необходимо, но он бы предпочел этого не делать, так как изменение размера массива является несколько затратной операцией. Например:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
#include <iostream> #include <vector> int main() { std::vector<int> array; array = { 0, 1, 2, 3, 4, 5 }; // ок, длина array равна 6 std::cout << "length: " << array.size() << " capacity: " << array.capacity() << '\n'; array = { 8, 7, 6, 5 }; // ок, длина array теперь равна 4! std::cout << "length: " << array.size() << " capacity: " << array.capacity() << '\n'; return 0; } |
Результат выполнения программы:
length: 6 capacity: 6
length: 4 capacity: 6
Обратите внимание, хотя мы присвоили меньшее количество элементов массиву во второй раз — он не перераспределил свою память, ёмкость по-прежнему составляет 6 элементов. Он просто изменил свою длину. Таким образом, он понимает, что в настоящий момент активны только первые 4 элемента.
Оператор индекса и функция at()
Диапазон для оператора индекса []
и функции at() основан на длине вектора, а не на его ёмкости. Рассмотрим массив из вышеприведенного примера, длина которого равна 4, а ёмкость равна 6. Что произойдет, если мы попытаемся получить доступ к элементу массива под индексом 5? Ничего, поскольку индекс 5 находится за пределами длины массива.
Обратите внимание, вектор не будет изменять свой размер из-за вызова оператора индекса или функции at()!
std::vector в качестве стека
Если оператор индекса и функция at() основаны на длине массива, а его ёмкость всегда не меньше, чем его длина, то зачем беспокоиться о ёмкости вообще? Хотя std::vector может использоваться как динамический массив, его также можно использовать в качестве стека. Мы можем использовать 3 ключевые функции вектора, которые соответствуют 3-м ключевым операциям стека:
функция push_back() — добавляет элемент в стек.
функция back() — возвращает значение верхнего элемента стека.
функция pop_back() — вытягивает элемент из стека.
Например:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
#include <iostream> #include <vector> void printStack(const std::vector<int> &stack) { for (const auto &element : stack) std::cout << element << ' '; std::cout << "(cap " << stack.capacity() << " length " << stack.size() << ")\n"; } int main() { std::vector<int> stack; printStack(stack); stack.push_back(7); // функция push_back() добавляет элемент в стек printStack(stack); stack.push_back(4); printStack(stack); stack.push_back(1); printStack(stack); std::cout << "top: " << stack.back() << '\n'; // функция back() возвращает последний элемент stack.pop_back(); // функция pop_back() вытягивает элемент из стека printStack(stack); stack.pop_back(); printStack(stack); stack.pop_back(); printStack(stack); return 0; } |
Результат выполнения программы:
(cap 0 length 0)
7 (cap 1 length 1)
7 4 (cap 2 length 2)
7 4 1 (cap 3 length 3)
top: 1
7 4 (cap 3 length 2)
7 (cap 3 length 1)
(cap 3 length 0)
В отличие от оператора индекса и функции at(), функции вектора-стека изменяют размер std::vector (выполняется функция resize()), если это необходимо. В примере, приведенном выше, вектор изменяет свой размер 3 раза (3 раза выполняется функция resize(): от ёмкости 0 до ёмкости 1, от 1 до 2 и от 2 до 3).
Поскольку изменение размера вектора является затратной операцией, то мы можем сообщить вектору выделить заранее заданный объем ёмкости, используя функцию reserve():
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
#include <iostream> #include <vector> void printStack(const std::vector<int> &stack) { for (const auto &element : stack) std::cout << element << ' '; std::cout << "(cap " << stack.capacity() << " length " << stack.size() << ")\n"; } int main() { std::vector<int> stack; stack.reserve(7); // устанавливаем ёмкость (как минимум), равную 7 printStack(stack); stack.push_back(7); printStack(stack); stack.push_back(4); printStack(stack); stack.push_back(1); printStack(stack); std::cout << "top: " << stack.back() << '\n'; stack.pop_back(); printStack(stack); stack.pop_back(); printStack(stack); stack.pop_back(); printStack(stack); return 0; } |
Результат выполнения программы:
(cap 7 length 0)
7 (cap 7 length 1)
7 4 (cap 7 length 2)
7 4 1 (cap 7 length 3)
top: 1
7 4 (cap 7 length 2)
7 (cap 7 length 1)
(cap 7 length 0)
Ёмкость вектора была заранее предустановлена (значением 7) и не изменялась в течение всего времени выполнения программы.
Дополнительная ёмкость
При изменении вектором своего размера, он может выделить больше ёмкости, чем требуется. Это делается для обеспечения некоего резерва для дополнительных элементов, чтобы свести к минимуму количество операций изменения размера. Например:
1 2 3 4 5 6 7 8 9 10 11 12 13 |
#include <iostream> #include <vector> int main() { std::vector<int> vect = { 0, 1, 2, 3, 4, 5 }; std::cout << "size: " << vect.size() << " cap: " << vect.capacity() << '\n'; vect.push_back(6); // добавляем другой элемент std::cout << "size: " << vect.size() << " cap: " << vect.capacity() << '\n'; return 0; } |
Результат на моем компьютере:
size: 6 cap: 6
size: 7 cap: 9
Когда мы использовали функцию push_back() для добавления нового элемента, то нашему вектору потребовалось выделить комнату только для 7 элементов, но он выделил комнату для 9 элементов. Это было сделано для того, чтобы при использовании функции push_back() в случае добавления еще одного элемента, вектору не пришлось опять выполнять операцию изменения своего размера (экономя, таким образом, ресурсы).
Как, когда и сколько выделяется дополнительной ёмкости — зависит от каждого компилятора отдельно.
Дополню: в некоторых случаях, если произошло удаление большого количества элементов из вектора (size() уменьшился, а capacity() осталась большой), если дальнейшее добавление элементов в вектор не планируется, то логично освободить задействованную память. Для этого есть специальный метод shrink_to_fit().
Подскажите пожалуйста, почему в одном примере push_back() увеличил ёмкость только на 1, а в другом примере (последнем) уже на 3? Они были скопилированы на разных системах?
Насколько я понял, в последнем примере был именно динамический вектор.
Динамический вектор это что-то новенькое… Нет, этот код скомпилирован на одной системе(скорее всего). Компилятор сам решает сколько емкости добавлять вектору. Видимо, чем больше элементов в векторе, тем больше выделяется дополнительной ёмкости при добавлении элемента.
Это было сделано для того, чтобы если пользователь добавит ещё один элемент, то вектор не будет опять увеличивать ёмкость (т.к. это затратная операция) с целью экономии ресурсов.
"Это было сделано для того, что, если бы мы использовали push_back() для добавления ещё одного элемента, вектору не пришлось бы опять выполнять операцию изменения своего размера (экономя, таким образом, ресурсы)."
То есть push_back() увеличивает емкость автоматически?
Как я поняла:
1) это зависит от компилятора
2) если текущей ёмкости не достаточно (при изменении длины) — да, она увеличивается автоматически. Другое дело, что в примере выше она увеличилась не до 7, а сразу до 9, немного впрок, т.к. изменение ёмкости — затратная операция.
Предусмотрительные были ребята.
Думаю, что более новые компиляторы и выделяют больше.
gcc выделил 12
gcc 9.3.0