Адаптери. STL (частина 15)




stack, Програмування для початківців

Окремою категорією бібліотеки стандартних шаблонів є адаптери. Адаптери - це не нові поняття або реалізації, а адаптація вже існуючих понять бібліотеки під конкретні, часто використовуються цілі. Часто така адаптація робиться за допомогою обмеження функціональності базового поняття під запити адаптера. У бібліотеці представлені адаптери контейнерів, ітераторів і функцій.

Найпростіше показати, як з'являються адаптери на прикладі адаптерів контейнерів: stack (стек), queue (черга), priority_queue (черга з пріоритетами). Уже з їх перерахування зрозуміло, що:

  • Це дуже широко і часто використовувані структури даних;

  • Для них не потрібні якісь окремі реалізації. Для забезпечення їх функціональності можна використовувати (адаптувати) в якості базового будь-який зі стандартних контейнерів STL, який забезпечує операції типу push_back, pop_back или pop_front (в залежності від типу адаптера);

  • «Зайві» операції з арсеналу базового контейнера для адаптера потрібно виключити (щоб не створювати спокуси ... наприклад, операцію індексації, якщо vector використовується для адаптації стека);

И, замість громіздких шаблонних синтаксичних визначень (заголовки <stack>, <queue> і т. п.), звернемося до прикладів…

Почнемо зі стека: стек характерний тим, що отримати доступ до його елементів можна лише з одного кінця, званого вершиною стека. Це колекція даних, що функціонує за принципом LIFO (Last In - First Out). Ось такий простенький приклад розкриває нам практично всю функціональність стека:

Проаналізуємо код і зробимо деякі висновки:

  • перше визначення stack<string> (ми його далі не використовуємо) оголошує змінну стек, елементами якого є рядки. Звертаємо увагу на те, що об'єкти string самі по собі є контейнерами STL. Таким образом, стек може містити елементи будь-якої глибини укладення контейнерів (що властиво і будь-яким іншим контейнерів STL).

  • таке визначення ( stack<string> ) ви зможете побачити, як опис стека в переважній більшості прикладів. Багато авторів і не підозрюють, що може бути по-іншому. Але ми скористаємося іншим визначенням: stack< string, vector<string> > - Це стек рядків (багато в чому еквівалентний попередньому), але побудований на базовому класі vector<string>. Як базові можуть використовуватися, например, vector, list і deque, або навіть ваш власний контейнерний клас, розширює базові. По умолчанию (так як в 1-м визначенні) використовується база deque. Іноді запитують: чому не можна написати (визначити так в реалізації stack): stack< vector<string> > (прибравши дублювання string)? Тому що (і це цілком можливо) це буде опис зовсім іншого типу: стек векторів строк (см. вище зауваження про структурну вкладеності контейнерів).

  • далі слід ініціалізація початкового стану з вектора рядків. відзначте, що такий трюк допустимо тільки в стандарті C ++ 11.

  • Далі ми бачимо практично всі операції (методи), вимагаються від стека: push() – заталківаніе об'єкта в стек, top() – отримання посилання на елемент в вершині стека, pop() – викидання верхнього елементу, size() – поточний розмір стека, empty() – перевірка на порожнечу.

  • Як легко зрозуміти, адаптер stack втратив властиві базовому контейнеру методи (at(), [ ] та ін.), але придбав (перевизначенням) свої власні (push(), pop()).

Тепер подивимося що з цього вийшло:

stack, Програмування для початківців

Розібравшись зі стеком тепер елементарно просто перенести аналогії на чергу. На противагу стеку – це колекція даних, що функціонує за принципом FIFO (First In - First Out). (Це така «труба», в один кінець якої щось втікає, а з іншого кінця потім випливає.)

Спеціально залишимо для черги приклад практично незмінним, внісши правки, необхідні семантикою мови:

Від нас вимагали змінити:

  • Черга не може бути побудована на базовому контейнері vector у якого немає методу pop_front(), але може будуватися на list, deque, або будь-якому іншому контейнері, реализующем базовий набір методів (front(), push_back(), pop_front()), за замовчуванням використовується deque.

  • У адаптера queue немає методу top(), а є метод аналогічного змісту front().

І в результаті отримуємо (порівняйте з результатами для стека!):

stack, Програмування для початківців

Нові уроки з програмування:

дата
сторінка
Адаптери. STL (частина 15)
рейтинг
51зірка1зірка1зірка1зірка1зірка
Olej

Про Olej

Стаж практичних програмних розробок близько 40 лет. Викладач міжнародної софтверної компанії Global Logic. Постійний автор публікацій IBM Developer Works. Науковий редактор книжкового видавництва комп'ютерної літератури "Символ-Плюс", Санкт-Петербург.

залишити коментар

Код розміщуйте в тегах: <pre class="lang:C ++ декодуванням:true ">ВАШ КОД</заздалегідь>