контейнеры STL

1. Тема 16

Контейнеры STL
© 2012, Serge Kashkevich

2.

Что такое STL?
STL (standard template library) – библиотека
стандартных методов и классов, входящая в состав
любой системы программирования, основанной на
языке C++. Эта библиотека основана на шаблонах.
В состав STL входят:
потоковые классы;
классы для работы со строками (string);
контейнерные классы;
итераторы и алгоритмы для работы с
контейнерными классами;
математические классы;
диагностические классы (в т.ч. класс exception);
прочие классы.

3. Для чего нужны контейнерные классы?

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

4. Классификация контейнеров

Контейнеры
Последовательные
Адаптеры
Ассоциативные
vector
stack
map
deque
queue
multimap
list
priority_queue
set
multiset
bitset

5. Различия в типах контейнеров

Последовательные контейнеры обеспечивают
хранение однотипных величин в виде непрерывной
последовательности, т.е. определены понятия
"начальный элемент", "конечный элемент",
"предыдущий элемент", "последующий элемент ";
2. Использование ассоциативных контейнеров
предполагает, что в хранимых данных выделяется
ключ, который определяет конкретный элемент
хранимых данных, и неключевая информация.
Ассоциативные контейнеры обеспечивают быстрый
доступ к данным по значениям ключа.
1.

6. Различия в типах контейнеров

Адаптеры реализованы на основе базовых
последовательных контейнеров и предназначены для
выполнения ограниченного набора операций. Каждый
адаптер строится с использованием механизма
реализации конкретного базового класса.
3.

7. Создание контейнеров

Для создания контейнера необходимо в
качестве параметра шаблона указать тип
данных, хранящихся в шаблоне:
vector <int> v;
Для создания адаптера, кроме типа данных,
можно указывать базовый контейнер,
используемый для создания адаптера:
stack <double> s1;
// базовый контейнер – deque <double>
stack <int, vector <int> > s2;

8. Итераторы

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

9. Определение итераторов

Итератор описан в каждом контейнере как
вспомогательный класс, поэтому при определении
итератора необходимо указывать контейнер, для
которого итератор будет использоваться:
vector <int> :: iterator i1; // правильно
vector :: iterator i2; // неправильно
iterator i3; // неправильно
Можно сделать и так:
typedef vector <int> :: iterator it_vint;
it_vint i1, i2, i3;

10. Действительные и недействительные итераторы

Итераторы могут быть действительными и
недействительными. Действительный итератор
связан с конкретным элементом контейнера, и мы
можем получить доступ к этому элементу, используя
итератор. С недействительными итераторами так
поступать нельзя.
Итераторы становятся недействительными:
после определения, но до инициализации;
при выходе за границы контейнера;
после удаления элемента, с которым был связан
итератор;
после вставки в вектор и deque (иногда);
в результате присвоения значения метода end(),
rend().

11. Основные операции над итераторами

Пусть i – итератор, n – целое число, c - контейнер
Все итераторы
– получение доступа к элементу контейнера, с
которым связан итератор;
i++ – после этой операции итератор становится
связанным со следующим элементом контейнера
i+n – перемещение итератора на n элементов (при
этом возможен выход за границы контейнера!). Для
итераторов, связанных с контейнером list, эта
операция недопустима
i1 = i2 – присваивание
i1 == i2, i1 != i2 – сравнение (других операций
сравнения нет!)
*i

12. Основные операции над итераторами

Пусть i – итератор, n – целое число, c – контейнер
Прямые итераторы
– итератор связывается с первым
элементом контейнера c;
= c.end() – итератор связывается с фиктивным
элементом контейнера c, который «стоит» за
последним элементом. Итератор i становится
недействительным!
i = c.begin()
i

13. Основные операции над итераторами

Реверсивные итераторы
– итератор связывается с последним
элементом контейнера c;
= c.rend() – итератор связывается с фиктивным
элементом контейнера c, который «стоит» перед
первым элементом. Итератор i становится
недействительным!
i = c.rbegin()
i
c.rend()
c.rbegin()
Реверсивные итераторы
Прямые итераторы
c.begin()
c.end()

