find()
применяется к последовательности, определенной парой итераторов. Мы ищем значение val
в полуоткрытой последовательности [first:last]
. Результат, возвращаемый функцией find()
, является итератором. Он указывает либо на первый элемент последовательности, равный значению val
, либо на элемент last
. Возвращение итератора на элемент, следующий за последним элементом последовательности, — самый распространенный способ, с помощью которого алгоритмы библиотеки STL сообщают о том, что элемент не найден. Итак, мы можем использовать алгоритм find()
следующим образом:
void f(vector
{
vector
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
{
vector
if (p!=v.end()) { /* мы нашли x */ }
// ...
}
find()
, являются операциями над итераторами типа vector
; т.е. оператор ++
(в выражении ++first
) просто перемещает указатель на следующую ячейку памяти (где хранится следующий элемент вектора), а операция *
(в выражении *first
) разыменовывает этот указатель. Сравнение итераторов (в выражении first!=last
) сводится к сравнению указателей, а сравнение значений (в выражении *first!=val
) — к обычному сравнению целых чисел.
Попробуем применить алгоритм к объекту класса list
.