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

{

  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. Примеры использования обобщенных алгоритмов

 

Программирование. Принципы и практика использования C++ Исправленное издание - _002.png
 Алгоритм
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 */ }

    // ...

}

 

Программирование. Принципы и практика использования C++ Исправленное издание - _002.png
 Здесь операции над итераторами, использованные в алгоритме
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 */ }

    // ...

}

 

Программирование. Принципы и практика использования C++ Исправленное издание - _002.png
 Здесь операции над итераторами, использованные в алгоритме
find()
, являются операциями над итераторами класса
list<string>::iterator
. Эти операторы имеют соответствующий смысл, так что логика их работы совпадает с логикой работы операторов из предыдущего примера (для класса
vector<int>
). В то же время они реализованы совершенно по-разному; иначе говоря, оператор
++
(в выражении
++first
) просто следует за указателем, установленным на следующий узел списка, а оператор
*
(в выражении
*first
) находит значение в узле
Link
. Сравнение итераторов (в выражении
first!=last
) сводится к сравнению указателей типа
Link*
, а сравнение значений (в выражении
*first!=val
) означает сравнение строк с помощью оператора
!=
из класса
string
.

Итак, алгоритм

find()
чрезвычайно гибкий: если мы будем соблюдать простые правила работы с итераторами, то сможем использовать алгоритм
find()
для поиска элементов в любой последовательности любого контейнера. Например, с помощью алгоритма
find()
мы можем искать символ в объекте класса Document, определенного в разделе 20.6.

void f(Document& v,char x) // работает с объектами класса Document

{

  Text_iterator p = find(v.begin(),v.end(),x);

  if (p!=v.end()) { /* мы нашли x */ }

    // ...

}

Эта гибкость является отличительной чертой алгоритмов из библиотеки STL и делает их более полезными, чем многие люди могут себе представить.

21.3. Универсальный алгоритм поиска: find_if()

Нам редко приходится искать какое-то конкретное значение. Чаще нас интересует значение, удовлетворяющее определенным критериям. Мы смогли бы выполнять намного более полезную операцию

find
, если бы могли определять свои собственные критерии поиска. Например, мы могли бы найти число, превышающее
42
. Мы могли бы также сравнивать строки, не учитывая регистр (верхний или нижний).