Программирование

  Прежде всего, алгоритм find() применяется к последовательности, определенной парой итераторов. Мы ищем значение val в полуоткрытой последовательности [first:last]. Результат, возвращаемый функцией find(), является итератором. Он указывает либо на первый элемент последовательности, равный значению val, либо на элемент last. Возвращение итератора на элемент, следующий за последним элементом последовательности, — самый распространенный способ, с помощью которого алгоритмы библиотеки STL сообщают о том, что элемент не найден. Итак, мы можем использовать алгоритм find() следующим образом:

void f(vector& v,int x)

{

  vector::iterator p = find(v.begin(),v.end(),x);

  if (p!=v.end()) {

    // мы нашли x в v

  }

  else {

    // в v нет элемента, равного x

  }

  // ...

}

В этом примере, как в большинстве случаев, последовательность содержит все элементы контейнера (в данном случае вектора). Мы сравниваем возвращенный итератор с концом последовательности, чтобы узнать, найден ли искомый элемент.

Теперь мы знаем, как используется алгоритм find(), а также группу аналогичных алгоритмов, основанных на тех же соглашениях. Однако, прежде чем переходить к другим алгоритмам, внимательнее посмотрим на определение алгоритма find().

template

In find(In first,In last,const T& val)

 // находит первый элемент в последовательности [first,last],

 // равный val

{

  while (first!=last && *first != val) ++first;

  return first;

}

Вы полагаете, что этот цикл вполне тривиален? Мы так не думаем. На самом деле это минимальное, эффективное и непосредственное представление фундаментального алгоритма. Однако, пока мы не рассмотрим несколько примеров, это далеко не очевидно. Сравним несколько версий алгоритма.

template

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& v,int x) // работает с целочисленными векторами

{

  vector::iterator p = find(v.begin(),v.end(),x);

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

    // ...

}

  Здесь операции над итераторами, использованные в алгоритме find(), являются операциями над итераторами типа vector::iterator; т.е. оператор ++ (в выражении ++first) просто перемещает указатель на следующую ячейку памяти (где хранится следующий элемент вектора), а операция * (в выражении *first) разыменовывает этот указатель. Сравнение итераторов (в выражении first!=last) сводится к сравнению указателей, а сравнение значений (в выражении *first!=val) — к обычному сравнению целых чисел.

Попробуем применить алгоритм к объекту класса list.