Урок №106. Ёмкость вектора

  Юрий  | 

  Обновл. 8 Июн 2019  | 

 11176

 ǀ   3 

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

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

Длина vs. Ёмкость

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

Мы можем сказать, что длина массива — 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 (89 оценок, среднее: 4,90 из 5)
Загрузка...

Комментариев: 3

  1. Аватар somebox:

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

    То есть push_back() увеличивает емкость автоматически?

    1. Аватар Анастасия:

      Как я поняла:
      1) это зависит от компилятора
      2) если текущей ёмкости не достаточно (при изменении длины) — да, она увеличивается автоматически. Другое дело, что в примере выше она увеличилась не до 7, а сразу до 9, немного впрок, т.к. изменение ёмкости — затратная операция.

      1. Аватар Алексей:

        Предусмотрительные были ребята.
        Думаю, что более новые компиляторы и выделяют больше.

Добавить комментарий для somebox Отменить ответ

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