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

  Юрий  | 

  |

  Обновл. 24 Янв 2022  | 

 57198

 ǀ   9 

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

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

  1. Finchi:

    Дополню: в некоторых случаях, если произошло удаление большого количества элементов из вектора (size() уменьшился, а capacity() осталась большой), если дальнейшее добавление элементов в вектор не планируется, то логично освободить задействованную память. Для этого есть специальный метод shrink_to_fit().

  2. Константин:

    Подскажите пожалуйста, почему в одном примере push_back() увеличил ёмкость только на 1, а в другом примере (последнем) уже на 3? Они были скопилированы на разных системах?

    1. Игроь:

      Насколько я понял, в последнем примере был именно динамический вектор.

      1. Сергей:

        Динамический вектор это что-то новенькое… Нет, этот код скомпилирован на одной системе(скорее всего). Компилятор сам решает сколько емкости добавлять вектору. Видимо, чем больше элементов в векторе, тем больше выделяется дополнительной ёмкости при добавлении элемента.

    2. Эдуард:

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

  3. somebox:

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

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

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

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

      1. Алексей:

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

        1. Владимир:

          gcc выделил 12

          gcc 9.3.0

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

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