Б. Страуструп - Язык программирования С++. Специальное издание, 3-изд. Бином. 2004 (1160791), страница 112
Текст из файла (страница 112)
То есть память выделяется с некоторым запасом (обычно на десять элементов) — Примеч.ред. 509 16.3. Вектора вес!от«1п«> о; о.рор ЬасЬ (); // неопределенный зффект; состояние и //становится неопределенным // неопределеннь!й эффект: состояние и // не определено, возможно оно плохое о.рияЬ Ьасй (т); Эффект переполнения снизу не определен, но очевидная реализация функции рор Ьасй () приводит к тому, что произойдет запись в область памяти, не принадлежащей вектору. Как и переполнение сверху, переполнения снизу следует избегать. 16.3.6.
Операции, характерные дли списков Операции рияй Ьас)е (), рор Ьасй () и Ьасй () Я 16.3.5) позволяют эффективно использовать вектор в качестве стека. Кроме того, иногда бывает гюлезно добавлять элементы в середину вектора или удалять их: !етр!а1е с!аяя Т, с1аья А = айоса1от Т > с1аяя оес1ог( риЫ)с //- //операции, характерные для списков !!ега1ог !пке«1 (пега!отрок, сопз1 Тй х); //добавление перед роя иоЫ )пкег! (!!ета1огроя, ксее 1уре п, сопк1 Т8 х); !етр!а1е«с!аяя 1п> //!п должен быть итератором для чтения (З !9.2.!) ооЫ1пяе«1(1!я«а!о«рок,1п/1гя1Тп!ак!) //вставка злельентов //из последовательности //удаление элемента из роя //удаление последоватпельности //удаление всех клементов Иега1от егаяе (!1ета!отрок); Пега!от егаяе (!«ега1о«Я«к1, пега!от 1ая!) ооЫ с!еаг (); Итератор, возвращаемый шяег1 (), указывает на только что вставленный элемент.
Итератор, возвращаемый егазе (), указывает на элемент, следующий за последним удаленным элементом. Чтобы посмотреть, как работают эти операции, давайте проделаем несколько (бессмысленных) действий с вектором фруктов. Сначала определим контейнер пес!о«и «заселим» его названиями фруктов: оес1отчя1ппд Тти!1, /пи1рикЬ Ьаса ("реасЬ") /ги!! рияЬ ЬасЬ ("арр1е ) /ги!!рияЬ ЬасЬ ('Ь!т~пи~; Уги11ризЬ Ьасд ("реат"); /ги!!рикЬ Ьаса ('к1афи! ); /ти!!рикЬ Ьасд (" угаре" ); Размер вектора, возвращаемый функцией кие (), неявно увеличивается функцией рияй Ьасй (), так что вектор не может переполниться (до тех пор, пока есть доступная свободная память, см. э" 19.4.1).
Однако вектор может «переполниться» в другую сторону; вой ( 510 Глава 1б, Организация библиотеки н контейнеры Если мне не нравятся фрукты на букву 'р', я моту удалить их названия: когг (Р ш1 беат () Ггийепй ()); оес1ог к1ппрй1ега1ог р! =~Япй [! (1гштЬеу!и ()1ПИ1елй (), Ьийа! ( р )); оес1огкк1ппу сИега1огр2 =1)пй Ц ~р1,)гиИ епй (), !пИ!а! по1 ( р )); 1гин.егаке (р1, р2); Другими словами, мы сортируем пес!от, находим первый и последний фрукты на букву 'р' и удаляем изупи1 эти элементы, Как написать проверочную функцию Иийа! (х) [первая буква х?) и т!Иа! по1 (х) [первая буква не 'х'?) объясняется в 2 18.4.2.
Операция егаке (р1,р2) удаляет элементы с р1-то до р2-то, не включая последний. Это молсно проиллюстрировать графически: 1гиИ[]. р1 рг ( арр1е угаре угиИ реасА реаг к1агэгиИ Функция егаке (р1, р2) удалит реасА и реаг, оставив: 1гиИ[]: арр1е угаре й!ш!)гш1 ктаг1гиИ Как обычно, последовательность, затрагиваемая операцией, определяется ее первым элементом н элементом, следующим за последним. Было бы соблазнительно написать так: оес1ог~ктг!пд>снегатог р1 = Апй !ОгиИ.Ьеу!л '() 1гинепй (), !пИ!а! ('р')); оестоглктг!лд> .геоегке Иега тот р2 = рай (Г(1гии гбеу1п () 1гиИ гепй (), тИ!а! ( р )); 1гинегаке (р1,р2е1); 1!ошибка: непарный гпил Однако оес1ог 1ги!1асй1ега1ог и пес1огфи!1ысгепегке Иега1огвовсе не должны быть одного и того же типа, поэтому мы не можем рассчитывать, что егаке () скомпилирустся.
Чтобы использовать гепегке Иега1ог вместе с Иега1ог, геиегке Иега1ог должен быть явно преобразован: 1гииегаке (р1, р2.Ьаке ()); 1! иэалекаеи Иегатогаэ шаегке Иега1ог !4 192а) Удаление элемента вектора изменяет его размер, а элементы после удаленного переносятся в освободившиеся позиции. В данном примерами!1,к?ге () становится равным 4, а к1атугш1, бывшаяуги!1[5], теперь сталауги!1[2]. Естественно, можно удалить и какой-нибудь один элемент.
В этом случае нужен только один итератор для этого элемента (а не пара итераторов). Например: 1' инегаке (?тй ()Ешь Ьеутп (),1гшт елй (), "ктаг1гиИ')) )гш1.егаке ()гиИ.Ьеутп ()е1); удаляет к1агугиИи раре, оставляя воуги!! два элемента: l ?гш1[]: арр!е А!ш!Ггш1 Элемент можно вставить в вектор. Например: Зги!Ь1пкег1 ~ш! 1. Ьеу1п ()т1, " сАеггу') )гш1 ткег1 ~пи! епй (], "ага пбеггу") Новый элемент вставляется перед указанной позицией, а элементы до конца сдвига- ются, чтобы освободить место.
Мы получим: 511 16.3. Вектора уги1!(]. арр!е сИеггу УниеУги1! сгааЬеггу Отметим, чтоу1пзег! (геп!1 (), х) эквивалентно уризЬ Ьаса (х). Мы можем также вставить целую последовательность: ]ги1Ь1азег! (]ги1!.Ьеу!а Ог2, сухие Ьеу1п (), с!!гиз.еае! ()); Если с11 из представляет из себя следующий контейнер снгиз(]: 1етоп угаре~го!! огалуе !!те мы получим: 2ги!!Ц: арр!е сйеггу 1етоп дгарегги!! огалде 1!те Ь!то()ги!! сгапЬеггу Элементы контейнера сИгиз копируются в вектор 1ги11 функцией 1пзег1 (). Значение с11гиз остается неизменным. Ясно, что 1пзег! () и егазе () более универсальны, чем операции, затрагивающие только конец вектора(3 16.3.5). Вообще говоря, они дороже, потому что при вставке или удалении не в конец контейнера приходится копировать элементы.
Если вставка и удаление — распространенные операции, возможно, лучше использовать списки, а не вектора. Списки 11з! оптимизированы для операций 1пзег! () и егазе (), а не для обращений по индексу 12 16 3 3). Вставка и удаление из вектора (из списка или ассоциированного итератора вроде тар) потенциально сдвигает элементы. Следовательно, итератор, указывающий па какой-то элемент в векторе, может после 1пзег! () или егазе () указывать на другой элемент или вообще не на элемент. Чтобы выделить память для нового элемента, 1пзег1() может заставить вектор перенестись в новую область памяти. Подобным же образом после удаления элемента функцией егазе () итераторы указывают не на тс элементы.
Никогда не обращайтесь к элементам через неправильный итератор: результат этого не определен и с большой вероятностью приведет к печальным последствиям. В частности, остерегайтесь использовать итератор, который применялся лля указания места вставки: 1пзег! () делает свой первый аргумент недействительным.
Например: оой е1ир!1са1е е1етеагз (оес!ог з!г!пу Й Я ( )ог (оес!огсзпзпд~с!!его!игр =ДЬеу!а () р1=!.епе1 ();++р) )упзегс(о,*р); /,!нет! ) Просто помните об этом Ц 16.5(! 5]). Реализация контейнера пес1ог может сдвинуть все алементы — или по крайней мере все элементы после р, чтобы выделить место для нового элемента.
Операция с1еаг () удаляет все элементы контейнера. Таким образом, с с1еаг (] — это краткая запись для с.егазе (с. Ьеу!п (), с.епа! ()). После с.с1еаг () с.з1хе () равно О. 16.3.7. Адресация элементов Чаще всего объектом применения операций егазе () и !пзег! () является хорошо известное место в контейнере 1например Ьеу1п () нли епс( ()), результат поиска (рпс( ()) или место, найденное путем итераций. В таких случаях мы имеем итератор, указынающий на подхо- Глава 1б. Организация библиотеки и контейнеры 512 (сбеугп()+7); //правильно Гескиитераторсподдерживает+ Гслс5' !92 !)) (бе[7)); //не универсально (с+ 7); //ошибки: прибавление 7 к контейнеру бесела слепни (сбасб ()); // ошибка: с.басу !) — ссылка, а не итеритор (с.епс1 ()-2); //правильно !пред-пред-последний элемент) (агбеу!и ()+2); //ошибка: векторные гесете Иет1ог //и Нега!ог — риэнае лпипа ((сгбеу!п()ь2)базе()); //неясно, носойдет Гель 9 !92 5) с.егазе с.егазе с.егазе с.егазе с.егазе с.егазе с.егазе Самая соблазнительная альтернатива, Ъс[7), действительно работает с очевидной реализацией оес1ог, где с[7) ссылается на элемент, а его адрес является корректным итератором.
Однако с может оказаться контейнером, нтератор которого не является простым указателем на элемент. Напрмер, оператор индексирования для ассоциативных массивов [9 17А.1,3) возвращает торрес( 1уребч а не указатель на элемент [оа!ие !урез). Не все контейнеры допускают применение операции + к своим итераторам. Например, !!з1 не допускает даже с Ьей1п ()+7. Вели вам на самом деле необходимо увеличить !!з1з!1ега1ог па 7, воспользуйтесь многократно ++ или используйте а()оапсе (). Варианты с+ 7 и с.басй () — просто ошибки в типе. Контейнер — не числовая переменная, к которой можно прибавить 7, а с.басй () — это элемент со значением вроде "реаг, не определяющий положения груши !реаг) в контейнере с.
18.3.8. Размеры и емкость Пока что вектор описывался с минимальнылг упоминанием о распределении памяти. По мере необходимости вектор растет. Обычно это и все, что нужно знать. Однако можно задать прямой вопрос, каким образом вектор получает память, а при случае стоит прямо вмешаться в этот процесс. Операции таковы: 1етр!а1е<гЛазз Т, с1азя А = а!!оса1огк7» с1азз оесгог ( ри61са //." //ел~кость: зсзе 1уре з!хе () сопз1; // число элементов ба о! етр1у () сопз1 ( ге1игп з)зе () == У, ) з!хе 1уре тах я!хе сопя!; О размер самого длинного // воэл~ожного вектора оо!д гезтзе (з!зе !урезе, Тпа! = Т!)) //добавленнае элемента // ипил(иолиэируклтся оа! з!хе 1уре сарасиу() сопя!; //размер выделенной полляти [число элементов) оо!л! гезегое (зсзе 1уре и); // выделяет место для всех и элементов; // не инициализирует // генерирует !епу16 епог, если п>тах Нее !) дяший элемент.