14. Примеры работы с итераторами

просмотр всех элементов списка
typedef list <int> :: iterator it_lint;
list <int> L;
// заполнение списка
for (it_lint i = L.begin(); i!=L.end(); i++)
cout << *i << endl;
просмотр всех элементов списка в обратном
порядке
typedef list <int> :: reverse_iterator rit_lint;
list <int> L;
// заполнение списка
for (rit_lint i = L.rbegin(); i!=L.rend(); i++)
cout << *i << endl;

15. Интервал

Интервал – несколько подряд идущих элементов
контейнера. Интервал задаётся двумя итераторами i1
и i2. Итератор i1 связан с первым элементом,
входящим в интервал, а i2 – с элементом, стоящим за
последним элементом интервала. Если i2 == c.end(),
то в интервал входят последние элементы контейнера.
Если i1 == i2, то интервал пуст.
i1
i2

16. Операции над последовательными контейнерами

Следующие операции допустимы над всеми
последовательными контейнерами:
вставка в начало контейнера (перед первым
элементом) – push_front;
вставка в конец контейнера (после последнего
элемента) – push_back;
удаление начального элемента – pop_front;
удаление последнего элемента – pop_back;
вставка в произвольное место – insert;
удаление из произвольного места – erase;
доступ к элементу по его индексу – at или [].

17. Допустимость и трудоёмкость операций для различных типов последовательных контейнеров

vector
deque
list
push_front
нет
О(1)
О(1)
push_back
О(1)
О(1)
О(1)
pop_front
нет
О(1)
О(1)
pop_back
О(1)
О(1)
О(1)
insert
O(n)
O(n)
О(1)
erase
O(n)
O(n)
О(1)
at, []
O(1)
O(1)
нет

18. Основные типы, используемые при работе с последовательными контейнерами

value_type, T
Тип данных, хранящихся в контейнере
size_type
iterator
Тип индексов, числа элементов,
размеров
Прямой итератор
reverse_iterator
Реверсивный итератор
reference
Ссылка на элемент контейнера (может
быть L-value)
Определение размеров контейнера
size_type size()
Число элементов в контейнере
size_type max_size() Максимально допустимое число
элементов
bool empty()
true, если контейнер пуст

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

Доступ к элементам контейнера
reference operator
К элементу контейнера без
[](size_type)
контроля выхода за границы
контейнера (нумерация
начинается с нуля)
reference at(size_type) К элементу контейнера, при
выходе за границы порождается
исключение out_of_range
reference front()
К первому элементу контейнера
reference back()
К последнему элементу
контейнера

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

Добавление и удаление элементов контейнера
void push_front
Добавление нового элемента в
(const T& значение)
начало контейнера
void push_back
Добавление нового элемента в
(const T& значение)
конец контейнера
void pop_front()
Удаление начального элемента
void pop_back()
Удаление конечного элемента

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

Добавление и удаление элементов контейнера
iterator
Вставка элемента с указанным
insert(iterator
значением перед указанной
позиция, const T&
позицией (если позиция равна
значение)
begin(), то вставка в начало, если
end() – в конец). Возвращает
итератор на вставленный элемент.
void insert(iterator Вставка нескольких одинаковых
позиция, size_type
элементов
количество, const T&
значение)
template <class Iter> Вставка в один контейнер
void insert(iterator элементов из другого контейнера
позиция, Iter i1,
(интервал вставляемых элементов
Iter i2)
задаётся итераторами i1 и i2)

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

Добавление и удаление элементов контейнера
iterator erase(iterator Удаление элемента,
позиция)
находящегося в указанной
позиции. Возвращает итератор
на элемент, следующий за
удалённым, или end().
iterator erase(iterator Удаление интервала элементов
i1, iterator i2)
контейнера, задаваемого парой
итераторов (i1, i2). Возвращает
итератор на элемент, следующий
за удалёнными, или end().

23. Конструкторы последовательных контейнеров (на примере vector)

