Б. Страуструп - Язык программирования С++. Специальное издание, 3-изд. Бином. 2004 (1160791), страница 116
Текст из файла (страница 116)
Например, операция присваивания, генерирующая исключение, может оставить какай-нибудь элемент лигць частично скопированным. Она может оставить даже сам контейнер в состоянии, которое потом принесет неприятности. Такие операции копирования сами по себе являются плохо спроектированными Я 14.4.6.1, приложение /[). Когда копирование элементов — это пе совсем то, что нужно, альтернативой служи' помещение в контейнер вместо самих объектов указателей на объекты. Наиболее очевидныйй пример — полиморфные типы (~ 2.5.4, гз 12.2.6). Например, чтобы сохранить полим орфи ое поведение, мы используем оес!ог<$!гаре*>, а не вес!ос< Я/горе>. 17.1.4.1.
Сравнения Ассоциативные контейнеры требуют, чтобы их элементы гяогли быть упорядочены. То же самое касается многих операций, которые можно применить к контейнерам (например, зог! ()). По умолчанию для определения порядка используется оператор <. Если < нс подходит, программист может обеспечить альтернативу Я 17А.1.5, ~ 18.4.2). Критерий упорядочивания должен определить строгое слабое упорядочение (зтпсс в еа)с огдеппд).
Неформально это означает, что «меньше» и «равно» должны быть транзитивными. То есть для критерия упорядочения стр: (1) стр (х, х) есть~а!зе. (2) Если стр (х, у) и стр (у, х), то стр (х, х). (3) Определим еди!о (х, у) как! (стр (х, у) )((стр (у, х)). Если еди!и (х, у) и едиш (у, г), то еди!о (х, я).
Рассмотрим: // для сравнения используея < <гетр!аге.с!азз кап> оо!а' зог! (йап/!гз1, йап !аз!); // используем стр !етр!иге<с!азз кап, с!азз Стр> оо!г! зогг (кап/1 гзг, йап !азг, Стр стр); Первая версия пользуется оператором <, а вторая — пользовательской функцией сравнения стр ().
Например, мы могли бы решить отсортировать фрукты /ги!! при помощи 526 Глава 17, Стандартные контейнеры сравнения без учета регистра. Мы сделаем это, определив объект-функцию Я 11.9, 5 18.4), который осуществляет сравнение, будучи вызванным для пары строк з!г!пд: с!аззХосазе( )гг сравнение без учета регистра риЫ1с Ьоо! орегагог () (сопя! з!г1пасч сопз1 з1г!пуЬ у) сопя!; ); Ьоо))чосазегорегагог () (сопз1 зв!пав х, сопя! згг!пуй у) сопз1 ,!!возвращает 1гое, если хлексикографическп л~еныие челг у, /) не нрпнилая в рас ~ет регистр зггту"сопз1 11ега1огр =х Веут (); в!ггпу-.сопя! !1ега1огс! = у.Ьеу!и (); шЫ!е (р1=х.епй () аа дту епй () г<ч, 1оиррег (*р)==1оиррег ('у)) ( -ньр; .Н-у, (! (Р==х.епй Щ ге!игл ум уепй(), (!' (у == у.
ел й ()) ге 1 игл 1а!зе; ге1 ига 1оиррег ('р) < !оиррег ('д); Пользуясь этим критерием сравнения, мы можем вызвать зог! (). Например: возьмем контейнер; )ги)Г ирр1е реаг Арр!е Реаг !етоп Отсортировав прн помощи зог1 (!ги!!.ьерп () гги!1,елй (), )чосазе [)), получим; )гш1 Арр!е арр1е !етоп Реаг реаг в то время как простое зог1 (ртл!1.Ьеу!и (), уги!! епй ()) может дать что-то вроде: Хги!1; Арр!е Реаг арр!е !етоп реаг в предположении, что в наборе символов сначала идут заглавные, а потом строчные буквы. Имейте в виду, что для С-строк (то есть айаг*) оператор < не определяет лексикографического порядка (5 13.5.2).
Таким образом, при использовании в качестве ключей С-сгрок ассоциативные контейнеры будут работать не так, как ожидало бы большинство людей. Чтобы заставить их работать должным образом, нужно пользоваться операцией <меньшесч производящей сравнение, основываясь на лексикографическом порядке. Например: з!гис1 Сз1г!пу 1езз ( Ьоо! орега1ог() (сопя! сЬаГ' р, сопл! сдаг* у) сопз1( ге1игп в!гетр (р, с!)<О, ') тир<сдпг', 1п1, Се!ггпу !езз> т; )) ассоииативныилшссив, конюрый нспользуепг )) ьпстр!) для сравнения клюо ~ейсолз1 сьаг' 17.1.
Стандартные контейнеры 17.1.4.2. Другие операторы отношения 527 По умолчанию контейнеры и алгоритмы, когда нужно произвести сравнение на «меньше», пользуются оператором <. Когда умолчание не подходит, программист может задать свой критерий сравнения. Однако для проверки на равенство никакого механизма не обеспечивается. Вместо этого, когда программист предоставляет функцию сравнения стр (), равенство проверяется при помощи двух сравнений.
Например: Ц (х == у) // нв делается, если пользователь обеспечил свое сравнзние 1з' (~стр (х, у) йй!стр (у, х)) // ват что делается, если пользоваьпвль //обеспечил свое сравнение Так мы избавляемся от необходимости добавлять к каждому ассоциативному контейнеру и большинству алгоритмов критерий равенства. Это может показаться расточительным, но библиотека не так уж часто обращается к сравнению, а в 50Ж случаев требуется всего лишь одно обращение к стр ().
Применение отношения равенства, определенного функцией «мепыпе» (по умолчанию оператором <), а не функцией «равно > (по умолчанию оператором ==), имеет также и практическое применение. Например, ассоциативные контейнеры (Ь 17А) сравнивают ключи при помощи такой проверки на эквивалентность: ! [стр (х, у) ) (стр (у, х)) Это подразумевает, что эквивалентные ключи не обязаны быть равны.
Например, ти!1(тар Я 17А.2), использующий критерий сравнения без учета регистра, будет считать строки Ааз1, !аз1, Ик1, (а%и 1азТ эквивалентными даже при том, что оператор == для строк не считает их равными. Это позволяет нам не принимать во внимание разли пия, которые мы считаем несущественными при сортировке. Имея операторы < и ==, мы можем легко сконструировать остальные часто применяемые сравнения, Стандартная библиотека определяет их в пространстве имен з11!сге! орк и представляет в заголовочном файле <и11!11у>: !етр!а1е<с1акз Т> Ьвп! ге! оркспрега1пг!= (сппк1 Тй к, сппз1Тй у) ( ге1игп! (х==у); ) 1етр!а1е<с!азк Т> Ьпа! ге1 орк: прега1ою (свпзг Тй к, сопкгТй у', ( ге1игп у<к; ) 1етр1аге<с!акз Т> Ьпв! ге! врззврегагпг<= (сппк1 Тй х, сппз1Тй у) ( гвгигп ~ (у<х), ) !етр!а1з<с1азз Т Ьап1 ге! прзьпрзга1ог>= (сопз1 Тйк, сопк1Тй у) ( гвгигп ~ (х<у), ) Поместив эти операции в ге! орз, мы гарантируем, что при необходимости ими легко воспользоваться, и при этом они не создаются неявно, если только их це «вытащить из пространства имен: ив1д Т() ( изину патекрасе кгд; //!=, > и т.
д., нв порождаются по умолчанию иппу у () ( 528 Глава 17. Стандартные контейнеры ив1пд пат еерасе вЫ; ив!пу патеврасе вЫ >ге! орв; //!=, > и т. д., порождаютсл по умолчанию Операпии!= и т. д. пе определены прямо в вЫ потому, что они не всегда нужны, и иногда их определение может помешать пользовательской программе. Например, если бы я писал обобщенную математическую библиотеку, мне бы захотелось иметь свои собственные операторы сравнения, а не версии из стандартной библиотеки, 1?.2.
Последовательности Последовательности следуют модели, описанной для векторов Я 16.3). Стандартная библиотека обеспечивает следующие фундаментальные последовательности: ° вектора (иес1ог); списки (Е!в1); очереди с двумя концами (с(ение). Из них, предоставлением соответствующего интерфейса, созданы ° стеки (в(ас(е); очереди (с(иеие); очереди с приоритетами (рг(ог11у уиеие). Эти последовательности называются контейнерными адаптерами, адаптерами последовательностейй или просто адаптерами (9 17.3).
17.2.1. Вектора Стандартный вектор оес1ог подробно описан в 9 16.3. Средства для резервирования памяти (9 16.3.8) уникальны для оес1ог. По умолчанию при использовании индексации [~ диапазон не проверяется. Если нужна проверка, пользуйтесь а1(1 (16.3.3), вектором с проверкой (З 3.7.2) или итератором с проверкой Я 19.3). Контейнер эес1ог обеспечивает итераторы с произвольным доступом (з 19.2.1).
17.2.2. Списки Список Е!в1 — это последовательность, оптимизированная для вставки и удаления элементов. По сравнению с вектором (и !Еедиа 9 17.2.2) обращение к элементу списка по шщексу оказалось бы чрезвычайно медленным, поэтому оно для него пе предоставляется. И поэтому список обеспечивает двунаправленные итераторы (9 19.2.1), а не итераторы с произвольным доступом. Это приводит к тому, что список, как правило, реализуется при помощи некоторой формы двусвязного списка (см. 9 17.8(161). Контейнер Е!в!обеспечивает все типы членов и операции, предлагаемые контейнером оес1ог (9 16.3), за исключением индексации, сарае!Еу Д и ! евегое !!: 1етр1а1ексЕавв Т, с!авв А = а1!оса!ог<Т» с!авв вЫ: Вв! ( риЫ1с. // типы и операции похожие на типы и операции // для векторов, кроле (], о!(), сорос!!у() и тете() //- 529 17.2.
Последовательности 17.2.2.1. Удаление-вставка, сортировка и слияние В добавление к основным операциям с последовательностями (!я!предоставляет операции, специально приспособленные для манипулирования со списками; 1стр!а!в<с!аяя т, с!аяя А = а!!осагою т» с!аяя !!я1 ( рий!с: 0". //опера~!пи, специфичные для списков // первлчещение всех элементов из х на место // перед роя в данном списке без копирования //(удаление-вставка) ивЫ яр11сс (Нега!агрос, !!я1& х); // перемещение *р из х на место перед роя без копирования иоЫ яр!!се (Нета1вт роя, !!я1Ь х, Нета1вт р), ио!Й яр!!св (Нета1вт роя, !!я% х, 11ега1вгЯтя1, Юста1вг!ая1) //объединение отсортированныхсписков ивЫ тес!1в (!!я15); 1етр1а1е<с!аяя Стр> ивЫ тстув (!!яИ, Стр); иоЫяог1(); 1етр!а1е<с!аяя Стр> иоЫ яог! (Стр); 0-. Все эти операции контейнера /!я!устойчив!я, то есть сохраняют опюсительный порядок элементов, имеющих одинаковые значения.
Пример с фруктами из 9 16.3.6 работает с контейнером /ги!1, определенном как список. В добавок мы можем извлекать элементы из одного списка и вставлять в другой одной операцией удаления-вставки (зр)(се). Имея списки Хги!С арр!е реаг с!Ьия: огапяе нгаре~яи11 !стоп мы можем удалить огапяе из с!1гия и вставить его во /ги!! следующим образом: !1я1<ягтти>згегасогр =Хаас! альфи!1Ьеу!и (), )гииепч1 (), Ы!Ка! ( р)); /ги!1.яр!!се (р, п1гия Ьед!п ()); Это приведет к удалению первого элемента из с!1гия (с!1гия Ьей!и ()) и помещению его прямо перед первым элементом списка ~па! на букву 'р'; тем самым получится: ,6и!1: арр1с исаакие реаг с!Ьия: угаре~~'и11 1втвп Отме~им, что функция яр/!се () це копирует элементы, как !пяег! () Я 16.3.6).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
