Бьерн Страуструп. Язык программирования С++. Специальное издание (2011) (1004033), страница 131
Текст из файла (страница 131)
Конец второй последовательности не задается, то есть !аз(2 отсутствует. Вместо этого предполагается, что во второй последовательности элементов не меньше, чем в первой, так что вместо Еаз(2 используется Вгя(2г (Еая(-Еугз() . Такой подход используется в рамках стандартной библиотеки в тех случаях, когда для операций над парами элементов задается пара последовательностей. Как показано в 818.5.1, стандартные алгоритмы более полезны, чем это может показаться на первый взгляд, поскольку пользователи могут предоставлять предикаты, задающие критерии равенства и соответствия.
Заметьте, что последовательности не обязаны быть одного и того же типа. Например: го!(Е('(Из(<!л(>з И, гее(ог<((оиЫе>з и!) ( Ьоо! Ь = е((иа!(И.Ьедш (),И.еп(Е(), ы(Е.Ьее!и () ) ( ) Все, что здесь требуется, это чтобы элементы последовательностей подходили в качестве операндов предикатов. Две версии т!зта(сЬ () отличаются только использованием предикатов. Фактически, их можно реализовать одной функцией с умолчательным аргументом-шаблоном: (етр(а(е<е!азз 1л, е!аш 1пг, с1аш В(прге(Е> ра(г<1п, Епг> т(зта(еЬ (Еп Е(гз(, 1п (аз(, Епг Е)гз(2, Вшрге(Е р = е(Еиа! (о<(урепате 1п:: га(пе 1уре> () ) ИЗ!В.4.2. ! ( пя(Ие ( Е!гз(! =1аз1 з з р ( 'Е)гз(, *Е(гз(2) ) ( з (1(гз(( ++(1 ге(г( ) ге(огп рап<1п, 1а2> (Е(гз(, Е)гз(2) Разницу между двумя функциями и одной функцией с умолчательным аргументом легко выявляется любым, кто использует указатели на функции.
Тем не менее, если мысленно представлять себе все варианты стандартных алгоритмов как версии ) 8.5. Немодифицирующие алгоритмы 6Э1 с предикатом по умолчанию, то число необходимых для запоминания вариантов сократится примерно вдвое. 18.5.5. Поисковые алгоритмы Поисковые алгоритмы зеагсЬ(), зеагсЬ л() и Т!л(1 ел(1() выявляют вхождение некоторой последовательности в качестве подпоследовательности другой последовательности (для поиска одиночных элементов используйте 1(лВ() (818.5.2) или Ь)лагу зеагсй () (818.7.2)): (етр!а(е<с!азз Гог, с!азз Го«2> Гог зеагсл (Го«1(гз(, Гог 1ам, Го«2 ((гз(2, Го«2 !аз(2) (етр!а(е<с!азз Гог, с!азз Го«2, сЬ(зз В(лР«е((> Гог зеа«сЬ (Го«3тм, Гог 1аз(, Го«21(гз(2, Го«2 !аз(2, В(пР«е((р); (етр!а(е<с!азз Гог, сЬ(зз Гог2> Го« (ш(( еп(((Гог ((гз(, Гог !ам, Го«2 ((гз(2, Гог2 !аи2); (етр!а(е<с!ат Гог, с1азз Гог2, с!азз В(пРгеВ> Гог(ш(( ел(((Гогу(гз(, Го« !аз(, Го«2((гз(2, Гог2 !ам2, В!лР«е((р) (етр!а(е<с1азз Гог, с!азз Иге, с!азз Т> рог зеагсЬ п(Гог((гз(, Рог 1аи, Язе и, сопя( Тз га!) (етр1а(е<с!азз Гог, с!азз Язе, с!аз( Т, с!аяз Вшргеи' Гог зеагсЬ п (Гог((гз(, Гог 1ам, Язе п, сопя( Та га1, В(пР«е((р); Алгоритм зеагсЬ () ищет свой второй аргумент-последовательность как подпоследовательность первого аргумента-последовательности.
В случае успеха поиска возвращается итератор на первый совпадающий элемент в первой последовательности. Таким образом, возвращаемое значение всегда находится внутри (Лгз(, 1аз(1 . Конец последовательности 1аз( возвращается для указания на отрицательный результат поиска. Например: з(г!пя ((ио(е (" И%у (газ(е Вте !еагп!пд, (ввел !ало«алое (з !лз(ап(алеоиз?" ) Ьоо! ш ((ио(е (солз( з(г!пяь з) ( (уре((е(' з(г(п8: ( сопя( Вега(ог БС1; БС1 р = зеагсЬ (оио(е.
Ьее(п (), оио(е. ели (), з. Ьея(л (), з. ели () ); о' ищем я в ((ио(е ге(игп р! =((ио(е. ели () ( ) яо!(( е ( ) ( Ьоо! Ы = !и ((ио(е ("!еагпшя" ) ( Ьоо1 Ь2 = (л аио(е ( "!етт(па" ) ( ) о'Ы = («ие о'Ь2 = Та!зе Алгоритм поиска подстроки зеа(сй() очень полезен, так как он универсален для любых последовательностей. Умолчательным критерием совпадения элементов служит операция ==. Когда требуется иной критерий, применяется аргумент, являющийся бинарным предикатом (818.4.2). Глава 18.
Алгоритмы и классы функциональных обьектов 632 Алгоритм 11яз( елИ() ищет свой второй аргумент-последовательность как подпоследовательность первого аргумента-последовательности. В случае обнаружения вхождения этот алгоритм возвращает итератор на последний совпадающий элемент первой последовательности. Другими словами, ЯЫ еЫО работает как зеагсй(), но с концевой фиксацией возвращаемого результата — он находит последнее (а не первое) вхождение второго аргумента в первый аргумент-последовательность. Алгоритм зеагсгз а () находит последовательность из по'крайней мере а вхождений аргумента-значения га1 в свой первый аргумент-последовательность. Он возвращает итератор на первый элемент найденной последовательности. 18.6.
Модифицирующие алгоритмы Если нужно изменить последовательность, ее можно итерировать и изменять значения элементов. Однако где это допустимо, мы стараемся уйти от такого стиля программирования в пользу более простых и регулярных приемов. Альтернативой является применение алгоритмов, которые проходят последовательность и выполняют требуемые действия.
Когда мы просто читаем элементы последовательности, мы используем немодифицирующие алгоритмы (818.5). Модифицирующие алгоритмы выполняют наиболее распространенные виды обновления данных. Причем некоторые алгоритмы действительно обновляют содержимое последовательности, в то время как другие строят новые последовательности на базе информации, извлеченной во время прохода по исходной последовательности. Стандартные алгоритмы работают со структурами данных через итераторы. Это приводит к некоторым трудностям тогда, когда элемент вставляется в контейнер или удаляется из него.
Действительно, имея один лишь итератор элемента, как мы найдем контейнер, из которого собственно и надо элемент удалить? Кроме как в случае специальных итераторов (например, в случае итераторов для вставки; 83.8 и 819.2.4), операции с итераторами не изменяют размера контейнеров. Вместо вставки и удаления элементов алгоритмы изменяют их значения, меняют элементы местами, копируют значения элементов. Даже алгоритм геизозе () работает посредством переписывания элементов, подлежащих удалению (818.6.5).
Вообще говоря, результаты наиболее фундаментальных модифицирующих алгоритмов являются модификациями их входов. Те же алгоритмы, которые, как представляется, изменяют последовательности, являются вариантами копирующих алгоритмов. 18.6.1. Копирующие алгоритмы Копирование — это простейший способ получить из некоторой последовательности другую последовательность. Определения простейших копирующих алгоритмов тривиальны: !егер!аге<с!азз 1п, с!азз Оиг> Оиг сору(1и1!гзг, 1а !азг, Ои! гез) ( ый!!е (11гзз! =!аи) *гезэз = *ягзз~-~; ге!игл гез) ) 8.6. Модифицирующие алгоритмы 633 гетр(иге<с(азз В(, с(авз В!2> В(2 сору ЬасЬгагй (В! Вез!, В! (ам, В(2 гез) ( вЬ!(е(у!гзг! =!аз!) *--гез = *--!азг; гегигн гез; ) Результат копирующего алгоритма не обязан быть контейнером.
Подойдет все, что можно описать выходным итератором (519.2.6). Например: го!й!'((В!<С!иЬ>а (с, омгеать оз) ( сору((с.Ьед!и (), (с.епй(), озггеат иегагог<С(иЬ> (оз) ) ! ) Для чтения последовательности нам требуется знать, откуда начинать читать и где заканчивать.
Для записи же требуется лишь итератор, указываюший куда писать, Однако нужно соблюдать осторожность, чтобы не произвести запись за конец последовательности. Один из способов застраховаться от такой проблемы состоит в применении специальных итераторов вставки (519.2.4), увеличивающих размеры последовательности по мере необходимости. Например: го!й г (сопл! гесгог<слаг>ь гз, нес!ос<слог>ь г) ( сору(гз.
Ьел!п О, гз.епй(), г.Ьект О ); дможет писать за конец г сору(гз.Ье8!п О,гз.енй(),ьасд (змее(ег(г) ); Удобавлает элементы из гз в конец г ) Входная и выходная последовательности могут перекрываться. Мы используем сору (), когда последовательности не перекрываются или когда конец выходной последовательности находится в пределах входной последовательности.
Мы используем Ьасуогагй сору(), когда начало выходной последовательности находится внутри входной последовательности. Таким образом, никакие элементы не будут переписаны до того, как их значения будут скопированы. См. также 518.13[131 Естественно, чтобы скопировать что-нибудь в направлении от конца к началу, нам нужен двунаправленный итератор 519.2.1) как для входной, так и для выходной последовательности. Например: го!йг (гес(ос<слог>ь гс) ( сору Ьаслпагй(гс. Ьек!и (), гс. епй(), омгеат !(его!ос<слог> (соим ) !,У еггог гесгог<сйаг> г (гс. з!се () ); сору ЬасЬгагй(гс.бед!и (), гс.епй(), г.епй() ) г сору (г. Ьеа!и (), г. епй (), озегеат Вегагог<сяаг> (сои!) ) ) Часто нужно копировать лишь элементы, отвечающие некоторому критерию.
К сожалению, сору (!'() как-то выпал из набора стандартных алгоритмов (шеа сц1ра — моя вина (лат.)). С другой стороны, определить его совсем не трудно: гетрьгге<с!азз 1п, сгазз Оиг, с(авз Ргей> Ои! соруЯ(1п 11 ге!, 1н (азг, Ош гез, Реей р ) ( пЬИе (!!гзг! =(аз!) Глава ) 8. Алгоритмы и классы функциональных объектов 634 ( г)'(р (*!)гз!) ) *гезеэ = "у)гзг; «Лг51 ' ) ге!игл гез; ) Теперь, если мы, например, захотим распечатать лишь элементы, значение которых больше и, то это можно сделать следующим образом: юоЫ1(1йг<1пг>ь Ы, тз и, оз«еата оз) ( сору ф(Ы.Ьедгп(),Ы.етг(),озиеат пегайг<тг> (оз),Ьта2па(реа~ег<тз>(),п) ); См. также гетоге сору 11 () К)8.6.5).
18.6.2. Алгоритм 1галвФогпт() Хотя это и сбивает с толку, но а апзуогт () вовсе не обязательно изменяет входную последовательность. Вместо этого алгоритм работает над выходной последовательностью, формируя ее элементы в виде результата предоставляемой пользователем операции, выполняемой над элементами входной последовательности: гетр(а<е<с1азз 1п, с(ат Оиг, с(ат Ор> Ои! !гааз)огт (1п Г«зг, !и 1ам, Оиз гез, Ор ор) ( пИ1е()згзг! =!аз!) *гезеэ = ор(*у(гзс««); ге!ига гез; ) гетр)аге<с(от 1п, с1азз 1п2, с)ат Ои(, с(от ВтОр> Ои! !гааз!огт (!из)гзз, 1п 1азг, 1п2!згз!2, Оиг гез, В!пОр ор) ( н 1и1е ()тгзз! =1ам] *гез«е = ор ( «у)гзз««, "уггз12 ««) ! ге!игп гез; ) Алгоритм «апзгбгт(), читающий единственную входную последовательность для порождения значений элементов выходной последовательности, аналогичен алгоритму сору() .
Но вместо копирования значений элементов, он записывает результат операции над элементами. Мы даже могли бы определить сору() как «апзуогт () с операцией, возвращающей свой аргумент: !етрга!е<с(ат Т> ТЫепйу(сопз! Ть х) (гейгп х) ) гетр!осе<с!от 1п, с(ат Оиг> Ои! сору (1и у«ге!, 1п 1ат, Ои! гез) ( ге!ига «апз1огт (Вгзз, !аз!, гез, Ыепйу<гурепате Вегагог иайз<1п>:: га1ие гуре>) ) Явная квалификация Ыепйгу потребовалась для получения конкретной функции из функционального шаблона. Шаблон Вега!ог гга1« (519.2.2) используется для именования типа элементов, на которые указывает 1п. б35 ) 8.6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
