Бьерн Страуструп. Язык программирования С++. Специальное издание (2011) (1004033), страница 118
Текст из файла (страница 118)
Операция гетоге (!'О воспринимает критерии удаления. Например, уги11.гетоге !1(1п111а1 ( '1' ) ); удаляет элементы, начинающиеся на букву 1, что приводит к следующему результату: уса!1: аррге дгаре2гий реаг пи!псе Удаление элементов часто производится с целью устранения дубликатов. Для этого специально предназначена функция вящие(): гги(г. хогг ( ); !го!!. ипщие ( ); Причина предварительной сортировки заключается в том, что ипщие () удаляет лишь смежные дубликаты. Например, будь содержимое списка следующим арр1е реаг арр1е арр(е реаг простой вызов Яи11. вящие О приведет к арр(е реаг арр!е реаг а в случае предварительной сортировке — к арр1е реаг Если нужно удалить лишь определенные дубликаты, мы можем предоставить предикат (условие), специфицирующий, какие именно дубликаты должны быть удалены.
Например, можно определить бинарный преликат (Ь)лагу ргейсаге, 518.4.2) иииаЮ(х), чтобы выявлять строки, начинающиеся на букву х, и возвращающий 2айе в иных случаях (когда строка не начинается на букву х). Например, если в списке содержатся фрукты реаг реаг арр(е арр1е мы можем удалить последовательные дубликаты фруктов, начинающихся на букву р, вызовом уги11. опцие (1п111а12 ( 'Р ' ) ); Это даст следующий список фруктов: реп г арр1е арр1е 570 Глава 17.
Стандартные контейнеры Как отмечено в 816.3.2, иногда требуется просматривать контейнер в обратном порядке. Для списков имеется возможность инвертировать порядок элементов без необходимости их копирования. Это выполняется функцией гегегве () . Пусть задан следующий список: )гий: Ьапапа сиепу йте вггатаеггу Тогда вызов )Ьи!!.
гегегве ( ! даст следующий результат; )гий: вггатЬеггу йте слепу Ьапапа Удаляемый из списка элемент уничтожается. Однако заметьте, что уничтожение указателя не есть уничтожение указуемого объекта. Если вам нужен контейнер указателей, который при удалении из него элемента (то есть указателя) уничтожает указуемый объект, вам придется написать его самому (817.8[! 3[).
17.2.3. Контейнер с[ее1це Контейнер г(ег)ие реализует структуру данных, называемую двусторонней очередью (доиЫе-епдед с)иеие). То есть это последовательный контейнер, оптимизированный таким образом, что головные и концевые операции для него почти так же эффективны, как для списков, а индексирование почти так же эффективно, как для векторов: гетр!а!в<с!ат Т, с!ат А = айосагог<Т' > с!авв вгд::децие ,У типы и операции кок у»ес!ог (31б.3.3, 31б.3,5, 3!б.З.б) 1) кроме сарасйу() и гевегге() г7 плюс "головные" операции (317.2.2.2) как у Ьм !' В то же время, вставка и удаление элементов где-нибудь в «середине контейнера» неэффективны так же, как и для векторов.
Следовательно, Иейие используется в случаях, когда добавление элементов и их удаление производятся на обоих краях (в начале или конце) контейнера. Например, можно применить двустороннюю очередь для моделирования участка железной дороги или лля представления колоды карт в карточной игре: Иецие<саг> туйпь по 3; «!едка<Саги> Ьопав! 17.3.
Адаптеры последовательных контейнеров Последовательные контейнеры пес!ос, !!м и г(еиие нельзя построить один из другого без потери эффективности. С другой стороны, можно элегантно и эффективно реализовать стеки и очереди при помощи этих трех фундаментальных последовательных контейнеров. Поэтому егасй и ииеие определяются не как независимые контейнеры, а как адаптеры фундаментальных последовательных контейнеров. 17.3. Адаптеры последовательных контейнеров 571 Контейнерный адаптер (сол1айег айар1е«) призван предоставлять ограниченный интерфейс к контейнеру.
В частности, адаптеры не предоставляют итераторов, так как предполагается, что адаптерные контейнеры нужно использовать только через их специализированный интерфейс. Методы, с помощью которых из фундаментальных контейнеров создаются адаптерные контейнеры, могут в общем случае применяться при неинтрузивном подстраивании классового интерфейса под нужды пользователей. 17.3.1. Стек Адаптер згас1! определен в заголовочном файле <з!а«Ь>.
Он столь прост, что лля его изучения лучше всего просто представить его реализацию: !«трйг!е<с!азз Т, с(азз С = йеаие<Т» с!азз яЫ::з!а«Ь ( ргогес!ей: Сс; риЫ1с: турей«1 !Урепате С:: ча(ие !уре ча!ие !уре! гурей«1 тур«пате с:: «йге !уре зйе !уре; Зурей«1 С соп!а!лег !уре; «хрдсй тась (соля! Сь а = С() ): с (а) ( ) Ьоо! етр1у() сот! (ге!игп с.етр!у () з ) иге !уре вйге() сопя! (ге!игп с я!ге(); ) ча!ие !урез !ор(] (ге!игп с.Ь«са() ! ) сопя! ча!ие !урез !ор () сот! [ге!игл с.
Ьа«Ь [); ) чоЫ ризЬ (солт ча!ие (урез х) (с.ризЬ Ьа«Ь(х) ! ) чоЫрор() (с.рор Ьаса() з ) )1 Таким образом, я!а«Ь есть просто интерфейс для контейнера, который передается ему в качестве шаблонного параметра. Все, что делает стек, сводится к удалению из интерфейса нестековых операций и к переименовыванию операций Ьа«Ь[), ризЬ Ьасй() н рор Ьас1г() в более традиционные для стеков имена — гор(), ртй() ирор(). По умолчанию стек хранит свои элементы в двусторонней очереди, но можно использовать и любой другой последовательный контейнер, предоставляющий операции Ьас!г[), ризЬ Ьа«Ь() и рор Ьа«Ь() . Например: я!а«в<слог> з1; гу используем деди«<слог> для хранения элементов типа «Ьог та«Ь<ии, чес!ог<вп!» з21 У и«пользу«м чес!ог<т!> для хранения элементов типа !л! Можно предоставить существующий контейнер для инициализации стека: чоЫ рг!п! Ьа«Ь!чагйз (чес!ог<!л!> ь ч) з!а«Ь<!пг, чес!ог<!п!» з!а!е (ч); !! инициализируем я!а!е из ч !«И1« [та!е.
иге ( ) ) Глава 17. Стандартные контейнеры сои(« з(а(в,(ор() в(а(в.рор () ( ! ) Надо иметь в виду, что элементы аргумента-контейнера копируются, так что предоставление существующего контейнера в качестве аргумента функции довольно дорогостоящая затея. Элементы добавляются в стек при помощи операции риз(з бас(с() базового контейнера, используемого для хранения элементов. Следовательно, стек не может переполниться, пока имеется достаточно памяти для выделения под элементы этого контейнера (с помощью его же аллокатора; см. 5)9.4). С другой стороны, стеку может грозить «переисчерпание» (цп()егйотч): гоЫ 7'( ) ( з(ас((<(п(, ввс(ог<(п(» з( .р л(г)( ф'(з .
втрзу ( ) ) ( //нв делать рор ) в(зв ( з.рор() т з.рор (); ) ) зу защита от ипс(екало»г ((чудесно: зэягей становится 0 У эффект не определен, возможны проблемы Отметим, что для использования элемента стека нет необходимости выполнять операцию рор(). Вместо этого используют (ор(), а рор() применяют тогда, когда элемент больше не нужен. Это не вызывает особых затруднений и более эффективно в случаях, когда нет нужды в операции рор (): гоЫ З (з(ас((<сваг> ь з) ( (Г(з. (ор ( ) == ' с ' ) з .
рор ( ) ( У ... ) (з удаляем возможные начальные 'с' В отличие от фундаментальных контейнеров з(асй (как и другие адаптеры) не имеет среди параметров шаблона распределителя памяти. Вместо этого он полагается на распределитель памяти базового фундаментального контейнера. 17.3.2. Очередь (етр(а(в<с(азв !) с(азз С = ((в((ив< Т» с(азз в(И::((ивов Адаптер авеле, определенный в заголовочном файле <(7иеие>, реализует интерфейс к контейнеру, позволяющему добавлять элементы в конец и извлекать их с головы (структуры данных с такими свойствами называют очередями — (7иеиез): 17.3.
Адаптеры последовательных контейнеров 573 рго!ес!еИ: Сс; риЫ(с: гуребеу' зурепате с:: га(ие (уре га(ие (уре; 1урегге~зурепате С::Ызе (уре иге !уре; зуребе!' С сопсаЫег !уре; ехр11е!! диеие(сопл! Сз а=С() ): с(а) () Ьоо! етр!у ( ) сопи! ( ге!ига с. етргу ( ); ) з(ге (урез!зе() сопл! (ге!игл с.иге() г ) га1ие (уреа$гоп!() (ге!ига с.угон!(); ) сопз! нагие гуреь!гоа!() сопл! (ге!игп с.!гоп!(); ) га1ие (урез ЬаеИ() (гегигп с. баса(); ) сопл! га(ие !урез Ьаса() сопл! (ге!игп с.баса() ! ) гоЫ риза (сопл!го(ие (урез х) (с.риза Ьаех(х) ) ) гоЫрор() (е.рорггопг(); ) По умолчанию очередь диеие использует для хранения элементов контейнер г!едие, но можно использовать и любой другой последовательный контейнер, предоставляющий операции угон!О, Ьасйы, ризЬ Ьасйы и рор угон!О.
Поскольку зесгог не предоставляет операции рор )зонг ( ), он не может использоваться в качестве базового фундаментального контейнера для хранения элементов очереди. Очереди находят применение практически во всех системах. Например, для системы передачи и обработки сообщений можно определить следующий сервер: зггие! Методе ( У... )' соЫ зеггег (диеие<Меззаее> з ( м4и(е( (д.етргу() ) ( Метаяез т = д4гоп!(); т . зегг!ее ( ); д.рор (): ) ) II получить сообщение з! обслужить запрос l/уничтожить сообщение гоЫ зеггег2 (диеие<Метаяе>ь д, Йосйа 1еа) ( юЫ(е(! д. етр!у О ) ( Методе т; Сообщения помещаются в очередь операцией ризЬ () . Если сервер и клиентская программа работают в разных процессах или потоках, потребуется некоторое средство синхронизации доступа к очереди.
Например: Глава ) 7. Стандартные контейнеры 574 В языке С++ нет стандартных средств реализации параллельной работы и взаимоблокировок. Посмотрите, что может предложить ваша система и как это реализовать на С++ 617.8[8[). 17.3.3. Очередь с приоритетом Очередь с приоритетом (рпоп!у диеие) — это такая очередь, которая каждому элементу назначает приоритет, определяющий порядок, в котором элементы просматриваются (операция гор()) пользователем: !етрйл!е<с1аяя Т, с(ат С = чес(ог<Т>, с(ат Стр=!еяя<(урепате С::ча!ие !уре» с)аяя яи1::рпоп!у диене ( рго!ес!еИ: Сс; Стр сгир; риЬ|с: гурег!еу турепате С:: ча1ие !уре ча(ие !уре; яуредеу (уРепате С:: иге !уре иге !уре; гуредеу С сои!атее туре; елрбс!! рпопгу диеие(сопя! Стра а1 = Стр(), сопя! Ся а2 = С() ) : с(а2), стр(а1) (тале Ьеар(с.Ьед!п(),с.епдп,стр) г) бсм.з!8.8 !етр1ате<с(аяя 1и> рпоп!у диеие(1пуггят, 1п 1аяя, сопя! Стра = Стр(), сопя! Сг = С() ); Ьоо( етр!у() сопя! (ге(иги с.етргу(); ) я!ге гуре иге ( ) соии ( ге!игл с.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
