Шаблоны STL

STL (англ. Standard Template Library -Стандартная библиотека шаблонов). Стандартная библиотека шаблонов до включения в стандарт C++ была сторонней разработкой, в начале — фирмы HP, а затем SGI. Стандарт языка не называет её «STL», так как эта библиотека стала неотъемлемой частью языка, однако многие люди до сих пор используют это название, чтобы отличать её от остальной части стандартной библиотеки (потоки ввода/вывода (iostream), подраздел Си и др.).

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

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

Контейнер (container) - Основа библиотеки STL. Контейнер служат для хранения данных, управления ими и размещения. Иными словами, это объект, предназначенный для хранения и использования других элементов.
Алгоритм (algorithm) - специальная функция для работы с данными, содержащимися в контейнере.
Итератор (iterator) - специальный указатель, который позволяет алгоритмам перемещаться по данным конкретного контейнера. Итератор прослойка между контейнерами и алгоритмами. Посредством итератора мы удаляемся от понятия типа контейнера, т.е. к разным контейнерам можно применять одинаковые алгоритмы.
Функторы (functor) - Функтор передается алгоритмам для дальнейшего использования. При помощи функтора заполнить вектор числами Фибоначчи. Функторы (иначе говоря, функциональные объекты) - это специализированный вид классов, которые включают в себя перегруженный оператор вызова функции. Как правило, функтор можно применить везде, где требуется функция. Проще говоря, когда должна быть вызвана функция, вызывается перегруженный оператор вызова функции.(оператор "круглые скобки"). Основным отличием функтора от обычной функции, является возможность хранения некоторого значения по принципу статических переменных.

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

Аллокатор - распределитель памяти. Такой распределитель памяти имеется у каждого конкретного контейнера. Данная конструкция просто-напросто управляет процессом выделения памяти для контейнера. Следует отметить, что по умолчанию распределителем памяти является объект класса allocator. Однако, можно определить свой собственный распределитель.
Предикат - функция нестандартного типа, используемая в контейнере. Предикат бывает унарный и бинарный. Может возвращать логическое значение (истину либо ложь). Часто используется при сортировке.

Справочники по STL

Официальный справочники по STL в Linux

# apt install stl-manual
$ firefox file:///usr/share/doc/stl-manual/html/index.html

Контейнеры

STL: Класс auto_ptr C++ (automatic pointer - автоматический указатель)
STL: Класс string шаблон STL языка C++
Класс vector - заменяет динамический массив.
Класс list - рассчитан на поиск. К данным нельзя обратиться через [], только через итератор.
Контейнеры STL: Класс map - быстрый поиск значений по ключу. Map будет игнорировать вставку если пара уже существует. Поддерживает ассоциативный контейнер (т.е. ключ может быть строкой)
Класс multimap - поддерживает повторяющиеся ключи в отличии от map

Алгоритмы

В библиотеке STL существуют функции, которые выполняют различные стандартные действия. Действия эти, например, - поиск, преобразование, сортировка, копирование и так далее. Эти функции называются алгоритмами. В качестве параметрами для алгоритмов принято использовать итераторы.

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

Все алгоритмы делятся на две группы: те, которые изменяют данные, и те, которые их не изменяют. Каждый алгоритм представляет собой шаблон функции или набор шаблонов функций. То есть, любой алгоритм может работать с абсолютно разными контейнерами. Алгоритмы, возвращающие итератор, обычно, для сообщения о неудаче используют конец входной последовательности. Алгоритмы не выполняют проверки диапазона на их входе и выходе.

Если алгоритм возвращает итератор, это будет итератор того же типа, что был на входе в алгоритм.

Алгоритмы определены в заголовочном файле <algorithm>. Приведем наиболее используемые алгоритмы библиотеки STL.

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

for_earch() - выполняет операции для каждого элемента последовательности find() - находит первое вхождение значения в последовательность find_if() - находит первое соответствие предикату в последовательности count() - подсчитывает количество вхождений значения в последовательность count_if() - подсчитывает количество выполнений предиката в последовательности search() - находит первое вхождение последовательности как подпоследовательности search_n()- находит в последовательности подпоследовательность, состоящую из n повторений и возвращает её первое вхождение.

