for (int i = 0; i<v2.size; ++i) cout << v2[i] << ", ";
Алгоритмы вставки описаны в разделе Б.6.1. В итоге получается следующий результат:
0.5, 1, 1.5, 2, 2, 2.5, 3, 4,
Алгоритмы
equal_range
,
lower_bound
и
upper_bound
используются точно так же, как и их эквиваленты для ассоциативных контейнеров (раздел Б.4.10).
Б.5.5. Алгоритмы для множеств
Эти алгоритмы интерпретируют последовательность как множество элементов и выполняют основные операции над множествами. Входные
и выходные последовательности предполагаются упорядоченными.
Б.5.6. Кучи
Куча — это структура данных, в вершине которой находится элемент с наибольшим значением. Алгоритмы над кучами позволяют программистам работать с последовательностями произвольного доступа.
Куча позволяет быстро добавлять элементы и обеспечивает быстрый доступ к элементу с наибольшим значением. В основном кучи используются при реализации очередей с приоритетами.
Б.5.7. Перестановки
Перестановки используются для генерирования комбинаций элементов последовательности. Например, перестановками последовательности
abc
являются последовательности
abc
,
acb
,
bac
,
bca
,
cab
и
cba
.
Если последовательность
[b:e]
уже содержит последнюю перестановку (в данном примере это перестановка
cba
), то алгоритм
next_permutation
возвращает значение
x
, равное
false
; в таком случае алгоритм создает первую перестановку (в данном примере это перестановка
abc
). Если последовательность
[b:e]
уже содержит первую перестановку (в данном примере это перестановка
abc
), то алгоритм
prev_permutation
возвращает значение
x
, равное
false
; в таком случае алгоритм создает последнюю перестановку (в данном примере это перестановка
cba
).
Б.5.8. Функции min и max
Сравнение значений полезно во многих случаях.
Б.6. Утилиты библиотеки STL
В стандартной библиотеке есть несколько инструментов для облегчения использования стандартных библиотечных алгоритмов.
Б.6.1. Вставки
Запись результатов в контейнер с помощью итератора подразумевает, что элементы, на которые указывает итератор, можно перезаписать. Это открывает возможность для переполнения и последующего повреждения памяти. Рассмотрим следующий пример:
содержит меньше 200 элементов, то возникает опасность. В заголовке
<iterator>
стандартная библиотека предусматривает три итератора, позволяющих решить эту проблему с помощью добавления (вставки) элементов в контейнер, а не перезаписи его старых элементов. Для генерирования этих трех итераторов вставки используются три функции.
Для правильной работы алгоритма
inserter(c,p)
необходимо, чтобы итератор p был корректным итератором для контейнера
c
. Естественно, каждый раз при записи очередного элемента с помощью итератора вставки контейнер увеличивается на один элемент. При записи алгоритм вставки добавляет новый элемент в последовательность с помощью функции
push_back(x)
,
c.push_front
или
insert
, а не перезаписывает существующий элемент. Рассмотрим следующий пример:
Многие стандартные алгоритмы принимают в качестве аргументов объекты-функции (или функции), чтобы уточнить способ решения задачи. Обычно эти функции используются в качестве критериев сравнения, предикатов (функций, возвращающих значения типа
bool
) и арифметических операций. Несколько самых общих объектов-функций описано в заголовке
<functional>
стандартной библиотеки.
Рассмотрим следующий пример:
vector<int> v;
// ...
sort(v.begin,v.end,greater<int>); // сортировка v в убывающем
// порядке
Обратите внимание на то, что предикаты
logical_and
и
logical_or
всегда вычисляют оба свои аргумента (в то время как операторы
&&
и
||
— нет).
Б.6.3. Класс pair
В заголовке
<utility>
стандартная библиотека содержит несколько вспомогательных компонентов, включая класс