STL представляет собой большую библиотеку шаблонов включающую в себя три ключевых компонента: контейнеры, итераторы, алгоритмы. Кроме того, STL является расширяемой библиотекой. STL избегает операторов new и delete и использует распределители памяти(allocators) для выделения и высвобождения памяти. Существует возможность создавать пользовательские распределители памяти. Типы исключений в STL:
Контейнеры делятся на три основных категории: контейнеры последовательностей, ассоциативные контейнеры и адаптеры контейнеров. Контейнеры последовательностей (sequence containers) и Ассоциативные контейнеры имеют общее название – контейнеры первого класса (first-class containers). Существует ещё четыре типа контейнеров, которые считаются «почти контейнерами» («near-containers») – С-подобные массивы, string, bitset и valarray.
Контейнерные заголовочные файлы стандартной библиотеки:
Общие имена типа typedef имеющиеся в контейнерах первого класса:
Имя | Назначение | Тип итератора |
Контейнеры последовательностей | ||
| vector | Быстрые вставки и удаление в конец контейнера, прямой доступ к любому элементу. | произв. доступ |
| deque | Быстрые вставки и удаления в начало и конец контейнера, прямой доступ к любому элементу. | произв. доступ |
| list | Двухсвязный список, быстрая вставка и удаление элементов везде. | двунапр. |
Ассоциативные контейнеры | ||
| set | Быстрый поиск, дубликаты (одинаковые ключи)не допускаются. | двунапр. |
| multiset | Быстрый поиск, допускаются дубликаты. | двунапр. |
| map | Взаимно однозначное соответствие, дубликаты не допускаются, быстрый поиск значения по ключу. | двунапр. |
| multimap | Соответствие «один ко многим», дублирование ключей допускается, быстрый поиск значения по ключу. | двунапр. |
Адаптеры контейнеров | ||
| stack | «Последним пришел, первым вышел» (LIFO) | не поддерж. |
| queue | «Первым пришел, первым вышел» (FIFO) | не поддерж. |
| priority_ queue | Элемент с наивысшим приоритетом всегда достигает выхода из очереди первым. | не поддерж. |
Имя | Назначение |
| default constructor | Конструктор для обеспечения инициализации по умолчанию. |
| copy constructor | Конструктор, который инициализирует контейнер в качестве копии существующего контейнера. |
| destructor | Деструктор контейнера. |
| empty | Проверка контейнера на пустоту. |
| max_size | Возвращает максимальное число элементов в контейнере. |
| size | Возвращает число элементов в контейнере. |
| = | Присваивает один контейнер другому. |
| <, <=, >, >=, ==, != | Сравнивает два контейнера. |
| swap | Поменять местами элементы двух контейнеров. |
Только в контейнерах первого класса | |
| begin | Возвращает iterator, либо const_iterator который ссылается на первый элемент контейнера. |
| end | Возвращает iterator, либо const_iterator который ссылается на последний элемент контейнера. |
| rbegin | Возвращает reverse_iterator, либо const_reverse_iterator который ссылается на последний элемент контейнера. |
| rend | Возвращает reverse_iterator, либо const_reverse_iterator который ссылается на позицию перед первым элементом контейнера. |
| erase | Удаляет один или несколько элементов из контейнера. |
| clear | Удаляет все элементы из контейнера. |
Классы vector и deque реализованы на базе массивов. Класс list реализует связанный список. Дополнительные операции характерные для контейнеров последовательностей:
front
front();
Возвращает ссылку на первый элемент в контейнере.
back
back();
Возвращает ссылку на последний элемент в контейнере.
push_back
push_back();
Вставляет новый элемент в конец контейнера.
pop_back
pop_back();
Выталкивает последний элемент контейнера.
Контейнер vector обеспечивает структуру данных непрерывной областью памяти. Это позволяет обеспечивает эффективный прямой доступ к любому элементу контейнера vector посредством операции индексирования []. Все алгоритмы STL могут работать с контейнером vector. Итераторы для vector обычно реализуются как указатели на элементы контейнера vector.
std::vector<int> v;
v.push_back(2);
cout << "\nРазмер вектора v: " << v.size();
std::vector<int>::const_iterator p1;
for(p1 = v.begin(); p1 != v.end(); p1++) cout << *p1 << ' ';
std::vector<int>::reverse_iterator p2;
for(p2 = v.rbegin(); p2 != v.rend(); ++p2) cout << *p2 << ' ';
int a[ 6 ] = { 1, 2, 3, 4, 5, 6 };
std::vector<int> v1(a, a+6);
std::ostream_iterator<int> output(cout," ");
std::copy(v1.begin(), v1.end(), out); //печать вектора
try
{
v1.at(100) = 777; //доступ вне массива
}
catch(std::out_of_range e)
{ cout << "\nИсключение" << e.what(); }
v1.erase(v.begin());
Контейнер list предоставляет эффективную реализацию операции вставки и удаления в любую позицию контейнера. Класс list реализуется как двухсвязный список, то есть каждый узел в list содержит указатель на предыдущий и на следующий узел. Любой алгоритм, который требует итераторов для чтения и для записи, прямых и двунаправленных итераторов, может выполняться с list. Дополнительные функции класса list:
inplace_merge
void inplace_merge(_BidirectionalIter first, _BidirectionalIter middle, _BidirectionalIter last, _Compare comp);
Объединяет две возростающие последовательности в одном и том же контейнере.
splice
splice();
Вырезает элементы из одного контейнера и помещает их в другой.
push_front
push_front();
Вставить элемент в начало контейнера.
pop_front
pop_front();
Вытолкнуть элемент с начала контейнера.
remove
remove();
Удалить элемент из начала контейнера.
merge
_OutputIter merge(_InputIter1 first1, _InputIter1 last1, _InputIter2 first2, _InputIter2 last2, _OutputIter result)
Объединяет две возростающие последовательности в одну.
sort
void sort(_RandomAccessIter first, _RandomAccessIter last);
Сортировка элементов в возрастающем порядке.
std::list<int> Values, otherValues;
Values.push_front(1);
Values.push_back(2);
values.sort();
Контейнер deque объединяет многие возможности классов vector и list. Реализуется на основе очереди с двумя концами и обеспечивает эффективный индексный доступ с эффективной операцией вставки в начало и конец контейнера. Класс deque обеспечивает поддержку итераторов произвольного доступа. Наиболее часто deque используется в качестве очереди FIFO.
std::deque<double> values;
std::ostream_iterator<double> output(cout," ");
values.push_front(2.2);
values.push_back(1.1);
for(int i=0; i < values.size(); ++i)
cout << values[i] << ' ';
values.pop_front();
values[1]=5.4;
Ассоциативные контейнеры STL предназначены для обеспечения прямого доступа с целью сохранения и выборки элементов с помощью ключей (ключи поиска). Имеется четыре ассоциативных контейнера: multiset, set, multimap, map. В каждом контейнере ключи сохраняются упорядоченными. Ассоциативные контейнеры поддерживают дополнительные функции:
equal_range
pair<_ForwardIter, _ForwardIter> equal_range(_ForwardIter first, _ForwardIter last, const _Tp& val);
Возвращает пару прямых итераторов, содержащих результаты lower_bound и upper_bound.
find
find();
Поиск ключа.
lower_bound
_ForwardIter __lower_bound(_ForwardIter first, _ForwardIter last, const _Tp& val, _Distance*)
Определения позиции первого вхождения указанного ключа.
upper_bound
_ForwardIter upper_bound(_ForwardIter first, _ForwardIter last, const _Tp& val)
Определения позиции за последним вхождением указанного ключа.
count
count();
Возвращает количество указанных ключей в контейнере.
Контейнеры multiset и set используются для быстрого сохранение и выборки ключей. Контейнер multiset допускает использование одинаковых ключей. Упорядочение элементов определяется компараторным объектом-функцией. Контейнеры поддерживает двунаправленные итераторы (но не итераторы произвольного доступа).
int a[10] = {7,22,9,1,18,30,100,22,85,13};
typedef std::multiset<int, std::<int> > ims;
ims intMultiset;
std::ostream_iterator<int> output(cout, " ");
intMultiset.insert(15);
result=intMultiset.find(20);
if ( result != intMultiset.end() ) cout << "Найдено значение";
intMultiset.insert(a, a+10);
std::copy(intMultiset.begin(),intMultiset.end(), output);
Контейнеры multimap и map используются для быстрого сохранения и нахождения ключей и ассоциированных значений (пара ключ/значение). При вставке в эти контейнеры используется объект pair. Контейнер multimap позволяет ассоциировать несколько значений с одним ключем. Упорядочение элементов определяется компараторным объектом-функцией. Контейнеры поддерживает двунаправленные итераторы (но не итераторы произвольного доступа).
typedef std::multimap<int, double, std::less<int> > mmid;
mmid pairs;
pairs.insert(mmid::value_type(15, 2.7) );
for(mmid::const_iterator iter = pairs.begin();
iter != pairs.end(); ++iter)
cout << iter->first << '\t' << iter->second << '\n';
pairs[25]=45.65;
STL предоставляет три адаптера контейнера – stack, queue, priority_queue. Адаптеры не являются контейнерами первого класса, поскольку они не предоставляют реализации фактической структуры данных в которой могут сохраняться элементы, и поскольку адаптеры не поддерживают итераторы. Все три класса адаптеров предоставляют функции-члены push и pop, которые реализуют соответствующий метод вставки элемента.
Адаптер stack обеспечивает структуру LIFO и может быть реализован с любым из контейнеров последовательности. Адаптер queue обеспечивает структуру FIFO и может быть реализован с контейнерами list и deque. Адаптер priority_queue обеспечивает очередь в которой наиболее приоритетное значение всегда будет удаляться первым. priority_queue может быть реализован с контейнерами vector и deque. Сравнение элементов выполняется с помощью функции-объекта less<T>.
std::stack<int> intDequeStack;
std::stack<int, std::vector<int> > intVectorStack;
std::stack<int, std::list<int> > intListStack;
intDequeStack.push(23);
intVectorStack.push(23);
intListStack.push(34);
Итераторы схожи с указателями и используются для указания на элементы контейнеров первого класса. STL контейнеры первого класса предоставляют функции-члены begin() и end(), которые возвращают итератор указывающий соответственно на первый и последний элемент контейнера. Если итератор i указывает на определённый элемент, то ++i указывает на «следующий» элемент, а *i ссылается на элемент, на который указывает i. Итератор, полученый из функции end(), может использоваться в сравнении на равенство и неравенство для определения окончания «движущегося итератора». Для ссылки на элемент контейнера используется объект типа iterator или const_iterator.
Имя | Назначение |
Все итераторы | |
| ++p | Преинкримент итератора |
| p++ | Постинкримент итератора |
Итераторы ввода | |
| *p | Разыменование итератора |
| p=p1 | Присвоение итератора итератору |
| p==p1 | Сравнение итераторов на равенство |
| p!=p1 | Сравнение итераторов на неравенство |
Итераторы вывода | |
| *p | Разыменование итератора |
| p=p1 | Присвоение итератора итератору |
Однонаправленные итераторы | |
| * | Обеспечивают все функциональные возможности итераторов ввода и вывода |
Двунаправленные итераторы | |
| -p | Предекремент итератора |
| p- | Постдекремент итератора |
Итераторы с произвольным доступом | |
| p+=i | Инкремент итератора p на i позиций |
| p-=i | Декремент итератора p на i позиций |
| p+i | Итератор помещается на позицию p+i |
| p-i | Итератор помещается на позицию p-i |
| p[i] | Возвращение ссылку на элемент, смещённый от p на i позиций |
| p<p1, p<=p1, p>p1, p>=p1 | Сравнение итераторов |
Категории итераторов:
Категория итератора, поддерживаемая каждым контейнером, определяет, может ли этот контейнер использоваться со специфическими алгоритмами в STL.
Контейнеры инкапсулируют некоторые базовые операции, но STL-алгоритмы реализуются независимо от контейнеров. Алгоритмы оперируют элементами контейнеров только с помощью итераторов. Можно создавать собственные алгоритмы.
copy
copy();
Копирование.
copy_backward
_BidirectionalIter2 __copy_backward(_BidirectionalIter1 first, _BidirectionalIter1 last, _BidirectionalIter2 result, bidirectional_iterator_tag, _Distance*)
Обратное копирование части одного контейнера в другой контейнер.
fill
void fill(_ForwardIter first, _ForwardIter last, const _Tp& value);
Заполняет все элементы контейнера значением <value>.
fill_n
_OutputIter fill_n(_OutputIter first, _Size n, const _Tp& value);
Заполняет указанные элементы контейнера значением <value>.
generate
void generate(_ForwardIter first, _ForwardIter last, _Generator gen)
Заполняет все элементы контейнера значением возвращаемым функцией <gen>.
generate_n
generate_n();
Заполняет указанные элементы контейнера значением возвращаемым функцией <gen>.
iter_swap
void iter_swap(_ForwardIter1 a, _ForwardIter2 b);
Перестановка значений контейнера (по ссылке).
includes
bool includes(_InputIter1 first1, _InputIter1 last1, _InputIter2 first2, _InputIter2 last2);
Проверяет находятся ли элементы второго множества в первом.
next_permutation
bool next_permutation(_BidirectionalIter first, _BidirectionalIter last);
Следующая перестановка в лексикографическом порядке.
prev_permutation
bool prev_permutation(_BidirectionalIter first, _BidirectionalIter last);
Предыдущая перестановка в лексикографическом порядке.
partition
_ForwardIter partition(_ForwardIter first, _ForwardIter last, _Predicate pred);
Разделение диапазонов элементов.
remove
_ForwardIter remove(_ForwardIter first, _ForwardIter last, const _Tp& value);
Удаление из указанного участка контейнера всех указанных объектов <value>
remove_copy
_OutputIter remove_copy(_InputIter first, _InputIter last, _OutputIter result, const _Tp& value);
Перенос из указанного участка контейнера в другой контейнер всех указанных объектов <value>.
remove_copy_if
remove_copy_if();
Перенос из указанного участка контейнера в другой контейнер объектов выбранных функцией сравнения <pred>.
remove_if
_ForwardIter remove_if(_ForwardIter first, _ForwardIter last, _Predicate pred);
Удаление из указанного участка контейнера объектов выбранных функцией сравнения <pred>
replace
void replace(_ForwardIter first, _ForwardIter last, const _Tp& old_value, const _Tp& new_value);
Производит замену объекта <old_value> на <new_value> по указанному участку контейнера.
replace_copy
_OutputIter replace_copy(_InputIter first, _InputIter last, _OutputIter result, const _Tp& old_value, const _Tp& new_value);
Производит замену объекта <old_value> на <new_value> по указанному участку контейнера и помещений старых значений в контейнер <result>.
replace_copy_if
_OutputIter replace_copy_if(Iterator first, Iterator last, _OutputIter result, _Predicate pred, const _Tp& new_value);
Производит замену объекта выбраного функцией <pred> на <new_value> по указанному участку контейнера и помещений старых значений в контейнер <result>.
replace_if
void replace_if(_ForwardIter __first, _ForwardIter last, _Predicate pred, const _Tp& new_value);
Производит замену объекта выбраного функцией <pred> на <new_value> по указанному участку контейнера.
reverse
void reverse(_BidirectionalIter first, _BidirectionalIter last, bidirectional_iterator_tag);
Инвертирование последовательности указанных элементов контейнера./
reverse_copy
_OutputIter reverse_copy(_BidirectionalIter first, _BidirectionalIter last, _OutputIter result);
Копирует указанные элементы в обратном порядке.
rotate
_ForwardIter rotate(_ForwardIter first, _ForwardIter middle, _ForwardIter last);
Ротация элементов.
rotate_copy
_OutputIter rotate_copy(_ForwardIter first, _ForwardIter middle, _ForwardIter last, _OutputIter result);
Ротация элементов с копированием.
set_difference
_OutputIter set_difference(_InputIter1 first1, _InputIter1 last1, _InputIter2 first2, _InputIter2 last2, _OutputIter result);
Определение элементов из первого множества отсутствующих во втором.
set_intersection
_OutputIter set_intersection(_InputIter1 first1, _InputIter1 last1, _InputIter2 first2, _InputIter2 last2, _OutputIter result);
Определение элементов из первого множества присутствующих во втором.
set_symmetric_difference
_OutputIter set_symmetric_difference(_InputIter1 first1, _InputIter1 last1, _InputIter2 first2, _InputIter2 last2, _OutputIter result);
Определение элементов из первого множества отсутствующих во втором и элементов второго отсутствующих в первом.
set_union
_OutputIter set_union(_InputIter1 first1, _InputIter1 last1, _InputIter2 first2, _InputIter2 last2, _OutputIter result);
Создаёт множество отсортированных элементов их двух контейнеров в третьем.
stable_partition
_ForwardIter stable_partition(_ForwardIter first, _ForwardIter last, _Predicate pred);
Подобна partition.
swap
void swap(_Tp& a, _Tp& b);
Перестановка значений контейнера.
swap_ranges
_ForwardIter2 swap_ranges(_ForwardIter1 first1, _ForwardIter1 last1, _ForwardIter2 first2);
Перестановка группы элементов контейнера.
transform
transform();
-//-
unique
_ForwardIter unique(_ForwardIter first, _ForwardIter last);
Удаляет из контейнера одинаковые элементы
unique_copy
_OutputIter unique_copy(_InputIter first, _InputIter last, _OutputIter result, _Tp*);
Копирует все уникальные элементы в другой контейнер.
adjacent_find
_ForwardIter adjacent_find(_ForwardIter first, _ForwardIter last, _BinaryPredicate binary_pred);
Возвращает итератор для чтения, указывающий на первый из двух идентичных смежных элементов в последовательности.
equal
inline bool equal(_InputIter1 first1, _InputIter1 last1,_InputIter2 first2);
Сравнение указанных участков двух контейнеров.
find
_InputIter find(_InputIter first, _InputIter last, const _Tp& val, input_iterator_tag);
Возвращает положение искомого значения <val>
find_each
find_each();
-//-
find_end
find_end();
-//-
find_first_of
find_first_of();
-//-
find_if
InputIter find_if(_InputIter first, _InputIter last, _Predicate pred, input_iterator_tag);
Возвращает положение значения определённого функцией <pred>.
lexicographical_compare
bool lexicographical_compare(_InputIter1 first1, _InputIter1 last1, _InputIter2 first2, _InputIter2 last2);
Используется для лексикографического сравнения двух массивов символов.
max
const _Tp& max(const _Tp& a, const _Tp& b);
Определение максимального значения.
min
const _Tp& min(const _Tp& a, const _Tp& b);
Определения минимального значения.
mismatch
pair<_InputIter1, _InputIter2> mismatch(_InputIter1 first1, _InputIter1 last1, _InputIter2 first2);
Выполняет сравнение указанных участков двух контейнеров и возвращает пару итераторов указывающих различные позиции контейнеров.
std::pair<std::vector<int>::iterator, std::vector<int>::iterator> location;
location = std::mismatch(v1.begin(),v1.end(),v3.begin());
search
search();
-//-
search_n
search_n();
-//-
accumulate
_Tp accumulate(_InputIterator first, _InputIterator last, _Tp init);
Суммирование значений указанной области контейнера.
adjacent_difference
_OutputIterator adjacent_difference(_InputIterator first, _InputIterator last, _OutputIterator result);
Вычисление разницы между парой смежных элементов
count
void count(_InputIter first, _InputIter last, const _Tp& value,_Size& n);
Выполняет подсчет количества объектов <value> в указанной области контейнера.
count_if
void count_if(_InputIter first, _InputIter last, _Predicate pred, _Size& n);
Выполняет подсчет количества объектов выбранных функцией <pred> в указанной области контейнера.
for_each
_Function for_each(_InputIter first, _InputIter last, _Function f);
Применение функции <f> к указанным элементам контейнера. Общая функция должна принимать текущий элемент в качестве аргумента и не должна модифицировать этот элемент.
inner_product
_Tp inner_product(_InputIterator1 first1, _InputIterator1 last1, _InputIterator2 first2, _Tp init);
Вычисление суммы произведений двух последовательностей.
max_element
_ForwardIter max_element(_ForwardIter first, _ForwardIter last);
Возвращает указатель на максимальный элемент в контейнере.
min_element
_ForwardIter min_element(_ForwardIter first, _ForwardIter last);
Возвращает указатель на минимальный элемент в контейнере.
nth_element
void nth_element(_RandomAccessIter first, _RandomAccessIter nth, _RandomAccessIter last);
Разделение диапазонов элементов.
partial_sum
_OutputIterator partial_sum(_InputIterator first, _InputIterator last, _OutputIterator result);
Вычисление суммы элементов двух контейнеров с накоплением.
partial_sort
void partial_sort(_RandomAccessIter first, _RandomAccessIter middle, _RandomAccessIter last);
Сортировка части последовательности.
partial_sort_copy
_RandomAccessIter partial_sort_copy(_InputIter first, _InputIter last, _RandomAccessIter result_first, _RandomAccessIter result_last);
Сортировка части последовательности с копированием результата.
random_shuffle
inline void random_shuffle(_RandomAccessIter first, _RandomAccessIter last);
Располагает элементы указанного участка контейнера в произвольном порядке.
stable_sort
void stable_sort(_RandomAccessIter first, _RandomAccessIter last);
Сортировка (аналогично sort)
transform
_OutputIter transform(_InputIter first, _InputIter last, _OutputIter result, _UnaryOperation oper);
Применение функции <f> к указанным элементам контейнера. Общая функция должна принимать текущий элемент в качестве аргумента, не должна модифицировать этот элемент и должна возвращать трансформированное значение.
make_heap
make_heap(_RandomAccessIterator first, _RandomAccessIterator last);
Создание и инициализация кучи.
pop_heap
void pop_heap(_RandomAccessIterator first, _RandomAccessIterator last);
Удаление элемента с вершины кучи.
push_heap
void push_heap(_RandomAccessIterator first, _RandomAccessIterator last);
Добавление нового элемента в кучу.
sort_heap
sort_heap(_RandomAccessIterator first, _RandomAccessIterator last, _Compare comp);
Сортировка последовательности значений.
Класс bitset обеспечивает операции для создания и манипуляции наборами битов. Наборы битов имеют фиксированный размер: bitset<size> b;. Операции:
set
Установка указанного бита.
reset
Сброс указанного бита.
flip
Переключает бит.
at
Получить бит.
test
Проверка бита.
size
Возвращает число битов в наборе.
count
Возвращает число установленных битов.
any
Возвращает true если хоть один бит в наборе установлен.
none
Возвращает true если не один бит в наборе неустановлен.
==, !=
Сравнение наборов битов.
&=, |=, ^ =, >>=, <<=
Битовые операции над наборами битов.
to_string
Преобразует набор битов в строку.
to_ulong
Преобразует набор битов в unsigned long.
Объекты-функции и адаптеры-функций предназначены для того чтобы сделать STL более гибкой. Объект-функция содержит функцию, которая может быть интерпретирована с синтаксической и семантической точки зрения как функция, использующая operator(). Объекты-функции STL:
divides<T> – арифметический;
equal_to<T> – реляционный;
greater<T> – реляционный;
greater_equal<T> – реляционный;
less<T> – реляционный;
less_equal<T> – реляционный;
logical_and<T> – логический;
logical_not<T> – логический;
logical_or<T> – логический;
minus<T> – арифметический;
moduls<T> – арифметический;
negate<T> – арифметический;
not_equal_to<T> – реляционный;
plus<T> – арифметический;
multiplies<T> – арифметический;