Стандартная библиотека шаблонов STL. Контейнеры последовательностей. Лекция 14

Литература по STL:
1) Д. Мюссер, Ж. Дердж, А. Сейни, C++ и STL: справочное руководство, 2-е изд. (серия C++ in Depth).: Пер. с англ. — М.: Вильямс, 2010. — 432 с., илл.
2) С. Мейерс, Эффективное использование STL. Библиотека программиста. — М.: Питер, 2002. — 224 с., илл.
3) Л. Аммерааль, STL для программистов на С++: Пер. с англ. — М.: ДМК, 1999. — 240 с., илл.

Стандартная библиотека шаблонов -
Standard Template Library (STL)
является частью стандартной библиотеки языка С++
предоставляет набор классов-контейнеров
предоставляет набор фундаментальных алгоритмов
использует методы обобщенного программирования
большинство компонентов реализованы через шаблоны С++
Главные особенности библиотеки STL:
1) высокая степень адаптивности компонентов друг к другу
2) высокая эффективность (скорость) работы алгоритмов

Взаимодействие между основными компонентами STL
Не всякий алгоритм может работать с любым итератором!
Совместимость алгоритмов и контейнеров обеспечивается за счет контроля типов С++.

Компоненты STL – контейнеры последовательностей.
• vector
. Вектор, динамический массив c произвольным доступом к элементам (время доступа O(1)). Обеспечивает вставку и удаление элементов с конца последовательности с амортизированным O(1). Элементы вектора хранятся с памяти последовательно.
• deque<Т>. Дек, аналогичен вектору, но с возможностями вставки и удаления элементов с обоих концов последовательности. Доступ к элементу — O(1), вставка/удаление — амортизированное O(1). Реализован в виде двусвязного списка линейных массивов.
• list
. Двусвязный список, элементы которого хранятся в различных участках памяти. Время доступа к элементам — линейное (0[N), где N — текущее число элементов), время вставки/удаления — O[1] в любом месте последовательности.
Обычный массив a[N] также считается контейнером последовательности, и для него работают все алгоритмы STL. Кроме того, строковый тип string (из заголовочного файла
) совместим с алгоритмами STL.

#include
#include
using namespace std;
int main()
{
vector
v; // создаем вектор нулевой длины
int i;
// Отображаем исходный размер объекта v
cout << "размер = " << v.size() << endl;
// Помещаем значения в конец вектора:
// в результате вектор будет расти
for(i=0; i<10; i++) v.push_back(i);
// Отображаем текущий размер объекта v.
cout << "размер сейчас = " << v.size() << endl;
Пример: работа с векторами STL

// Доступ к содержимому вектора
// можно получить, используя индексы
for(i=0; i<10; i++)
cout << v[i] << " ";
cout << endl;
// Доступ к первому и последнему
// элементам вектора.
cout << "первый = " << v.front() << endl;
cout << "последний = " << v.back() << endl;
// Доступ через итератор.
vector
:: iterator p = v.begin();
while(p != v.end())
{
cout << *p << " " ;
p++;
}
return 0;
}

Обзор функций-членов класса vector
базовые функции для вставки элемента и последовательного обхода элементов в прямом и обратном порядке
обход элементов в режиме "только чтение"
размер и емкость вектора (см. рис.)

доступ к элементам по индексу
конструкторы и деструктор
Примеры использования:
Пример:

доступ к первому и последнему элементам
оператор присваивания
Пример:
Пример:
меняет местами содержимое двух векторов одного типа
Примеры:

Функции вставки и удаления элементов. Занимают время O(n), где n - номер позиции для вставки/удаления.
Пример:
вставка одного элемента в позицию position
вставка нескольких элементов
удаление элементов по одному и группой

Дополнительные функции-члены класса deque
Большинство функций дека повторяет соответствующие функции вектора (см. выше). Далее мы рассмотрим только специфические для дека функции.
К примеру, дек поддерживает вставку элементов не только в конец, но и в начало очереди (за константное время). С другой стороны, функции capacity и reserve для дека не определены.
Пример:

Дополнительные функции-члены класса list
Связанный список (list) обеспечивает вставку/удаление элементов в любой позиции за константное время. Однако доступ к элементу требует O(n) операций. Как следствие, для списка не реализован оператор доступа по индексу [].
Пример:

Функции сцепки списков (splicing) - перемещение одного или более элементов из одного списка в другой.
Вставляет содержимое списка x в текущий список перед позицией position, и оставляет список x пустым.
Вставляет элемент из списка x (в позиции j) в текущий список (перед позицией position).
Вставляет элементы диапазона [first, last] из списка x в текущий список (перед позицией position).
Пример:

Адаптер стека. Функции-члены класса stack
Стек представляет собой структуру данных, допускающую только две операции, изменяющие ее размер: 1) добавление элемента в конец последовательности, 2) извлечение элемента из конца последовательности.
В STL стек реализуется на основе вектора, дека или связанного списка. Таким образом, стек – не новый тип контейнера. Он реализован в виде адаптера к существующим контейнерам vector, deque или list. Если при создании стека тип используемого контейнера не указан, то по умолчанию используется дек.
Для стека определены следующие функции:
type top(); Значение верхнего элемента в стеке
void push(type); Поместить элемент в стека
void pop(); Извлечь элемент из стека
int size(); Количество элементов в стеке
bool empty(); Стек пуст?

Пример:

Адаптер очереди. Функции-члены класса queue
Очередь представляет собой структуру данных, в которой новый элемент добавляется в конец последовательности, а извлечение элемента происходит из начальной позиции.
В STL очередь реализуется на основе дека или связанного списка, то есть как адаптер к контейнерам deque или list. Если при создании очереди тип контейнера не указан, то по умолчанию используется дек.
Для очереди определены следующие функции:
type front(); Значение первого элемента в очереди
type back(); Значение последнего элемента в очереди
void push(type); Поместить элемент в очередь
void pop(); Удалить элемент из очереди
int size(); Количество элементов
bool empty(); Очередь пуста?

Пример:

Адаптер очереди с приоритетом.
Функции-члены класса priority_queue
Очередь с приоритетом является структурой данных, из которой можно удалить только наибольший элемент (т.е. элемент с наибольшим приоритетом).
В STL очередь с приоритетом реализуется на основе вектора или дека, как адаптер к контейнерам vector или deque. По умолчанию используется дек.
Определены следующие функции:
type top(); Значение верхнего элемента
void push(type); Поместить элемент
void pop(); Удалить элемент
int size(); Количество элементов
bool empty(); Очередь пуста?