Урок 106. Емкость вектора. std::vector в качестве стека

   | 

   | 

 Обновлено 11 Янв 2018  | 

 3010

В уроке о введении в std::vector, мы узнали что такое std::vector и как его можно использовать в качестве динамического массива, который будет запоминать свою длину и длина которого может быть динамически изменена по мере необходимости.

Хотя использование std::vector в качестве динамического массива – это самая полезная и применимая его особенность, но он также имеет и некоторые другие возможности, которые могут быть полезными.

Длина против Емкости

Рассмотрим следующий пример:

Мы можем сказать, что длина массива – 12, но используется элементов только 7 (которые мы, собственно, выделили).

Однако, что, если мы хотим выполнять итерации только с элементами, которые мы инициализировали, оставляя в резерве неиспользованные элементы для будущего применения? В таком случае нам потребуется отдельно отслеживать, сколько элементов было «использовано» из того, сколько элементов было выделено всего. В отличие от стандартного массива или std::array, которые запоминают только свою длину, std::vector имеет два отдельных свойства: длину и емкость. Длина в std::vector — это то, сколько фактически используется элементов в массиве, тогда как емкость (или еще вместимость) в std::vector — это количество элементов, выделенных в памяти.

Рассмотрим пример из урока про std::vector:

Результат выполнения программы выше:

The length is: 6
0 1 2 3 0 0

В примере выше мы использовали функцию resize() для изменения длины вектора на 6. Это сообщает массиву, что мы намереваемся использовать только первые его 6 элементов, поэтому он должен их учитывать как активные (те, которые фактически используются). Однако возникает следующий интересный вопрос: «Какова емкость этого массива?».

Мы можем спросить в std::vector какая у него емкость, используя функцию capacity():

Результат на компьютере автора:

The length is: 6
The capacity is: 6



В этом случае функция resize() заставила std::vector изменить как длину, так и емкость. Обратите внимание, емкость всегда должна быть не меньше длины массива (но может быть и больше), иначе доступ к элементам в конце массива будет за пределами выделенной памяти!

Зачем нужны и длина, и емкость? std::vector может перераспределить свою память, если это необходимо, но он бы предпочел бы этого не делать, так как изменение размера массива является несколько затратной операцией. Например:

Результат:

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() — вытягивает элемент из стека.

Например:

Результат выполнения программы выше:

(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():

Результат:

(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) и не изменялась в течение всего срока выполнения программы.

Векторы могут выделять дополнительную емкость

При изменении вектором своего размера, он может выделить больше емкости, чем требуется. Это делается для обеспечения некого резерва для дополнительных элементов, чтобы свести к минимуму количество выполнения операций изменения размера. Например:

Результат на компьютере автора:

size: 6 cap: 6
size: 7 cap: 9

Когда мы использовали push_back() для добавления нового элемента, нашему вектору потребовалось выделить комнату только для 7 элементов, но он выделил комнату для 9. Это было сделано для того, что, если бы мы использовали push_back() для еще одного элемента — ему не пришлось бы опять выполнять операцию изменения своего размера (экономя таким образом ресурсы).

Как, когда и сколько выделяется дополнительной емкости – зависит от каждого компилятора отдельно.

Оценить статью:

Звёзд: 1Звёзд: 2Звёзд: 3Звёзд: 4Звёзд: 5 (23 оценок, среднее: 4,96 из 5)
Загрузка...
Подписаться на обновления:

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

ВОЛШЕБНАЯ ТАБЛЕТКА ПО С++