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

Страуструп Бьерн
Шрифт:

Б.5.4. Сортировка и поиск

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

<
, а эквивалентность пар значений
a
и
b
определяется условием
!(a<b)&&!(b<a)
, а не оператором
==
.

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

vector<int> v;

list<double> lst;

v.push_back(3); v.push_back(1);

v.push_back(4); v.push_back(2);

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<double> v2;

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

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. Вставки

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

void f(vector<int>& vi)

{

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

// vi[0]..[199]

}

Если вектор

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

Для правильной работы алгоритма

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