Библиотека стандартных шаблонов STL (Standard Template Library). Общие понятия. Контейнеры. Алгоритмы. Итераторы. Функторы

Данная тема является началом изучения библиотеки STL языка C++.

Содержание

Поиск на других ресурсах:

1. Библиотека STL. Общие сведения

В языке C ++ был разработан мощный набор инструментов для создания разнообразных программ — библиотека стандартных шаблонов (Standard Template Library, STL). Эта библиотека, фактически, является неотъемлемой составляющей языка C++, что является большим достижением ее разработчиков. Библиотека STL включена в стандарт языка C++ и содержит универсальные шаблонные классы и функции, которые реализуют широкий спектр алгоритмов и структур данных. Эти средства программирования можно применять практически к любым типам данных.

Различают следующие основные составляющие (компоненты) библиотеки STL:

контейнеры (container)
алгоритмы (algorithm)
итераторы (iterator)
функциональные объекты или функторы (functor).

Использование и сочетание этих составляющих позволяет программировать решения очень широкого круга задач программирования.

⇑

2. Контейнеры. Общие сведения. Перечень

В программировании контейнер — это объект, который сохраняет другие объекты внутри себя. Объекты, хранящиеся в контейнерах, могут быть как базовых (примитивных) типов так и экземплярами классов с соответствующим необходимым функционалом.

В библиотеке STL реализованы следующие контейнеры:

bitset — набор битов;
deque — двухсторонняя очередь;
list — линейный список;
map — ассоциативный контейнер, построенный по принципу key:value, в котором каждому ключу key соответствует значение value;
multimap — ассоциативный контейнер, в котором одному значению (key) соответствует несколько значений (value1, value2, …, valueN);
multiset — множество, в котором один и тот же элемент может встречаться несколько раз;
priority_queue — очередь с приоритетами;
queue — очередь;
set — множество, в котором каждый элемент встречается только один раз;
stack — стек;
vector — динамический массив.

⇑

3. Алгоритмы. Общие сведения

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

Для доступа к алгоритмам, нужно подключить соответствующую библиотеку

#include <algorithm>

Все алгоритмы являются шаблонными функциями. Они могут быть применены к любому типу контейнера. Ниже приведен перечень алгоритмов библиотеки STL:

adjacent_find — осуществляет поиск пары соседних элементов, которые совпадают между собой;
binary_search — выполняет бинарный поиск в упорядоченной последовательности;
copy — копирует одну последовательность в другую;
copy_backward — делает то же, что и copy, только результирующая последовательность записывается в обратном порядке;
count — подсчитывает количество вхождений заданного элемента в последовательности;
count_if — вычисляет количество вхождений элемента в последовательности, соответствующей заданному условию;
equal — определяет, совпадают ли элементы двух диапазонов;
equal_range — возвращает диапазон, который допускает вставку элементов без нарушения порядка;
fill, fill_n — заполняют диапазон нужными значениями;
find — осуществляет поиск элемента в заданной последовательности, возвращает позицию (итератор) первого вхождения элемента в последовательности;
find_end — осуществляет поиск последнего вхождения подпоследовательности, содержащийся в заданном диапазоне;
find_first_of — выполняет поиск первого элемента подпоследовательности, который совпадает с любым элементом другой подпоследовательности;
find_if — находит первый элемент последовательности, который совпадает с элементом с другой последовательности;
for_each — применяет указанную функцию к заданному диапазону элементов;
generate, generate_n — присваивают элементам диапазона значения, возвращаемые функцией-генератором;
include — определяет, содержит ли одна последовательность другую;
inplace_merge — объединяет два диапазона;
iter_swap — осуществляет обмен местами двух значений, на которые указывают аргументы;
lexicographical_compare — осуществляет лексикографическое сравнение двух последовательностей;
lower_bound — определяет первый элемент последовательности, который не меньше заданного значения;
make_heap — на основе заданной последовательности создает «кучу»;
max — возвращает максимум из двух значений;
max_element — возвращает позицию (итератор), которая установлена на максимальный элемент последовательности;
merge — объединяет две упорядоченные последовательности. Результат записывается в третью последовательность;
min — из двух значений возвращает минимальное;
min_element — возвращает позицию (итератор), которая установлена на минимальный элемент последовательности;
mismatch — для двух заданных последовательностей находит первое несовпадение;
next_permutation — формирует следующую перестановку элементов последовательности;
nth_element — упорядочивает последовательность таким образом, что все элементы, которые меньше заданного элемента, размещаются перед этим элементом в последовательности;
partial_sort — выполняет сортировку элементов в заданном диапазоне;
partial_sort_copy — упорядочивает элементы последовательности в заданном диапазоне, затем копирует в результирующую последовательность отсортированные элементы;
partition — упорядочивает последовательность так, чтобы все элементы, которые соответствуют заданному условию, размещались перед всеми другими элементами этой последовательности;
pop_heap — меняет местами первый и предпоследний элементы и перестраивает «кучу»;
prev_permutation — воспроизводит предыдущую перестановку, состоящую из элементов последовательности;
push_heap — заталкивает элемент в конец кучи;
random_shuffle — меняет последовательность в заданном диапазоне;
remove — удаляет из указанной последовательности элементы, которые имеют определенное значение;
remove_if — удаляет из указанной последовательности элементы по заданному предикату;
remove_copy — копирует из указанной последовательности элементы, имеющие определенное значение, в заданную последовательность;
remove_copy_if — копирует из указанной последовательности элементы в другую область на основе заданного предиката;
replace — заменяет элементы заданного диапазона из одного значения на другое;
replace_if — заменяет элементы заданного диапазона на основе предиката;
replace_copy_if — копирует элементы заданной последовательности в другую область с заменой одного значения на другое;
replace_copy — копирует элементы заданного диапазона в другую последовательность, заменяя элементы на основе заданного предиката другим значением;
reverse — изменяет порядок элементов последовательности на противоположный в пределах заданного диапазона;
reverse_copy — изменяет порядок элементов в последовательности на противоположный и результат записывает в другую последовательность;
rotate — выполняет циклический сдвиг влево элементов последовательности в заданных пределах;
rotate_copy — выполняет циклический сдвиг влево элементов последовательности, результат помещает в другую последовательность;
search — выполняет поиск подпоследовательности в последовательности;
search_n — находит n-е вхождение заданного элемента в последовательности;
set_difference — для двух заданных последовательностей создает последовательность, содержащую несовпадающие элементы (разность множеств);
set_intersection — для двух заданных последовательностей создает последовательность, содержащую совпадающие элементы (пересечение множеств);
set_symmetric_difference — создает последовательность, которая является симметричной разности двух последовательностей;
set_union — создает последовательность, которая является объединением двух последовательностей;
sort — упорядочивает последовательность в заданном диапазоне;
sort_heap — упорядочивает «кучу» внутри заданного диапазона;
stable_partition — упорядочивает последовательность в заданных пределах таким образом, чтобы все элементы, которые удовлетворяют заданному условию, предшествовали всем другим элементам. Разбивка последовательности фиксируется;
stable_sort — упорядочивает последовательность в заданных пределах таким образом, что равные элементы не меняют свои места;
swap — меняет местами значения, заданные ссылками;
swap_ranges — меняет местами элементы заданного диапазона;
transform — для заданной последовательности выполняет функцию к каждому элементу этой последовательности. Результат сохраняется в новой последовательности;
unique — вытягивает дубликаты из указанной последовательности;
unique_copy — делает копию из последовательности извлекая из нее дубликаты (одинаковые элементы):
upper_bound — находит последний элемент последовательности, не превышающий заданное значение.