Модифицирующие операции.

copy() - копирует последовательность, начиная с первого элемента swap() - меняет местами два элемента replace() - заменяет элементы с указанным значением replace_if() - заменяет элементы при выполнении предиката replace_copy() - копирует последовательность, заменяя элементы с указанным значением replace_copy_if() - копирует последовательность, заменяя элементы при выполнении предиката fill() - заменяет все элементы данным значением remove() - удаляет элементы с данным значением remove_if() - удаляет элементы при выполнении предиката remove_copy() - копирует последовательность, удаляя элементы с указанным значением remove_copy_if() - копирует последовательность, удаляя элементы при выполнении предиката reverse() - меняет порядок следования элементов на обратный random_shuffle() - перемещает элементы согласно случайному равномерному распределению ("тасует" последовательность) transform() - выполняет заданную операцию над каждым элементом последовательности unique() - удаляет равные соседние элементы unique_copy() - копирует последовательность, удаляя равные соседние элементы

Сортировка.

sort() - сортирует последовательность с хорошей средней эффективностью partial_sort() - сортирует часть последовательности stable_sort() - сортирует последовательность, сохраняя порядок следования равных элементов lower_bound() - находит первый элемент, меньший чем заданное значение upper_bound() - находит первый элемент, больший чем заданное значение binary_search() - определяет, есть ли данный элемент в отсортированной последовательности merge() - сливает две отсортированные последовательности

Работа с множествами.

includes() - проверка на вхождение set_union() - объединение множеств set_intersection() - пересечение множеств set_difference() - разность множеств

Минимумы и максимумы.

min() - меньшее из двух max() - большее из двух min_element() - наименьшее значение в последовательности max_element() - наибольшее значение в последовательности Перестановки. next_permutation() - следующая перестановка в лексикографическом порядке prev_permutation() - предыдущая перестановка в лексикографическом порядке

Предикаты

Зачастую, вам могут понадобиться специальные средства, которые принимают решения в зависимости от ситуации и координируют выполнение какой-либо вашей программы. Обычно для этих целей мы используем логические выражения языка программирования. Однако, в STL принято решать данную проблему иным способом. А именно, создавать предикаты.

Предикат - специальная функция, которая возвращает логическое значение (true либо false).

Наверное, вы уже догадались, что создать предикат достаточно легко - нужно просто написать функцию которая возвращает тип bool. Рассмотрим пример. Попробуем создать предикат, определяющий четность числа. Если число окажется четным, предикат будет возвращать true.

Используем следующий порядок действий:

Четность определяется получением остатка от деления на 2.
Затем, заполняется контейнер-список значениями от 1 до 10. (для этого вызывается метод push_back(), который добавляет значение в конец списка)
Затем значения выводятся на экран.
Далее осуществляется поиск и выделение всех четных значений.

Эту задачу решает алгоритм remove_if. Обратите внимания, что многие алгоритмы, оканчивающиеся на _if, в качестве последнего параметра используют предикаты. Алгоритм remove_if сдвигает все подходящие значения в начало контейнера и возвращает итератор, который указывает на элемент, следующий за удаляемыми значениями. По этой причине, мы будем считать, что начиная с адреса, на который ссылается возвращаемый итератор, и до конца области данных контейнера располагаются неудаленные значения, для которых предикат вернул false. Здесь, в нашем примере, мы используем данную особенность следующим образом: все четные значения выводятся на экран (для этого мы копируем их в поток вывода, передав потоковому итератору пару итераторов, которые описывают область удаленных значений.)

#include <algorithm>
#include <iostream>
#include <list>
using namespace std;
 
// предикат
bool isEven(int num)
{
  return bool(num % 2); 
}
 
void main()
{
    list<int> l;
	list<int>::iterator t;
 
    for(int i=1; i<=10; i++)
        l.push_back(i);
 
	copy(l.begin(), l.end(), ostream_iterator<int>(cout," "));
	cout<<"\n\n";
	t=remove_if(l.begin(), l.end(), isEven);
	copy(l.begin(), t, ostream_iterator<int>(cout," "));
}