В послідовних контейнерах дані зберігаються подібно до того, як стоять будинки на вулиці – в ряді. Кожен елемент зв’язується з іншим за посередництвом номара своєї позиції в ряду. Всі елементи, крім кінцевих, мають по сусіду з кожного боку. Прикладом послідовного контейнера є звичайний масив.
Проблема з масивами полягає в тому, що їх розміри слід вказувати при компіляції, тобто у вихідному коді. На жаль, під час написання програми переважно невідомо, скільки саме елементів міститиме масив, тому розраховують на найгірший варіант і вказують розмір «з запасом». Як наслідок, під час роботи програми виявляється, що пам’яті або забагато, або все-таки не вистачає, а це може призвести навіть до зависання програми. В STL для боротьби з такими труднощами існує контейнер вектор.
Але з масивами виникає ще одна проблема. Припустімо, що наш масив містить дані про співробітників, відсортовані за алфавітним порядком їх прізвищ. Вставка нвого запису або збиває порядок сортування, або ж вимагає трудомістких зсовувань елементів. В STL є контейнер список, який базується на ідеї зв’язного списку і вирішує дане питання. Вивчаючи вказівники, ми вже працювали зі зв’язним списком і вставляли туди дані за допомогою перестановки кількох вказівників.
Третім представником послідовних контейнерів є черга з двостороннім доступом. Це комбінація стеку та звичайної черги. Стек організований за принципом «останнім ввійшов, першим вийшов», черга – навпаки: «першим ввійшов – першим вийшов». Черга з двостороннім доступом використовує комбінований порядок обміну даними. І вносити зміни в чергу з двостороннім доступом, і виходити з неї можна з двох сторін. Це доволі гнучкий інструмент, він цінний не лише сам собою, а також як база для стеку черг.
В таблиці 10.1 приведені характеристики послідовних контейнерів STL. Для порівняння приводиться звичайний масив.
Таблиця 15.1
Основні послідовні контейнери
Контейнер
| Характеристика
| Плюси/мінуси
|
Звичайний масив
| Фіксований розмір
| Швидкісний випадковий доступ (за індексом)
Повільна вставка або вилучення даних з середини
Розмір не може бути змінений під час роботи програми
|
Вектор
| Перерозподілюваний розширюваний масив
| Швидкісний випадковий доступ (за індексом)
Повільна вставка або вилучення даних з середини
Швидкісна вставка або вилучення даних з хвоста
|
Список
| Аналогічний до зв’язного списку
| Швидкісна вставка або вилучення даних з будь-якого місця
Швидкий доступ до обох кінців
Повільний випадковий доступ
|
Черга з двостороннім доступом
| Як вектор, але доступ з обох сторін
| Швидкісний випадковий доступ.
Повільна вставка або вилучення даних з середини.
Швидкісна вставка або вилучення даних з хвоста або голови
|
.Реалізація на практиці контейнера STL не становить особливих труднощів. По-перше, треба включити в програму відповідний заголовочний файл. Передача інформації про те, які типи об’ктів будуть зберігатися, відбувається у вигляді передачі параметра в шаблон. Наприклад:
vector <int> avect; //створення вектора цілих чисел
або
list<airtime> atime_list; //створити список типу atime
В STL не потрібно специфікувати розміри контейнера. Вони самі турбуються про розміщення своїх даних в пам’яті.