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

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

Контейнеры –структуры для хранения данных .

Алгоритмы – шаблонные универсальные функции для обработки данных

Итераторы – указатели для доступа к элементам контейнеров

Контейнер

Алгоритм

Итераторы

Объекты

Семь основных типов и три производных.

Выделяют последовательные – с обычной целочисленной нумерацией и ассоциативные контейнеры – доступ по ключам.

Последовательные контейнеры – базовые (векторы, линейные списки, двусторонние очереди) и производные (стеки, очереди, очереди с приоритетами).

Ассоциативные контейнеры – множества, множества с дубликатами, словари (отображения), словари с дубликатами.

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

Список. Быстрые добавление и вставка. Медленный доступ к середине массива.

Двусторонняя очередь. Быстрое добавление и удаление в любом конце, доступ по номеру. Медленное добавление и удаление из середины.

= " width="640"

Заголовочный файл 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) – резервирование памяти / изменение размера вектора

Сравнение ==, !=, , =

Вставка

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)

Заголовочный файл list. Описание

list имя ;

Доступ к элементам [] невозможен.

push_front(x), front(), pop_front() – добавление, чтение, удаление из начала

splice(iterator pos, list&x) – сцепка списков

sort() – сортировка списков

reverse() - обращение списков

merge(list l) – слияние упорядоченных списков

unique() – удаление повторений

Заголовочный файл deque. Описание

deque имя ;

Поддерживает [] , front(), back().

Память распределяется блоками.

s; stack, queue, priority_queue bool empty(); int size(); top() (для очереди front(), back()) push(x) pop() " width="640"

Стек, очередь , очередь с приоритетами

По умолчанию определены на базе дека

stack s;

stack, queue, priority_queue

bool empty();

int size();

top() (для очереди front(), back())

push(x)

pop()

Итераторы – объекты, которые используются для доступа к элементам контейнеров.

Так как элементы контейнеров не всегда располагаются последовательно, то обычные указатели использовать нельзя.

Итераторы можно применять для последовательного продвижения по контейнеру от элемента к элементу. Итераторы можно увеличивать с помощью ++.

Значение элемента получается с помощью *.

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

Итератор для последовательных контейнеров определяется так: тип_контейнера ::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

// обратный порядок

for (list::reverse_iterator i = v.rbegin();

i != v.rend(); i++ ) cout

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

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

back_inserter (контейнер) – вставка в конец

front_inserter (контейнер) – вставка в начало

inserter( контейнер, итератор) – вставка в позицию итератора

Потоковые итераторы используются для ввода и вывода.

Итератор вывода

ostream_iterator имя (поток, разделитель)

Итератор ввода

istream_iterator имя (поток)

istream_iterator имя () – конец ввода

#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;

}

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

}

iterator first (x) - поиск элемента

iterator lower_bound(x) – указатель на первый элемент, ключ которого не меньше x

iterator upper_bound(x) – указатель на первый элемент, ключ которого больше x

int count(x) – количество элементов, равных x

pair equal_range(x) – возвращает пару итераторов, определяющих все вхождения элемента с заданным ключом.

name; i = s.find(name); if (i == s.end()) cout cin name1 name2; for (i = s.lower_bound(name1); i != s.upper_bound(name2); i++) cout " width="640"

string name, name1, name2;

cin name;

i = s.find(name);

if (i == s.end()) cout

cin name1 name2;

for (i = s.lower_bound(name1); i != s.upper_bound(name2); i++)

cout

В словаре хранятся пары ключ-значение. Определена шаблонная структура

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(); i!= phone.end(); i++) cout first second cout str; cout " width="640"

#include

#include

#include

#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

cout str;

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 } " width="640"

#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 str;

pair x = phone.equal_range(str);

for (book::iterator i = x.first; i!= x.second; i++)

cout first second

}

s (names, names + 3); set ::iterator i; for (i = s.begin(); i != s.end() ; i++ ) cout " width="640"

Для ассоциативных контейнеров можно указать функтор сравнения. Это либо функция, либо функциональный объект.

У функционального объекта переопределена операция вызова функции ().

Имеются встроенные функциональные объекты типа plus,minus, less, greater и т.д.

Пример :

s tring names[] = {"Mary", "Elena", "Olga"};

set s

(names, names + 3);

set ::iterator i;

for (i = s.begin(); i != s.end() ; i++ )

cout

Алгоритмы ( alghorithm)

Немодифицирующие операции

count (first, last, x) – количество элементов между first и last равных x.

find (first, last, x) – поиск x, возвращает итератор, если найден, иначе – конец последовательности

search (first1, last1, first2, last2) – поиск в первой последовательности второй.

for_each (first, last, f) – выполняет для последовательности функцию f.

copy (first, last, out) – копирует последовательность в out.

fill (first, last, x) – заполняет последовательность значением x.

generate (first, last, gen) – заполняет последовательность значениями, сгенерированными gen

remove (first, last, x) – удаляет элементы, равные х, из последовательности. Алгоритм возвращает границу конца последовательности.

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

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

Пример. Обработка массива с помощью алгоритмов

#include

#include

#include

using namespace std;

void show (int x) {cout

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

partial_sort(v, v + 7, v + 10);

copy (v, v + 10, cout_iter); cout

sort(v, v + 10);

copy (v, v + 10, cout_iter);

}