Стандартная библиотека шаблонов (STL)

Лабораторная работа № 8

Разработка приложений обработки абстрактных структур данных.

Цель работы

Овладеть практическими навыками работы с абстрактными структурами данных. Научиться формировать абстрактные структуры данных, освоить технику программирования операций над ними.

Краткие сведения из теории

Стек – это односвязный список, в котором можно удалять только первый элемент, а добавлять новый элемент – только перед первым. Таким образом, стек есть список, в котором возможно удалить только первый элемент, т. е. элемент, включенный в список последним, является головным (или первым). Иначе говоря, стек – это структура, у которой вход и выход совпадают.

На практике структура «стек» встречается очень часто: это и железнодорожный тупик, и пирамида, и рожок от автомата, и способ организации данных при работе программы на компьютере и т. д. Для стека существуют всего две операции – добавить элемент в стек и удалить элемент из стека. Эти операции принято оформлять соответственно в виде функций push() и pop(). Также реализуются операции вывода содержимого стека и определения глубины стека (количества элементов в стеке).

Очередь – это односвязный список, в котором можно удалять только первый элемент, а добавлять новый элемент – только к последнему.

Основными операциями для очереди являются: добавление элемента в очередь, удаление элемента из очереди, просмотр содержимого очереди, определение длины очереди.

Стандартная библиотека шаблонов (STL).

STL обеспечивает общецелевые, стандартные классы и функции, которые реализуют наиболее популярные и широко используемые алгоритмы и структуры данных.

STL строится на основе шаблонов классов, и поэтому входящие в нее алгоритмы и структуры применимы почти ко всем типам данных.

Ядро библиотеки образуют три элемента: контейнеры, алгоритмы и итераторы.

Контейнеры (containers) - это объекты, предназначенные для хранения других элементов. Например, вектор, линейный список, множество.

В каждом классе-контейнере определен набор функций для работы с ними. Например, список содержит функции для вставки, удаления и слияния элементов.

Алгоритмы (algorithms) выполняют операции над содержимым контейнера. Существуют алгоритмы для инициализации, сортировки, поиска, замены содержимого контейнеров. Многие алгоритмы предназначены для работы с последовательностью (sequence), которая представляет собой линейный список элементов внутри контейнера.

Итераторы (iterators) - это объекты, которые по отношению к контейнеру играют роль указателей. Они позволяют получить доступ к содержимому контейнера примерно так же, как указатели используются для доступа к элементам массива.

В STL определены два типа контейнеров: последовательности и ассоциативные.

Ключевая идея для стандартных контейнеров заключается в том, что когда это представляется разумным, они должны быть логически взаимозаменяемыми. Пользователь может выбирать между ними, основываясь на соображениях эффективности и потребности в специализированных операциях. Например, если часто требуется поиск по ключу, можно воспользоваться map (ассоциативным массивом). С другой стороны, если преобладают операции, характерные для списков, можно воспользоваться контейнером list. Если добавление и удаление элементов часто производится в концы контейнера, следует подумать об использовании очереди queue, очереди с двумя концами deque, стека stack. По умолчанию пользователь должен использовать vector ; он реализован, чтобы хорошо работать для самого широкого диапазона задач.

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

В STL определены следующие классы-контейнеры (в угловых скобках указаны заголовочные файлы, где определены эти классы):

• bitset - множество битов <bitset.h>
• vector - динамический массив <vector.h>
• list - линейный список <list.h>
• deque - двусторонняя очередь <deque.h>
• stack - стек <stack.h>
• queue - очередь <queue.h>
• priority_queue - очередь с приоритетом <queue.h>
• map - ассоциативный список для хранения пар ключ/значение, где с каждым ключом связано одно значение <map.h>
• multimap - с каждым ключом связано два или более значений <map.h>
• set - множество <set.h>
• multiset - множество, в котором каждый элемент не обязательно уникален <set.h>

Итераторы:

• begin() - указывает на первый элемент
• end() - указывает на элемент, следующий за последним
• rbegin() - указывает на первый элемент в обратной последовательности
• rend() - указывает на элемент, следующий за последним в обратной последовательности

Доступ к элементам:

• front() - ссылка на первый элемент
• back() - ссылка на последний элемент
• operator [](i) - доступ по индексу без проверки
• at(i) - доступ по индексу с проверкой

Включение элементов:

• insert(p, x) - добавление х перед элементом, на который указывает р
• insert(p, n, x) - добавление n копий х перед р
• insert(p, first, last) - добавление элементов из [first:last] перед р
• push_back(x) - добавление х в конец
• push_front(x) - добавление нового первого элемента (только для списков и очередей с двумя концами)

Удаление элементов:

• pop_back() - удаление последнего элемента
• pop_front() - удаление первого элемента (только для списков и очередей с двумя концами)
• erase(p) - удаление элемента в позиции р
• erase(first, last) - удаление элементов из [first:last]
• clear() - удаление всех элементов

Другие операции:

• size() - число элементов
• empty() - контейнер пуст
• capacity() - память, выделенная под вектор (только для векторов)
• reserve(n) - выделяет память для контейнера под n элементов
• resize(n) - изменяет размер контейнера (только для векторов, списков и очередей с двумя концами)
• swap(x) - обмен местами двух контейнеров
• ==, !=, < операции сравнения

Операции присваивания:

• operator =(x) - контейнеру присваиваются элементы контейнера х
• assign(n, x) - присваивание контейнеру n копий элементов х (не для ассоциативных контейнеров)
• assign(first, last) - присваивание элементов из диапазона [first:last]

Ассоциативные операции:

• operator [](k) - доступ к элементу с ключом k
• find(k) - находит элемент с ключом k
• lower_bound(k) - находит первый элемент с ключом k
• upper_bound(k) - находит первый элемент с ключом, большим k
• equal_range(k) - находит lower_bound (нижнюю границу) и upper_bound (верхнюю границу) элементов с ключом k

Манипулирование контейнером, сортировка, поиск в нем и тому подобное возможно с помощью глобальных функций файла - заголовка <algorithm.h>.

Порядок выполнения работы

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