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

Страуструп Бьерн
Шрифт:

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

Кроме того, мы могли найти первое нечетное число. А может, мы захотели бы найти запись с адресом "

17 Cherry Tree Lane
".

Стандартный алгоритм поиска в соответствии с критерием, заданным пользователем, называется

find_if
.

template<class In,class Pred>

In find_if(In first,In last,Pred pred)

{

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

return first;