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

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

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

Цель работы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Итераторы:

  • 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

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

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

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

Рандомно подобранные статьи с сайта:

Язык С++: Введение в стандартную библиотеку шаблонов (STL). Центр онлайн-обучения «Фоксфорд»


Похожие статьи:

admin