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