Использование STL

Преимущества STL увеличение скорости написания программ гарантированное отсутствие ошибок универсальность (независимость от типов данных) оптимальная асимптотика и использование памяти

Недостатки STL сложность отладки «непредсказуемое» поведение «локальность» - сложность обращения к глобальным переменным

Итератор Объект, обладающий следующими операторами: ++ - переход на следующий элемент -- - переходит на предыдущий элемент * - разыменование, получение значения элемента

Random Access Iterator Итератор, позволяющий переходить сразу на N элементов. Поддерживает операторы += и -=.

Алгоритмы STL

Алгоритмы #include Большинство STL-алгоритмов позволяют находить какие-либо характеристики множества объектов одного типа, обычно задаваемого двумя итераторами.

Алгоритм count count(it1, it2, value); a[5] = {1, 2, 8, 2, 2}; count(a, a + 5, 2); // 3 count(a, a + 5, 8); // 1 count(a, a + 4, 2); // 2

Алгоритм find find(it1, it2, value); a[5] = {6, 2, 8, 1, 3}; find(a, a + 5, 2); // &a[1] find(a, a + 5, 4); // &a[5] find(a, a + 5, 1) - a; // = 3

Алгоритмы min_element/max_element min_element(it1, it2); max_element(it1, it2); a[5] = {6, 2, 8, 1, 3}; min_element(a, a + 5); // &a[3] max_element(a, a + 5); // &a[2] min_element(a, a + 5) - a; // = 3 max_element(a, a + 5) - a; // = 2 *min_element(a, a + 5); // = 1 *max_element(a, a + 5); // = 8

Алгоритм binary_search binary_search(it1, it2, value); a[5] = {1, 2, 8, 17, 239}; binary_search(a, a + 5, 17); /* true */ binary_search(a, a + 5, 19); /* false */

Алгоритмы lower_bound/upper_bound lower_bound(it1, it2, value); upper_bound(it1, it2, value); a[5] = {1, 2, 2, 6, 8}; lower_bound(a, a + 5, 1); // &a[0] upper_bound(a, a + 5, 1); // &a[1] lower_bound(a, a + 5, 2); // &a[1] upper_bound(a, a + 5, 2); // &a[3]

Алгоритмы sort/stable_sort sort(it1, it2); a[5] = {6, 2, 8, 1, 3}; sort(a, a + 5); /* a[5] = {1, 2, 3, 6, 8} */

Алгоритм replace replace(it1, it2, value1, value2); a[5] = {1, 2, 2, 6, 8}; replace(a, a + 5, 2, 4); /* a[5] = {1, 4, 4, 6, 8} */

Алгоритм reverse reverse(it1, it2); a[5] = {6, 2, 8, 1, 3}; reverse(a, a + 5); // a[5] = {3, 1, 8, 2, 6}

Алгоритм merge merge(it11, it12, it21, it22, out_it) a[5] = {1, 2, 2, 6, 8}; b[3] = {2, 3, 9}; *c; merge(a, a + 5, b, b + 3, c); /* &c[8], c[8] = {1, 2, 2, 2, 3, 6, 8, 9} */

Алгоритм unique unique(it1, it2) a[5] = {1, 2, 2, 6, 6}; unique(a, a + 5); /* &a[3], a[3] = {1, 2, 6} */

Алгоритм random_shuffle random_shuffle(it1, it2) a[5] = {6, 5, 1, 4, 3}; random_shuffle(a, a + 5); /* возможный результат a[5] = {1, 5, 6, 3, 4}; */

Алгоритм next_permutation next_permutation(it1, it2) a[5] = {6, 1, 1, 5, 3}; next_permutation(a, a + 5); /* true, a[5] = {6, 1, 3, 1, 5} */ a[5] = {6, 5, 3, 1, 1}; next_permutation(a, a + 5); /* false, a[5] = {6, 5, 3, 1, 1} */

Алгоритм prev_permutation prev_permutation(it1, it2) Аналогичен next_permutation, но задает на множестве лексикографически предыдущую перестановку.

Класс pair

pair Объявление: pair var; Содержит 2 поля: var.first - первый элемент пары var.second - второй элемент пары

pair Преимущества: универсальность (подходит для любых классов) передача одного параметра вместо двух в функциях стандартный компаратор: сравнение сначала по первому элементу, в случае равенства - по второму функция make_pair, позволяющая не указывать типы элементов в паре

pair int x, y; double w;... pair coordinates = pair (x, y); pair coordinates = make_pair(x, y); pair > point = make_pair(w, make_pair(x, y));

Контейнеры STL

