Б. Страуструп - Язык программирования С++. Специальное издание, 3-изд. Бином. 2004 (1160791), страница 110
Текст из файла (страница 110)
Это приводит к минимальным затратам времени и памяти, и в то же время позволяет пользователю задействовать общность и на уровне контейнеров (как при подходе с общим базовым классом), и па уровне итера- торов (как при подходе со специализированными контейнерами). ЯТВ-подход в болыпой степени опирается на шаблоны.
Чтобы избежать чрезмерного повторения кода, для обеспечения общей реализации контейнеров, содержа!цнх указатели, обычно требуется частичная специализация Я 135). Глава 16. Организация библиотеки и контейнеры 500 !уредеу иЫэгеоегзе Ыега1огчуега1ог> геоегие !!ега1ог; 1урес1е~игс!эгеоегие !1ега1оксопз! Ыегагог> сопи! геоегие Пега!юг; !уредеТ1урепатеАэро1п!егрот1ег; !/укаэательнаэлэл~ент !уредер !урел а те Аэсопи1ро!п1ег сопз1ро!п1ег; 1уреде~1урепатеАчге~егепсе ге)егепсе; /!ссьыка на элемент !уреде1 !урепатеАэсопи! ге~егепсе сопи1 ге~егепсе; 1урепате С-оа!ие 1уре и = О, 1урепате С:холит Пега1огр -сЬеу!и 11; в!э!1е 1р!= с.епс! 111 1 и+= '!и; Нр; // начинаем с начала ,11' продолжаем до конца !1 полу чаем знач ение элемеюпа 11 указатель р будет укаэывагчь ,1! на следующий элемент ге1 ига з Необходимость добавлять 1урепате перед именами типов членов в параметрах шаблона раздражает.
Однако компилятор — вещь неодушевленная, и у него нет Ь Каждый стандартный контейнер определяет эти имена типов в качестве членов. Каждый определяет их способом, наиболее подходящим для своей реализации. Тип элементов в контейнере задается первым аргументом шаблона и известен как оа1ие 1уре.
Второй, необязательный аргумент а!!оса!ос 1уре определяет, как оа!ие 1уре взаимодействует с различными механизмами распределения памяти. В частности, он предоставляет функции, используемые контейнером, чтобы выделять и освобождать память для своих элементов. Распределители памяти обсуждаются в з 19А. Как правило, и1ве 1уре описывает тип, используемый в контейнере для индексации, а аЩегепсе 1уре — означает тип результата вычитания двух итераторов для контейнера. Для болыпинства контейнеров они'соответствуют з1ге 1 и р1гйЯ ! Ц 6.2.1). В приложении Д обсуждается поведение вектора, если распределение памяти или операции с элементами генерируют исключения.
С итераторами мы познакомились в э 2.7.2, более подробно они описаны в главе 19. Их можно представлять себе, как указатели па элементы контейнера. Каждый контейнер обеспечивает тип под названием 11ега1ог для указания на свои элементы. Он также предоставляет тип сопи! 11ега1ог, который используется, когда элементы не нужно модифицировать.
Как и с указателями, мы используем более безопасную версию с сопи! если нет каких либо причин поступать иначе. Фактические типы итераторов вектора определяются при реализации. Их очевидные определения для стандартного шаблона оес1ог были бы соответственно Т * и сопи1 Т *. Типы обратных итераторов для контейнера оес1ог конструируются из стандартных шаблонов геоегзе !1ега1ог Я 19.2.5).
Они представляют последовательность в обратном порядке. Как показано в 9 3.8.1, эти имена типов членов позволяют пользователю писать программу с использованием контейнеров, ничего не зная об их настоящих типах. В частности, они позволяют составить код, который будет работать с любым стандартным контейнером. Например: !етр1а1е<с1аии С> 1урепате Сгоа!ие 1уре кит 1сопз! СЬ с 1 501 16.3. Вектора другого способа узнать, что член типа аргумента шаблона является именем типа Я В.13.5).
Что касается указателей, префикс ' означает разымйнование итератора (9 2.7.2, 5 19.2.1), а +-ь — его инкремент. 16.3.2. Итераторы Как показано в предыдущих разделах, прн помощи итераторов программист может управлять контейнералзи, не зная фактических типов, используемых для идентификации элементов. Несколько ключевых функций-членов позволяют программисту найти концы последовательности элементов: 1етр!а1е<с!аяз Т,с1аяяд=а!!осагогкТ > с1аяяоес1ог( риЬИс.
0- // итераторы //указывает на первый элемент Иега1ог Ьеугп (); сопя! Иега1ог Ьедт () сопя1; // указывает на злемеюп, следующий за последним Иега1огепй(), сопя1 Иега1огепй() сопя1; //указывет на первый злемент в обратной последовательности геиегяе Иегагог гЬеу1п (); сопя1 геоегяе Иега1ог гЬеу1п () сопя!; // указывает на элемент, следуи!ий за погледним, в образпной последовательности геиегяе Иега1ог гепй (), сопя! геиегяе Иега1оггепй() сопя!; Пара Ьеу!п ()/епс! () выдает элементы контейнера в обычном порядке, то есть за нулевым элементом следует первый, затем второй и т. д, Пара гбеу!и ()/гепс! () выдает их в обратном порядке, то есть за и-1 элементом следует п-2, затем и-3 и т.
д. Вот как видит последовательность Иега1ог. (А)=(В)=( )=;..' Л вот как зту жс последовательность рассматривает геэегяе Иега1ог Я 19.2.5): гела () (С)~ДВ, ~ДА~~,' Это позволяет нам использовать алгоритмы, которым удобнее представлять последовательность в обратном порядке. Например: 1етр1а!е<с1аяя С> Гурепате Сзаега!ог/)пй !ая! (Сд с, 1урепате Ссоа1ие 1уре о) ( 1урепате Сагеоегяе Иега!ог И =/!пй (сгЬеу!п (), сгепй (), о); Глава 16. Организация библиотеки и контейнеры 502 //использувла аепд!), чтобы указать аане найдено» !/ (та == с, те од ()) те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урепате С:11ега1ог а = р. базе (); те!игл — 1; .Н.р; //внимание: инкрелаент Е++), о не декрелаент Š— ) ) ге!и л с.епд(); О используела с.епдЕ), чтобы указать «не найдено» ) Обратите внимание, что Сггеоегзе !Еега1огэто не тот же самый тип, что Сс!Еегагог.
16.3.3. Доступ к элементам Одним из важных аспектов контейнера оес1огпо сравнению с другими контейнерами является легкий и эффективный доступ к его отдельным элементам в произвольном порядке: 1етр1а1е«с)акк Т, с1акк А = а!!оса!от«л» с)азк оес1ог ( риЬЕ!с а 0- // доступ к злвлаенапалаа ге~етепсе арета!от() (кгее !уре п); // доступ без аароверки сопк1 те~егепсе орега1ог() (к!ее 1уре и) сопк1, ге~егепсе а1 (з!зе !уре п); // доступ с проверкой соле! геХегелсе а1(к!ее 1уре и) соле!; ге~егелсе) гол! (); // первый элемент )!ля геиегке !Еега1ог п'.базе () возврашает !Еега1ог, указываюаций на один элемент вперед позиции, на которую указывает г! Я 19.2.5). Бсз обратных итераторов пам бы пришлось писать явный цикл: 503 16.3. Вектора сопя1 ге/егелсезгоп1 () солИ; ге~егелсе Ьасй (); сопя1 ге~егелсе ЬасЬ () соля1! // последний элемент Индексация осуществляется орега1ог() () и функцией а! (); орега1ог() () обеспечивает доступ без проверки, в то время как функция а! () осуществляет проверку диапазона и возбуждает исключение оа! оу галде, если индекс выходит за его пределы.
Напри- мер; иоЫЯпесгог<1пГ>й и, !л1 !1, 1пг 12) Й'р ( /ог (!л!1=О;!<и.в!ее();!я-+)( //размер уже проверен: используях! и(!) без проверки ) //проверяем диапазон при дострпе о аг(!1) = и.аг(12); //- са1сЬ(ои! о/ галде)( // ошибка диапазона ) оо!сЦ(пес!от Йоид!е>5 и) ( с1оиЫе с! = и(и. я!ее ()]; // не определено: плохой индекс !Ге!<айаг> 1вг; сйагс= 1яг,!гол!() // не определено: список прет ) В стаплартных последовательностях обращение по индексу поддерживают только пес1ог и с(е!)ие Я 17.2.3).
Причина — желание не запутывать пользователей, предоставляя фундаментально неэффективные операции. Например, обращение по индек- Этот пример иллюстрирует одно из возмоэкных использований. То есть, если диапазон уже проверен, можно безопасно использовать оператор индексации () без проверки; в противном случае разумно использовать функциэо а1 (), которая проверяет диапазон, Это различие важно, когда большое внимание уделяется эффективности.
Когда она не играет роли, или когда не совсем очевидно, точно ли проверен диапазон, безопаснее пользоваться вектором с проверяющим диапазон оператором П (как Уес из 9 3.7.1) или итератором с проверкой Я 19.3). Доступ по умолчанию не производит проверки, чтобы соответствовать массивам.
Поверх быстрого доступа без проверки вы можете построить безопасное (с проверкой) средство, но вы не можете ускорить медленное срелство. Операции доступа возвращают значения типа ге/егелсе или солИ ге~егелсе в зависимости от того, применяются ли они к объекту типа солИ или нет. Тип ге/егелсе удобен для доступа к элементам. В простой и очевидной реализации контейнера оес1ог<Х>, ге~егепсе — это просто ХЯ, а солИ ге/егелсе — это просто сопя! Хй.
Эффект от попытки создания ссылки за пределы диапазона не определен. Например: '504 Глава 16. Организация библиотеки и контейнеры су может быть обеспечено и для списков !!з! Я 17.2.2), но это опасно неэффективно (то есть, О (и)). Функции-члены !гоп! () и Ьасй () возвращают ссылки на первый и последний элемент соответственно. Они наиболее полезны там, где эти элементы заведомо существуют, и в программах, где эти элементы представляют особый интерес. Очевидный пример — контейнер оес1ог, используемый в качестве контейнера з1асй Ц 16.б.б). Отметим, что функция /гоп!() возвращает ссылку на элемент, итератор которого возвращает функция Ьей!п(), Я часто представляю /гоп!() как первый элемент, а Ьейтп () — как указатель на первый элемент.
Соотношение между Ьасй () и епс( () не так просто: Ьасп () — это последний элемент, а епс( () указывает на позици!о элемента, следующего за последним. 16.3.4. Конструкторы Естественно, эес1ог обеспечивает полный набор (2 11.7) конструкторов, деструкто- ров и операций копирования: 1етр!а1е<с!азе Т, с!аяя А = а!!оса1от Т» с!аея иес1ог ( риЫ!с //... // конструкторы и пь т ехр!!с!1 оесгог (сопе1Ай А ()); //л копий иа! ехр!!с!1 оес1ог (е!ее 1уре л, соля1 Тй оа1 = Т (), сопя1 Ай=А ()); //!пдолженбытьитератором для чтения (2 !92!) 1етр1аге <с!азз Тл> оесгог(!п/!ге!,!и !ае1, сопз1Ай =А ()); //копирование ив (!гя1:!аз1( иес1ог (соля! иесгогй х); -оес1ог(); оес1огй орега1ог —. (сопе1 иесгогй х); 1етр!асе <с!аез Тп> //!и должен быть итераторол для чтения (2 19,2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