⇑

4. Итераторы. Общие сведения

Итераторы — это объекты, которые позволяют перемещаться по содержимому контейнера. Итераторы подобны указателям. Итераторы являются абстракцией указателя. С помощью итераторов можно считывать и изменять значения элементов контейнера.

Чтобы использовать итераторы нужно подключить заголовок iterator

#include <iterator>

В C++ различают 5 видов итераторов:

RandIter — итератор произвольного доступа — записывает и извлекает значение из контейнера. Обеспечивает произвольный доступ к элементам контейнера;
BiIter — двунаправленный итератор — записывает и извлекает значения. Перемещается вперед и назад;
ForIter — прямой итератор — перемещается только вперед. Записывает и извлекает значения;
InIter — итератор ввода — только извлекает значения. Перемещается только вперед;
OutIter — итератор вывода — только записывает значения. Перемещается только вперед.

В библиотеке <iostream> определены следующие классы, реализующие итераторы:

iterator — базовый класс для всех итераторов;
iterator_traits — представляет различные типы, определенные итератором;
insert_iterator — обеспечивает работу итераторов вывода, которые вставляют объекты в контейнеры;
back_insert_iterator — обеспечивает работу итераторов вывода, которые вставляют объекты в конец контейнера;
front_insert_iterator — обеспечивает работу итераторов вывода, которые вставляют объекты на начало контейнера;
reverse_iterator — поддерживает работу обратных итераторов;
istream_iterator — поддерживает работу потоковых итераторов ввода;
istreambuf_iterator — поддерживает работу потоковых итераторов ввода символов;
ostream_iterator — поддерживает работу потоковых итераторов вывода;
ostreambuf_iterator — поддерживает работу потоковых итераторов вывода символов.

⇑

5. Функторы. Общие сведения

Для обеспечения гибкого взаимодействия между итераторами, контейнерами и алгоритмами, используются функторы. Функтор — это класс, в котором реализована операторная функция operator(). Благодаря функторам объект класса представляется как функция.

Чтобы использовать функторы в программе, нужно подключить заголовок functional

#include <functional>

В библиотеке STL функторы делятся на две категории:

бинарные — содержат два аргумента;
унарные — содержат один аргумент.

Библиотека STL содержит следующие бинарные функторы:

plus — суммирует (+) два аргумента;
minus — вычитает (–) аргументы;
multplies — умножает (*) два аргумента;
divides — делит (/) аргументы;
modulus — возвращает результат операции % для двух аргументов;
equal_to — сравнивает два аргументы на равенство (==);
not_equal_to — сравнивает два аргументы на неравенство (!=);
greater — определяет, больше ли первый аргумент чем второй аргумент (>);
greater_equal — определяет, первый аргумент есть больше или равен второму аргументу (>=);
less — определяет, меньше ли первый аргумент чем второй аргумент (<);
less_equal — определяет, первый аргумент меньше или равен второму аргументу (<=);
logical_and — применяет к аргументам логическое «И» (AND);
logical_or — применяет к двум аргументам логическое «ИЛИ» (OR).

Также определены два унарных функтора:

logical_not — применяет к аргументу логическое «НЕТ» (NOT);
negate — изменяет знак своего аргумента на противоположный.

⇑

Связанные темы

Шаблон класса. Ключевое слово template. Преимущества шаблонов. Аргументы в шаблонах. Примеры

⇑

BestProg

C++. Библиотека стандартных шаблонов STL. Общие понятия