vector()
конструктор по умолчанию
vector(size_type размер,
const T& значение=T())
создает вектор заданного
размера и инициализирует его
значения
создает vector на основе
элементов другого контейнера
(два итератора задают
интервал для добавляемых
элементов)
конструктор копирования
template <class Iter>
vector (Iter первый, Iter
граница)
vector (const vector<T>& )

24. Примеры работы с последовательными контейнерами

vector <int> v1, v2;
// описываем два вектора
…
for (int i=1; i<=10; i++) v1.push_back(i);
// содержимое v1: 1 2 3 4 5 6 7 8 9 10
…
v2.insert(v2.begin(), 5);
// содержимое v2: 5
…
v2.insert(v2.end(), 5, 2);
// содержимое v2: 5 2 2 2 2 2
…
v2.insert(v2.begin(), v1.begin()+5, v1.begin()+7);
// содержимое v2: 6 7 5 2 2 2 2 2
…
v1.erase(v1.begin());
// содержимое v1: 2 3 4 5 6 7 8 9 10
…
v1.erase(v1.begin()+4, v1.end()-1);
// содержимое v1: 2 3 4 5 10

25. Примеры работы с последовательными контейнерами

vector <int> v1;
Задание: удалить из контейнера все элементы, меньшие 5
vector <int> ::iterator i;
for (i=v1.begin(); i!=v1.end(); i++)
if (*i<5)
v1.erase(i);
Результат неверен, т.к. после удаления элемента
связанный с ним итератор становится недействительным,
и выполнять операцию i++ нельзя!

26. Примеры работы с последовательными контейнерами

Верные варианты решения этой задачи:
vector <int> ::iterator it;
for (unsigned i=0; i<v1.size();) {
if (v1[i]<5) {
it = (v1.begin() + i);
v1.erase(it);
}
else
i++;
}
vector <int>::iterator i;
for (i=v1.begin(); i != v1.end();) {
if (*i<5)
i = v1.erase(i); // erase возвращает правильный
// итератор на элемент, следующий за удаленным
else
i++;
}

27. Особенности работы с контейнером vector

Память под вектор выделяется динамически, возможно,
сразу под группу элементов. Выделением памяти можно
управлять:
Методы для управления распределением памятью
size_type capacity()
количество элементов, которое
const
может быть помещено в
вектор без дополнительного
выделения памяти
void reserve(size_type
резервирует память для
количество)
указанного количества
элементов
void resize(size_type
изменяет количество
количество, T
элементов в векторе, при
новоезначение=T())
необходимости удаляя или
добавляя элементы

28. Примеры управления распределением памяти

vector <int> L; // память будет выделяться поэлементно
cout << L.capacity() << " " << L.size() << endl;
// результат: 0 0
L.push_back(10);
L.push_back(12);
L.push_back(15);
L.push_back(16);
L.push_back(11);
L.insert(L.begin()+1, 30);
cout << L.capacity() << " " << L.size() << endl;
// результат: 6 6
L.pop_back();
cout << L.capacity() << " " << L.size() << endl;
// результат: 6 5

29. Примеры управления распределением памяти (продолжение)

L.reserve(100);
cout << L.capacity() << " " << L.size() << endl;
// результат: 100 5
L.resize(20);
cout << L.capacity() << " " << L.size() << endl;
// результат: 100 20
// новые элементы примут значение 0

30. Примеры управления распределением памяти (продолжение)

vector <int> L(100);
// память будет выделяться блоками по 50 элементов
cout << L.capacity() << " " << L.size() << endl;
// результат: 100 100
L.push_back(10);
cout << L.capacity() << " " << L.size() << endl;
// результат: 150 101

31. Особенности работы с контейнером list

Контейнер List обладает дополнительными методами:
Перенос элементов из одного списка в другой
void splice(iterator
Вставляет перед указанной
позиция, list <T>&
позицией все элементы из
источник)
списка-источника; источник
очищается
void splice(iterator
то же, но из списка-источника
позиция, list <T>&
переносится только один
источник, iterator
элемент
позицияисточника)
void splice(iterator
позиция, list <T>&
источник, интервал)
то же, только переносится
интервал элементов из спискаисточника

