Бьерн Страуструп. Язык программирования С++. Специальное издание (2011) (1004033), страница 117
Текст из файла (страница 117)
Также в стандартной библиотеке имеют место случаи проверки отношения эквивалентности с помощью сравнения на меньше, а не сравнения на равенство. Например, ассоциативные контейнеры (517.4) сравнивают ключи с помошью проверки на эквивалентность . '(стр(х,у)!!стр(у,х) ). Из этого следует, что эквивалентные ключи не обязаны быть равными. Например, контейнер та!отар (В)7.4.2), использующий критерий сравнения без учета регистра, рассматривает строки 1л(ю, 1ая, Ия, 1ао( и 1азТ как эквивалентные, хотя операция == считает их разными.
Это позволяет игнорировать при сортировке те различия, которые мы считаем несущественными. Прн наличии операций < и == мы можем легко сконструировать остальные операции сравнения. Стандартная библиотека определяет их в пространстве имен я(1:: ге1 оря и расположены они в заголовочном файле <ип11(у>: (етр1а(е<с1азз Т> Ьоо1 ге1 орз:: орелиог! = (сопя( Ть х, сопя Ть у) ((еиоп ! (к==у) ( ) (етр1а(е<с!азз Т> Ьоо( ге( орз(: орега(ог> (сопю Ть х, сопя( Тй у) (гешгп у<х( ) (етр!те<с!азз Т> Ьоо1ге1 орз(: орегашг<= (сопя Ть х, соля Тй у) ( ге(игп ! (у<х) ( ) (етр!а(е<с!азз Т> Ьоо! ге1 орз::орега(ог>= (соля Тй х, сопя( Ть у) (ге(игп ! (х<у) ( ) Размещение этих операций в ге1 орз гарантирует их простое использование при необходимости, в то же время уберегая нас от их неявного создания: гоЫ Т() ( из(пя патезрасе зЫ( //.(=, >, и т.д.
) гоЫя() ( из!пе патезрасе зЫ( из!ля патезрасе зЫ:: ге( орз( //!=, >, и т.д. 565 17,2. Последовательные контейнеры Операции ! = и др. не определяются в пространстве имен згд потому, что они далеко не всегда нужны, а иногда их определение может вступить в противоречие с кодом пользователя. Например, если бы я писал некоторую общую математиче'скую библиотеку, мне наверняка потребовались бы свои собственные операции сравнения, а не их версии из стандартной библиотеки. 17.2.
Последовательные контейнеры Все последовательные контейнеры следуют модели, описанной для векторов (816.3). Стандартная библиотека содержит следующие фундаментальные последовательные контейнеры: ° гесгог (вектор) ° !!з! (спнсок) ° деоие (двусторонняя очередь) Менее фундаментальные последовательные контейнеры строятся поверх фундаментальных предоставлением соответствующего интерфейса: ° згас!г (стек) ° опеке (очередь) ° рг!огйу аиеие (очередь с приоритетом) Их называют контейнерными адаптерами или просто адаптерами (адар!ет) (817.3). 17.2.1. Контейнер честог Стандартный контейнер гесгог в деталях описан в 816.3.
Средства резервирования памяти (816.3.8) уникальны для этого контейнера. По умолчанию, операция индексирования не проверяет диапазон индексов. Если нужна проверка, пользуйтесь аг() (816.3.3), вектором с проверкой (83.7.2) или итераторами с проверкой (819.3). Контейнер гесгог предоставляет итераторы с произвольным доступом ($19.2.1). 17.2.2. Контейнер! 1вт Контейнер Вз! (список) — это последовательный контейнер, оптимизированный под операции вставки и удаления элементов.
По сравнению с векторами (н контейнерами десне; 817.2.3) операция индексации для списков чрезвычайно медлительна, так что в 1В! ее даже и не включают. В итоге 1!м предоставляет не итераторы произвольного доступа, а двунаправленные итераторы (819.2.1). Все это обуславливает типичную реализацию 1й! в виде той илн иной формы структур данных, называемых двусвязными списками (доид!у !!и!сед !!з!) (э" 17.8[161).
Контейнер!!зг предоставляет все типы и операции, предоставляемые контейне'- ром гесгог ($16.3), за исключением индексации, сарае!!у О и гезегге О: Гетр!аге<с1аев Т, с!аяз А = а!!оса!ог<Т» с!аяв зИ:: 1Ь! риЫ!с: $66 Глава 17. Стандартные контейнеры //типы и операции как у тес!ог, кроме Ц, а((), сарае((у() и гезегге() // ... )! 17.2.2.1.
Операции зр!ке(), зогт() и п)егдеО Дополнительно к стандартным для всех последовательных контейнеров операциям !!зт реализует еще и операции, предназначенные для специфических манипуляций со списками: (етрйиесс!аиз Т, с)азз А = айосагог«Т» с(азз 1й! ( риЬНс: // ... Р операции, специфичные для списков: ю!д зрйсе (йепиог роз, 1мм х); // перемещение всех эл-ов из х на место перед //роз в данном списке без копирования. юЫзрйсе(йегагог роз, 1йм х, йега!оср); //то же самое, но с позиции р изх.
гоЫ зрдсе (!!его!ог роз, 1йм х, йега!ог/!ге!, йегагог 1аз!) ! го!й тегее (Ьз!и ); //слияние сортированных списков !етр!амссЫзз Стр> юЫ тегзе (1и!ь, Стр) ! юЫ зогз (): гетр)азе<с(азз Стр>»оЫ зогз(Стр); /... )! /гий ! арр(е сй из: огапее реаг ЛгареЯии! 1е топ мы можем переместить агапке (апельсин) из списка сй! из в список)гий следующим образом: 1зззкз!кипа> ! ! йегазог р = /« ай и/ (рии!. Ьеат (),угии!. епд (), 1и1иа1 ( 'р ' ) ) ! 7гий.зр)зсе (р, сйгиз, сйгиз.
Ьеа(п () ); Здесь из сйвиз удаляется первый элемент (указуется итератором сйгиз. Ьеяй () ), и этот элемент вставляется в список уги!! перед первых элементом, начинающимся на букву р. Вот что из этого получается: угий: арр1е сйгиз: агаре7гий огапее реаг 1етоп Эти операции характеризуются устойчивостью (и!аЫе врага!(опз) в том смысле, что они сохраняют относительный порядок эквивалентных элементов.
«Фруктовый» пример из 5)6.3.6 переиначим сейчас на контейнер/гий типа !и!. Теперь мы можем извлекать элементы из одного списка фруктов и внедрять их в другой список единственной операцией зрйсе(). Если имеются два списковых контейнера фруктов 17.2. Последовательные контейнеры 567 Отметим, что операция вр11се () не копирует элементы таким же образом, как это делает ймегг() (816.3.6).
Вместо этого она просто изменяет внутренние указатели на данные, относящиеся к элементам. Операция зр!1се() помимо удаления-вставки индивидуальных элементов и их диапазонов может все это выполнить для целого списка: угий. зр!йе (Ггий. Ьее(п ( ), сйгиз ) з Это дает следующий результат: угий з ягоре~я ий сйгив: <етр1у> !етоп арр!е агапке реаг 1!11<взг!ия> з: йегагог р = $зпг! Ц (Ггий.
Ье81и ( ),7гий. епз! ( ), 1ий(а! ( ' р ' ) ); угий. вр!зсе (р, сйгиз, с(и из. Ьед!п () ); У ой згий.врйсе(р, сйгиз,угий. Ьея1п () ) з Уеггозс7гий.Ьее(п() не указывает внутрь сйгиз сйгив.врйсе (р,угий,ггий. Ьея!п () ) з Уеггогз р не указывает внутрь сйгиз Первый вызов врйсе() корректен даже в случае, когда контейнер сйгиз пуст. Операция шегйе () (слияние) объединяет два сортированных списка, изымая их из одного списка и вставляя в другой с сохранением порядка. Например, списки он!псе реаг дгареугш1 огапае !зте арр!е 77з !еизоп могут быть отсортированы и объединены следующим образом: 77 .вог1() 1 72.вогг() г 77 . тесле (77) 1 В результате получится арр!е хгаре~гий !етои йте огапде реаг г!и!псе 73з <етрзу> Если один из объединяемых списков не отсортирован, функция тегйе() все равно породит объединенный список, однако по поводу его упорядоченности нет никаких гарантий.
В любых версиях функция вр11се() в качестве второго аргумента получает список, из которого элементы забираются. Это позволяет забирать элементы из точно специфицированного источника — тут итератора бьщо бы недостаточно, ибо нет способа выявить контейнер по одному лишь итератору на его элемент (98.6). Естественно, аргументы-итераторы должны быть корректны по отношению к спискам, на элементы которых они якобы указывают.
То есть они должны либо указывать на действительный элемент списка, либо иметь значение, возвращаемое функцией еиг1 () . В противном случае результат не определен и потенциально катастрофичен. Например: 568 Глава 17. Стандартные контейнеры Как и операция яр1<се(), функция тегяе() фактически не копирует элементы.
Вместо этого она удаляет элементы из списка-источника и на уровне внутренних структур данных вставляет их в список-приемник. После выполнения х. <пегле(у), список у оказывается пустым. 17.2.2.2. аГоловные» операции «Головные» операции, то есть операции над самыми первыми (находящимися в голове) элементами списков, призваны дополнить «концевые» операции, присущие всем последовательным контейнерам Я)6.3.6): <етр<а<е <с!аяя Т, с1аяя А = а<<оса<ог<Т» с<аяя 1Ы< ( риЫ<с: У... УУ доступ к элементам: ге7егепсе агап< ( ) < сопи ге(егепсе Тгоп<() сопя<; УУ ссылка на первый элемент чоЫ рива <гоп<(сопя< Тя); чоЫ рор ~гоп< ( ) < У... УУ добавить новый первый элемент УУудалить первый элемент 17.2.2.3. Другие операции Вставка и удаление элементов особо эффективны для списков.
Это заставляет людей предпочесть контейнер 11м в случаях, когда приходится выполнять их часто. В свою очередь, это требует прямой реализации методов улапения элементов: <етр!а<е <с<вяз Т, с<аяя А = аИоса<ог< Т» с!аяя 1!я< ( риЫ1с: уу ... юЫгеточе(сопя< Тя ча1) < <етр1а<е<с<аяя Рге«> юЫ геточе <7 (Рге<< р); юЫ ип<1ие() < Уудаляет дубликаты с помощью == <етр1а<е<с<аяя В(прге<<> чоЫ ип(«ие (В(прге<< Ь) < У<удаляет дубликаты, используя Ь; юЫ сечете() т УУ обратный порядок элементов Головной (самый первый) элемент контейнера принято называть|гоп<.
Для списков головные олерации (!гоп< орегабопя) столь же эффективны и удобны, как и концевые операции (Ьас/с орега<!опя) 516.3.5). Если имеется возможность выбора, то лучше предпочесть концевые операции головным операциям, поскольку код, использующий лишь концевые операции, одинаково хорошо подходит и для списков, и для векторов. То есть если существует ненулевая вероятность того, что код, изначально написанный для списков, постепенно может эволюционировать в обобщенный код, пригодный для всех типов контейнеров, лучше ограничиться более широко распространенными концевыми операциями.
Это частный случай правила, гласящего, что для того, чтобы добиться максимальной гибкости, нужно применять минимальный набор операций (517.1.4.1). 17.2. Последовательные контейнеры Например, для контейнера 1' ий: арр1е агапке дгаре1ги1г 1етоп агапке Йгпе реаг Чи(псе мы можем следующим образом удалить все элементы со значением агапке: (ги11 . гетоге ( погапдеп ); При этом получится следующий результат: уса!1: арр(е дгаретги11 1етоп Дте реаг пи!псе Часто при удалении элементов более интересны иные критерии, чем просто удаление элемента с заданным значением.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
