Б. Страуструп - Язык программирования С++. Специальное издание, 3-изд. Бином. 2004 (1160791), страница 137
Текст из файла (страница 137)
Они предназначены для того, чтобы быть типами значений, возвращаемых соответственно операторами орегагог«() н орега1ог -> (), для некоторого итератора. Тип Иега1ог 1гаИя является ключом к упрощению многих опирающихся на итераторы интерфейсов и к эффективной реализации многих алгоритмов, 19.2.3. Категории итераторов Различные виды итераторов — обычно называемые категориями итераторов — укла- дываются в следующую нерархикх Дпя записи Однонаправленный и — Двунаправленный и — С произвольнымдоступом Для чтения Здесь тип результата выражается через Иега1ог 1гаИя входа.
Причина этого состоит в том, что не существует примитивов языка, которые могли бы непосредственно выразить один произвольный тип через комбинации других типов. В частности, нет способа негюсредственно выразить следующее: «тип, является результатом вычитания двух типов 1п». Вместо Иега1ог 1гаИя мы могли бы использовать для указателей специализированный счетчик соип1 (): Глава 19.
Итераторы и распределители памяти 818 0 для чтения // для записи я1гис1 триР Нега!от Рад(); в!тисР оиРриР Нега1ог Рву(); в1гис1/ог!иагй йега1от Рау: риЬПс шри1 йега1ог 1ау(); !утис!6!й!тес!!опа! йега1ог Рад. риЫРс/оттоатй нега!от Рад(); вттисггапйотп асееве йега1ог Рау: риЫгс 6Ыггеспопа! йета1ог Рад(), // однонаправленный //двунанравленный //с произволении досгпупол! Глядя на операции, поддерживаемые итераторами для чтения и итераторами для записи Я 19.2.(), мы можем предположить, что/оттоагй !Рета!от Рай (последовательный итератор) должен быть производным от ои!ри1 !Реги!от !айи три! !1ега1ог 1ай. Причины почему это не так, достаточно запутанны и, вероятно, не совсем логичны, Однако, я еще не видел примера, где бы такое наследование упростило реальную программу.
Наследование для всех этих классов-ярлыков (!ая — <ярлык>) полезно (только) для того, чтобы избавиться от определения различных версий функций, в которых несколько видов итераторов — но не все — могут использовать одни и те же алгоритмы. Рассмотрим, как реализовать й!в1апсе: 1егпр1а1е<с!авя Ь~> Рурепапье йега1ог Рта!Ря<!п>..й(Оегепсе !уре йгвгапсе (Рп/Ртвс, !п !авРР Есть две очевидные альтернативы: (1( Если!и — это итератор с произвольным доступом, мы можем вычестьЯгв! из (ав!.
Д В противном слу сае мы должнь! инкрементировать итератор от йгв! до (аз1 и подсчитывать расстояние, Эти две альтернативы можно выразить парой функций-помощников: 1егпр!а !е<с! о вв 2п> Рурепагпе йега1ог !га!!в<1п>зй((/егепсе 1уре й!в1 Бе!рег((п/!тв1,1п !авг, три! нега!от Рая! Рурепагпе !1егатог Ртаг!в<1п>гй!Цегепсе Руре й = О, кЬР!е (/!гв1<+~=!ав1(йч+; Оиспользуеитолькоинкреленгп ге1игп й; РепРр!а!в<с!аввР<ап> 1урепатпе Нега!от !та!!в<1п "й((Регепсе !уре Это не днаграыма наследования классов. Категория итераторов — это характеристика типа, основанная на том, какие операции он обеспечивает. Многие, в друючх отношениях не связанные между собой типы, могут относиться к одной н той же категории итераторов.
Например, и обыкновенные указатели (9 (9.2.2), п объекты класса С/Ресйей !!ег Я (9.3) являются итераторами с, произвольным доступом. Как отмечено в главе 18, различные алгоритмы требуют в качестве аргумента итераторов различных видов. Кроме того, один и тот же алгорРитм для различных видов итераторов иногда можно реализовать с различной эффективностью. Чтобы в случае перегрузки компилятор мог различать алгоритмы, основываясь на категориях итера- торов, стандартная библиотека обеспечивает пять классов, представляющих пять категорпй итераторов: 6!9 19.2. Итераторы и последовательности с!1я! Ье!рег(капЯя! !1ап 1аяг, галс!от ассеяя Нега1ог 1ау) ( ге1игп !ая1 — /!гя1; // опирае кся на произвольньл!! доспи!п ) Категории итераторов, указанные в качестве аргументов, явна определяют, какой из итераторов ожидается. Категория итератора используется нсклююп ельно для разрешения имен при перегрузке; она пе принимает участия в действительных вычислениях.
Этот механизм относится исключительно к компиляции. Вдобавок к автоматическому выбору функции-помощника этот прием обеспечивает непосредственную проверку типа Я 13.2.5)г Теперь очень просто определить с!1я1апсе () путем вызова соответствующей функции-помощника: 1етр!а!в<с!аяя 1п> 1урепате иега1ог гга!1я<!п>зс)фегепсе 1уре сйя!апсе (1п/л гя1, !и !ая!) ( ге!игп Ы!ли Ье!рег(/!гяг, !аяг, Мега1ог Ггаия гп>..!!ега!ог са!едой()), Чтобы вызвать Йя! Ье!рег, используемая категория !1ега1ог 1га11я<!п>гл1ега1ог са1еуогу должнабытьлпботри1 !1ега1ог 1аулибагапс!от ассеяя !1ега1ог 1ад. Однакодляпоследавательных и двунаправленных итераторов нет необходимости делать две различные версии Йя! !ле!рег(). Благодаря наследованию классов категорий эти случаи обрабатываются функцией-помощником аС!я! !ле/рег(), которая в качестве аргумента принимает гари1 !!его!ог 1ар.
Отсутствьсе версии с ои1ри1 л1егагог !ау отражает тот факт, что применительно к итераторам для записи !2!я1апсе () не имеет смысла: ооЩ(вес!от га1>й и', !1я! <л1оиЬ!е>й !с1, 1я!геат 11ега1ог<я1г!пу>й !я!, ся!геат 1!ега!о~, яазпу>й ся2, оя!геат !!его!ос<я!г!пд>й оя1, ояггеат пега!ос<я!глад>й оя2) // используелл илгоритлл с вь китаниелл //используелл алгорнпллл синкрекентолс // используелс алгоритлс с инкрелсентолл // ошибка: неправильния категория итератора, // тип аргумента для сдя! Ье!рег неверен с!!я! а псе (осбеугп (), и1.ел с! ()); с!ииапсе (!с!Ьеу!и (), Ы.епс)()); Йя!апсе (!я1, !я2); йя1апсе (оя1, оя2); Впрочем, в реальной программе вызов г(1я!апсе () для 1я1геат с1ега1ог, вероятно, не имеет большого смысла. Эффект будет таков: чтенве входа, выбрасывание входных значений и возвращение числа выброшенных значений.
Использование с!ега1ог 1га11я<Т>с1!ега1ог са1еуогу позволяет программисту обеспечить альтернативную реализацию, чтобы пользователь, которому нет никакого дсла до реализации алгоритмов, автоматически получал самую подходящую реализацию для каждой используемой структуры данных. Иными словами, это позволяет нам скрыть детали реализации за соответствующим интерфейсом. Для гарантии того, чта эта изящество достигается не ценой быстродействия, можно воспользоваться встраиванием. б20 Глава 19. Итераторы и распределители памяти 19.2.4. Вставки ()пвегтегв) Вывод данных через итератор в контейнер приводит к тому, что элементы, следующие за тем, на которые указывает итераторы, могут быть перезаписаны. Это может также принести к переполнению и, следовательно, к порче памяти.
Например: иоЫХ(иес1ою !пРй и) /1 !! и (иЬЬекгп (),200, 2), // присваивание 7 всел! эяелленталл и!(0) .ил(199) ) Если в Ы меньше 200 элементов, будет плохо. В заголовочном файле <!1ега1ог> стандартная библиотека предлагает решение этой проблемы; три шаблона классов итераторов плюс три функции (вставки), чтобы эти итераторы было удобно использовать: 1етр!а1е<с!аккСопР Ьасу !пкегг Кегагог<СопР Ьасй !пкеггег(Соп1йс); гетр!а1е<с!акк СопР/гош !пкегГ вега!ос<Соп1>/гоШ 1пкегеег (Сопгй с), 1етр!а1е<с!акк Сопг, с1акк Ои1>!пкегг Пега1ог<СопР спкегеег(Соп1й с, Ои1 р); Функция Ьасй (пкег(ег() добавляет элементы в конец контейнера,угол! !пкег1ег() добавляет элементы в начало, а «просто» вставка !пвег1ег() добавляет элементы перед своим аргументом-итератором.
В !пкег1ег (с, р) р должно быть действительным итератором для с. Естественно, с каждой вставкои значения контейнер растет. При записи вставка вставляет новый элемент в последовательность с использовани цем рикй Ьас/е (), рикй/гоп1 () или !пкег1 (), вместо того, чтобы перезаписывать сугцествующий. Например: иоЫ д (иес1ог тРй Ы) ( /)!! и (Ьасу !пкег1ег(ил), 200, 7); // добавяение 200 семерок в конец Ы Вставки столь же просты и эффективны, сколь и полезны. Например; 1етр!а1е<с!акк Соп1> с!аккткегг Нега1ог,риЫ!сйега1ог<ои1ри1 вега!ос гад, иоЫ,иоЫ,иоЫ, иоЫ>( рго1ес1ес): Сопгй санга!пег, // контеинер, в катар»лй вставляелл гурепате Соп1эйега1ог!1ег; //указывает на элелленты контейнера риЫлс: ехр!!с11 !пкегг йегагог(Сопгйх, 1урепалпе Соп1э11ега1ог !) : соп1агпег(х), пел. (л) () ЫкегГ Пега1огй орегагог — (сопк1 гурепате Соп1лиа1ие 1урей иа!) ( Нег = сои!а!пег.!пкегг (пег, иа!); »»!1ег; ге1игп '1Ык, 1пкегг йега1огй орегагог* () ( ге1игп *1Ык; ) !пкег1 11егагогй орега1ог»» () ( ге1игп "1ЬЫ; ) // арефа ясный.н.
621 19.2. Итерпторы и последовательности !ляегг пега!огорега!огв+ (!и!) уге1игп "1Ь!я;) //поспяриксный+~- Ясно, что вставки — это итераторы для записи. юпяег1 йега1ог — это особый случай выходной последовательности. По аналогии с !вед из 9 18.3.1, мы можем определтктпп 1етр!а1е<с!акк Сонг> !пяег1 йега1ог<Сон! океу (Солгй с, 1урелате Соппйегагою /сгя1, 1урепате Сол1зйе! а1ог 1ак1) ( //егаве1) объясняется в 6 16.в.6 гейвгл тяег! йегагог<Сонг> (с, с.егаке (/пя1, !акг)) Другими словами, выходная последовательность удаляет свои старые элементы и заменяет их выходными значениями. Например: по!<1/(йя1<шт>у й, пес!ос<!и!>й и) //заменяет вторую половину ш копией из у ( сору (16 Ьешп ~, 11 елй (), оксу (ш', и Ьеу!и () +тяпе ()/2, ой ела ())) ) Лргументом опек) должен быль контейнер, поскольку уменьшить размеры контейне- ра невозможно, имея только итсратор на его элементы 19 18.6, 9 18.6.3).
19.2.5. Обратные итераторы Стандартные контейнеры обеспечивают операции гЬеу!и () и гепг1 () для перебора элементов в обра~ном порядке Гв 16.3.2), Эти функции-члены возвращают итераторы типа геоегве йега1ог. 1етр!а1е<с! аяк йег с1аяв геиегяе йега1ог: риЬйс йега1ог 1урепате йега1ог 1гайк<йег>.йегагог сагеуогу, !урепате йега1ог !гайк<йег>яиа1ие 1уре, !урепате йега1ог !гайя<йег>: веселее 1уре, 1урслате йега1ог 1гайя<Нег>прош1ег, 1урепате йегааог 1гайк<Нег сге/егепсе> ( ргогес1ей; йег сиггеп1; //сиггеп1 указывает на элемент, // следуюи(ий за тель на которве ссылается *!Ь!я риЬйп 1урейе/Нег пега 1ог 1уре; геиегве йега1ог() сиггел1() () ехрйсйт еиегве пега 1ог (йег х) .
сштеп1 (х) () гетр1а1е<с!акк !У> геоегве йегагог (соля! гепегяе пега!ос<!)>Р х), сиггеп1 (х Ьаяе ())1) йегЬаяе () сопк1( ге1игп сиггел1; ) // значение шекутего итератора ге/егелсе орега1от () сопя!(йег1тр=сиггеп1; ге!игл* — Плр; ) рошгегорега1ог->() сопя!; 622 Глава 19. Итераторы и распределители памяти ге~егепсе орега1ог[) !Г!сЦегепсе 1уре п) сопв1, гевегве !1ега1огйорега1ог++ [)( — сиггеп1;ге1игп*гЬ(в;) //отметте: не++ гевегке 11ега1огорега1огьь (!лг) ( гевегке !1егагог1=сиггел1, — сиггепг; гетгп1, ) гевегве йега1огй орега1ог — [) [++сиггеп1, гевал *1Ь!в, ) // он~ме~лте: не— гевегке 11ега1огореги1ог — [!л1) ( гевегке 11ега1ог1=сиггеп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}
