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

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

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

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

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

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

#include <iostream> 
#include <vector> 
#include <stack> 
#include <string>
using namespace std;

int main(int argc, char *argv[]) {
	setlocale(LC_ALL, "rus");

	stack<string> st;
	stack<string, vector<string> > vst(
		vector<string>({ "строка 1", "строка 2" })
	);
	vst.push("последняя строка");
	while (!vst.empty()) {
		cout << vst.top() << " : в стеке строк " << vst.size() << endl;
		vst.pop();
	}
	cout << "стек " << (vst.empty() ? "" : "не ") << "пуст" << endl;
}

#include <iostream>

#include <vector>

#include <stack>

#include <string>

using namespace std;

int main(int argc, char *argv[]) {

setlocale(LC_ALL, "rus");

stack<string> st;

stack<string, vector<string> > vst(

vector<string>({ "строка 1", "строка 2" })

);

vst.push("последняя строка");

while (!vst.empty()) {

cout << vst.top() << " : в стеке строк " << vst.size() << endl;

vst.pop();

}

cout << "стек " << (vst.empty() ? "" : "не ") << "пуст" << endl;

}

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

перше визначення 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). (Це така «труба», в один кінець якої щось втікає, а з іншого кінця потім випливає.)

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

#include <iostream> 
#include <list> 
#include <queue> 
#include <string>
using namespace std;

int main(int argc, char *argv[]) {
	setlocale(LC_ALL, "rus");

	queue<string> st;
	queue<string, list<string> > vst(
		list<string>({ "строка 1", "строка 2" })
	);
	vst.push("последняя строка");

	while (!vst.empty()) {
		cout << vst.front() << " : в очереди строк " << vst.size() << endl;
		vst.pop();
	}

	cout << "очередь " << (vst.empty() ? "" : "не ") << "пуста" << endl;
}

#include <iostream>

#include <list>

#include <queue>

#include <string>

using namespace std;

int main(int argc, char *argv[]) {

setlocale(LC_ALL, "rus");

queue<string> st;

queue<string, list<string> > vst(

list<string>({ "строка 1", "строка 2" })

);

vst.push("последняя строка");

while (!vst.empty()) {

cout << vst.front() << " : в очереди строк " << vst.size() << endl;

vst.pop();

}

cout << "очередь " << (vst.empty() ? "" : "не ") << "пуста" << endl;

}

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

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

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

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