32. Особенности работы с контейнером list

Контейнер List обладает дополнительными методами:
void remove(const T&
значение)
void remove_if(предикат)
void sort()
void unique()
void merge(list <T>&)
void reverse()
удаляет из списка все элементы с
определенным значением
удаляет из списка все элементы с
значениями, удовлетворяющими
предикату
сортирует элементы списка в
соответствии с правилами
сравнения для типа T
оставляет в списке только первый
элемент из серии одинаковых
подряд идущих элементов
сливает два упорядоченных списка
в третий, также упорядоченный.
Список-параметр очищается.
изменяет порядок следования
элементов на обратный

33. Примеры работы с контейнером list

typedef list <int> :: iterator it_lint;
typedef list <int> :: reverse_iterator rit_lint;
list <int> L(10), L1;
void WriteList(list <int> L) {
cout << L.size() << ": ";
for (it_lint i = L.begin(); i!=L.end(); i++)
cout << *i << " ";
cout << endl;
}
int c=0;
for (it_lint i = L.begin(); i!=L.end(); i++)
(*i)=(c+=4);
WriteList(L);
// результат: 10: 4 8 12 16 20 24 28 32 36 40

34. Примеры работы с контейнером list (продолжение)

L1.splice(L1.begin(), L);
WriteList(L);
WriteList(L1);
// результат:
// 0:
// 10: 4 8 12 16 20 24 28 32 36 40
L1.splice(L1.begin(), L, L.begin());
WriteList(L);
WriteList(L1);
// результат:
// 9: 8 12 16 20 24 28 32 36 40
// 1: 4

35. Примеры работы с контейнером list (продолжение)

L1 = L;
L1.remove(16);
L.remove(12);
L1.merge(L);
WriteList(L);
WriteList(L1);
// результат:
// 0:
// 18: 4 4 8 8 12 16 20 20 24 24 28 28 32 32 36 36 40 40

36. Примеры работы с контейнером list (продолжение)

bool f(int k) {
return (k%10==2);
}
L1 = L;
L1.remove_if(f);
WriteList(L1);
// результат:
// 8: 4 8 16 20 24 28 36 40

37. Адаптеры

Методы адаптера stack
void push(const T& элемент) заносит новый элемент в стек
void pop()
удаляет элемент из стека
T& top()
обращается к элементу на
вершине стека, может быть
Lvalue
Методы адаптера queue
void push(const T& элемент) заносит новый элемент в
конец очереди
void pop()
удаляет элемент из начала
очереди
T& front()
обращается к элементу в
начале очереди, может быть
Lvalue
T& back()
обращается к элементу в
конце очереди, может быть
Lvalue

38. Адаптеры

По умолчанию приоритет элемента,
помещаемого в priopity_queue – его значение
Методы адаптера priority_queue
void push(const T& элемент) заносит новый элемент в
конец очереди
void pop()
удаляет элемент из начала
очереди
T& top()
обращается к элементу в
начале очереди, может быть
Lvalue
Кроме того, для всех адаптеров определены
методы size() и empty()

39. Пример работы с адаптером priority_queue

enum prty {Low, Normal, High};
struct pq_item {
int I;
prty P;
pq_item (int i, prty p=Normal){I=i; P=p;}
};
class Compare {
public:
bool operator()(pq_item a, pq_item b) {
return a.P<b.P;
}
};

40. Пример работы с адаптером priority_queue (продолжение)

priority_queue <pq_item, deque<pq_item>, Compare> pq;
// описываем очередь
pq.push(pq_item(10));
pq.push(pq_item(14, High));
cout << pq.top().I; // результат – 14
При изменении приоритета элемента, стоящего в голове
очереди, порядок элементов не нарушается!
pq.push(pq_item(10));
pq.push(pq_item(14, High));
pq.push(pq_item(22, High));
pq.top().P = Low;
cout << pq.top().I; // результат – всё равно 14

41. Ассоциативные контейнеры

