Материал: LW_6_STL_Sontainers_adapters

ЛАБОРАТОРНАЯ РАБОТА №6 ПО ПРЕДМЕТУ «ОБЪЕКТНО-ОРИЕНТИРОВАННОЕ ПРОГРАММИРОВАНИЕ». ЧАСТЬ 2. «ВВЕДЕНИЕ В СТАНДАРТНУЮ БИБЛИОТЕКУ ШАБЛОНОВ. АДАПТЕРЫ КОНТЕЙНЕРОВ»

Стандартная библиотека STL предоставляет различные типобезопасные контейнеры для хранения коллекций связанных объектов. При объявлении переменной контейнера указывается тип элементов, которые будет содержать контейнер.

vector<int> rating(5);//вектор из 5 значений типа int

Контейнеры могут создаваться с использованием списка инициализаторов.

vector<double> payments({ 45.99, 39.23, 19.95, 89.01 });

Контейнеры содержат методы-элементы для добавления и удаления элементов контейнера и выполнения других операций над элементами контейнера.

Перебор элементов в контейнере и доступ к отдельным элементам реализуется с помощью итераторов. Можно использовать итераторы явно, с помощью их функций-элементов и операторов, а также глобальных функций. Итераторы для всех контейнеров STL имеют общий интерфейс, но каждый контейнер определяет собственные специализированные итераторы.

Контейнеры можно разделить на три категории: последовательные контейнеры, ассоциативные контейнеры и контейнеры-адаптеры.

КОНТЕЙНЕРЫ-АДАПТЕРЫ

Существуют структуры данных, которые часто используются в решении некоторого типа задач. Эти структуры данных имеют очень ограниченный набор операций с элементами. Любой, подходящий для этих целей, последовательный контейнер можно использовать для реализации таких структур. Чтобы реализовать работу с такими структурами как стек

или очередь, в C++ используются адаптеры контейнеров. Контейнер-

адаптер — это разновидность последовательного или ассоциативного контейнера, который ограничивает интерфейс для простоты и ясности. Контейнеры-адаптеры не поддерживают итераторы.

Адаптер – класс, который не реализует собственную функциональность, а вместо этого предоставляет альтернативный интерфейс к функциональности другого класса.

Контейнер queue соответствует семантике FIFO (первым поступил — первым обслужен). Первый элемент передается, помещается в очередь и должен первым извлекается, удаляться из очереди.

Контейнер priority_queue упорядочен таким образом, что первым в очереди всегда оказывается элемент с наибольшим значением (приоритетом).

Контейнер stack соответствует семантике LIFO (последним поступил

— первым обслужен). Последний элемент, отправленный в стек, становится первым извлекаемым элементом.

Поскольку контейнеры-адаптеры не поддерживают итераторы, их нельзя использовать в алгоритмах STL.

Адаптер (adaptor) — это фундаментальная концепция библиотеки. Существуют адаптеры контейнера, итератора и функции. По существу, адаптер — это механизм, заставляющий нечто одно действовать как нечто другое. Адаптер контейнера получает контейнер существующего типа и заставляет его действовать как другой. Например, адаптер stack получает любой из последовательных контейнеров (array и forward list) и заставляет его работать подобно стеку. Функции и типы данных, общие для всех адаптеров контейнеров, перечислены в таблице ниже.

Таблица – Функции и типы, общие для всех контейнеров адаптеров

Каждый контейнер адаптер определяет два конструктора: стандартный конструктор, создающий пустой объект, и конструктор, получающий контейнер и инициализирующий адаптер, копируя полученный контейнер. Предположим, например, что deq – это двусторонняя очередь deque<int>. Ее можно использовать для инициализации нового стека следующим образом:

deque<int> deq;

stack<int> stk(deq);//копирует элементы из deq в stk

По умолчанию контейнеры-адаптеры, stack и queue, реализованы на основании контейнера deque. Контейнер-адаптор priority_queue может быть реализован как на базе контейнера vector так, и на базе deque.

Заданный по умолчанию тип контейнера можно переопределить, указав последовательный контейнер как второй аргумент при создании адаптера:

//пустой стек, реализованный поверх вектора stack<string, vector<string>> strStack1; vector<string> strVector2; strVector2.push_back("firstString"); strVector2.push_back("secondString"); strVector2.push_back("thirdString");

//strStack3 реализован поверх вектора, первоначально содержит копию strVector2

stack<string, vector<string>> strStack3(strVector2);

Существуют некоторые ограничения на применение контейнеров с определенными адаптерами.

Всем адаптерам нужна возможность добавлять и удалять элементы. В

результате адаптеры не могут быть основаны на массиве. Точно также нельзя использовать контейнер forward_list, поскольку все адаптеры требуют функций добавления, удаления и обращения к последнему элементу контейнера.

Адаптер stack требует только функций push(), pop(), top(), поэтому для стека можно использовать контейнер любого из остальных типов.

Следующая программа иллюстрирует использование адаптера stack:

//Пример №1. Использование класса stack #include <stack>

#include <iostream> using namespace std; int main() {

stack<int> intStack; //пустой стек //заполнить стек

for (size_t i = 0; i != 10; ++i)

intStack.push(i);//добавление в intStack значений от 0 до 9 while (!intStack.empty()) {//пока в intStack есть значения

cout << intStack.top()<<endl; intStack.pop();//извлечь верхний элемент и повторить

}

return 0;

}

Результаты работы программы:

Сначала intStack объявляется как пустой стек целочисленных элементов. Затем цикл for добавляет десять элементов, инициализируя каждый следующим целым числом, начиная с нуля. Цикл while перебирает весь стек, извлекая и выводя верхний элемент, пока стек не опустеет.

Хотя стек реализован на основании контейнера, прямого доступа к функциям контейнера deque нет. Для стека нельзя вызвать функцию push_back(), вместо нее следует использовать функцию push().

По умолчанию адаптер stack реализован на базе контейнера deque, но адаптер stack может быть также реализован на базе контейнеров list

или vector.

//Пример №2. Использование класса stack #include <stack>

#include <iostream> using namespace std; int main() {

system("chcp 1251"); system("cls"); stack <int> s1, s2; s1.push(10); s1.push(20); s1.push(30);