Бьерн Страуструп. Язык программирования С++. Специальное издание (2011) (1004033), страница 130
Текст из файла (страница 130)
18.5. Немодифицирующие алгоритмы Немодифицирующие алгоритмы являются основным средством поиска чего угодно в последовательности элементов без применения циклов. Кроме того, они позволяют получить информацию об элементах. Эти алгоритмы могут принимать константные итераторы (519.2.1) и не должны (кроме алгоритма 1Ьг еасй () ) вызывать операции, изменяющие элементы последовательности. 1Гя.5.1.
Алгоритм 1ог еас1)О Мы применяем библиотеки, чтобы воспользоваться ранее выполненной работой. Использование библиотечной функции, класса, алгоритма и т.д. экономит огромные усилия, которые в противном случае пришлось бы затратить на их проектирование, реализацию, и тестирование, Применение стандартной библиотеки делает код более понятным для любого человека, знакомого с этой библиотекой — ему не надо разбираться во внутреннем механизме чьей либо уникальной «программной кухни», Одним из ключевых достоинств алгоритмов стандартной библиотеки является то, что онн избавляют программиста от применения циклов.
Явное программирование циклов и утомительно, и чревато ошибками. Алгоритм Уог еасй() — простейший в том смысле, что он ничего не делает, кроме как устраняет необходимость в цикле. Фактически он просто вызывает свой аргумент-операцию для заданной последовательности: гетр(иге<с!аяя 1п, с(аяя Ор> Ор лог «ась (1пуггяя, 1п 1ат, Ор)) ( пл!1е (Гягяя! =!ее!) !'("!)гя!»») ! ге!игп 1! Какие функции имеет смысл вызывать таким образом? Если вам нужно накапливать информацию от элементов, применяйте асспгпп1аге() (822.6). Если нужно что-то найти в последовательности элементов — применяйте 21пя1() или Лпя! «У() (818.5.2).
Если вы изменяете или удаляете элементы, применяйте гер1асе() (818.6.4) или гегаоге() (818.6.5). Вообще, перед тем, как применить|ог еасй(), подумайте, нет ли более специализированного алгоритма, применимого в вашем случае. 627 18.5. Немодифицирующие алгоритмы Возвращаемый алгоритмом уог еасЬ () результат есть либо функция, либо функциональный объект, переданный ему в качестве третьего параметра. Как показано в примере с классом Ялт из 818.4, это позволяет вернуть информацию вызывающей функции.
Типичным применением алгоритмауог еасЬ() является задача об извлечении информации из элементов последовательности. Например, нам нужно собрать всю информацию об официальных лицах неизвестного числа клубов (структура С1лЬ из 8 18.4.2.1): то!а' ехгтаст (соли !из<С!иЬ> з 1с, Езз<регзоп* > з о1)т) ( )ог еасл (1с.Ьея!и (), !с.ела(), Ехзгаст оЯсегз(оЦ~ ); ) Параллельно примерам из 818.4 и 818.4.2 мы определяет класс функциональных обьектов, предназначенный для извлечения необходимой информации. Необходимые имена из списка!!зг< С1лЬ> переносим в наш список 11ат<Регзол* >, то есть класс ехласг оЯсегз просто копирует сведения об официальных лицах из одного списка в другой: с(азз Ехз аст оДкегз ( 1аз<Регзол*> ь !зз; риЬИс: ехрлсй Ехзтасз оЯ)сете (Езг<Регзоп" >з х): Ья (х) ( ) то!з(оретазот() (сопзт С(иЬЗ с) соле! (сору (с.
о11)сете. Ьея!и (), с. оЯнегз. епт((), Ьася !изет!ее (!зз) ) 1 ) )' Наконец, мы можем распечатать полученный список официальных лиц, снова применив алгоритм /ог еасЬ ( ): той! ехпаст апа' Рппз (соле! 1!зг<С(иЬ>з !с) ( !!Зз<РЕГЗОП*> ОУУ( ехьаст(!с, о1)т) т )ог еась (оф.ьел!п(),оД.епи(),Рплз пате(сои!) ); Написание Рг(л! пагле мы оставляем в качестве упражнения (818.13[4)). Алгоритм Уог еасЬ () классифицируется как немодифицирующий, потому что он сам по себе не изменяет последовательность. Однако будучи применен к неконстантной последовательности, этот алгоритм через свой третий аргумент может изменять элементы последовательности — см., например, использование лелаге в 811.9. 18.5.2. Алгоритмы поиска Алгоритмы поиска просматривают элементы одной или двух последовательностей для нахождения значения или соответствия предикату.
Простейший алгоритм Ялз(() из этого семейства алгоритмов просто ищет конкретное значение или производит поиск на соответствие предикату: 628 Глава ) 8. Алгоритмы и классы функциональных объектов <етр<а<е<с<азз 1п, с<от Т> 1пЯпй(1п3<гз<, 1п <аз<, сопя< Ть га<) < <етр<а<е<с<азз 1п, с!аз< Ргей> 1пу)пй а (1пу<гз<, 1п 1ам, Ргей р); Алгоритмы Япй() и 3<ай (1() возвращают итератор для первого элемента, имеющего требуемое значение или отвечающего предикату, соответственно. Фактически, Впй() можно рассматривать как версиюу<пй <1() с предикатом ==.
Почему бы тогда не назвать обе эти версии просто Япйц? Ответ заключается в том, что механизм разрешения перегрузки функций не всегда способен различить вызовы двух шаблонных функций с одинаковым числом аргументов. Рассмотрим пример: Ьоо< ргей (!и<); гойЦ(гес<ог<Ьоо1('3) (ш<) >ь г1, гес<ог<ш<>ь г2) ( 3<ай (г1 . Ьея<п (), г1.
епй (),реей) < <! находим ргей Яви(г2. Ьеяш (), г2. епй (), ргей) < Л походим пя дяя которого ргейо еозераи<ает оие ) Если бы 3<ай ( ) и Впй (1( ) имели одно и то же имя, неожиданно возникла бы неоднозначность. В общем случае, суффикс <1'означает, что алгоритм работает с преди катом. Алгоритм 1!ай 1<ге< оГ() находит первый элемент последовательности, имеющий соответствие во второй последовательности: <етр<а<е<с<азз Гог, с<паз Гог2> Гогу<ай «гз< оГ(Гогу<ге<, Гог 1ат, Гог2Ягз<2, Гог2 <ат2) <етр1а<е<с!азз Гог, с1ат Гог2, с!азз В(пРгей> Гогу<ай <<гз< оГ(ГогЯгз<, Гог !аз<, Го<2 !)ге<2, Гог2 <а<а2, ВшРгей р) Например: а«х[] = ( 1,3,4 ); <а<у[] = ( 0,2,3,4,5) < го<йу'( ) ( ш<* р = 3<ай Ягз< оу' (х, х+3, у, у+5) ' У р = &хИ !и<* о =3<ай Ягз< о3(рг<,х+З,у,у+5); < 2 = &х~21 ) Указатель р покажет на х[1], поскольку 3 — это первый элемент из х, имеющий значение, совпадающее со значением элемента из у.
Аналогично, а покажет на х[2]. Алгоритм айуасеп< /зпй() найдет пару соседних совпадающих значений: <етр<а<е<с<азз Гог> Гог ай!ясен< <<пй(Гог3)гз<, Гог!аз<) < <етр1а<е<с<азз Гог, с<паз Вшргей> Гог ай1асеп< <<пй(Гога<я<, Рог <аз<, Вп<ргейр) < Возвращаемым значением является итератор на первый совпадающий элемент. Например: го!й Г(ге<<ос<я<с<па> я <ех<) ( тес<ос<я<с<па> <: Вега<ог р = ай!ясен< [<пй (<ех<. Ьея!и (), <ек<. епй () ) ) 8.5.
Немодифицирующие алгоритмы 629 !!я снова иродублировал "йе У (Т(р! =(ехг.еий() зз *р=="гйе") ( !! ... ) 18.5.3. Алгоритмы соиптО и соипт 0() Алгоритмы сопи!() и сопи! (!() подсчитывают число вхождений в последовательность некоторого значения: гетр(а<е<с(ат 1и, с!ат Т> (уреиате Вега!ог (га1!з<1и>:: йфегеисе гуре сони!(1и))гзг, 1и !аз!, соиз! Тз га1) !етр(аге<с(азз 1и, с(азз Реем> (уреиате 11егагог гга1!з<1п>::дфегепсе (уре сони! ф'(1пу)гзг, 1п !аз!, Ргеа р) Интересен тип возврата алгоритма соил!() . Рассмотрим очевидную (и наивную) версию сопи!(): гетр(а!е<с(азз 1и, с(азз Т> 1и! сони!(1и ))гзг, 1и 1ам, соизг Тз га1) ( тз гез = О! и й(1е (1!ге!! =1азз) (!'(*у)гзгг+ == га1) в чгез! ге!иго гез; Проблема состоит в том, что тип 1из не совсем подходит для типа возврата.
На машинах с недостаточно большим зпг его может не хватить для хранения числа подсчитанных алгоритмом сопи!() элементов последовательности. И наоборот, на машинах с большим 1и! будет более эффективной реализация с возвратом зйогс Ясно, что число элементов в последовательности не может быть больше максимальной разности между ее итераторами (919.2.1). Поэтому, можно было бы определить тип возврата следующим образом: гуреиате 1и:: дфегепсе !уре Однако стандартные алгоритмы должны работать и со встроенными массивами, а не только со стандартными контейнерами. Например: гоИЯсдаг* р, тг з(зе) ( 1пз и = соил((р,резце, 'е' ); !1иодсчет числа вхождений буквы 'е' ) К сожалению, с)заг*:: й3егепсе суре не проходит в С+-ь.
Проблема решается при помощи частичной специализации йега!оз па!уз (519.2.2). Глава 18. Алгоритмы и классы функциональных объектов 630 18.5.4. Алгориталы ес)иа10 и гп1впта1с)з() Алгоритмы е(Еиа1() и т!ята(сЬ () сравнивают две последовательности: (етр(а(е<е!азз 1п, е!аи 1пг> Ьоо! е(Ела((1пМтз(, Еп !аз(, Еп2 Е)гз(2) ( (етр!а(е<е(аш 1п, е!аи 1п2, с1ат В(лрге(Е> Ьоо! е(Ела!(1п Е(гз(, !и (аз(, Епг (1гз(2, Вшрге((р) (етр!а(е<с!ат Еп, с!аш 1п2> ра(г<1и, 1лг> п(ата(еЬ (1л Е)гз(, 1л !ат, Еи2 ()гз(2) ( (етр(а(е<е(ам 1п, е!аи 1п2, е!аш Вшргед> ран <1и,1п2> та(иа(еЬ (Ел (!гз(, 1и 1аз(, Еиг()гз(2, Верее((р) Алгоритм е(Ела!() просто проверяет, эквивалентны ли все пары соответствуюших элементов двух последовательностей; т!зта(сЬ () ищет первую пару неэквивалентных друг другу элементов, и возвращает итераторы на эти элементы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
