ільного місця, або все-таки не вистачає осередків, а це може призвести до чого завгодно, аж до зависання програми. У STL для боротьби з такими труднощами існує контейнер vector. Але з масивами є ще одна проблема. Припустимо, в масиві зберігаються дані про працівників, і ви відсортували їх за алфавітом відповідно з прізвищами. Тепер, якщо потрібно буде додати співробітника, прізвище якого починається з букви Л, то доведеться зрушити всіх працівників з прізвищами на М - Я, щоб звільнити місце для вставки нового значення. Все це може займати досить багато часу. У STL мається контейнер список, який заснований на ідеї зв'язного списку і який вирішує дане питання. Третім представником послідовних контейнерів є чергу з двостороннім доступом. Це комбінація стека і звичайній черзі. Стек, як ви пам'ятаєте, працює за принципом LIFO (останній увійшов - першим вийшов). Тобто і введення, і виведення даних в стеку проводиться «зверху». У черзі ж, навпаки, використовується принцип FIFO (першим прийшов - першим вийшов): дані надходять «зверху», а виходять «знизу». Черга з двостороннім доступом, треба думати, використовує комбінований порядок обміну даних. І вносити значення в чергу з двостороннім доступом, і виводити з неї можна з обох сторін. Це досить гнучкий інструмент, він цінний не тільки сам по собі, але може служити базою для стеків черг, в чому ми незабаром зможемо переконатися.
Асоціативні контейнери.
Асоціативний контейнер - це вже дещо інша організація
даних. Дані розташовуються не послідовно, доступ до них здійснюється за допомогою ключів. Ключі - це просто номери рядків, вони зазвичай використовуються для вибудовування зберігаються елементів у певному порядку і модифікуються контейнерами автоматично. Прикладом може служити звичайний орфографічний словник, де слова сортуються за алфавітом. Ви просто вводите потрібне слово (значення ключа), наприклад «кавун», а контейнер конвертує його в адресу цього елемента в пам'яті. Якщо відомий ключ, доступ до даних здійснюється дуже просто. У STL є два типи асоціативних контейнерів: безлічі і відображення. І ті й інші контейнери зберігають дані у вигляді дерева, що дозволяє здійснювати швидку вставку, видалення і пошук даних. Множини і відображення є дуже зручними і при цьому досить універсальними інструментами, які можуть застосовуватися в дуже багатьох ситуаціях. Але здійснювати сортування та виконувати інші операції, що вимагають випадкового доступу до даних, незручно. Безлічі простіше і, можливо, через це більш популярні, ніж відображення. Безліч зберігає набір елементів, що містять ключі - атрибути, використовувані для упорядкування даних. Наприклад, безліч може зберігати об'єкти класу person, які упорядковуються в алфавітному порядку. Як ключ при цьому використовується значення name. При такій організації даних можна дуже швидко знайти потрібний об'єкт, здійснюючи пошук по імені об'єкта (шукаємо об'єкт класу person по атрибуту name). Якщо в безлічі зберігаються значення одного з базових типів, таких, як int, ключем є сам елемент. Деякі автори називають ключем весь об'єкт, що зберігається в множині, але ми будемо вживати термін ключовий об'єкт, щоб підкреслити, що атрибут, використовуваний для впорядковування (ключ), - це не обов'язково весь елемент даних. Відображення зберігає пари об'єктів. Один кортеж в такій «базі даних» складається з двох «атрибутів»: ключовий об'єкт і цільової (асоційований) об'єкт. Цей інструмент часто використовується в якості контейнера, кілька нагадує масив. Різниця лише в тому, що доступ до даних здійснюється не по номеру елемента, а за спеціальним індексом, який сам по собі може бути довільного типу. Тобто ключовий об'єкт служить індексом, а цільовий - значенням цього індексу. Контейнери відображення і безліч дозволяють зіставляти тільки один ключ даному значенням. Це має сенс в таких, наприклад, випадках, як зберігання списку працівників, де кожному імені зіставляється унікальний ідентифікаційний номер. З іншого боку, мул'тіотображенія і мультимножини дозволяють зберігати кілька ключів для одного значення Наприклад, слову «ключ» в тлумачному словнику можна порівнювати кілька статей.
2.1.3 Контейнерні класи
Кожен контейнер має певний для нього аллокатор (allocator). Аллокатор управляє виділенням пам'яті для контейнера. Аллокатором за замовчуванням є об'єкт класу allocator, але ви можете визначати свої власні аллокатори, якщо це необхідно для спеціалізованих додатків. Для більшості застосувань аллокатора за замовчуванням цілком достатньо.
Контейнери реалізовані за допомогою шаблонних класів. Наприклад, нижче показу- на специфікація шаблону контейнера deque. Усі контейнери використовують схожі специфікації: template lt; class T, class Allocator=allocator lt; T gt; gt; class deque Тут узагальнений тип T специфікує тип об'єктів, що збе...