Контейнеры позволяют хранить в себе множества элементов одного типа и выполнять какие-либо операции над ними, итерировать и т.п. При создании контейнера необходимо указывать, какого типа элементы он будет в себе хранить.

Контейнеры STL size() - возвращает размер контейнера (количество элементов в нем) empty() - проверяет, является ли контейнер пустым. clear() – очищает контейнер методы добавления элементов в контейнер (различаются между разными контейнерами), методы удаления элементов, итераторы

Контейнер vector #include "Динамический массив", хранит добавляемые элементы в виде массива (в порядке добавления их в контейнер).

Контейнер vector push_back(value) - добавить элемент value в конец вектора pop_back() - удалить последний элемент из вектора capacity() - текущий размер выделенной памяти resize(size) - изменить размер до заданного значения (size) reserve(cap) - зарезервировать в векторе указанное число элементов (с учетом уже имеющихся

Контейнер vector begin() - итератор, соответствующий первому элементу end() - итератор, соответствующий позиции после последнего элемента

Контейнер vector vector v; v.push_back(100); /* вектор содержит один элемент – 100 */ v.push_back(500); /* вектор содержит два элемента и 500 */ *v.begin(); /* 100 */ v.size(); /* 2 */

Контейнер vector Обход вектора через индекс элемента: vector v;... for (int i = 0; i < v.size(); i++) { int x = v[i];... }

Контейнер vector Обход вектора через итераторы: for (vector ::iterator it = v.begin(); it != v.end(); it++) { int x = *it;... }

Контейнер vector Применение алгоритмов к множеству элементов вектора. vector v;... sort(v.begin(), v.end()); int c = count(v.begin(), v.end(), 100ll);

Использование vector в задачах а). Построение списков смежности vector v[MAXN];... cin >> n; for (int i = 0; i < M; i++) { int x, y; cin >> x >> y; v[x].push_back(y); v[y].push_back(x); }

Использование vector в задачах б). "Отложенный" вывод. vector ans;... ans.push_back(value);... reverse(all(ans)); for (int i = 0; i < ans.size(); i++) cout

Использование vector в задачах в). Временное хранилище. int f(int x) {... vector tmp;... tmp.push_back(h[y]);... sort(tmp.begin(), tmp.end()); int sum = 0; for (int i = 0; i < min(k, tmp.size()); i++) sum += tmp[i]; return sum; }

Использование vector в задачах г). Простые преобразования множества элементов. vector v;... v.push_back(x);... sort(v.begin(), v.end()); v.resize(unique(v.begin(), v.end()) - v.begin());...

Контейнер queue #include front() - первый элемент. pop() - удаление первого элемента. push(value) - добавление элемента value в конец очереди

Использование queue в задачах a). Поиск в ширину... int x, y; q.push(mp(x, y)); while (!q.empty()) { process(q.front()); q.pop(); }...

Контейнер priority_queue #include top() - первый (наибольший) элемент. pop() - удаление первого элемента. push(value) - добавление элемента value в конец очереди

Использование priority_queue в задачах а). Алгоритм дейкстры... int x; q.push(mp(0, x)); while (!q.empty()) { process(q.top()); q.pop(); }...

Использование priority_queue в задачах void process(pair p) { int d = -p.first; int x = p.second; if (ans[x] != d) return; for (int i = 0; i < v[i].size(); i++) { int y = v[x][i].first; int nd = d + v[x][i].second; if (ans[y] > nd) { q.push(make_pair(-nd, y)); ans[y] = nd; } }}

Контейнер set #include insert(value) erase(value) erase(it) lower_bound(value) upper_bound(value); find(value)

Использование set в задачах а). set как online-множество уникальных элементов. На плоскости добавляются по одной N точек, нужно указать, сколько среди них различных после каждого шага.

Использование set в задачах б). set как динамическое множество. Задача построения наидлиннейшей последовательности, не содержащей одинаковых соседних элементов.

Использование set в задачах в). set как связный список. Задача - раскраска отрезка. Даны N запросов на перекрашивание подотрезка в определенный цвет. Необходимо определить итоговые цвета клеток отрезка.

Использование set в задачах г). set как очередь. Алгоритм Дейкстры.

Контейнер multiset #include Метод erase(value) удаляет все значения value из сета. Метод erase(it) удаляет только указанный итератор.

Использование multiset в задачах а). Поиск максимума на отрезках заданной длины. Дана последовательность длины N. Для каждых M подряд идущих элементов нужно найти максимум среди них.

Ссылки Удобный справочник по C++: Статья на topcoder.com: dule=Static&d1=tutorials&d2=stand ardTemplateLibrary dule=Static&d1=tutorials&d2=stand ardTemplateLibrary2