Библиотека стандартных шаблонов STL (Standard Template Library). Общие понятия. Контейнеры. Алгоритмы. Итераторы. Функторы
Данная тема является началом изучения библиотеки STL языка C++.
Содержание
- 1. Библиотека STL. Общие сведения
- 2. Контейнеры. Общие сведения. Перечень
- 3. Алгоритмы. Общие сведения
- 4. Итераторы. Общие сведения
- 5. Функторы. Общие сведения
- Связанные темы
Поиск на других ресурсах:
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 — изменяет знак своего аргумента на противоположный.
⇑
Связанные темы
⇑