'

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

Понравилась презентация – покажи это...





Слайд 0

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


Слайд 1

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


Слайд 2

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


Слайд 3

Векторы Заголовочный файл vector. Описание vector <тип> имя; Конструкторы: vector <int> v(10,1); //10 элементов все равные 1 int a [] = {1,2,3,4,5}; vector <int> 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) – резервирование памяти / изменение размера вектора Сравнение ==, !=, <, <=, >, >=


Слайд 4

Вставка и удаление в вектор Вставка 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)


Слайд 5

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


Слайд 6

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


Слайд 7

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


Слайд 8

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


Слайд 9

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


Слайд 10

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


Слайд 11

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


Слайд 12

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


Слайд 13

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


Слайд 14

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


Слайд 15

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


Слайд 16

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


Слайд 17

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


Слайд 18

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


Слайд 19

Пример. Телефонный справочник. #include <map> #include <fstream> #include <iostream> #include <string> using namespace std; typedef map <string, long> 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 << i->first <<" "<< i->second << endl; cout << "Enter name "; cin >> str; cout << phone[str]; }


Слайд 20

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


Слайд 21

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


Слайд 22

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


Слайд 23

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


Слайд 24

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


Слайд 25

Алгоритмы, связанные с сортировкой 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


Слайд 26

Множества 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) – объединение множеств


Слайд 27

Пример. Обработка массива с помощью алгоритмов #include <algorithm> #include <iterator> #include <iostream> using namespace std; void show (int x) {cout << x << " "; } class gen { public: int operator()() { return rand(); } }; int main() { ostream_iterator <int> cout_iter (cout, ";"); int v[10]; generate(v,v+10,gen()); for_each(v, v + 10, show); cout << endl; partial_sort(v, v + 7, v + 10); copy (v, v + 10, cout_iter); cout << endl; sort(v, v + 10); copy (v, v + 10, cout_iter); }


×

HTML:





Ссылка: