Программирование. Принципы и практика использования C++ Исправленное издание

lst.push_back(0.5); lst.push_back(1.5);

lst.push_back(2); lst.push_back(2.5); // список lst упорядочен

sort(v.begin(),v.end());              // сортировка вектора v

vector v2;

merge(v.begin(),v.end(),lst.begin(),lst.end(),back_inserter(v2));

for (int i = 0; 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. Вставки

Запись результатов в контейнер с помощью итератора подразумевает, что элементы, на которые указывает итератор, можно перезаписать. Это открывает возможность для переполнения и последующего повреждения памяти. Рассмотрим следующий пример:

void f(vector& vi)

{

  fill_n(vi.begin(),200,7); // присваиваем 7 элементам

                              // vi[0]..[199]

}

Если вектор vi содержит меньше 200 элементов, то возникает опасность. В заголовке стандартная библиотека предусматривает три итератора, позволяющих решить эту проблему с помощью добавления (вставки) элементов в контейнер, а не перезаписи его старых элементов. Для генерирования этих трех итераторов вставки используются три функции.

Для правильной работы алгоритма inserter(c,p) необходимо, чтобы итератор p был корректным итератором для контейнера c. Естественно, каждый раз при записи очередного элемента с помощью итератора вставки контейнер увеличивается на один элемент. При записи алгоритм вставки добавляет новый элемент в последовательность с помощью функции push_back(x), c.push_front() или insert(), а не перезаписывает существующий элемент. Рассмотрим следующий пример:

void g(vector& vi)

{

  fill_n(back_inserter(vi),200,7); // добавляет 200 семерок

                                   // в конец vi

}

Б.6.2. Объекты-функции

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

Рассмотрим следующий пример:

vector v;

// ...

sort(v.begin(),v.end(),greater()); // сортировка v в убывающем

                                        // порядке

Обратите внимание на то, что предикаты logical_and и logical_or всегда вычисляют оба свои аргумента (в то время как операторы && и || — нет).

Б.6.3. Класс pair

В заголовке стандартная библиотека содержит несколько вспомогательных компонентов, включая класс pair.

template

  struct pair {

    typedef T1 first_type;