Мы уже знаем, что такое 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() в случае добавления еще одного элемента, вектору не пришлось опять выполнять операцию изменения своего размера (экономя, таким образом, ресурсы).
Как, когда и сколько выделяется дополнительной ёмкости — зависит от каждого компилятора отдельно.
"Это было сделано для того, что, если бы мы использовали push_back() для добавления ещё одного элемента, вектору не пришлось бы опять выполнять операцию изменения своего размера (экономя, таким образом, ресурсы)."
То есть push_back() увеличивает емкость автоматически?
Как я поняла:
1) это зависит от компилятора
2) если текущей ёмкости не достаточно (при изменении длины) — да, она увеличивается автоматически. Другое дело, что в примере выше она увеличилась не до 7, а сразу до 9, немного впрок, т.к. изменение ёмкости — затратная операция.
Предусмотрительные были ребята.
Думаю, что более новые компиляторы и выделяют больше.
gcc выделил 12
gcc 9.3.0