Использование ассоциативных контейнеров
предполагает, что в хранимых данных выделяется ключ,
который определяет конкретный элемент хранимых
данных, и неключевая информация. Ассоциативные
контейнеры обеспечивают быстрый доступ к данным по
значениям ключа.
Основные операции для ассоциативных контейнеров:
• вставка элемента (трудоёмкость O(log N));
• удаление элемента (трудоёмкость O(log N));
• поиск элемента по ключу (трудоёмкость O(log N));
• последовательный просмотр (в порядке возрастания
ключей, независимо от порядка вставок).

42. Типы ассоциативных контейнеров

map
обеспечивает хранение данных в формате
«ключ-значение» с уникальным значением
ключа
multimap
обеспечивает хранение данных в формате
«ключ-значение» с повторяющимися
значениями ключа
set
обеспечивает хранение только ключевых
данных с уникальным значением ключа
multiset
обеспечивает хранение только ключевых
данных с повторяющимися значениями
ключа
bitset
предназначен для хранения битовых
последовательностей заданной длины

43. Вспомогательный класс pair

template <typename T1, typename T2> class pair
{
T1 first;
T2 second;
};
template <typename T1, typename T2>
pair <T1, T2> make_pair (T1 a, T2 b);

44. Работа с контейнером map

Класс map является шаблоном, зависящим от двух
или трех параметров:
типа ключа;
типа неключевых данных;
функционального класса, определяющего правила
сравнения ключей (если для ключевого класса
определена стандартная операция «меньше», третий
параметр указывать не обязательно).

45. Примеры описаний контейнера map

#include <map>
using namespace std;
map <int, string> m1;
// ключ целое число, неключевые данные – строки
map <int, string, greater <int> > m2;
// использование стандартного функционального
// класса greater <int> позволяет сортировать по
// убыванию
map <int, pair <string, int> > m3;
// неключевые данные – структура из двух полей

46. Пример работы с контейнером map

Задача: Вывести на консоль количество, а также все
элементы контейнера в порядке убывания ключей
typedef map <int, string, greater <int> > m2;
typedef map <int, string, greater <int> > :: iterator
it_m2;
m2 M2;
void WriteMap(m2 L) {
cout << L.size() << ":\n";
for (it_m2 i = L.begin(); i!=L.end(); i++) {
cout << i->first<< " ";
cout.write((i->second).c_str(),
(i->second).size());
cout << "\n";
}
cout << endl;
}

47. Пример работы с контейнером map (продолжение)

int main() {
M2.insert(make_pair(15, "fifteen"));
M2.insert(make_pair(10, "ten"));
M2.insert(make_pair(50, "fifty"));
WriteMap(M2);
return 0;
}

48. Реализация телефонной книги контейнером map

Ключ: информация о владельце контакта (ФИО,
название учреждения, ник)
Неключевые данные: информация о контакте (номер
телефона, e-mail)
typedef map <string, string> phb;
typedef phb::iterator phb_it;
phb Phb;

49. Перегрузка операции индексации для контейнера map

В классе map переопределена операция взятия индекса
T& operator[](const Key&)
так, что с помощью этой операции можно осуществлять
поиск данных по ключу или изменять содержимое
неключевых данных. Эта же операция дает возможность
вставлять новый элемент контейнера
Phb[”kash”] = ”123456789”;
// вставляем новый элемент с ключом ”kash”
// и номером телефона ”123456789”
cout << Phb["kash"] << endl;
// результат – строка ”123456789”
cout << Phb["pupkin"] << endl;
// результат – пустая строка, т.к. ключ не найден.
// Однако в словарь будет вставлен новый элемент!

50. Другие методы ассоциативных контейнеров

Поиск элементов
iterator find(const
Возвращает итератор на элемент,
key_type& ключ)
ключ которого равен заданному, или
end()
iterator
Возвращает итератор на первый
upper_bound(const
элемент, ключ которого больше
key_type& ключ)
заданного, или end()
iterator lower_bound
Возвращает итератор на первый
(const key_type& ключ)
элемент, ключ которого не меньше
заданного, или end()
pair <iterator, iterator> Возвращает пару (lower_bound,
equal_range (const
upper_bound) для заданного ключа
key_type& ключ)
(т. е. интервал, включающий все
элементы с заданным ключом)

