Б. Страуструп - Язык программирования С++. Специальное издание, 3-изд. Бином. 2004 (1160791), страница 131
Текст из файла (страница 131)
Однако, если все множество вариантов стандартных алгоритмов считать просто «версией с преликатом по умолчанию>, это на добрую половину сократит число шаблонных функций, которые надо запоминать. 18.5.5. Поиск Алгоритмы кеагсй () и зеагсй и () и/впс! епг2() находят одну послеловательность как подпоследоватсльность другов: 1етр1а1е с!вяз Гог, с!акз Гог2> Гог зеагсЬ (ГогЯЯ, рог !аз1, Гог2Ягз12, Гог2 1аз12); 1етр!аге<с!азз Гог, с1азк Гог2, с1азк Вшргед> Рог кеа гсЬ (Гог/шз 1, рог 1ак1, Го г2/! ге 12, Гог2 !а в!2, В1пргес! р); 1етр!а1е<с!акк Гог, с1акк Гог2> Гог !!пс! епсК(Гог/!гк1, Гог 1ак1, Гог2Ягк!2, Гог 2 !аз!2); 1етр!иге<с!азк Гог, с1акз Гог2, с!акк В1пргес1> ГогЯпд ет1 (Гог/!гк1, Гог 1ая1, Гог2Ягк!2, Гог2 !аз!2, В1пРгедр); 1етр!аге<с!акк Гог, с!вяз 5!ее, с1акк Т> ГогзеагсЬ и (ГогЯгк! Гог! з1, 5!ее и, сопя! Тй оа1); 1етр1аве<с1иккГог, с!иве З!ее, с!икк Т, с!акк Вшргед> Гог кеагсЬ и (Гог/1гкг Гог !аз1, 3!ее и, сопк1 Тй оа1, В1пргес! р); Алгоритм кеагсп () ищет вторую последовательность-аргумент как подпоследовательность в первой.
Если таковая найдена, возвращается итератор паперный совпалающи!2 элемент в первой последовательности. Таким образом, возвращенное значение всегда находится и интервале (/!гя1, !аз!), Конец последовательности !/аз1) возвращается для указания на отрицательные результаты поиска. Например: з1г1па дио1е (" Зачем тратить время на обучение, если невежество дается даром ай). Ьоо! !и уио1е (сопк1 кгг1пуй к) ( 1урес/е~звгшу.:.сопя! Иегагог ЗС3; Глава 18.
Алгоритмы и объекты-Функции 592 БС!р = ееагсь (дио!е Ьеу1п () дио1е епд (! х Ьеу!и (), и епд ()); // находит е дио1е строну е ге1игп р!= дио1е.епд (); ооЫу () ( Ьоо!Ь! =1п дио1е( учение ) Ьоо! Ь2 = гп диоге ('лечение'); 0Ь! -Ние // Ь2 =/айе Таким образом, зеагсЬ () — это операция для поиска подстроки, универсальная для всех последовательностей. Значит, зеагсЬ () — очень полезный алгоритм. Алгоритм /)пс! епс! () ищет вторую заданную последовательность (свой второй аргумент) как подпоследовательность первой. Если вторая последовательность найдена, /!пс( епс(() возвращает итератор, указывающий на последнее совпадающий элемент в первой строке.
Другими словами,/!ги! еги! () — это зеагсЬ () «с остановкой в конце». Этот алгоритм находит последнее, а не первое вхождение второго аргумента в первой строке. Алгоритм зеагсЬ и () находит в последовательности подпоследовательность из по крайней мере и совпадений со значением аргумента па!ие. Возврап!антея итератор на первый элемент из и совпадений. 18.6. Алгоритмы, модифицирующие последовательность 18.8.1. Копирование Копирование — простейший способ произвести из одной последовательности дру- !ую. Определения базовых операций копирования тривиальны: Если нам нужно изменить последовательность, вы можете явно обратиться к ее элементам через итераторы. Затем вы можете изменить значение алемецта.
Однако, мы предпочитаем избегать такого программирования ради более простого и систематического стиля. Альтернативой являются алгоритмы, которые проходят по последовательности, выполняя указанные действия, Когда мы просто считываем элементы последовательности, этой цели служат немодифицирующие алгоритмы 19 18.5). Изменяющие последовательность алгоритмы нужнь! для того, чтобы выполнять наиболее распространенные операции обновления данных. Некоторые алгоритмы обнонляют последовательность, в то время как другие создают новую последовательность, основываясь на информации, найденной за время прохода.
Стандартные алгоритмы работают со структурами посредством итераторон. Это приводит к тому, что нстанка нового или удаление старого элемента нз контейнера вызывают трудности. Например, имея только итератор с указателем на элемент, как нам найти контейнер, из которого нужно удалить элемент? Не считая специальных итераторов (например, вставок, 9 3.8, 9 19.2А), операции с итераторами не изменяют размеров контейнера. Вместо вставки и удаления элементов такие алгоритмы изменяют значения элементов, меняют элементы местами и копируют их.
Даже операция гетоое () работает посредством переписывания элементов, которые нужно удалить Я 18.6.5). Вообще говоря, фундаментальные изменяющие операции дают на выходе измененные копии входа. Те алгоритмы, которые фактически меняют последовательность, являются вариантами копирующих алгоритмов. г 18.8. Алгоритмы, модифицирующие последовательность !етр1а!с<с!аяк эл, с1аяя Ои!> Ои! сору (1п/1 ге!, 1п !ая1, Ои! гея) ( щб!!е (/)гз!!=!ая!) 'геяь+ =*Ягясьь; ге!игл гея; ) !етр!а!е<с!аяя Вб с!азк В!2> В!2 сору бас!лоагд(В1/1гз1,В! 1ая1,В12 гея! тб11е (ргз! ~= 1ая!) ' — гея = * — 1аяг; гебигп гея; Результат копирующего алгоритма не обязан быть контейнером. Сгодится все, что мох<щз описать итератором для записи Я 19.2.8). Например: ио!ь!Я!з!<С!иб>& 1с, ояб.еатй оя) сору (!с.бед!л (), !с.еле! (), оябгеат 1!ега!ос<С!иб> (оз)); Чтобы прочитать последовательность, нам нужна последовательность, описывающая, где начать и где закончить.
Чтобы что-либо записать в нее, нам нужен только итератор, описывающий куда писать. Однако, мы должны соблюдать осторожность, чтобы не произвести запись за конец последовательности. Одним из способов застраховаться от этого является использование вставки Я 19.2А), по мере надобности увеличивающей размер последовательности. Например: оо!<Щсопз! оес!ог<сбаг> й оз, оесгог<сбаг> й о) ( оес!ос<сдпг> о; сору (оз Ьеу1п (), оя.елс((), оЬеу!и ()); //можем выйти эа конец в сору (озбеу!и (),озепс! (), басу шкег!ег (о)); /! добавляем элементы иэ вк в конец в ооЫ/(оес!ос<сдпг> й ос) сору Ьасбщагь)(ос.бед!л (), ос.епь!(), оз!геат Вега!оь сбаг> (сои!)) оес!ог<сбаг> о (ос.злее ()); // ошибка // правильно О правильно сору басбщап1 (ос.беу!и (), ос.ел<1 (), о.елс! ()); сору (и.беуш (), и.епй (), оя!геат Вега!ог сбаг> (сои!)! Входная и выходная последовательности могут перекрываться.
Мы пользуемся сору (), когда последовательности не перекрываются, или если конец выходной последовательности находится внутри входной. Мы используем Ьаслщагс( сору (), когда начало выходной последовательности находится внутри входной, Таким образом, никакие элементы не запишутся поверх других, пока последние не будут скопированы— см. также 9 18.13[13!.
Естественно, чтобы скопировать что-то по направлению от конца к началу, нам нужен двунаправленный итератор 19 19.2.1) как для входной, так и для выходной последовательностей. Например: Глава 18. Алгоритмы и объекты-функции 594 Часто цам нужно скопировать только элементы, отвечаюшие некоторому критерию. К сожалению, сору (Я как-то выпал из набора алгоритмов стандартной библиотеки (пГеа сп)ра'). С другой стороны, определить его очень просто: Гетр!аГе<с!авв 1л, с1авв ОиГ, с1азз Ргей> Ои1 сору (Г(1п Г)гз1, 1л !азГ, ОиГ гев, Ргей р) ( тьй!е (()гз1 ы Гав!) ( !Г (р ~'Ягвг)) *геФ-+ =*1Ггв1; нфгз1; ) ге1игл гез; Теперь если мы захотим распечатать элементы со значением больше, чем и, мы мо- жем сделать это так: оо!й Г'(!!зГ<!п1>8 Ы, Гл1 л, оз1геатй ов) ( сору (Г(!й.ЬедГп (), 1й.епй (), озягеит Вгеагог<!лГ> (ов), Ьшй2лй (угеаГег<1пт>(), л)); ) Посмотрите также гетопе сору !!'() (9 ) 8,6.5).
18.6.2. Алгоритмы агапэ!огпт Несколько сбивает с толку, что Ггалзйогт () вовсе не обязательно изменяет (трансформирует) входную последовательность. Вместо этого Ггапя~огт () создает выход, который является преобразованием входа, основанным на определенной пользователем операции; 1етр!псе<с!авв 1п, с!авз Ои!, с!азв Ор> Оиг Ггапз1огт (Гп Гсгвя, 1л !аз1, Ои1 гев, Ор ор) ( яеЫ!е (ГГгз1!= !ав1) *геен- = ор ( Г)гв1<->); ге1игп гев; ) 1етр1а1е<сГазв 1л, с1аяз 1л2, с!аяв Ои1, с!авв ВГлОр> Ои1 Ггапзгогт (1лу) гв1, 1л 1аз1, 1п21Ггв12, ОЫ гев, ВшОр ор) тЫ!е (ргз1 )= !азй *гев<-<- = ор (*!)гзг-н-,'Ягв12<-~) ге!игл гез; Алгоритм Ггапзгоггп (), который читает единственную последовательность, чтобы выдать на выход результат, напоминает сору ().
Вместо записи элементов он запГлсывает результат выполнения указанной операции над элементами. Таким образом, мы могли бы опреде.лить сору () как ГгапзуогГп () с операцией, возвращаюГдей свой аргумент: !етр!а1е<с!авв Т ТЫеп1Иу(солз1 Тйх)(ге!игах;) ОвозяраиГаелГ аргуяент 1етрГаге<с!аяз 1л, с!аяз Оия> Оиг сору )!л ГГгз1, 1л 1азГ, Ои1 гез) ( ге1игп Ггалз1огт (ргв1, !ав1, гез, Гйеп111у <Гурепате Вега1ог 1гайз<1п»оа1ие 1уре>); ) ' <Моя вива> (лат.) 595 18.6. Алгоритмы, модифицирующие последовательность Явная квалификация Ыелй1у понадобилась, чтобы получить конкретную функцию ыз шаблона.
Для получения типа элемента 1л мы применили шаблон !!ега1ог ! акЬ (5 19.2.2). Другой взглял на 1галз/огт () — рассмотреть его как вариант/ог еасй, который явно формирует свой выход. Например, мы можем при помощи !галя/огт () создать список имен типа я1г)лд из списка элементов типа С1иЬ: // извлекает строку с ииенеи ягг!полатев/(сопя!С!иЬй с) ( ге1игп с.пате; ооЫ1(!!я!<С!иЬ> й !с) ( !галя!огт (!сЬеу1п (), 1с.ешУ(), оя1геат !!ега1ог<я!г1лд> (сои!), питео/); Одна из причин, почему алгоритм !галя/огт () был назван естапз!отш> (изменить), заключается в том, ьто результат операции часто пишется туда же, откуда пришел аргумент.
В качестве примера рассмотрим уничтожение объектов, на которые указывает набор указателей: я1гис1Ре!е1е рсг( //кьпоби приленить встраивание, исполькуепобъекьп-функуто 1етр!а1е<с!аяз Т> T орегагог() (Т" р) ( с!е!е1е р; ге1игп 0; ) иоЫ ракете (ь/еуие<5Ьаре*>й я) ( 1гапя1огт (я.Ьеу!п (), к.епг!(), я.Ьеу1п (), Ре!е1е р1г ()), ) Алгоритм !галя/огт () всегда выдает выхолнуко последовательность. Здесь я направил результаг обратно во входную последовательность, так что Ре1е1е р!г (р) производит тот же эффект, что и р = Ре1е1е р!г (р). Вот почему я решил из РеЬ1е р!г; орега!ок() () вернуть О.
Алгоритм 1галя/огт (), имеющий дело с двумя последовательностями, позволяет объединить информацию из двух источников. Например, при анимации может понадобиться процедура, которая меняла бы положение нескольких фигур, применяя операцию сдвига: // кларе — фигура, тове кларе — переместить фигуру БЬаре" тоие кларе (БЬаре*я, Ро!п1р) //*я ь= р ( я->тосе !о (я — сеп1ег ()ьр~! ге1игп з, ) во!<! ирс!а1е ротиопз (Пз!<Кларе*>й Ь, иес1ог<ротий орег) ( // вызов операуии над соответствующая обьектои: !гапяХогт (! з.
Ьеу1п (), !я.ела (), о рек Ьеа~ и (), Ь Ьец!и (), тоие кларе); ) Нам на самом деле не нужно возвращать значение из топе зйаре(). Олнако 1галз/отл (] настаивает на присваивании чему-то результата операции, поэтому я по- 59б Глава зб. Алгоритмы и объекты-функции ввалил топе Маре () вернуть свой первый операнд; тем самым я могу записать его туда, откуда получил. Иногда у нас нет такой возможности. Например, операции, которые писал не я, и которые мне не хочется изменять, могут не возвращать значения. Иногда входная последовательность является константной. В таких случаях мы можем определить уог еасГГ () для двух последовательностей, чтобы он совпадал с Ггапзуоггл () для двух последовательностей: ГетрГа1е сГакз Гп, сГаяз 1п2, с!асс ВГпОр> В!лОрГог еасЬ (ГпЯгз1, Гп 1аз1, 1п27)гк12, ВтОр ор) ( шй Ве (ГГгк1! = 1азй ор ('ГГ з1<- >, 'Гсгз12<->); ге1игп ор; ) иоа! ир<Га1е рояйсолз (!Гкг<ЯЬаре*>й Гз, вес1ог,рош1ег>й орег) ( Гог еасЬ (Гк.Ьешп (), Гк.ел<! (), орег.ЬеуГл (), толе кларе); В других случаях может быть полезно иметь итератор для записи, который в действительности ничего не пишет Я !9.6(2)).
Алгоритмов, которые читали бы три последовательности и более, в стандартной библиотеке нет. Впрочем, такие алгоритмы легко написать. Или можно многократно использовать 1гапзуогт (). 18.6.3. Алгоритмы мпк2ие При сборе информации часто происходит дублирование данных. Алгоритмы ил щие () и ил!сГие сору () удаляют соседние одинаковые значения: 1етр!а!с<с!асс рог>рог илщие(рогГсгзг, Рог!аз!1 Гетр!а!с<сГазз рог, с!аз< Вгпрге<Г> Рог ипщие (Рог Вгк1, Рог Газ1, В!лргзЫр); Гетр!а1е<сГаяя Гп, с1азя Оиг> Ои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}
