Стандартная библиотека шаблонов (STL) Контейнеры –структуры для хранения данных. Алгоритмы – шаблонные универсальные функции для обработки данных Итераторы. - презентация

1 Стандартная библиотека шаблонов (STL) Контейнеры –структуры для хранения данных. Алгоритмы – шаблонные универсальные функции для обработки данных Итераторы – указатели для доступа к элементам контейнеров Алгоритм Контейнер Объекты Итераторы

2 Контейнеры Семь основных типов и три производных. Выделяют последовательные – с обычной целочисленной нумерацией и ассоциативные контейнеры – доступ по ключам. Последовательные контейнеры – базовые (векторы, линейные списки, двусторонние очереди) и производные (стеки, очереди, очереди с приоритетами). Ассоциативные контейнеры – множества, множества с дубликатами, словари (отображения), словари с дубликатами.

3 Последовательные контейнеры Вектор – массив произвольного размера. Поддерживает быстрый доступ по номеру элемента, быстрое добавление и удаление в конце. Медленно – добавление и удаление в середине. Список. Быстрые добавление и вставка. Медленный доступ к середине массива. Двусторонняя очередь. Быстрое добавление и удаление в любом конце, доступ по номеру. Медленное добавление и удаление из середины.

4 Векторы Заголовочный файл vector. Описание vector имя; Конструкторы: vector v(10,1); //10 элементов все равные 1 int a [] = {1,2,3,4,5}; vector v(a, a+5); // инициализация из массива a Методы [] –доступ по индексу без проверки тип at(int n) - доступ по индексу c проверкой push_back(x)/ pop_back() – добавление/удаление из конца int size()/max_size()/capacity() – количество/ максимальное количество/размер памяти элементов тип front()/back() – первый/последний элемент вектора bool empty() – пуст ли вектор? reserve(x)/resize(x) – резервирование памяти / изменение размера вектора Сравнение ==, !=,, >=

5 Вставка и удаление в вектор Вставка iterator insert( iterator position, const T& value) void insert( iterator position, int n, const T& value) void insert( iterator position, inpiterator first, inpiterator last) Удаление iterator erase( iterator position) iterator erase( iterator first, iterator last)

6 Список Заголовочный файл list. Описание list имя; Доступ к элементам [] невозможен. push_front(x), front(), pop_front() – добавление, чтение, удаление из начала splice(iterator pos, list &x) – сцепка списков sort() – сортировка списков reverse() - обращение списков merge(list l) – слияние упорядоченных списков unique() – удаление повторений

7 Двусторонняя очередь Заголовочный файл deque. Описание deque имя; Поддерживает [], front(), back(). Память распределяется блоками.

8 Стек, очередь, очередь с приоритетами По умолчанию определены на базе дека stack > s; stack, queue, priority_queue bool empty(); int size(); top() (для очереди front(), back()) push(x) pop()

9 Итераторы Итераторы – объекты, которые используются для доступа к элементам контейнеров. Так как элементы контейнеров не всегда располагаются последовательно, то обычные указатели использовать нельзя. Итераторы можно применять для последовательного продвижения по контейнеру от элемента к элементу. Итераторы можно увеличивать с помощью ++. Значение элемента получается с помощью *.

10 Типы итераторов Прямой - может только увеличиваться. Двунаправленный – может как увеличиваться, так и уменьшаться (- -) С произвольным доступом – может перемещаться на произвольное число элементов (+ n, - k) Входной итератор – указывает на входной поток и может считывать данные в контейнер (используется только для чтения) Выходной итератор- указывает на выходной поток и выводит элементы (используется только для записи)

11 Использование итераторов Итератор для последовательных контейнеров определяется так: тип_контейнера::iterator Пример: вывод списка в прямом и обратном порядке list v(10); list ::iterator i; int t=0; //заполнение списка for (i = v.begin(); i != v.end(); i++ ) *i = t++; // прямой порядок for (list ::iterator i = v.begin(); i != v.end(); i++ ) cout

12 Прямые и обратные итераторы Для прохода от начала до конца контейнера используется прямой итератор. Его значения изменяются от begin() до end(). Для обратного прохода используется обратный итератор. Его значения изменяются от rbegin() до rend().

13 Итераторы вставки. Потоковые операторы back_inserter(контейнер) – вставка в конец front_inserter(контейнер) – вставка в начало inserter(контейнер, итератор) – вставка в позицию итератора Потоковые итераторы используются для ввода и вывода. Итератор вывода ostream_iterator имя (поток, разделитель) Итератор ввода istream_iterator имя (поток) istream_iterator имя () – конец ввода

14 Пример #include using namespace std; int main() { list v; list ::iterator i; int t = 0 ; istream_iterator cin_iter (cin); istream_iterator end_stream; while (cin_iter != end_stream) *(back_inserter(v)) = *cin_iter++; ostream_iterator cout_iter (cout, ";"); for (i = v.begin(); i != v.end(); i++ ) *cout_iter++ = *i; }

15 Ассоциативные контейнеры Ассоциативные контейнеры реализованы на основе сбалансированных деревьев Множество – хранит записи с ключами. Поддерживает быстрые добавление, удаление, поиск. Словарь хранит пары объектов – ключ + любой объект. Контейнеры с дубликатами поддерживают повторяющиеся ключи.

16 Добавление и удаление в множествах insert(x) / erase(x) #include using namespace std; int main() { string names[] = {"Mary", "Elena", "Olga"}; set s (names, names + 3); set ::iterator i; s.insert("Alex"); s.insert("Serg"); s.erase("Olga"); i = s.begin(); while ( i != s.end()) cout

