Б. Страуструп - Язык программирования С++. Специальное издание, 3-изд. Бином. 2004 (1160791), страница 136
Текст из файла (страница 136)
Составьте список студентов, не изучающих науки. Составьте список студентов, изучающих французский и математику, но не изучаюп1их ни английский, нп биологию. (*1.5) Напишите функцию гетоое (), которая бы действительно удаляла элементы из контейнера. - Итераторы и распределители памяти Структуры данных и алглригпмы могут работать вместе только наглому, что они ничего не знают друг о друге, — Алекс Степанов Итераторы и последовательности — операции над нтераторами — свойства итераторов — категории итераторов — вставки — обратные итераторы — итераторы потоков — итераторы с проверкой — исключения и юггоритмы — распределители памяти — стандартный распределитель памяти — пользовательские распределители памяти — низкоуровневые функции для работы с памятью — советы — упрюкнения.
19.1. Введение Итераторы — зто клей, который удерживает контейнеры и алгоритмы вместе, Итераторы обеспечивают абстрактный взгляд на данные, так что создателю алгоритма нет необходимости заботиться о конкретных деталях всех возможных структур данных. И наоборот, обеспечиваемая итераторами стандартная модель доступа к данным освобождает контейнеры от необходимости предоставлять более широкий набор операций доступа. Подобным же образом, распределители памяти используются для того, чтобы при реализации контейнеров оградить разработчика от знания подробностей доступа к памяти.
Итераторы поддерживают абстрактную модель данных как последовательности объектов (~ 19.2). Распределители памяти обеспечивают отображение низкоуровневой модели, представляющей данные как массив битов, в высокоуровневую объектную модель Я 19.4). Самая распространенная низкоуровневая модель памяти поддерживается всего несколькими стандартными функциями Я 19.44). Итераторы — зто понятие, с которым должны быть знакомы все программисты. И напротив, распределители памяти — зто служебный механизм, о котором программисту редко нужно беспокоиться, и мало кому,из программистов когда-либо понадобится писать новый распределитель памяти. 614 Глава 19.
Итераторы и распределители памяти 19.2. Итераторы и последовательности Итератор — это чистая абстракция. То есть все, что ведет себя, как итератор, и есть итератор (ь 3,8.2). Итератор абстрагирует понятие указателя на элемент последовательности, Ключевые концепции итсратора таковы; «текуший указываемый элемент> (косвенное обрашение; представляется операторами * и ->); «указать на следуюший элемент» (инкремент; представляется оператором++), ° равенство (представлястся оператором ==).
Например, встроенный тнп т1* — это итератор для 1п1[1, а класс!и1<т(>с[1ега1ог— итератор для класса Йз1<[п1>. Последовательность — это абстракция понятия «нсчто такое, что мы можем перебирать от начала до копна, используя оператор получения следующего элемента»: Ье81пО еп[1О [ [[[ [ 'с [ [2! ].з,.
[ [[ [ -[[[' Примерами последовательностей служат массивы (ь 5.2), вектора Я 16.3), односвязныс списки Я 17.8[171), двусвязные списки Я 17.2.2), деревья Я 17.4.1), потоки ввода Я 21.3.1) и вывода Я 21.2.1). Каждая последовательность имеет свой вид итераторов. Итераторные классы и функции объявлены в пространстве имен эЫ и находятся в заголовочном файлс <вега(ог>.
Итератор не является обычным указателем. Скорее это абстрагированное понятие указателя на массив. Понятия «нулевой итератор» не существует. Проверку, указывает ли итератор на некоторый элемент или нет, принято делать путем сравнения его с концом даннои последовательности (а не с пай). Это упрошаст многие алгоритмы, избавляя от необходимости особого учета конца, и хорошо обобщается до последовательностей произвольных типов. Итератор, указывающий на какой-то элемент, называется действительным и через него можно получить доступ к элементу (при помощи ', [~ или ->).
Итератор может быть недействительным потому, что: не был инициализирован; указывает на контейнер, который явно или неявно изменил свои размеры Я 16.3.6, э 16.3.8), контейнер, на который он указывает, уничтожен; итератор обозначает конец последовательности. Конец последовательности можно представлять себе как итератор, указывающий на воображаемый элемент, слсдуюший за последним элементом в последовательности (опе-разг-сйе-1азс е1егпепс) (э 18.2). 19.2.1. Операции с итератораали Не все виды итераторов поддерживают один и тот же набор операций.
Например, чтег[ие требует лругих операций по сравнению с записью, а оес1ог позволяет »случить удобный и эффективный произвольный доступ способом, который был бы очень дороп[м для Йз1 или [зсгеат. Поэтому мы разобьем итераторы на пять категорий в 615 19.2. Итераторы и последовательности соответствии с операциями, которые они могут эффективно обеспечивать (то есть за постоянное время; 9 17.1).
Итераторы: операции и категории Ъ|о!тесн)опа) ганс)ощ-ассеяя двуна- с произвольным правленный доступом В! Кап оц1рцг гпрц1 !огзчаго' для записи для чтения однонаправленный Сокращение: Ои! !и гог -' [) р= ++ — + Чтение: Доступ: Запись: Итерация: Сравнение: »= <= И чтение, и запись производятся через итератор, разыменонывасмый при помощи *: // запись х через р //считывание в х через р 'р=к; к-'р; 1етр!а1е'с!аяя !п' Еурепате Пега1ог ггапя<!и>" с!Яегепсе гуре Йягапсе (!и/тяг,!и !ая1) ( !урепате Ыега1аг П а!1я<!п>зйДегепсе 1уре а! = О, тй!!е (/1гяР и-!аяГ) Нч+; ге1игп Й ) Чтобы выражать расстояние между элементами, для всех итсраторов 7п определен тип Вега1ог 1га!1я<В1ьсс!Яегепсе 1уре, Я 19.2,2).
Функция, приведенная ныше, названа йя1апсе (). а не орега1ог- (), потому что операция, выполняемая ею, довольно дорога, а все необходимые для итератора операторы выполняются за постоянное нремя (9 17.1). Подсчет элементов один за другим — это не тот вид операции, которьш я могу позволить себе нечаянно вызвать для большой Чтобы быть итсраторным, тип данных должен обеспечивать соответствующий набор операций. Эти операции должны иметь именна тот смысл, который обчячно подразумевается, Та есть каждая операция должна производить тот жс эффект, какой ана производит на обыкновенный указатель, Независимо от своей категории, итератор может позволять как констатный, так и неконстатный доступ к объекту, на который указывает.
Прп помощи итератора на сопя1 вы не можете писать в элемент, к какой бы категории итератор не относился. Итератор обеспечинает набор операций, по окончательным судьей, решающим, что можно сделать с элементом, является тип элементов, на которые указывает итератор. При чтении и записи объекты копиру!отея, поэтому типы элементов должны иметь обычную семантику копирования (9 17.1.4). Прибавлять (или вычитать) целое для относительной адресации можно только применительно к итераторам с произвольным доступом. Однако, если нс считать итераторон для записи, расстояние между двумя итераторами всегда можно найти путем перебора (из ерпрования) элементов. Для этого предназначена функция Йя1апсе (): 61б Глава 19. Итераторы и распределители памяти последовательности. Для итераторов с произвольным доступом библиотека обеспечивает гораздо более эффективную реалузацию функции с(!я1апсе ((.
Подобным образом предоставляется функция а!1оапсе ((в качестве потенциально медленного оператора «-=: 1етр1асе<с1аяя 1л, с!аяя В!я1> ио!й асЬапсе ((па 1, !1!я1 л(; // !»=л 19.2.2. Свойства итераторов гетр!а1е<с!аяя йег> з1гис! йега1ог !ганя ( 1урес!е! 1урепате йег> йегатог са1еувгу йега1аг сагедогу; гуре<!е/1урепате йег..иа!ие суре иа!ие 1уре, гурес!е/1урепатейегяЩегепсе 1уре ЙЯегепсе 1уре; гуре<!е/1урепатейегсротсег ро!п1ег; //возвраи!аелтй тил оператора -> 1урес!е~1урепатейеп>ге~егелсе ге~егелсе; //возвраи!аепый тип оператора '(! //~ !у.г.у //тип элелеюпа Тип сгсЯегепсе 1уре — это тип для выражения разности между двумя итераторами, а йега1ог са1едогу — это тип, показывающий, какие операции итератор поддерживает.
Для обьп<новенных указателей предоставляются специализации (9 13.5) для <Т*> и <соля1 Т'>, В частности: гетр1аге<с1аяя Т яггис1 йегагвг 1га!1я<Т'> ( //специализация для указателей 1урес!е/ галс!от ассеяя йега1ог 1ау йега1ог са1еуогу; 1урес(е~Т иа1ие 1уре; 1урег!е/р1гсЦ3 1 ЙЯегепсе 1уре; 1урейе/Т' рогл1ег; 1урег!е/ТЙ ге/егепсе; ); То есть разность между двумя указателями представляется стандартным библиотечным типом р1гс((!1" 1 из <ся11!г!е/> Я 6.2.1), и указатель обеспечивает произвольный доступ Я (9.2.3).
Имея тип йега1ог 1гайя, мы можем написать программу, зависящую от параметра-итератора. Классический пример — алгоритм соип1 (! (сосчитать): !етр!а1е<с!аяя1п, с!аяя Т 1урепате !1ега1вг 1га11я<1п>сЩегепсе 1уре соип1(1пягя1, 1п !ая1, сопя! ТЬ иа!( ( сурепате йегагог 1га!1я<1п>::ЩХегелсе 1уре гея = 0; свл!!е у!гя1!=!аяг((/('Лгягн-==па!(-нгея; ге1игл гея; Мы пользуемся итераторами, чтобы добраться до информации об объекте, на который они указывают, и о последовательности, па элементы которой они указывают.
Например, через итератор мы можем косвенно обратиться к объекту и манипулировать им, а также можем найти номер элемента в последовательности по описывающему его итератору. Чтобы выразить такие операции, нам нужно уметь работать с типами, возникающими при рассмотрении итераторов, как, например, «тип объекта, на который ссылается итератор» и «тип, обозначающий расстояние межлу двумя итера- торами».
Связанные с итератором типы описываются неболыпим набором объявленпй в шаблоне класса йега1ог 1 айя; б17 19.2. Итераторы и последовательности 1етр!а1е<с!аяя 1п, с!аяя Т> 1урепате 1п: йЯегепсе 1уре соил!(1пЯгя1!и !ая1, сопя1 Тй иа!); 1етр!а1е -с!аяя1п, с!аяя Т> р1гй!!Т 1соип1<Т', Т>(Т'/1 гя1, Т' !ая1, сопя1 Те, оа!), Однако так бы решилась проблема только для соип1 () Если бы мы воспользовались этим приемом для дюжины алгоритмов, информация о типах расстояния вызвала бы дюжину репликаций, а, как правило, лучше представлять принятое проектное решение в одном месте Я 23,4.2).
Тогда, при необходимости, и изменить его можно в одном месте. Так как тип Иега1ог 1гаИя<11ега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г = 7, с1аяя кег'= ть,> //у !9.2,3 // тип элемента // тип разности итераторов // возврои!пельш тип оператора — > // возврощаельа тип оператора * Отметим, что ге~егеявсе и ро!п1ег — не итераторы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
