Адаптери. 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, Програмування для початківців

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

Olej

Про Olej

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

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

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