Стандартная библиотека содержит около шестидесяти алгоритмов. Все они иногда чем-то полезны; мы сосредоточим внимание на часто используемых алгоритмах, которые используются многими, а также на тех, которые иногда оказываются очень полезными для решения какой-то задачи.
По умолчанию проверка равенства выполняется с помощью оператора
==
, а упорядочивание — на основе оператора
<
(меньше). Алгоритмы из стандартной библиотеки определены в заголовке
<algorithm>
. Более подробную информацию читатели найдут в приложении Б.5 и в источниках,
перечисленных в разделе 20.7. Эти алгоритмы работают с одной или двумя последовательностями. Входная последовательность определяется парой итераторов; результирующая последовательность — итератором, установленным на ее первый элемент. Как правило, алгоритм параметризуется одной или несколькими операциями, которые можно определить либо с помощью объектов-функций, либо собственно функций. Алгоритмы обычно сообщают о сбоях, возвращая итератор, установленный на конец входной последовательности. Например, алгоритм
find(b,e,v)
вернет элемент
e
, если не найдет значение
v
.
21.2. Простейший алгоритм: find
Вероятно, простейшим из полезных алгоритмов является алгоритм
find
. Он находит элемент последовательности с заданным значением.
template<class In, class T>
In find(In first, In last, const T& val)
// находит первый элемент в последовательности [first,last], равный val
{
while (first!=last && *first != val) ++first;
return first;
}
Посмотрим на определение алгоритма
find
. Естественно, вы можете использовать алгоритм
find
, не зная, как именно он реализован, — фактически мы его уже применяли (например, в разделе 20.6.2). Однако определение алгоритма
find
иллюстрирует много полезных проектных идей, поэтому оно достойно изучения.
Прежде всего, алгоритм
find
применяется к последовательности, определенной парой итераторов. Мы ищем значение
val
в полуоткрытой последовательности
[first:last]
. Результат, возвращаемый функцией
find
, является итератором. Он указывает либо на первый элемент последовательности, равный значению
val
, либо на элемент
last
. Возвращение итератора на элемент, следующий за последним элементом последовательности, — самый распространенный способ, с помощью которого алгоритмы библиотеки STL сообщают о том, что элемент не найден. Итак, мы можем использовать алгоритм
find
следующим образом:
void f(vector<int>& v,int x)
{
vector<int>::iterator p = find(v.begin,v.end,x);
if (p!=v.end) {
// мы нашли x в v
}
else {
// в v нет элемента, равного x
}
// ...
}
В этом примере, как в большинстве случаев, последовательность содержит все элементы контейнера (в данном случае вектора). Мы сравниваем возвращенный итератор с концом последовательности, чтобы узнать, найден ли искомый элемент.
Теперь мы знаем, как используется алгоритм
find
, а также группу аналогичных алгоритмов, основанных на тех же соглашениях. Однако, прежде чем переходить к другим алгоритмам, внимательнее посмотрим на определение алгоритма
find
.
template<class In, class T>
In find(In first,In last,const T& val)
// находит первый элемент в последовательности [first,last],
// равный val
{
while (first!=last && *first != val) ++first;
return first;
}
Вы полагаете, что этот цикл вполне тривиален? Мы так не думаем. На самом деле это минимальное, эффективное и непосредственное представление фундаментального алгоритма. Однако, пока мы не рассмотрим несколько примеров, это далеко не очевидно. Сравним несколько версий алгоритма.
template<class In, class T>
In find(In first,In last,const T& val)
//
находит первый элемент в последовательности [first,last],
// равный val
for (In p = first; p!=last; ++p)
if (*p == val) return p;
return last;
}
Эти два определения логически эквивалентны, и хороший компилятор сгенерирует для них обоих одинаковый код. Однако на практике многие компиляторы не настолько хороши, чтобы устранить излишнюю переменную (
p
) и перестроить код так, чтобы все проверки выполнялись в одном месте. Зачем это нужно? Частично потому, что стиль первой (рекомендуемой) версии алгоритма
find
стал очень популярным, и мы должны понимать его, чтобы читать чужие программы, а частично потому, что для небольших функций, работающих с большими объемами данных, большее значение имеет эффективность.
ПОПРОБУЙТЕ
Уверены ли вы, что эти два определения являются логически эквивалентными? Почему? Попробуйте привести аргументы в пользу их эквивалентности. Затем примените оба алгоритма к одному и тому же набору данных. Знаменитый специалист по компьютерным наукам Дон Кнут ((Don Knuth) однажды сказал: “Я только доказал, что алгоритм является правильным, но я его не проверял”. Даже математические доказательства содержат ошибки. Для того чтобы убедиться в своей правоте, нужно иметь как доказательства, так и результаты тестирования.
21.2.1. Примеры использования обобщенных алгоритмов
Алгоритм
find
является обобщенным. Это значит, что его можно применять к разным типам данных. Фактически его обобщенная природа носит двойственный характер.
• Алгоритм
find
можно применять к любой последовательности в стиле библиотеки STL.
• Алгоритм
find
можно применять к любому типу элементов.
Рассмотрим несколько примеров (если они покажутся вам сложными, посмотрите на диаграммы из раздела 20.4).
void f(vector<int>& v,int x) // работает с целочисленными векторами
{
vector<int>::iterator p = find(v.begin,v.end,x);
if (p!=v.end) { /* мы нашли x */ }
// ...
}
Здесь операции над итераторами, использованные в алгоритме
find
, являются операциями над итераторами типа
vector<int>::iterator
; т.е. оператор
++
(в выражении
++first
) просто перемещает указатель на следующую ячейку памяти (где хранится следующий элемент вектора), а операция
*
(в выражении
*first
) разыменовывает этот указатель. Сравнение итераторов (в выражении
first!=last
) сводится к сравнению указателей, а сравнение значений (в выражении
*first!=val
) — к обычному сравнению целых чисел.
Попробуем применить алгоритм к объекту класса
list
.
void f(list<string>& v,string x) // работает со списком строк
{
list<string>::iterator p = find(v.begin,v.end,x);
if (p!=v.end) { /* мы нашли x */ }
// ...
}
Здесь операции над итераторами, использованные в алгоритме
find
, являются операциями над итераторами класса
list<string>::iterator
. Эти операторы имеют соответствующий смысл, так что логика их работы совпадает с логикой работы операторов из предыдущего примера (для класса
vector<int>
). В то же время они реализованы совершенно по-разному; иначе говоря, оператор
++
(в выражении
++first
) просто следует за указателем, установленным на следующий узел списка, а оператор