Урок №112. Ємність вектора

  Юрій  | 

  Оновл. 21 Січ 2021  | 

 118

Ми вже знаємо, що таке 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 може використовуватися як динамічний масив, його також можна використовувати в якості стеку. Ми можемо використовувати три ключові функції вектора, які відповідають трьом ключовим операціям стеку:

   функція 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 Зірок (2 оцінок, середня: 5,00 з 5)
Loading...

Залишити відповідь

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