контейнеры STL презентация

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примеры работы с последовательными контейнерами
vector
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

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

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

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

Примеры управления распределением памяти
vector
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

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

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

Особенности работы с контейнером list
Контейнер List обладает дополнительными методами:

Особенности работы с контейнером list
Контейнер List обладает дополнительными методами:

Примеры работы с контейнером list
typedef list
:: iterator it_lint;
typedef list
:: reverse_iterator rit_lint;
list
L(10), L1;
void WriteList(list
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

Примеры работы с контейнером 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

Примеры работы с контейнером 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

Примеры работы с контейнером 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

Адаптеры

Адаптеры
По умолчанию приоритет элемента, помещаемого в priopity_queue – его значение
Кроме того, для всех адаптеров определены методы size() и empty()

Пример работы с адаптером 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
}
};

Пример работы с адаптером priority_queue (продолжение)
priority_queue
, 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

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

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

Вспомогательный класс pair
template
class pair
{
T1 first;
T2 second;
};
template
pair
make_pair (T1 a, T2 b);

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

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

Пример работы с контейнером map
Задача: Вывести на консоль количество, а также все элементы контейнера в порядке убывания ключей
typedef map
> m2;
typedef map
> :: 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;
}

Пример работы с контейнером 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;
}

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

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

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

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

Другие методы ассоциативных контейнеров (продолжение)
При удалении одного или нескольких элементов контейнера все итераторы, связанные с удаленными элементами, становятся недействительными!

Примеры работы с телефонной книгой
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;

Примеры работы с телефонной книгой (продолжение)
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);
}
}

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

Примеры работы с классом multimap
1. Вывести всю хранящуюся информацию для ключа "kash“.
typedef multimap
phb;
typedef phb::iterator phb_it;
typedef pair
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;

Примеры работы с классом multimap (продолжение)
2. Исправить адрес электронной почты для одного элемента ключа "kash“.
typedef multimap
phb;
typedef phb::iterator phb_it;
typedef pair
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 =="[e-mail]"){
(*i).second = "[e-mail]";
break;
}