11.9 – Емкость и стековое поведение std::vector
В уроке «10.23 – Знакомство с std::vector» мы представили std::vector и обсудили, как std::vector можно использовать в качестве динамического массива, который запоминает свою длину и может динамически изменять размер по мере необходимости.
Хотя это наиболее полезная и часто используемая часть std::vector, но он имеет кое-какие дополнительные атрибуты и возможности, которые делают его полезным и в некоторых других целях.
Длина и емкость
Рассмотрим следующий пример:
int *array{ new int[10] { 1, 2, 3, 4, 5 } }Мы бы сказали, что этот массив имеет длину 10, хотя мы используем только 5 из выделенных нами элементов.
Однако что, если мы хотим перебрать только инициализированные элементы, зарезервировав неиспользуемые для будущего расширения? В этом случае нам нужно будет отдельно отслеживать, сколько элементов было «использовано» из того, сколько элементов было выделено. В отличие от встроенного массива и std::array, которые запоминают только свою длину, std::vector содержит два отдельных атрибута: длину и емкость. В контексте std::vector, длина – это количество элементов, используемых в массиве, а емкость – это количество элементов, размещенных в памяти.
Взглянем на пример из предыдущего урока об std::vector:
#include <vector>
#include <iostream>
int main()
{
std::vector<int> array { 0, 1, 2 };
array.resize(5); // устанавливаем длину 5
std::cout << "The length is: " << array.size() << '\n';
for (auto element: array)
std::cout << element << ' ';
return 0;
}The length is: 5
0 1 2 0 0В приведенном выше примере мы использовали функцию resize(), чтобы установить длину вектора равной 5. Это сообщает переменной array, что мы собираемся использовать первые 5 элементов массива, поэтому следует учитывать те, которые используются активно. Однако возникает интересный вопрос: какова емкость переменной array?
Мы можем спросить std::vector, какова его емкость, с помощью функции capacity():
#include <vector>
#include <iostream>
int main()
{
std::vector<int> array { 0, 1, 2 };
array.resize(5); // устанавливаем длину 5
std::cout << "The length is: " << array.size() << '\n';
std::cout << "The capacity is: " << array.capacity() << '\n';
}На машине авторов это напечатало:
The length is: 5
The capacity is: 5В этом случае функция resize() заставила std::vector изменить как длину, так и емкость. Обратите внимание, что емкость гарантированно будет не меньше длины массива (но может быть больше), в противном случае доступ к элементам в конце массива будет за пределами выделенной памяти!
Еще сравнение длины с емкостью
Зачем различать длину и емкость? std::vector при необходимости перераспределяет свою память, но он предпочел бы этого не делать, потому что изменение размера массива требует больших вычислительных ресурсов. Рассмотрим следующее:
#include <vector>
#include <iostream>
int main()
{
std::vector<int> array{};
array = { 0, 1, 2, 3, 4 }; // ok, длина array = 5
std::cout << "length: " << array.size() << " capacity: " << array.capacity() << '\n';
array = { 9, 8, 7 }; // ok, длина array теперь 3!
std::cout << "length: " << array.size() << " capacity: " << array.capacity() << '\n';
return 0;
}Эта программа дает следующий вывод:
length: 5 capacity: 5
length: 3 capacity: 5Обратите внимание, что, хотя мы назначили нашему вектору меньший массив, он не перераспределил свою память (емкость по-прежнему равна 5). Он просто изменил свою длину, поэтому он знает, что в настоящее время действительны только первые 3 элемента.
Индексы массива и at() основаны на длине, а не на емкости
Диапазон для оператора индекса ([]) и функции at() основан на длине вектора, а не на его емкости. Рассмотрим массив в предыдущем примере, который имеет длину 3 и емкость 5. Что произойдет, если мы попытаемся получить доступ к элементу массива с индексом 4? Ответ заключается в том, что это не удается, поскольку 4 больше длины массива.
Обратите внимание, что вектор не изменит свой размер в зависимости от вызова оператора индекса или функции at()!
Стековое поведение с std::vector
Если оператор индекса и функция at() основаны на длине массива, а емкость всегда, по крайней мере, равна длине массива, зачем вообще беспокоиться о емкости? Хотя std::vector можно использовать как динамический массив, его также можно использовать как стек. Для этого мы можем использовать 3 функции, соответствующие нашим ключевым операциям со стеком:
push_back()помещает элемент в стек;back()возвращает значение верхнего элемента в стеке;pop_back()извлекает элемент из стека.
#include <iostream>
#include <vector>
void printStack(const std::vector<int> &stack)
{
for (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(5); // push_back() помещает элемент в стек
printStack(stack);
stack.push_back(3);
printStack(stack);
stack.push_back(2);
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)
5 (cap 1 length 1)
5 3 (cap 2 length 2)
5 3 2 (cap 3 length 3)
top: 2
5 3 (cap 3 length 2)
5 (cap 3 length 1)
(cap 3 length 0)В отличие от индексов массива или at(), стековые функции при необходимости изменяют размер std::vector. В приведенном выше примере размер вектора изменяется 3 раза (с 0 на 1, с 1 на 2 и с 2 на 3).
Поскольку изменение размера вектора – дорогостоящая операция, с помощью функции reserve() мы можем указать вектору заранее выделить определенную величину емкости:
#include <vector>
#include <iostream>
void printStack(const std::vector<int> &stack)
{
for (auto element : stack)
std::cout << element << ' ';
std::cout << "(cap " << stack.capacity() << " length " << stack.size() << ")\n";
}
int main()
{
std::vector<int> stack{};
stack.reserve(5); // Устанавливаем емкость (минимум) 5
printStack(stack);
stack.push_back(5);
printStack(stack);
stack.push_back(3);
printStack(stack);
stack.push_back(2);
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 5 length 0)
5 (cap 5 length 1)
5 3 (cap 5 length 2)
5 3 2 (cap 5 length 3)
top: 2
5 3 (cap 5 length 2)
5 (cap 5 length 1)
(cap 5 length 0)Мы видим, что емкость была предварительно установлена на 5 и не изменилась за время работы программы.
Векторы могут выделять дополнительную емкость
При изменении размера вектор может выделять больше емкости, чем необходимо. Это сделано для того, чтобы обеспечить некоторый «запас» для дополнительных элементов и свести к минимуму количество необходимых операций изменения размера. Давайте посмотрим на это:
#include <vector>
#include <iostream>
int main()
{
std::vector<int> v{ 0, 1, 2, 3, 4 };
std::cout << "size: " << v.size() << " cap: " << v.capacity() << '\n';
v.push_back(5); // добавляем еще один элемент
std::cout << "size: " << v.size() << " cap: " << v.capacity() << '\n';
return 0;
}На машине автора этот код печатает:
size: 5 cap: 5
size: 6 cap: 7Когда мы использовали push_back() для добавления нового элемента, нашему вектору требовалось место только для 6 элементов, но выделилось место для 7. Это было сделано для того, чтобы, если бы мы использовали push_back() с еще одним элементом, вектору не нужно было бы немедленно изменять размер.
Если, когда и сколько дополнительных ресурсов будет выделено, остается на усмотрение разработчика компилятора.