{
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
) просто следует за указателем, установленным на следующий узел списка, а оператор
*
(в выражении
*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
. Мы могли бы также сравнивать строки, не учитывая регистр (верхний или нижний).
