Стандартная библиотека шаблонов (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

, vector > 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 <<*i <<" ";
// обратный порядок
for (list::reverse_iterator i = v.rbegin();
i != v.rend(); i++ ) cout <<*i <<" ";


Слайд 12Прямые и обратные итераторы
Для прохода от начала до конца контейнера используется

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

Слайд 13Итераторы вставки. Потоковые операторы
back_inserter(контейнер) – вставка в конец
front_inserter(контейнер) – вставка в

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


Слайд 14Пример
#include
#include
#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
#include
#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 << *i++ << endl;
}


Слайд 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 << "not found"; else cout << *i << " found";
cin >> name1 >> name2;
for (i = s.lower_bound(name1); i != s.upper_bound(name2); i++)
cout << *i <<" ";


Слайд 19Словари (отображения)
В словаре хранятся пары ключ-значение. Определена шаблонная структура
pair

с операциями сравнения, присваивания. Для доступа к элементам пары используются поля first и second.
Для доступа к элементам словаря без дубликатов используется []. Допустимы методы insert, erase, find, lower_bound, upper_bound, count, equal_range.

Слайд 20Пример. Телефонный справочник.
#include
#include
#include
#include
using namespace std;
typedef map

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]; }

> num) { in.get(); in >> str; phone[str] = num;} for (book::iterator i = phone.begin(); i!= phone.end(); i++) cout first ">

Слайд 21Пример с использованием словаря с дубликатами
#include
#include
#include
#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 << "Enter name "; cin >> str;
pair x = phone.equal_range(str);
for (book::iterator i = x.first; i!= x.second; i++)
cout << i->first <<" "<< i->second << endl;
}

> 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 ">

Слайд 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 << *i << endl;

Слайд 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
#include
#include
using namespace std;
void

show (int x) {cout << x << " "; }
class gen
{ public:
int operator()() { return rand(); }
};
int main()
{ ostream_iterator 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);
}

Похожие презентации

Шаблон презентации 256
Кошки – мышки(вариант 2) 239
Я люблю лето 262
Проблема Сайты финансовых организаций предлагают шаблоны документов для загрузки, заполнения, печати и возврата в банк: заявления; соглашения; договоры; 238
Многообразие и свойства живых организмов. Развитие биологии в додарвиновский период. Вариант 1 332
Подзаголовок слайда 258

Обратная связь

Если не удалось найти и скачать презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

Это сайт презентаций, докладов, проектов, шаблонов в формате PowerPoint. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами с другими пользователями.

Для правообладателей

Яндекс.Метрика