Б. Страуструп - Язык программирования С++. Специальное издание, 3-изд. Бином. 2004 (1160791), страница 113
Текст из файла (страница 113)
Однако часто мы обращаемся к элементам вектора по индексу. Как нам получить итератор, подходящий в качестве аргумента для функций егазе () или спзег1 (), для элемента с индексом 7 в контейнере с типа оестог [или полобного оес1ог)? Поскольку это седьмой элемент от начала, правильный ответ — с. Ьву/п ()+ 7. Других альтернатив, которые могут казаться разумными по аналогии с массивами, следует избегать. Рассмотрим разные возможности; 1етр!ате<с!азз С> оо!с!/(Сб с) ( 513 16.3. Вектора 0- ); В любой момент времени вектор содержит информацию о числе элементов. Это число мохсно узнать, обратившись к функции яйае(), и изменить функцией геясге ().
Та'ким образом пользователь может определить размеры вектора и изменить их, если они кажутся ему недостаточными или избыточными. Например: с!аяя Н1я1оугат ( овс1ог<тя> соипй риЬНс: Нгя гаага т фпг Ь): сои п1 (тах (Ь, 8)) ( ) оосс( гвсога (шя 4~; ,Ч... вой Н1я~одгатсгвсогд(тм) ( сд' (! <О) ~ = 0; Ясоипаясхв()<=~) соипйгвяае (М); О выделяет много помята соипя[г!++; ) Использование гея(хе (] для песбог очень похоже на применение функции геайос () из стандартной библиотеки С для С-массива, располагаемого в свободной памяти.
Когда размеры вектора изменяются в соответствии с большим (или меньшим) числом элементов, все его элементы могут переместиться в новую область памяти. Следовательно, хранить указатели на элементы в векторе, который может изменять свои размеры — идея неудачная, так как после функции гея1ге () зги указатели могут указывать на незанятую область памяти. Вместо этого мы можем хранить индексы. Отметим, что операции рияй Ьаси (), швег~ () и егаяе () в неявном виде изменяют размеры вектора. В дополнение к хранению элементов реализация может выделять некоторую область памяти для потенциального расширения.
11 рограммист, считающей, что такое расширение вполне вероятно, может приказать контейнеру пвсуог зарезервировать место для будущего расширения, используя функцию геявгпе (). Например: янис~ Еий ( Еий' пехб ИпЬ (Ыпд* п=0): похе (и) ( ) ~!- овссог<ялпЬ> о; ооЫсйаш (язхв Г и) // заполняет о и злел~ентал~и типа( туг, // квак чтобы каждый ЫпА указывал на првдшвствуюи1ий ( о.геявгов (и); ирияЬ ЬасЬ ЯшЬ(0$ Хог (!пП = 1; т<п; 1++) о.рияд ЬасЬ 'я.1пЬ (йод — Ц), П- Глава 1б. Организация библиотеки и контейнеры 514 О копия и с емкостью пп умолчанию 77 теперь и имеет емкость по дмоляанию (ели 9 15.3,9) эес1ог 1тр =ел жегаар (1тр); Контейнер пес(ог получает необходимую для его элементов память путем вызова функций-членов своего распределителя памяти (9 19А.2) (переданного, как параметр шаблона).
Распределитель памяти по умолчанию, называемый а(!оса!ос (5 194.1), использует для выделения памяти оператор пеш, так что если памяти больше нет, будет возбуждено исключение бас( а(!ос, Другие распределители памяти могут использовать другую стратегию (см. 9 19А.2). Функции гезегтле () и сарае!1у () уникальны для контейнера эес1ог и схожих компактных контейнеров. Контейнеры типа списков ничего подобного не обеспечивают. 16.3.9. Другие функции-члены Во многих алгоритмах — в том числе и важных алгоритмах сортировки — нужно менять элементы местами (зшарр1пя).
Очевидный способ такой «перемены мес~ь (э 13.5.2) — просто копировать элементы. Однако пес1ог, как правило, реализуется структурой, которая действует как дескриптор ()ланс()е) для элементов (5 13.5, 9 17.1.3). Таким образом, два вектора могут быть переставлены более эффективно путем обмена их дескрипторов; это делает функция пес1огэзшар (). Разница во времени выполнения между этой функцией и зшар () по умолчанию в важных случаях отличается па несколько порядков; 1етр!а1е<с!аее л, с!аеа А = а!!оса!от!" > с!аее иесгаг ( Вызов жгезелте (и) гарантирует, что прц увеличении и не понадобится никакого выделения памяти, пока п.з!ге () не превзойдет и.
Резервирование памяти заранее имеет два преимущества. Во-первых, даже самая бесхитростная реализация может сразу выделить достаточно памяти одной операцией, а не требовать все время дополнительного выделения. Во-вторых, во многих случаях существует н логическое преимущество, которое перевешивает соображения эффективности. При возрастании пес!ос элементы контейнера потенциально переносятся в другое место в памяти. Таким образом, связи установленные между элементамн в в предыдущем примере, гарантируются только тем, что обращение к функции гезетле () обеспечило отсутствие всякого выделения памяти, пока шло построение вектора, Итак, в некоторых случаях гезелъе () кроме преимуществ в эффективности дает гарантию корректности.
Той же гарантией можно воспользоваться, чтобы быть уверенным, что исчерпание памяти и потенциально дорогое перераспределение элементов состоится в предсказуемый момент. Для программ реального времени это может быть очень важно. Отметим, что функция гезегпе () не изменяет размеры вектора.
Таким образом, ей не приходится инициализировать каждый новый элемент. В обоих отношениях эта операция отличается от гез!ге (). Так же, как з!ге () выдает текущее число элементов, сарасйу () сообщает нам текущее число зарезервированных мест; с.сарае!1у ()-с,з!ге () показывает, сколько еще элементов можно вставить без перераспределения памяти. Уменьшение размеров вектора не уменьшает его емкости. Просто остается больше места для увеличения вектора впоследствии.
Чтобы вернуть память системе, нужно сделать следующий трюк: 515 16.3. Вектора раЬЕ!с: О.. иоЫ стар (иестогй); а11оса1ог 1уреде1 аПоса!ог() сопс1; ); Функция де1 абоса1ог() дает программисту возможность управлять размещением вектора (Ь 16 3 1, 5 16 ЗА), Как правило, смысл этого — гарантировать, что данные пз прикладной программы, связанные с векторами, распределены в памяти схожим образом (также как и вектора) (5 19А.1). 1б.3.10. Функции-помощники Два вектора можно сравнить при помощи операторов == и <; 1етр1а1е<с1 ее Т, с!лез А> Ьоо!сЫ; орегатог== (сопИиестог<Т,А йх, сопл! иес1ог<Т,А>йу), 1етр!а1е<с1аее Т; с1аее А' Ьоо! еЫ сорега1о~ (сопе1 иес1ог Т,А>й х, сопс1 иес1ог<Т,А>й у); Два вектора и1 и и2 считаются равными (==), если и1.е1хе ()==и2.е!ге () и и1[п)==и2[п) для любого допустимого индекса и.
Аналогичным образом, < — это лексикографическое упорядочивание. Иными словами, оператор < для векторов можно определить так: 1етр1а1е<с!аее Т, с!аее А> !п!1пе Ьоо! еЫ.орего1ог< (сопл! пес!о г< Т А> й х, сопИ иесгог<Т А>й у) ( гетагл 1ехыоугарЫса! сотраге(сЬедгп(),х ел<!(),у Ьедш(),уел<1()); Ося. >' !Ь у ) Это означает, что х меньше д, если первый х[1), не равный соответствукнцему элементу у[1), меньше, чем у[1), илн х.яхе ()<у.л1хе () при равенстве всех х[1) соответствующим д[!).
Стандартная библиотека также предоставляет операторы!=, <55 > и >= с определениями, соответствующими -= и <. Поскольку функция ешар() — член класса, она вызывается с синтаксисом и1.зтоар(и2). Олнако не любой тип имеет функцию-член яшар (), поэтому в обобщенных алгоритмах пользуются общепринятым синтаксисом яшар (а,Ь). Чтобы заставить это работать и для векторов, стандартная библиотека обеспечивает специализацию; 1етр1а1е<с1аее Т, с!асс А> иоЫ еЫ,,стоар (иестог'Т А' й х, иес1ог Т А>й у) ( х стар (у), ) 1б.3.11. чес1ог<)зоо(> Специализация (6 13,5) иесгог<Ьоо1> вводится как компактный вектор, состоящий из элементов Ьоо1. К переменной типа Ьоо1можно обращаться по адресу, поэтому Глава 16. Организация библиотеки и контейнеры 516 она должна занимать по крайней мере один байт.
Однако нетрудно реализовать оес!ог<Ьоо!> так, что каждый элемент займет только один бит. Обычные операции с векторами работают и для пес!ог<Ьоо!> и сохраняют свой обычный смысл. В частности, обращение по индексу и итерации работают так, как от ннх н ожидается. Например: ооЩ(оесгог<Ьоо!>с о) ( // итерадив перев индексь~ Хог ((пг(=О,г<о.в!сей, -н-!) с!п» о(!); !урес7е~оесгог<Ьоо!>эсопв! !Еега1ог Ъ7; // шперси!ив при подои(и итераторов /ог (Р!р = о.Ьеутп (); р!=о.епс! Ь, +зр) сои!« *р; оо!а7" (оес!ог<6оо! >й о) Ьоо!'р = о.Ьеу!и (); //- ) //ошшбка: несоответствие типов Техника адресации одного бита в общих чертах описана в ~ 17.5.3.
Библиотека также обеспечивает Ь!!ве! как множество логических значений с набором логических операций над множествами Я 17.5.3). 1 6.4. СО~~Т1~! [1] Для сохранения переносимости пользуйтесь средствами стандартной библиотеки; в 16,1. [2] Не пытайтесь переопределить средства стандартной библиотеки; б 16.2. [3) Не верьте, что стандартная библиотека лучше всего подходит для любых задач.
[4] Создавая новое средство, подумайте, нельзя ли его получить даром в рамках стандартной библиотеки; э 16.3. [5) Помните, что средства стандартной библиотеки определены в пространстве имен в!а(; 6 16.1.2. [6] Объявляйте средства стандартной библиотеки, включая ее заголовочный файл, а не явным объявлением; б 16.1.2. [7) Пользуйтесь преимушеством поздней абстракции; з 16.2.1. [8] Избегайте жирнеях интерфейсов; 6 16.2.2. [9] Предпочитайте алгоритмы с обратными итераторами, а не явные циклы от конца в начало; 6 16.3.2.
[10] Для извлечения !!ега!огиз геиегве !!ега!ог пользуйтесь Ьаве (); 6 16 3 2. [11] Передавайте контейнеры по ссылке; 6 16.3.4. [12] Для обращения к элементам контейнера пользуйтесь итераторными типами, такими как !(в(<сйаг>з!!ега!ог, а не указателями; ~ 16.3.1. Чтобы добиться этого, реализация должна имитировать адресацию одного бита. По- скольку указатель не может алресовать единицу памяти, меньшую чем байт, итера- тор вес!о~ <Ьоо!>з!!ега!ог не может быть указателем. В частности, нельзя рассматри- вать Ьоо(* как итератор для вес!ог<Ьоо!>: 517 16.5.
Упражнения [13] Если вам не нужно модифицировать элементы контейнера, пользуйтесь константными итераторами; 9 16.3.1. [14] Если хотите проверять диапазон, пользуйтесь операцией а1(), прямо или косвенно; 9 16.3.3. [15] Применяйте оияЬ Ьасй () или гея)яе () для контейнера, а не геаИос () применительно к массиву; 9 16.3.5. [16] Не применяйте итераторы в векторе, с измененным размером; 9 16.3.8. [17] Чтобы избежать превращения итераторов в недействительные, пользуйтесь геяегве(); 9 16.3.8.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
