Бьерн Страуструп. Язык программирования С++. Специальное издание (2011) (1004033), страница 132
Текст из файла (страница 132)
Модифицирующие алгоритмы Под другим углом зрения «апзуогт () можно рассматривать как вариант алгоритма уог еасЬ (), явно формирующего свой выход. Например, вот как при помощи «апзуогт() порождается список имен клубов из списка объектов типа ОиЬ (8 18.4.2.1): ззг!пя патеоГ(сопя! С!ибя с) (ге!игп с.пате; ) гаЫ !'(дз!<С1»Ь> я 1с) ( (гапз1агт (1с. Ьед(п (), 1с. еп!( (), аз!сват !гегагаг<з!г!пд> (сат, "'!и" ), питео!) Одна из причин, по которой алгоритм назван»а»фогт () ', заключается в том, что результат этой операции часто пишется туда, откуда пришел аргумент. Рассмотрим уничтожение объектов, адресуемых набором указателей: з» ис! !уе1е!е р» ( Гетр(а(е<с!азз Т> Т* арегазаг() (Т* р) соил( (!!е1езе р; гетгп О! ) га!а' ригае (дедие<ЯЬаре*>з з) ггап фогт ( з. Ьел!п ( ), з.
епа ( ), з . Ьел(п ( ), 1уе1езе рзг ( ) ); ) Алгоритм «апзуогт() всегда трансформирует выходную последовательность. Здесь же я направляю результат назад во входную последовательность, так что зе1еге р«() (р) имеет тот же эффект, что и р=эе!еге р» () (р) . поэтому я и решил возвращать 0 из з)е1ете р«::орегагаг() () . Вариант алгоритма»апз/огт (), имеющий дело с двумя последовательностями, позволяет комбинировать информацию из двух источников. Например, программа анимации может иметь процедуру, обновляющую состояние списка фигур путем применения операции трансляции (сдвига); ь' з !=р ЯЬаре* та»е звере(Кларе* з, Ра!п!р) ( з->таге !а(з->сеп<ег()»р) г гегип! з; ) гаЫ ираа!е роз!!!апз (1!з!<>варе* > я Ы, гесгог<Ра!и!> я врег) ( д выполнить операцию над соответствующим обьектолс ггапз/огт (1з.
Ьее!и ( ), и. епг! ( ), арег. Ьед!и ( ), и. Ьев!и ( ), таге зиаре ) ) В принципе, никакой необходимости в возврате функции тоге зйаре() нет, но алгоритм «ап4огт () «настаивает» на том, чтобы возврат его операции присваивался чему-либо. Поэтому функция тоге зйаре() возвращает свой первый аргумент, и его можно записать туда, откуда он был получен. ! ТгапзГопн — изменять, преобразовывать, трансформировать. — Прим.
ред. Глава ) 8. Алгоритмы и классы функциональных объектов 63б Иногда такой возможности нет. Например, когда речь идет о чужой операции, не имеющей возврата (и которую нет желания или возможности исправлять). Или когда последовательность константная. В таком случае мы можем определить вариант <ог еасЬ() с двумя последовательностями, соответствующий варианту <гтмуогт () с двумя последовательностями: <етрЬ«в<с<а<я 1п, с1ат 1п2, с<от ВшОр> В!пОр <ог еасл (1п <<гя<, 1п 1ая<, 1п2 «гя<2, В1пОр ор) ( н ЬВе (у)гя<! =1ая<) ор ('21<веге, *Я<я<2+а) < ге<ига ор; го<а ар<<иге роя!попе (!(я«$ларе*>а Ь, гес<ог<Ро<п<>а орег) ( Гог еасл (Ь.Ьеи!и (), Ь.еп«(), орег. Ьее!и (), тоге <ларе) ) А бывают еще и случаи, когда полезно иметь выходной итератор, не выполняющий никакой фактической записи (5)9.6(2)).
Среди стандартных алгоритмов отсутствуют алгоритмы, работающие с тремя и более последовательностями. Правда, написать такие алгоритмы несложно. А в качестве альтернативы можно многократно использовать <гапяуог<и(). 18.6.3.
Алгоритм ып)с)ые() При сборе информации на хранение возможно ее дублирование. Алгоритмы ип1оие() и ипи1ие сору() устраняют последовательные повторы значений: <етр!а<в<с!аяя Рог> Рог ип(аие (Рог <<гя<, Рог <ая<) < <етр<а<е<с1аяя Рог, с<от В(прге<<> Рог ип(аие (Рог <<гя<, Рог <ая<, В(пРге«р); <етр1а<е<с1аяя 1п, с1аяя Ои<> Ои< ип(«ие сору(1п <<ге<, 1п 1ат, Оп< гея) <етр!а<е<с1аяя 1п, с1ат Ои<, с!аяя В(пРге«> Ои< ил<<ее сору (!ё!)гя<, 1п 1ая<, Ои< гея, Вшргедр) < Алгоритм ии1<уие() устраняет последовательное дублирование значений, а ип<'- аие сору() не допускает его.
Например; гоЫ у(1<я«я<г!пк>ь Ь, гес<ог<я<пих> ь гя) ( 1я.яог<() < !сортировка списка Гя!72.2.!) ипй<ие сору(Ь.Ьее!п(),<я.еп«О,васи )еметег(гя) ) ! Здесь 1я копируется в уз таким образом, что дубликаты автоматически удаляются. Применение яол() позволяет расположить одинаковые строки смежным образом. Как и другие стандартные алгоритмы, ип(аие () работает с итераторами. У него нет возможности знать тип контейнера, на элементы которого указывают итераторы, так что он не может модифицировать контейнер.
Он только может изменять значения элементов. Поэтому он не удаляет одинаковые элементы, как мы наивно могли бы предположить. Вместо этого он последовательно помещает уникальные элементы в начало последовательности и возвращает итератор на конец подпоследовательности уникальных элементов: 18 б.
Модифицирующие алгоритмы 637 <етр<а<е<с(азз Рог> Гог ил(!ие (Рог !)гз<, Рог 1аз<) ( Я<я< = а«!осел< !<л«(7)гз<,<аз<) < У?5!852 ге<игл ипв(не сору (рея<, !аз<,Ягз<) < ) Элементы за уникальной подпоследовательностью остаются неизменными. Поэтому нельзя сказать, что в векторе будут удалены все дубликаты: ноЫ/(нес<о<<я<с!пд>з гз) ( зог< (т.Ьел(п (), нз.
ел<<() ) < ??сортировка вектора илй<ие(нз.аед!п(),гз.еп«() ); Уустроняет дубликаты? Нет< ) УУ внимание: плохой код! (п< тао< () ( сдаг г [) = наЬЬсссден; сдаг" р = ипй<ие (ю и+<аггел (я) ); сои«< г « ' ' « р-г « '~п'; ) порождает следующий результат: аас«ес«е 5 Таким образом, р показывает на второе с.
Алгоритмы, которые вроде как должны удалять элементы (но не делают этого) присутствуют в двух формах: простые версии, перестраивающие элементы как ип!иле О, и версии, создающие новую последовательность, как это делает ип1<7ие сору() . Суффикс сору используется для того, чтобы различать эти два вида алгоритмов. Для устранения дубликатов из контейнера, его нужно явным образом «сжать» (уменьшить размер — з))пп)г); <етр1а<е<с1азз С> гоЫ е11пила<е дирдса<ез (Сз с) ( зог<(с.
Ьед(п (), с. ел<1 () ); <урепате С:: 1<ега<ог р = ап!«ие (с. Ьед(п (), с.еп«О ) < с.егазе(р,с.ел«() ); ) ?У сортируем У сжимаем Уукораннваем Отметим, что е1(яи(пате <1ир1<са<ез() не имеет смысла для встроенных массивов, в то время как алгоритм ипй7ие() вполне допустим и в этом случае. Пример с ил(иие сору () приведен в 83.8.3. 18.б.3.1. Критерии сортировки Чтобы удалить все дубликаты, входную последовательность нужно отсортировать (818.7.1). Кдк ипи1ие(), так и ип!иие сору() по умолчанию используют операцию == для сравнения элементов, но пользователь может предоставить и собственную операцию.
Например, можно изменить пример из 818.5.1 так, чтобы удалить Фактически, перемещая для устранения дубликатов задние элементы последовательности вперед, алгоритм ип1<7ие() можетпроизвести новыедубликаты, Например; Глава 18. Алгоритмы и классы функциональных объектов 638 все одинаковые имена. После извлечения имен официальных лиц клубов (тип С1иЬ), мы располагаем списком о1Т типа йяг<Регяои* > (818.5.1). После этого можно удалить дубликаты следующим образом: ейт!па1е аирйсагея (о/1) / Однако такой метод опирается на сортировку указателей и предполагает, что каждый указатель уникально идентифицирует официальное лицо клуба. В общем случае, нужно внимательнее анализировать записи типа Регяоп, чтобы ответить на вопрос об их эквивалентности.
Например, можно написать следухнцее: // эквивалентность объектов Ьоо! орега1ог== (сопя! Регяопь х, сопя! Регяопь у) ( // сравниваем х и у на равенство ) // "меньше чем" для обьектов Ьоог орегагог< (сопл Регяопь х, сопл Регяопь у) ( /сравниваем х и у с точки зрения упорядочения ) // равенство через указатель Ьоо! Регяоп еа (сопя( Регяоп* х, сопи! Регяоп* у) ( ге!ига *х == *у! ) // "меньше" через указатель Ьоо! Регяоп й(сопл Регяоп* х, сопя! Регяоп* у) ( ге!игл *х < "уз ) иоЫ ехггас1 апд рг!пг (сопя! йя1<С)иЬ>ь 1с) ( йя1<Регяоп*> оЯ;. ехп асг (1с, оу)г) 1 ог)".
хогг(Регяоп й); !!з1<Регяоп*>::йегагог р = ипйтие(о11.Ьед(п (), оЯ~.епд(),Регяоп ет!) /ог еасл (оЯ. Ьед/п ( ), р, Рпп1 пате (сои!) ); ) здесь я применяю 11м::хогг() (517.2.2.1), поскольку стандартный алгоритм лог!О (518.7.1) требует итераторов произвольного доступа, а 11яг предоставляет лишь двунаправленные итераторы (817.1.2). Полезно также убедиться, что критерий сравнения, применяемый при сортировке, соответствует критерию сравнения, применяемому при удалении дубликатов. Умолчательные операции == и < с указателями редко когда полезны для сравнения указуемых объектов. 18.6.4.
Алгоритмы замены элементов Алгоритмы замены проходят последовательность, заменяя некоторые значения на заданное значение. Они следуют модели алгоритмов 1(пи/1(па 11 и ип1оие/ио1- оие сору, порождая таким образом четыре варианта. И снова код весьма прост и нллюстративен: 18.6. Модифицирующие алгоритмы 639 <етр!а<есс1азз Гог, с!азз Т> го!а гер!осе (Гог)<гз<, Гог 1аз<, сопз< Ть га1, солт Ть пев га1) ( вЬ!<е (ргз<! =Л<з<) ( (Т(*!)гз< == га<) *Яп< = пев га1; +'Г ) ) <етрЬ«есс<азз Гог, с<азз Рге<1, с<азз Т> гоЫ гер!асс <1(Гог)<гз<, Го«<аз<, Рге<1 р, сопи< Ть пев ча1) ( вЬ11е (Т!гз<! =<аз< ) (Т(р("у)т<» .у)т =. ".!)гз« ) ) <етр!а<е<с<азз Ь<, с<паз Ои<, с!азз Тт Ои<гер<асе сору(1пЯгз<, 1п !аз<, Оп< гез, сопз< Ть га1, сопз< Ть пеп га1) ( вЬИе (!!гз<! =!ат) *гез++ = ("Я«<< == га1) ? пев га<: «у1«з« Р5« ) ге<ига гез; <етр<а<есс1азз 1п, с1азз Ои<, с1азз Рге«, с<аз< Т> Ои< гер!асе сору <) (1пЯгз<, 1п 1аз<, Ои< гез, Рге«р, сопз< Та пеп га<) ( вЬ!<е ((1«з<( =!а<и) ( *гезее = р (*Ягз<) ? пев га1: "!<гам .г.<Ь«з< < ) ге<ига гез; ) Вот пример, когда мы хотим пройтись по списку строк, заменяя английскую транслитерацию моего родного города Аагйиз на его истинное название А«Ьик гоЫ~(1!з<сз<г(пк)а <оввз) ( гер1асе (<овпз.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