17 Поиск во множествах iterator first (x) - поиск элемента iterator lower_bound(x) – указатель на первый элемент, ключ которого не меньше x iterator upper_bound(x) – указатель на первый элемент, ключ которого больше x int count(x) – количество элементов, равных x pair equal_range(x) – возвращает пару итераторов, определяющих все вхождения элемента с заданным ключом.

18 Пример string name, name1, name2; cin >> name; i = s.find(name); if (i == s.end()) cout > name2; for (i = s.lower_bound(name1); i != s.upper_bound(name2); i++) cout

19 Словари (отображения) В словаре хранятся пары ключ-значение. Определена шаблонная структура pair с операциями сравнения, присваивания. Для доступа к элементам пары используются поля first и second. Для доступа к элементам словаря без дубликатов используется []. Допустимы методы insert, erase, find, lower_bound, upper_bound, count, equal_range.

> num) { in.get(); in >> str; phone[str] = num;} for (book::iterator i = phone.begin()" title="Пример. Телефонный справочник. #include using namespace std; typedef map book; int main() { book phone; ifstream in("phone.txt"); string str; long num; while ( in >> num) { in.get(); in >> str; phone[str] = num;} for (book::iterator i = phone.begin()" class="link_thumb"> 20 Пример. Телефонный справочник. #include using namespace std; typedef map book; int main() { book phone; ifstream in("phone.txt"); string str; long num; while ( in >> num) { in.get(); in >> str; phone[str] = num;} for (book::iterator i = phone.begin(); i!= phone.end(); i++) cout first second str; cout > num) { in.get(); in >> str; phone[str] = num;} for (book::iterator i = phone.begin()"> > num) { in.get(); in >> str; phone[str] = num;} for (book::iterator i = phone.begin(); i!= phone.end(); i++) cout first second str; cout "> > num) { in.get(); in >> str; phone[str] = num;} for (book::iterator i = phone.begin()" title="Пример. Телефонный справочник. #include using namespace std; typedef map book; int main() { book phone; ifstream in("phone.txt"); string str; long num; while ( in >> num) { in.get(); in >> str; phone[str] = num;} for (book::iterator i = phone.begin()">

> num) { in.get(); in >> str; phone.insert(pair (str,num)); } cout" title="Пример с использованием словаря с дубликатами #include using namespace std; typedef multimap book; int main() { book phone; ifstream in("phone.txt"); string str; long num; while ( in >> num) { in.get(); in >> str; phone.insert(pair (str,num)); } cout" class="link_thumb"> 21 Пример с использованием словаря с дубликатами #include using namespace std; typedef multimap book; int main() { book phone; ifstream in("phone.txt"); string str; long num; while ( in >> num) { in.get(); in >> str; phone.insert(pair (str,num)); } cout > str; pair x = phone.equal_range(str); for (book::iterator i = x.first; i!= x.second; i++) cout first second > num) { in.get(); in >> str; phone.insert(pair (str,num)); } cout"> > num) { in.get(); in >> str; phone.insert(pair (str,num)); } cout > str; pair x = phone.equal_range(str); for (book::iterator i = x.first; i!= x.second; i++) cout first second "> > num) { in.get(); in >> str; phone.insert(pair (str,num)); } cout" title="Пример с использованием словаря с дубликатами #include using namespace std; typedef multimap book; int main() { book phone; ifstream in("phone.txt"); string str; long num; while ( in >> num) { in.get(); in >> str; phone.insert(pair (str,num)); } cout">

22 Функциональные объекты (функторы) Для ассоциативных контейнеров можно указать функтор сравнения. Это либо функция, либо функциональный объект. У функционального объекта переопределена операция вызова функции (). Имеются встроенные функциональные объекты типа plus,minus, less, greater и т.д. Пример: string names[] = {"Mary", "Elena", "Olga"}; set > s (names, names + 3); set >::iterator i; for (i = s.begin(); i != s.end(); i++) cout s (names, names + 3); set >::iterator i; for (i = s.begin(); i != s.end(); i++) cout ">

23 Алгоритмы (alghorithm) Алгоритмы – шаблонные функции, которые работают с контейнерам через итераторы. Обычно алгоритм получает в качестве параметров начало и конец обрабатываемой последовательности. Разным алгоритмам требуются разные типы итераторов, например, сортировка требует итератор произвольного доступа (поэтому работает только с векторами и деками), а копирование – прямой итератор.

24 Немодифицирующие операции count (first, last, x) – количество элементов между first и last равных x. find (first, last, x) – поиск x, возвращает итератор, если найден, иначе – конец последовательности search (first1, last1, first2, last2) – поиск в первой последовательности второй. for_each (first, last, f) – выполняет для последовательности функцию f.

25 Модифицирующие операции copy (first, last, out) – копирует последовательность в out. fill (first, last, x) – заполняет последовательность значением x. generate (first, last, gen) – заполняет последовательность значениями, сгенерированными gen remove (first, last, x) – удаляет элементы, равные х, из последовательности. Алгоритм возвращает границу конца последовательности.

26 Алгоритмы, связанные с сортировкой binary_search(first,last,x) – двоичный поиск х, возвращает логическое значение. nth_element(first, nth, last) – переставляет элементы так, что левее элемента nth будут меньшие его, правее – большие partial_sort(first, middle,last) – частичная сортировка первых элементов от first до middle. sort(first, last) – сортировка за N*logN stable_sort(first, last) – устойчивая сортировка за N(logn) 2

27 Множества includes(first1,last1,first2,last2) – проверяет вхождение второго множества в первое set_intersection (first1,last1,first2,last2, out) – пересечение множеств set_difference (first1,last1,first2,last2, out) – разность множеств set_union (first1,last1,first2,last2, out) – объединение множеств

28 Пример. Обработка массива с помощью алгоритмов #include using namespace std; void show (int x) {cout