Урок №205. Контейнери STL

  Оновл. 8 Жов 2021  | 

 4450

Безумовно, найбільш використовуваним функціоналом бібліотеки STL є контейнерні класи (або як їх ще називають — «контейнери»). Бібліотека STL містить багато різних контейнерних класів, які можна використовувати в різних ситуаціях. Якщо говорити в загальному, то контейнери STL діляться на три основні категорії:

   послідовні;

   асоціативні;

   адаптери.

Зараз зробимо їх короткий огляд.

Послідовні контейнери

Послідовні контейнери (або «контейнери послідовності») — це контейнерні класи, елементи яких знаходяться в послідовності. Їх визначальною характеристикою є те, що ви можете додати свій елемент в будь-яке місце контейнера. Найбільш поширеним прикладом послідовного контейнера є масив: при додаванні 4 елементів в масив, ці елементи перебуватимуть (в масиві) в точно такому ж порядку, в якому ви їх додали.

Починаючи з C++11, STL містить 6 контейнерів послідовності:

   std::vector;

   std::deque;

   std::array;

   std::list;

   std::forward_list;

   std::basic_string.

Клас vector (або просто «вектор») — це динамічний масив, здатний збільшуватися в міру необхідності для утримання всіх своїх елементів. Клас vector забезпечує довільний доступ до своїх елементів через оператор індексації [], а також підтримує додавання і видалення елементів.

У наступній програмі ми додаємо 5 цілих чисел в вектор і за допомогою перевантаженого оператора індексації [] отримуємо до них доступ для їх подальшого виводу:

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

10 9 8 7 6

Клас deque (або просто «дек») — це двостороння черга, яка реалізована у вигляді динамічного масиву, який може зростати з обох кінців. Наприклад:

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

7 8 9 10 0 1 2 3

List (або просто «список») — це двонаправлений список, кожен елемент якого містить 2 вказівники: один вказує на наступний елемент списку, а інший — на попередній елемент списку. List надає доступ тільки до початку і до кінця списку — довільний доступ заборонено. Якщо ви хочете знайти значення десь в середині, то ви повинні почати з одного кінця і перебирати кожен елемент списку до тих пір, поки не знайдете те, що шукаєте. Перевагою двонаправленого списку є те, що додавання елементів відбувається дуже швидко, якщо ви, звичайно, знаєте, куди хочете додавати. Зазвичай для перебору елементів двонаправленого списку використовуються ітератори.

Хоча про клас string (і wstring) зазвичай не говорять, як про послідовний контейнер, але він, по суті, є таким, оскільки його можна розглядати як вектор з елементами типу char (або wchar).

Асоціативні контейнери


Асоціативні контейнери — це контейнерні класи, які автоматично сортують всі свої елементи (в тому числі і ті, які додаєте ви). За замовчуванням асоціативні контейнери виконують сортування елементів, використовуючи оператор порівняння <.

   set — це контейнер, в якому зберігаються тільки унікальні елементи, і повторення заборонені. Елементи упорядковано відповідно до їх значень.

   multiset — це set, але в якому допускаються повторювані елементи.

   map (або «асоціативний масив») — це set, в якому кожен елемент є парою “ключ-значення”. “Ключ” використовується для сортування та індексації даних і повинен бути унікальним, а “значення” — це фактичні дані.

   multimap (або «словник») — це map, який допускає дублювання ключів. Всі ключі відсортовані в порядку зростання, і ви можете подивитися значення по ключу.

Адаптери

Адаптери — це спеціальні визначені контейнерні класи, які адаптовані для виконання конкретних завдань. Найцікавіше полягає в тому, що ви самі можете вибрати, який послідовний контейнер повинен використовувати адаптер.

   stack (стек) — це контейнерний клас, елементи якого працюють за принципом LIFO (англ. «Last In, First Out» = «останнім прийшов, першим пішов»), тобто елементи додаються (вносяться) в кінець контейнера і видаляються (виштовхуються) звідти ж (з кінця контейнера). Зазвичай в стеках використовується deque в якості послідовного контейнера за замовчуванням (що трохи дивно, оскільки vector був би більш підходящим варіантом), але ви також можете використовувати vector або list.

   queue (черга) — це контейнерний клас, елементи якого працюють за принципом FIFO (англ. «First In, First Out» = «першим прийшов, першим пішов»), тобто елементи додаються (вносяться) в кінець контейнера, але видаляються (виштовхуються) з початку контейнера. За замовчуванням в черзі використовується deque в якості послідовного контейнера, але також може використовуватися і list.

   priority_queue (черга з пріоритетом) — це тип черги, в якій всі елементи відсортовані (за допомогою оператора порівняння <). При додаванні елемента, він автоматично сортується. Елемент з найвищим пріоритетом (найбільший елемент) знаходиться на самому початку черги з пріоритетом, також, як і видалення елементів виконується з самого початку черги з пріоритетом.

На наступному уроці ми розглянемо ітератори STL.


Оцінити статтю:

1 Зірка2 Зірки3 Зірки4 Зірки5 Зірок (44 оцінок, середня: 4,98 з 5)
Завантаження...

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

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