Бьерн Страуструп. Язык программирования С++. Специальное издание (2011) (1004033), страница 111
Текст из файла (страница 111)
Вот как видится последовательность с помощью прямого итератора Вегасог: Ьедсп ( ) епсг() П П Х А вот как она представляется обратным итератором гечегзе Вегасог (519.2.5): гЬедсп ( ) П= гепс( ( ) ДВ ~~' ~ ~А~ ~~а Необходимость добавлять ключевое слово суреиате перед каждым именем типа из параметра шаблона весьма утомительна. Однако компилятор не экстрасенс, и у него нет иного способа узнать, что имя члена шаблонного параметра является именем типа 5С.13.5). Как и в случае указателей, операция * означает разыменование итератора (э2.7.2, з19.2.1), а операция ++ означает его инкрементирование. 536 Глава 16, Организация библиотеки и контейнеры Это позволяет использовать алгоритмы, которые просматривают элементы в обратном порядке.
Например: <етрЫе<сгазз С> <уре пате С:: Ыегагог)(пИ Ь<й ( Сь с, <уре пате С: < кайге <уре г) ( гурепап<е С: <гезегзе !ата<ог и =ЯпИ(с. гберп (), с. гепИ(), и) < з (и" == с. гепИ () ) ге<ига с. епИ (); р используем сет1Г) для индикации "не найдено" <урепате С:: бега<ос <' = и'. базе () < У извлекаем итератор из обратного итерра Гз!й25) гейип --« ) Для гегегзе 1гегагог, г1. Ьазе () возвращает 1<егагог, указывающий на одну позицию дальше, чем г1 Я (9.2.5).
Без обратных итераторов пришлось бы явным образом использовать цикл: <етр<а<е<с<азз С> гурепате С:: 1<ега<огу<пИ газе(Сь с, <урепате С<: га!ие <уре г) ( <урепате С«1<ега<огр = с. епИ ( ) ! <Уи<цем с конца в начало <гЬ!1е(р! =с. Ьее!и () ) <у(* р=ги) ге<ига р! ге<и<а с.епИ(); ) У используем с.епИО для индикации "не найдено" Обратный итератор — это совершенно обычный итератор, так что можно написать и следующий код: <етр<а<е<с!азз С> <урепате С::1<его<ос)<пИ 1аз<(Сь с, <урепате С: <иа!ие <уре г) ( <урепате С: <гегегзе йега<ог р = с.гЬее!и (); (<обход последов-ти в обратном порядке <оЬЙе(р)=с.гепИ() ) ( <у("р== ) ( <урепате С::бега<ос <' = р.Ьазе() ! гейип --<! ) l/вниз<ание< инкремент, о не декремент ге<ига с.еаИ( ) < Уиспользуем с.епИО для индикации "не найдено" ) Стоит подчеркнуть, что С:: гегегзе 1<егагог не тот же тип, что С:: пегагог.
16.3.3. Доступ к элементам <етр!а<е<с<азз Т, сгазз А = аНоса<ог<Т» сгазз гес<ог ( риЫ<с: У... о' доступ к элементам; Важным аспектом векторов по сравнению с другими контейнерами является возможность простого и эффективного произвольного доступа к его элементам: ) б.З. Контейнер типа нес(ог 537 ге~егепсе орегагог[] (зйе гуре и); //доступ без проверки салаг гегегепсе орега1ог[] (в[хе рре п) <олег; // доступ с проверкой сопя; // первый элемент ге~егепсе а1 (мге зуре и) 1 соим геуегепсе аз(ягЕ 1уре и) геуегепсеугоп1 () ) сопл( ге/егепсе Ггопз () сопв11 гегегеисе Ьасй(); соля гегегеисе Ьасй() соиз1; //...
)1 // последний элемент Индексирование выполняется как операцией орегагог(] (), так и именованной функцией-членом аг(); при первом варианте доступа контроля выхода за границы индексов не происходит, а во втором при этом генерируется исключение опт о1"' галие.
Например: иоЫЯиесзог<!п1>а и, т1 11, !п1 12) 1гу 1ог (1пг 1=01 г' < и. Ясе () ) 1++) ( //здесь диапазон гарантирован: используем иЯ без проверки // доступ с проверкой диапазона и . а1 (11 ) = з . а1 ( 12) 1 /... ) сагой (оиг о/' галде) ( // оорз: ошибка диапазона Здесь иллюстрируется идея о том, что если диапазон индексов уже проверен, то можно безопасно использовать операцию индексирования; в противном случае, будет разумно применить функцию аг(), осуществляющую соответствующую проверку.
Такие различия важно принимать к сведению в случаях, когда важна эффективность. Если же эффективность не столь важна или неизвестно, был ли проверен диапазон индексов, можно применить вектор с операцией индексации, проверяющей диапазоны (см. шаблон [/ес из 53.7.2) или итератор с проверкой 519.3). По умолчанию доступ к элементам осуществляется без проверок (как для встроенных массивов). Поверх быстрого средства всегда можно построить безопасное (с проверкой) средство, а вот поверх медленного быстрое построить невозможно.
Операции доступа возвращают значения типа геУегеисе или сева геуегепсе в зависимости от того, применяются ли они к константному или неконстантному объектам. Тип геуегепсе — это некоторый тип, удобный для доступа к элементам. В простой реализации контейнера весгог<Х> тип г4егепсе есть просто Ха, а сопя геуегеисе есть сопя Ха. Результат попытки создания ссылки за пределами допустимого диапазона индексов не определен. Например: Глава 16. Органиэация библиотеки и контейнеры 538 чей! Г(чес<ог«<оиЫе> ь ч) ( <<оиЫе << = ч (ч.з!ге () ) ) УУ не определено: плохой индекс 1!з«сйаг> Ьа< сваг с = м<.)гоп<(); ) У не определено: !Ы< - пустой 16.3.4.
Конструкторы Естественно, что чес<ог обеспечивает полный набор конструкторов (511.7), деструктор и операции копирования: <етр<а<е<с1азз Т, с<вез А = а!!оса<ос< Т» с1азз чес<ог ( риЫ!с: уу ... У конструкторы и т.п. ехр!!с!< чес<ог(сопл< Аь = А () ); ехр1кй чес<ог(зйе <уре и, сопл< Ть ча!=Т(), сопл< Аь=А () ) < УУп копий ча< <етр<а<е< с1азз Тп > УУ 1п - итератор ввода ГЗ!9.2.!) чес<ог(1п )<гз<, 1п 1аж, сопл< Аь = А () ); УУ копирование из !<<ге«1аз«' чес<ог (сопз< чес<огЬ х) < -чес<ог() < чес<огь орега<ог= (сопл< вес<ось х) УУ 1п - итератор ввода Д!9.2.!) УУ копирование из фгз«!аз<! <етр1а<е<с1азз Тп > чо!и азз!хп (1п !<гз<, Тп <аз<) < чоЫ азз<еп (зйе уре и, сопл< Ть ча1); УУ и копий ча! уу ... )< Контейнер чес<ог обеспечивает быстрый доступ к произвольному элементу, но изменение его размера является дорогостояшей операцией.
Поэтому при создании вектора ему лучше явно приписать начальный размер. Например: Из стандартных последовательных контейнеров только вес<ос и <!еаие (517.2.3) поддерживают индексирование. Это сделано для того, чтобы не смущать пользователей реализацией заведомо неэффективных операций. Например, можно конечно предоставить операцию индексирования списков (517.2.2), но эта операция весьма неэффективна (порядка 0(п) ). Функции-члены)<оп<() и Ьас1<() возврашают ссылки на первый элемент и последний элемент, соответственно. Они наиболее полезны в случаях, когда заведомо известно, что эти элементы сушествуют, и когда эти элементы представляют особый интерес. Очевидным примером является контейнер чес(ог, используемый как стек (515.3.5).
Заметьте, что бои<О возвращает ссылку на элемент, для которого Ьея<п() возврашает итератор. Я часто представляю себе)<оп<() как первый элемент, а Ьея(п () — как указатель на первый элемент. Соответствие между Ьасй () и ел<1() менее очевидно: Ьас!<() — это последний элемент, а еп<!() указывает на позицию элемента, расположенного в памяти за последним элементом. ) 6.3. Контейнер типа нес(ог гесса«<1(есо«0> и (10000); гоЫ С'(спс «1, исс «2) ( вессог<1пс> Ы («1) с весгог<лоиЫе>* р = пеш гесгог<сгоиЫе> («2) ) Элементы векторов, создаваемых таким образом, инициализируются конструкторами по умолчанию (соответствуюшими типу элементов).
То есть каждый из 10000 элементов контейнера вг инициализируется при помощи конструктора ссесогс((), и каждый из «1 элементов контейнера Ы инициализируется с помощью 1пс() . Заметьте, что для встроенных типов выполняется умолчательная инициализация соответствующим нулем (84.9.5, 86.2.8). Если у типа нет конструктора по умолчанию, невозможно создать вектор с элементами этого типа без явного указания значения всех элементов.
Например: оса««)чит // любая точность ( риЫ)с: )чит (!опя); // нет улюлчательного конструктора // ... )с гессог<Юит> «1 (1000); //еггог: нет умолчательного конструктора гессог<Ь/ит> «2 (1000,)чит (0) ) с // о/с Поскольку веюиор не может иметь отрицательное число элементов, его размер должен иметь неотрицательное значение. Это отражено в требовании, чтобы для вектора тип «1«е суре должен быть беззнаковым типом (ип«1яяес(). Это в некоторых аппаратных архитектурах допускает больший диапазон размеров векторов. Однако это может приводить и к сюрпризам: гоЫ 1'(тс с) ( гесгог<сваг> всО (-1) с //здесь компилятору легко выдать предупреждение ге<час<сваг> гс1(1); ) гоЫО() ( 2'(-1): // обманываемЯ, передавая ей большое положительное число! При вызовеу(-1) число -1 преобразуется в (довольно большое) положительное число (йС.6.7).
При удаче компилятор может и предупредить нас об этом. Размер веюиора можно указать неявно, предоставив начальные значения элементов. Это выполняется передачей конструктору интервала, по которому и нужно создать контейнер типа гессог. Например: гойЦ(соп«с 0«л<Х> ь Ьж) ( вессог<х> г! (1«с.бел!и (), 1«с.епсс() ) с //копируем элементы из й«с Глава ) б. Организация библиотеки и контейнеры 540 сааг р [ ) = "Неера(г" ! «есгог<сааг> «2(р, ар[э!сео1(р) -1) ) ! Укопируем символы иэ С-строки ) Конструктор класса «естог подгоняет размер создаваемого вектора под количество элементов из предоставленного интервала. Конструкторы класса «есгог, принимающие единственный аргумент, объявляются с модификатором ехрйсй во избежание предотвращения случайных преобразований [011.7.1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