51. Другие методы ассоциативных контейнеров (продолжение)

Вставка элементов
pair <iterator, bool>
Вставляет новый элемент в словарь.
insert (value_type&
Поле second результата содержит
элемент)
true при успешной вставке и false – в
противном случае, а поле first –
итератор на добавленный элемент
iterator insert
Вставляет новый элемент в словарь.
(iterator позиция,
Параметр «позиция» показывает, с
value_type& элемент)
какой позиции словаря
предполагается искать место для
вставки
template <class Iter>
Вставляет элементы из другого
void insert (Iter
контейнера
первый, Iter граница)

52. Другие методы ассоциативных контейнеров (продолжение)

Удаление элементов
void erase(iterator
Удаляет элемент по значению
позиция)
итератора.
size_type erase(const
Удаляет элемент по значению ключа;
key_type& ключ)
возвращает количество удаленных
элементов
void erase (iterator
Удаляет группу элементов
первый, iterator
граница)
void clear()
Удаляет все элементы
При удалении одного или нескольких элементов
контейнера все итераторы, связанные с удаленными
элементами, становятся недействительными!

53. Примеры работы с телефонной книгой

1. Найти телефон по фамилии или выдать сообщение об
отсутствии данных.
cout << "Enter name: ";
cin >> N1;
phb_it i = Phb.find(N1);
cout << (i == Phb.end() ? "Record not found" :
(*i).second) << endl;
2. Выдать содержимое телефонной книги с именами,
начинающимися на ”k”.
for (phonebook::iterator i=Phb.lower_bound("k");
i!=Phb.lower_bound("l"); i++)
cout << (*i).first << ":" << (*i).second << endl;

54. Примеры работы с телефонной книгой (продолжение)

3. Вставить новый элемент по паре «ключ – неключевые
данные».
Phb.insert(phb::value_type("kirill","2353555"));
4. Удалить все записи с пустыми номерами телефонов.
phb_it i, j;
for (i=Phb.begin(); i != Phb.end();) {
j=i;
i++;
if ((*j).second.length()==0) {
cout << "Deleting: " << (*j).first << endl;
Phb.erase(j);
}
}

55. Класс multimap

Класс miltimap допускает хранение нескольких
элементов с одинаковыми ключами (допускается также
полное дублирование хранящихся элементов).
Поэтому в этом классе операция доступа по индексу
запрещена, и вместо нее надо пользоваться
итераторами.
typedef multimap <string, string> phb;
typedef phb::iterator phb_it;
phb Phb;

56. Примеры работы с классом multimap

1. Вывести всю хранящуюся информацию для ключа
"kash“.
typedef multimap <string, string> phb;
typedef phb::iterator phb_it;
typedef pair <phb_it, phb_it> phb_int;
phb Phb;
ph_int Ph_int;
ph_it i;
Ph_int = Phb.equal_range("kash");
for (i=Ph_int.first; i != Ph_int.second; i++)
cout << (*i).first << ":" << (*i).second << endl;

57. Примеры работы с классом multimap (продолжение)

2. Исправить адрес электронной почты для одного
элемента ключа "kash“.
typedef multimap <string, string> phb;
typedef phb::iterator phb_it;
typedef pair <phb_it, phb_it> phb_int;
phb Phb;
ph_int Ph_int;
ph_it i;
Ph_int = Phb.equal_range("kash");
for (i=Ph_int.first; i != Ph_int.second; i++)
if ((*i).second =="[email protected]"){
(*i).second = "[email protected]";
break;
}

58. Классы set, multiset

Поскольку в контейнерах типа set и multiset
хранятся только ключи, он может быть описан с
помощью двух, а не трех параметров шаблона.
Соответственно упрощается описание всех
методов. Рассмотрим работу класса set на простых
примерах:
set <int> Set;
Set.insert(4);
Остальные операции над этими контейнерами
аналогичны уже рассмотренным, поэтому не
требуют особого описания.