Б. Страуструп - Язык программирования С++. Специальное издание, 3-изд. Бином. 2004 (1160791), страница 127
Текст из файла (страница 127)
Алгоритмы и объекты-функции 574 Наконец, библиотека обеспечивает перестановку элементов в последовательности: Перестановки (ф 18.10) <а!дог11Ьш> пех! реппи!ат!оп () Следующая перестановка в лексикографичсском порядке ргео регтп!айоп () Предыдущая перестановка в лексикографическом порядке Кроме того, несколько обобщенных численных алгоритмов определены в <лишено> Я 22,6). В описании алгоритмов важны имена параметров шаблона. /п, Ои1, Рог, В! паап означают соответственно: итератор для чтения, итератор для записи, однонаправленный итератор, двунаправленный итератор и итератор с произвольным доступом Я 19.2.1). Ргег/ означает унарный предикат (условие),В(пргеп! — бинарный предикат Я 18 4.2), Стр означает функцию сравнения Я 17.1АЛ,Я 18.7.1), Ор — унарную операцию, В!пор — бинарную операцию Я 18.4).
Обычно для аргументов шаблонов использовались гораздо более длинные имена, однако я нахожу, что даже после короткого знакомства со стандартной библиотекой длинные имена ухудшают, а не улучшают читабельность. Итераторы с произвольным доступом могут использоваться как двунаправленные итераторы, двунаправленные итераторы — как однонаправленные, а однонаправленные итераторы — как итераторы для чтения или для записи Я 19.2.1). Задание типа, пе обеспечивающего требуемой операци!и, приведет к ошибке инстанцировання шаблона Я В.13.7). Указание типа, имеющего нужную операцию, но с неверной семантикой, приведет к непредсказуемому поведению программы во время выполнения Я 17.1.4). 18.3.
Последовательности и контейнеры Есть хороший универсальный принцип: то, что наиболее часто используется, должно быть самь!м коротким, легко выражаемглы и безопасным. Стандартная библиотека нарушает этот принцип во имя универсальности. Для стандартной библиотеки универсальность важнее всего, Например, мы можем найти два первых вхождения числа 42 в списке так: эоиЦ(Ив!<(пг> 6 И) ( 0 первое вхождение // второе вхождение Ие!<уп!>: хгега го г р =/)яд (И Ьеавгп (), И еод (), 42); (/(р!=И.епд()) ( Ив!<ел! свега!осд =/(пд(+<р, И ею!(),42), //... //... ) Если бы функция Япс! () была выражена как операция над контейнером, лля поиска второго вхождения нам бы понадобился какой-то дополнительный механизм.
Важно отметить, что обобщение такого <дополнительного механизмаь на каждый контейнер и каждый алгоритм нс так просто. Вместо этого стандартные библиотечные алгоритмы работают с последовательностями элементов. То есть на вход алгорьыма подается пара итераторов, определяющих последовательность 1последовательность— это как бы то, что находится между ними). Первый птератор ссылается на первый 575 18.3. Последовательности и контейнеры элемент последовательности, а второй указывает на «место сразу же за последним элементом» Я 3.8, 9 19.2).
Такая последовательность называется «полуоткрытой», так как она включает в себя первое из значений, на которые указывают итераторы, но не включает второе. Полуоткрытая последовательность позволяет выразить большинство алгоритмов, не выделяя в особый случай пустую послеловательность. Последовательность — особенно последовательность, допускающую произвольный доступ — часто называют диалазоноль Традиционньле математические обозначения для полуоткрытого диапазона — (первый, лоснедний) или [первый, последний(.
Важно, что последовательностью могут быть элементы контейнера или подпоследовательность контейнера. С другой стороны, многие последовательности, такие как потоки ввода/вывода, не являются контейнерами. Однако алгоритмы, выраженные в терминах последовательностей, прекрасно работают и с ними. 18.3.1. Входные последовательности иогй)'(1!яг<ягг!пд>8 Гги!1, йя1<я1г!ау>й снгик) гуре<(еХ11я1<кгггпд>лаопк1 11егаГогТ1; Гу неверно! О правильно Т ! р1 = Яп<1 (й"и!1. Ьеугп (), г!!гик.
ел<1 (), 'арр1е"), Т2 р2 =~3пг( (а!!гик Ьеу!и (), а!!гик впй (), 'рваГ) /уУХрз = фпй (р1, р2, "рвааЬ"), 0- О неверно! В приведенном выше примере две ошибки. Первая очевидна (если подозреваешь, что она есть), но компи.лятору вяяявить ее нелегко. Вторую нелегко рассмотреть в реальной программе даже опытному программисту. Сократив число явно используемых итераторов, мы облегчим задачу. Здесь я очерчу подход к проблеме, основанный па том, чтобы сделать понятие входной последовательности явным.
Однако, чтобы удержать разговор о стандартных контейнерах строго в рамках стандартной библиотеки, далее в этой главе я пе стану прибегать к явным входным последовательностям. Ключевая илея состоит в явном указании того, что на входе — последовательность. Например; 1'у стандарт 1етр1аге<с1аяя 1п, с(аяк Т> Тп йпг( (ТаТ) гя1, Та 1ая1, аоая1 ТЙ в) ( тЬ!1е фгк11=!аз! М '!ггял=в) -нТ)гя1; гв1игпТ)гя1; ) !!расширение 1втр1а1в<с1акк 1п, а!вяз Т> Тп Япг( 4кву<!п> г, аовк1 Т8 и) ( ге1ига Я па' (гЯгя1, г.
як со пй, и); Чтобы выразить понятие «все элементы контейнера х», обычно пишут х.бед!и (), х.епс((). Тем не менее такое написание может привести к ошибке. Например, когла используется нескол ь ко птераторов, легко создать алгоритм с парой аргументов, не образующих последовательность: 576 Глава 18. Алгоритмы и объекты-функции Вообще говоря, когда используется аргумент Укед, перегрузка Я 13.3.2) позволяет предпочесть версию алгоритма со входной последовательностью.
Естественно, входная последовательность реализуется парой Я 17.4.1.2) нтераторов: 1етр!иге<с!акк 7л> к1гис! 7кед риЬ!!краи <1л, 1л> ( 7кед (!л ! 1, 1л !2) ра!г<!л, 1л> (!1, !2) ( ) )' Мы могли бы явно сделать так, чтобы для вызова второй версии /)лс((), требовалась входная последовательность: 72р =/! лс! (1кед<И> (/ги!1 Ьед!л () Дги! !ел<! ()), "арр!е"); Однако, это еще утомительнее, чем прямо вызывать изначальную /)лс( (). Залачу облегчит простая функция-помощник. В частности, 7кед (входная последоватсльность) контейнера — это последовательность элементов от его начала (Ьедт ()) до конца (елг1 ()): 1етр1а1е<с!акк С> 1кед<Стйего1ог> !сер (С8 с) //для конгаейнера ( ге!игл |кед<С<иега1ог> (с.Ьед!л (), с.елй ()); Это позволяет нам выразить алгоритм лля контейнеров компактно и без повторений.
Например: ио!г!Я!!к1<к1плд> 8 !к) ( !!к! <к1 пад>21ега1ог р -ЯаХ (!к Ьеи!л З, !кепс! (), "стандарт ); !!к1<к1плд>:31ега1ог д =/(лс! (!кед (!к), "раст прение ) ) Нетрудно создать версию саед (), произв одягцую входные последовательности для массивов, потоков ввода и т. п. Я 18.13(6)). Основной выгодой от ввеления /кед является то, что зто делает понятие входной последовательности явным.
Непосредственный практический эффект здесь заключается в том, что !кед () устраняет болыпую часть утомительных и ведущих к ошибкам повторений, необходимых, чтобы выразить входные последовательности в виде пары итераторов. Полезно также и понятие выходной последовательности, однако оно не столь просто и не так нужно, как входная последовательность Я 18.13(7); см. также з 19.2.4).
18.4. Объекты-функции Многие алгоритмы работают с последовательностями при помощи только итераторов и значений. Например, функцией у!а<1 () мы можем найти в послеловательиости первый элемент со значением 7 следующим образом; пои!/(!!к1<!л1 й с) ( Ик1<!л1>спега1огр =Ял<1 (с Ьед!л (), с елс! (), 7), //...
577 18.4. Объекты-функции Чтобы сделать что-нибудь поинтереснее, мы можем захотеть применить эти алгорит- мы для выполнения какого-то своего кода (э 3.8А). Например, мы можем найти в последовательности первый элемент со значением меньшим, чем 7, так: Ьво1!еяя 1Ьап 7(тгэ) ( ге1игп э<7; во(г! 7 (!1я1<!п1' 8 с) ( Ия1<!п1>::!1ега1аг р =~те! !!(с Ьеу!и (), с.епс( (), !еяя 1Ьап 7); ) 1етр!а1е<с1аяя Т> с!взя Яит ( Т гея; риЫ!с; $шп (Т ! = 0): гея (й ( ) иоиуврегагог() (Тх)(геяе=х;) Т геяип () сопя1 ( ге1игп гея; ); О ин>швали залил 7! накоп>ение г>/ возвращение султи Ясно, что класс Зит предназначен для арифметических типов, для которых опреде- лены иницализация нулем н оператор л-=.
Например: воЩ(!!я!<с!оиЫеьй !д) 5ит<с!оиЫеь я; я = Тес еась (!г!Ьеу!и (), !с!епс(з, я); />> вь>зов яО длл каждого элел>енгла Ы сои1« 'суммаравна' «яхеяиИ() «>>и'; ) Здесь аког еасЬ () 18" 18.5.1) вызывает $ит<с(оиЫеьсорега1ог () (с(оиЫе) для каждого элементаЫ. Суть заключается в том, чтоуог еасй () в действительности не считает, что ее третьим аргументом должна быль функция.
Она полагает, что ее третий аргумент — нечто такое, что можно вызвать с соответствующим аргументом. Подходящим образом определенный объект может подойти тут так же, как функция — а иногда и лучше. Например, встроить (1>17!не) обращение к оператору () класса легче, чем функцию, Функции, заданные в качестве аргумента, могут быть самыми разнообразными: логические предикаты, арифметические операции, операции извлечения информации из элементов и т, и. Писать отдельные функции для каждого случая неудобно и неэффективно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
