Б. Страуструп - Язык программирования С++. Специальное издание, 3-изд. Бином. 2004 (1160791), страница 130
Текст из файла (страница 130)
Естественно, связыватели, адаптеры и отрицатели часто сочетают, Например: ехгегп "С' !пг я1гстр )сопи! сЛаг*, сопи! еЬаг"). // из <я)йуЬ> оо!йз )!!и!<сбое'> й !я) // используется указа<пель на функцию ( 1урейе~1урепате !М1<слаг*>:юопз1 !1ега1огП; ЕХр =/1 ай Д!яЬед!и )), Ььеай )), по1! )Ыпй2пй Ь!1г /йп )я!гетр), 'забавно"))) Так находится элемент списка !я, содержащий С-строку "забавно . Отрицатель ну- жен из-за того, что з1гстр () возвращает й при равенстве строк.
587 18.5. Алгоритмы, не модифицирующие последовательность 18.5. Алгоритмы, не модифицирующие последовательность Немодифицирующие алгоритмы являются основным средством для поиска чего-либо в последовательности без написания цикла. Кроме топ л они позволяют получить необходимую информацию об элементах. Эти алгоритмы могут принимать в качестве аргументов константные итераторы 8 19.2.1) и — за исключением !ог еасй () -- не должны вызывать операции, изменяющие элементы последовательности. 18.5.1.
Алгоритмы 1ог вас(1 Мгя пользуемся библиотеками, чтобы воспользоваться работой, уже проделанной кем-то. Использование библиотечных функций, классов, алгоритмов и т. и. избавляет нас от лишнего придумывания, проектирования, написания, отладки и документирования. Использование стандартной библиотеки облегчает восприятие программы другим человеком, знакомым с библиотекой — ему не придется долго разбираться в вашем коде «собственного приготовления>. Основная выгода стандартных библиотечных алгоритмов заключается в том, что они избавляют программиста от написания явных циклов. Циклы могут быть утомительны и чреваты ошибками. Алгоритм рлг еасй () — простейший в том смысле, что он ничего не делает кроме того, что устраняет необходимость в янном цикле. Он просто вызывает свой операторный аргумент для последовательности: 1етр!аге<е!аяя тп, е1аля Ор' Ор )ог еаеб '1 пЯгя1, 1п !аяг, ОрЯ ( шб1!е (!(гег!= !аЯ1)1(улгЯ1++) ге1игп б ) Какие функции имеет смысл вызывать таким образом? Если вы хотите накапливать информацию от элементов, подумайте об ассигпи!а1е () Я 22.6).
Если вам надо найти что-нибудь в последовательности, рассмотрите прнменениеЛЫ () иу(пд (7"() (ф 18.5.2). Если вы изменяете или удаляете элементы, используйте гер!асе () Я 18.ЬА) или гетоое () Я 18.6.5), Вообще, прежде чем прибегать к 1ог еасй (), подумайте, нет ли более шлециалпзированного алгоритма, который больше вам подойдет.
Результатом (ог еасй () является функция или функциональный объект, передаваемый в качестве третьего аргумента, Как показано в примере Япт Я 18,4), это позволяет вернуть информацию в вызывающую функцию, Одно из обычных примсненийуог еасЬ () — извлечение информации из элементов последовательности. Например, рассмотрим сбор имен неизвестного числа объектов С!иб: иоЫ ех1гас1(еапя1 !!я!<С!иб> 8 1е, !1я1<Регяап* 8 оЯ // реял~ еща ел~ персонал из '!л< и 'оЯ" ( )ог еаеб (!е.бешп (), 1е епг! (),Ех1гае1 аЦкегя(ЬЯ; Подобно примеру из э 18А и () 18.4.2 мы определяем класс-функцию, которая извлекает желаемую информацию.
В этом случае имена, которые будут выданы, находятся в сппскзх !(я1<Регяоп*> в нашем спнскс Ия1<С!иЬ>. Следовательно, Ех1гас1 отЛсегядолгх; на скопировать в наш список весь персонал (оЯ)сегя) из списков оЯлсегя объектов С!пЬ: е!аяя Ех1гас1 ЬОлеегя ( йя1 <Регяоп*> 8 !я1; Глава 18. Алгоритмы и объекты-функции 588 риЬЫс. ехрйсьтЕхггас1 оЯ~!секя (Ия1<Регяоп*>8 х): !к1 (х) () оо!с! орега1ог () (сопя!С!и68 с) сопя1 (сору (со/21сегя Беат (), с о/йсегяепс((), Ьасд !пяег1ег(!я1));) Теперь мы можем распечатать имена, снова воспользовавшись/ог еасй (): оо!с! ех1гас! апг! ргт1 (сопя! !!я1<ОиЬ> 8 !с) ( Вк1<Регяоп*> оЯ ех1гас1 (!с, оо); /ог еас6 (оЯЬеу!и (), оДепс! (),Рг1п1 пате (сои!)1 Написание Рг!п! пате оставлено в качестве упражнения Я 18.13[4)). Ллгоритм/ог еасй () классифицируется как немоднфицнрующий, поскольку он явно не изменяет последовательность.
Тем не менее, будучи применен к неконстантной последовательности,/ог еас/1 () (через третий аргумент) может изменять ее элементы. См., например, использование пейа1е () в 9 11<В 18.5.2. Семейство 2(пс( Алгоритмы Япг! () просматривают последовательность или две последовательности в поисках значения илн соответствия некому предикату.
Простейшая версия/1пс(() ищет конкретное значение или производит поиск на соответствие предикату: 1етр!а1е<с!аяя !и, с!аяя к !пГтс!(1п/1гя! !и !ая!, сопя1 <8 оа!) гетр!а1е<с!аяя !и, с!акк Ргес!> 1пЯас! 1!(1п/1 гк1, 1п !ая1 Ргед р); Алгоритмы Япс! () и Япс( (! () возвращают итсратор для первого элемента, удовлезворяющего значению или предикату соответственно. Фактически,/1пс( () можно рассматривать как версиюЯпг! 1/'()с преднкатом ==. Почему бы обе эти функпии оыло не назвать/1пг! ()? Причина в том, что перегрузка функций не всегда различает вызовы двух шаблонных функций с одинаковым числом аргументов.
Рассмотрим такой пример: Ьо о! ргеи (т 1); оо!с(Х(оес1ог<Ьоо! (*!) (!пе)>8 о1, оес1ог<!и! >8 о2) ( Япс! (о!Ьеу1п (), о!, елд () ргед); // находил рте! Япс!Я(и26ерп (),о2 епд(), реем; // походии Чекое, для которого //ргед!) воквраи!ает 1гие Гели быЯпп! () ифпс( 1/'() имели одно и то же имя, возникла бы довольно интересная двусмысленность. Вообще, суффикс 1/'нспользуют для обозначения того, что алгоритм работает с преднкатом. Алгоритм/1пс! /1гя! оЯ находит в пос.ледовательности первый элемент, который имеется и во второй последовательности: 589 18.5, Алгоритмы, не модифицирующие последовательность 1етр1а1е<с1овя Гог, с1аяя Го«2> Гог/!пс! В гя! оЯГог/!гк1, Гог !ая1, Гог2/!гя12, Гог2 1ая!2); 1етр!а!е<с!аяя Рог, с!аяя Гог2, с!ая В!преет! Гог/!пс! Тсгя! о/(Гог/!гят,рог!акт, Гог2/!гя12, Го«2 1ая12,В!пРгес(р); Например: слтх[] = ( 1, о, 4); !л! уЦ = ( О, 2, Л, 4, б ); оо!сЩ ( 1пг р =/!пс! /!гя! о/(хх«3, у, у+ф //р = Ьх[!] !лр д=Япс/ Ягя! ог(р«1,х+о, у, у+б); //д = Бх[2] ) Указатель р укажет па х[1], потому что 3 — первый элемент из х, имеющийся также в 'у.
Подобным образом д укажет на х[2]. Алгоритм ас2!асеп! /)пс( () найдет пару соседних совпадающих значений; !етр!а1е<с1аяя Гог> Гог ас!!а<ел! Вла (Рог/!гя1, Рог !аят),' 1етр1аге<с!аяя Гог, с!акя В!пРгеФ Рог ас!!асеп! /!лс! (Гог/)гя1, Гог !ая1, В!пргес! Р), Возвращаемым значением является итератор на первый совпадающий элемент. На- пример: ио(<Ц(вес!о~ ятппу> й 1ех1) иес!ог<я1ппу>суега1ог р = ас!!асеп! !с ос! (1ехтфеусп (), тех1епс!()) Ц' (р!=1ех1епс! () ЬЪ 'р=='1!!е") ( // я слави лродублироеол «Иге>! 1ех1, е гаке (р); //- 18.5.3.
Алгоритмы соип1 Алгоритмы соип1 () и соип1 (/'() считают число вхождений в последовательность некоторых значении: 1етр!а!е<с!авя 1л, с!аяя Т> 1урепа те Него 1ог !га!!я<1 п>:.веселее 1уре соил! (1п/!гя! 1п !ая1, сопя1 Т8 оа4; 1етр!а1е<с1ояя 1п, с!аяя Ргес!> 1урелате Вега1ог 1га!!я<1п>х/Яегепсе 1уре соил! 1/(1п/!гят, 1п 1ая1, Рте«1р); Интересен возвращаемый алгоритмом соип1 () тип, Рассмотрим очевидную и доволь- но наивную версию соип1 (): 1етр!а1е<с1аяя !и, с1аяя Т !л1соип1(1п/!ге! 1п !ат, сопя1 Тй оа1) ( !п1«ее=У; то!! !!е (/!гя! и 1ат) (Г ( /!гя1++ = = па 1) +<тек; ге1игл гея; ) 590 Глава 18. Алгоритмы и объекты-Функции Проблема в том, что 1п1может быть неподходящим типом для результата.
На машине с маленьким !и!может быть слишком много элементов в какой-нибудь последовательности, чтобы значение соил!(] уместилось в 1и1. И наоборот, на конкретной машине может быть выполнена более быстродействующая реализация, если счетчик будет иметь тип зйог(. Ясно, что число элементов в последовательности не может быть бо иыпе, чем максимальная разность между ее итераторами (9 19.2.) ). Следовательно, очевиднын способ попьп аться решить проблему — определить тип возвращаемого значения как: 1урепате 1и::ЖДегепсе 1уре Однако, стандартный алгоритм должен быть приложим ко встроенным массивам, а также к стандартным контейнерам. Например: ооЫЯсйаг'р, 1и1яие) !и!и = соип1(о, р>я!ее, 'е'); // побсчет числа вхождений булки 'е' К сожалению, сопя! с)саг"::ЙДегепсе 1уре не годится для С++.
Эта проблема решается частичной специализацией 11ега1ог 1га11к (9 ) 9.2.2). 18.5.4. Равенство и несовпадение Алгоритмы едиа1 () (равенство) н т(вта1сй () (несовпадение) сравнивают две после- довате.льности; 1етр(а1ечс!акк 1п, с!аяк 1п2> Ьоо1 едио1(1иЯз11п !аз1, 1п2/1гз12), 1етр1аге с!а як 1п, с!акз 1п2, с! акя В1пРгеа> Ьоо1 едиа! 'йп/з я1, 1п !аз1, 1и2/!ге!2, В!пРгес! р); 1етр!а1ечс!акз 1и, с!аяз!и2> раи 1п,!п2> т!ята1сЪ (1пргя1,1п 1аи, 1п2/тгк!2) 1етр!а1е<с!акв!и, с1акя 1и2, с!азв ВйиРгес(> райге1и, 1и2> т!вта1сЬ (1и/1 ге! 1и 1ак! 1п2/1гв12 В1пРгейр); Алгоритм едиа1 () просто проверяет, равны ли соответствующие пары элементов в последовательностях; т!ята1сй () ишет первую пару элементов, которые при сравнении не совпадают, и возвращает итераторы на эти элементы. Для второй последонательности конец не определен, то есть 1ая12 нет.
Вместо этого считается, что во второй последовательности по крайней мере столько же элементов, сколько и в первой, и в качестве 1ая12 пспользуетсяу2гз12+ (1аз1 — /)гз1). Этот прием широко применяется в стандартной библиотеке, где для операций над парами элементов используются пары последонательностей. Как показано в 9 ! 85Я, зти алгоритмы даже полезнее, чем кажутся на первый аз~лад, поскольку пользователь может создавать предикаты, определяюшне, что счи,тать равенством и совпадением.
Отметим, что последовательности не обязаны быть одного типа. Например: ооЩ(1!ягчйп1>й 1й оес1ог<поиЬ(е>й сч!) Ьоо! Ь = еда а< (В Ьеу!и (), !1 елп (), ис(Ьеуйп ()); 591 18.5. Алгоритмы, не модифицирующие последовательность Все, что здесь требуется — чтобы элементы последовательности были допустимы как операнды предикатов. Две версии т/зта1с!в () отличаются только использованием преликатов. Фактически, мы можем реализовать нх одной функцией с аргументом-шаблоном по умолчанию: 1етр!аге<с1акз 1л, с1акк 1п2, с1азк ВшРгей> расс<То,,Гп2> тгкта1сЬ (ТпЯгк1, 1п 1ак1, Тп2/1 гк12/ Вшргес! р = еуиа1 1о<1псоа!ие 1уре> () ) //я 184.2.! тби!е (/)гк1!= 1ая1 йй р (*!)гк1, */)гз12)) ( +«/1гк1; -У)ге!2, ) ге1игп ра1г<Тп, Вп2> ~~ге!,3гк12! ) Разницу между двумя функциями и одной с аргументом по умолчанию можно увидеть при использовании указателей на функции.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
