Бьерн Страуструп. Язык программирования С++. Специальное издание (2011) (1004033), страница 22
Текст из файла (страница 22)
Как следствие, в стандартной библиотеке наряду с общеупотребительными контейнерами содержатся и общеупотребительные алгоритмы. Например, определив операции == (равно) и < (меньше) для типа Епегу, мы можем отсортировать вектор геегог<Епп у> и положить копии всех его уникальных элементов в список: Ьоо1 орегагог==(сопя(Епггуь а, сопгаЕпиуь Ь) ( ге(ига а.пате==Ь.пате» ) Ьоог орегаюг<(сопя(Епггуь а, сопя(Епггуь Ь) ( ге)игл а.пате<Ь.пате; ) гоЫ1(геегог<Епггу>ь ге, 1Гм<Епауьь 1е) ( хогг ( ге . Ьеййп ( ), ге . епй ( ) ) г ип(1ие сору( ге.Ьеягп О,ге.епй(),(е.Ьее1и () ); ) Стандартные алгоритмы рассматриваются в главе 18.
Они формулируются в терминах последовательностей элементов (яедиепсез оХе1етепгя) 52.7.2). Последовательность специфицируется парой итероторов, указывающих на ее первый элемент, и на «элемент, следующий за последним», В примере функция воет() сортирует последовательность элементов, начиная с ге.Ьее1п() и заканчивая ге.ело — здесь это соответствует всем элементам вектора ге. Для операции записи достаточно указать лишь первый из элементов, подлежащих перезаписи.
Если в операции участвует не один элемент, то будут перезаписаны все элементы целевого объекта, следующие за указанным. 3.8, Алгоритмы Можно также добавить новые элементы в конец контейнера: гоЫ у (гес<ог<Еп<гу> ь ге, !<з«Епиу> ь!е) зог<(ге. Ьее!л (), ге. еп<!() ) < илй!ие сору(ге. Ьеа!п (), ге. епд(),баса !лзег<ег(1е) ) < ) У добавить в конец !е гой!< (гес<ог<Епиу>ь ге, 1<м<Епагу>ь 1е) ( сору(ге.Ьее!п (),ге.ет!(),1е) < сору(ге.бее!л О г ге.еидО,1е.еп«О ) ! сору (ге. Ьеа!п ( ), ге.
еп<! ( ), 1е. Ьед!и ( ) ) < У ои<ибка< (е не итератор (< очень плохо: просто пии<ем за конец (< перезаписывает элемент»< 3.8.1. Использование итераторов Располагая контейнером, легко получить итераторы, указывающие на характерные элементы контейнера, например, вызвав функции Ьея!п () и еп<!() . Кроме того, многие алгоритмы возвращают итераторы. Например, стандартный алгорип<м у<и<!( ) ищет значение в последовательности и возвращает итератор, указывающий на найденный элемент. Используялп<!(), можно найти число вхождений символа в строку: <л< соил<(солги з<г!пяь з сйаг с) ( <п<л=б; з<г!ля <: сот< вега<ос <' = !)и<1(з.
Ьед(л (), з. ел<1(), с) <«Ь!1е ( <' (= з. елд () ) ( +«л< < = у)п<!(1+1,з.ел<!(),с) ге<игл и< ) Функция Япз!О возвращает либо итератор, указывающий на найденный элемент, либо итератор, указывающий на «элемент, следующий за последним», Рассмотрим, что происходит, когда вызывается функция соил<(): юй( <() ( з<г!пи т = "Магу Ьа<! а 1(и!е 1атЬ"; ила соил< = соил<(т, 'а' ) < С помощью Ьас!< !тег<ег() элементы добавляются в конец контейнера, при этом емкость контейнера автоматически расширяется до необходимых размеров (519.2.4).
Таким образом, стандартные контейнеры и Ьас!< имеггег() позволяют полностью избавиться от потенциально опасного управления памятью с помощью библиотечной функции геа11ос О языка С (816.3.5). Отметим, что если вы забудете про Ьасй ймег<ег() при добавлении элементов, то придете к разного рода ошибочным ситуациям.
Например: Глава 3 Обзор стандартной библиотеки 100 Первый вызов алгоритма угл!1() найдет символ 'и 'в слове Магу. В результате мы входим в цикл, так как возвращаемый при этом итератор указывает на внутренний символ строки и, естественно, не равен тел«!О. В цикле мы вызываемугл«!(), используя !+! для начального итератора последовательности, то есть продолжаем поиск с символа, следующего за ранее найденным символом 'а'. В результате циклических вызовов алгоритмаугл«!() мы находим три остальных символа 'а'.
В конце концов 3гл«!() возвратит значение, равное гьел!!(), так что условие ! '. = гнев«!() станет ложным и цикл завершится. Все это удобно проиллюстрировать рисунком: ГаПГ,,„) «:, т«) Ппэ ь! Здесь стрелки отображают начальное, промежуточные и конечное значения итератора ! Естественно, алгоритм!!и«!() будет работать аналогично с любым другим стандартным контейнером.
Поэтому мы могли бы обобщить функцию соил!() следующим образом: <етр!аге<с(ат С, с1аее Т> «п! соил!(соле! Сь г, Тхай ( гурепате С::солт дега!ог( ~1п«!(г.Ьеа!п(),г.еп«1(),ча1) г У(урепатеем. 3С!35 !лгл = О; и4«11е ( «! = г . ел«! ( ) ) «-ьпг +ь1;,У пропустить только что найденный элемент «=у!л«((«', г.епе((), га1); ) геиагп и; ) Вот пример, использующий новый вариант функции солги() (тил сотр!ехопределен в файле <сотр!ех>; Э3.9.), Э22.5): го!«! Г(11ег<сотргех<«гоиЫе»а 1с, нес!ог<е!г!ли>ь гх, егг(па х) ( т! 11 = соил!(1с, сотр(ох<«1оиЫе> (1,3) ); т! 11 = соил!(ге, "Сдгуэ!ррах" ); !п! «3 = соил!(е, 'х' ); ) На самом деле, нам нет нужды определять собственный функциональный шаблон соил!( ) .
Задача подсчета числа вхождений элемента настолько важна, что стандартная библиотека предоставляет соответствующий алгоритм. Для большей универсальности алгоритм соил!() из стандартной библиотеки принимает последовательность в качестве аргумента, а не контейнер. Так что клиентскую функциюу() следует переписать в следующем виде: 3,8, Алгоритмы 101 во[ау(!!в(<совр(ех<((оиЫе»ь 1с, чес(ос<в(г(пе>ь и, в(г(пе в) ( т( 11=саин((1с.
Ьее!п (),!с. еп(((), сотр(ех<((вийе> (1,3) ) ( !и( (2=саин( (и. бее[и ( ), и. еп(( ( ), "В!оленев" ); (п( !3=саин( (в. Ьея!п ( ), в. епй ( ), 'х ' ); ) Стандартный алгоритм соил(() может работать и со встроенными массивами, и с отдельными частями контейнеров. Например: воЫ е (сваг сл [ ), (п( вс) ( 1п( 11=саин((вся [О), ьсв [вс), 'с' ) ( Учисло символов г в массиве т( 12=саин( ( ьсв [ О), ьсв [т!2), ' с ' ); У число символов х в первой половине массива ) 3.8.2.
Типы итераторов Чем на самом деле являются итераторы? В общем случае, про них можно сказать, что это объекты некоторого типа. Фактически же, (нины у разных итераторов разные, так как конкретный итератор должен хранить информацию, позволяющую ему работать с конкретным типом контейнера. Типы итераторов могут отличаться в той же степени, в какой различаются типы контейнеров и цели, для достижения которых итераторы предназначены. Например, итераторы для контейнера вес(ог скорее всего есть просто встроенные указатели, так как их удобно использовать для ссылок на индивидуальные элементы вектора: итератор: вектор; В качестве альтернативы можно реализовать итераторы в виде пары — указатель на начало вектора плюс целочисленйое смещение: итератор: (начало==р, смещение == 3 вектор: Последнее решение позволяет реализовать проверку индексов 519.3). Итераторы для списков должны быть более сложными, чем просто встроенные указатели, так как элементы списков, в общем случае, не знают, где находится следующий элемент списка.
Итератор для списка, гипотетически, мог бы быть указателем на связь (йп[() между элементами: итератор. список: элементы: Глава 3, Обзор стандартной библиотеки 102 Общим для всех типов итераторов является их семантика и обозначения опера((ий. Например, если к любому итератору применить операцию +», то она вернет значение итератора, указывающего на следующий элемент. Аналогично, для любого итератора операция * возвращает элемент, на который настроен итератор.
На самом деле, любой объект, подчиняющийся некоторым требованиям, вроде рассмотренной семантики операций, и будет фактически итератором 519.2.1). Более того, пользователям в редких случаях нужно знать истинные типы итераторов; каждый контейнер сам «знает» типы своих итераторов и предоставляет их пользователям под стандартными именами Нега(ог и сопя( Нега(ок Например, для 1(в(<Еп(гу> общим типом итераторов является тип 11я(<Еп(гу>:: Нега(ог. Мне редко доводилось интересоваться деталями устройства этого типа.
3.8.3. Итервторы и ввод/вывод Итераторы являются очень обшей и полезной концепцией для манипулирования последовательностями элементов в контейнерах. Тем не менее, последовательности элементов встречаются не только в контейнерах. Например, входной поток образует последовательность значений; мы записываем последовательность значений в поток вывода. Как следствие, концепция итераторов естественным образом применяется ко вводу/выводу. Для создания итераторного объекта типа ов(гент Нега(ог мы должны указать, какой поток будет использоваться и каков тип выводимых в него объектов. Например, мы можем определить итератор, ссылающийся на стандартный поток вывода, соиг.
оз(гент Вега(ог<я(гтя> оо (сои(); Если мы что-то присваиваем выражению *оо, то смыслом такого присваивания является запись присваиваемого значения в поток сои(. Например: (п( таи( () ( *оо ="Недо, + <оо; *оо ="нег!(() т,п" ( ) ?? означает сои( «? "Не!1о, " ?? означает сои( «? "«о~ )д! )и" Ь(гент !(ега(ог<л(нпд> й (с!и); Так как входные итераторы (!при( ((ега(огз) неизменно используются парами, специфицирующими последовательность элементов, мы должны еще предоставить Можно сказать, что это еше один способ осуществить стандартный вывод «канонического текста» Не!!о, нюгЫ). Выражение +<оп имитирует запись в массив с помощью указателей.
Конечно, я не стал бы на практике использовать показанный код для решения столь простой задачи, но заманчиво сразу же показать работу с потоками вывода как с контейнерами <только для записи» (нг((е-оп!у соп(атег); вскоре эта идея должна стать очевидной (если не уже стала очевидной). Аналогично, о(гент !(ега(ог есть нечто, что позволяет нам работать с потоком ввода как с контеинером «только для чтения» (геа((-оп)у соп(атег). Мы должны указать используемый поток ввода и тип ожидаемых объектов: 3.8.
Алгоритмы 103 итератор, указывающий на конец ввода. Им является итератор типа иггеат Ье< а<ог, создаваемый «конструктором по умолчаниюгк Ьпеат !<ега<ог<з<ппе> еоз< Теперь мы можем ввести фразу Не1!о, июг1д), а затем вывести ее: сои«<з1« ' ' «з2« ' чп '; ) Вообще-то, итераторы типов оз<геат Ьега<ог и Ьпеат Ьеп»ог не предназначены для непосредственного использования. Они, как правило, используются в качестве параметров алгоритмов. Например, следующая простая программа читает файл, сортирует прочитанные слова, устраняет дубликаты и выводит результат в другой файл: // поток ввода (с з<гО; си 33.5.
! и з20 3. 7) // итератор ввода для потока // страж ввода аз<геев !з((гот. с з<г() ) < Ьиеат !<ега<ог<з<ппд> й(и) < Ь<геат !<ега<ог<з<ппе> воз< // Ь зто вектор, инициолизируемый вводом // сортируем буфер веиог<»ппд> Ь («', еоз) < ти(Ь.Ьеет (), Ь.еп<<() ) < о/з<геат оз(<о.с з<г() ) < //поток вывода озпеат дега<ос<»пня> оо(оз, "о<«) < //итератор вывода для потока ипй!ие сору (Ь. бед<я (), Ь.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
