Бьерн Страуструп. Язык программирования С++. Специальное издание (2011) (1004033), страница 119
Текст из файла (страница 119)
иге ( ); ) сопя! ча1ие гурег тор () сопя! (ге(игп с.угон!(); ) чо!г! рияи (сопи ча1ие гурег) чо!д рор ( ); )' Объявление ргуог!гу диеие находится в заголовочном Файле <диеие>. По умолчанию, рг!ог!гу диеие упорядочивает элементы, сравнивая их с помощью операции <, а операция !ор() возвращает наибольший элемент: яи ис! Методе ( !п! рг!ог(гу ! Ьоот орега<ог< (сопя! Метабег х) сопя! ( ге!игп рг!ог(гуся.рг!ог!(у; ) ( 1ОСЬР(г Ь (1СЬ) ! !1(д.етр!у() ) ге!иги; т=д.!гоп!(); д.рор (); ) т . яегч!се ( ); ) ) У блокировка на время получения сообщения Гсм. я!4,4.
!! У кто-то другой получил сообщение 17.3. Адаптеры последовательных контейнеров 575 // ... )1 гоЫ зеггег(рпопту диеие<Меззаде>ь д, 1лзсйь 1сй) ( ти!1е(!д.втрое() ) ( Меззаее т; ( йосйргг й (1сй); д'(д.етрту() ) ге(игл; т = 1. тор ( ); дро ()1 т. зегг(се () 1 ) ) /7 блокировка на время получения сообщения (см. З!4.4.!) // кто-то другой получил сообщение рг!ог!(у диеие<згппя, иесгог<зтппя>,Мосазе> рд; 07/овале для сравнений Ц!714!) при помощи рд.рит)з () и извлекая их при помощи рд. тор () и рд. рор () . Отметим, что объекты, создаваемые из шаблонов, которым передаются разные шаблонные аргументы, имеют разный тип (э13.б.3.1): рпогйу диене<этапу>ь рд1 = рдт // еггог; несовпадение типов Но мы можем предоставить критерий сравнения, не затрагивая типа рг)ог1- ту диеие, просто передав его конструктору в виде аргумента: мгист Яг(пе стр //тип, представляющий критерий сравнения на этапе выполнения ( Яг!пя стр (1пт и = 0); // ...
)1 ьрреае1'рг!ог!(у диеие<згг!пя, гестог<зтг(пд>, Яггтид стр> Рдиеие; гоЫ д (Рдиеиев рд) //рд использует 5(г/пя стр() для сравнений ( Рдиеиерд2 (Вития стр (посоле) ) 1 // "посоле" - сравнение без учета регистра букв рд = рдгт // о(с: рд и рд2 - одного типа, //рд теперь также использует утг!пд стр(посоле) ) Поддержание упорядоченного хранения элементов не дается задаром, но оно и не столь дорого.
В одной из реализаций рг)ог1ту диеие с целью отслеживания от- Этот пример отличается от примера с очередью (Э!7.3.2) тем, что сообщения с более высоким приоритетом будут обслуживаться первыми. Порядок, в котором элементы с одинаковым приоритетом поступают в голову рг)ог)ту диеие, не определен. Два элемента считаются одинаково приоритетными, если ни у одного из них приоритет не выше, чем у другого (Э17.4.1.5). Альтернативный операции < критерий сравнения элементов можно передать в виде аргумента шаблона. Например, можно отсортировать строки без учета регистра букв, поместив их в Глава 17.
Стандартные контейнеры носительного положения элементов используется дерево, что для операций риза() и рар() приводит к оценке 0(7вб(и) ). По умолчанию очередь с приоритетом использует для хранения своих элементов вектор, но можно использовать и любой другой последовательный контейнер, предоставляющий операции ргаиг(), риз7г бас!с (), рар бас!с () и итераторы произвольного доступа. Чаше всего реализации рг!аг!гу (!иене так или иначе используют Ьвар (818.8).
17.4. Ассоциативные контейнеры Ассоциативный массив (аззос!аг(че аггау) — один из самых полезных универсальных пользовательских типов. Более того, в языках, ориентированных на обработку текстов и символов, это зачастую встроенный тип. Ассоциативный массив, часто называемый также отображением (тар) или словарем (дуст!опагу), содержит пары значений. Зная одно значение, называемое ключом ()сву), можно получить доступ к другому значению, называемому отображенным значением (тарред ча!ие).
Ассоциативный массив можно представлять себе как вектор, у которого индекс не обязательно целочисленный: гетр(а!в<с(азз К, сгавв )г> с(авв Аззвс ( риьбс: Гь врегагвг(1 (салзгКа) т //возвраи(ает ссылку на К саатветствуюи(ай К // ... )' Таким образом по ключу типа Х находится отображенное значение типа и Ассоциативные контейнеры являются обобщением понятия ассоциативного массива. Например, контейнер тар — это традиционный ассоциативный массив, в котором единственное значение ассоциируется с уникальным ключом. Ассоциативный контейнер ти!птар является ассоциативным массивом, для которого каждому ключу может соответствовать несколько значений; лег и ти!пзег являются вырожденными ассоциативными массивами, для которых ключу не ставится в соответствие никаких значений. 17.4.1.
Ассоциативный массив п)ар Ассоциативный массив тар — это последовательность лар (ключ, значение), которая обеспечивает быппрое нахождение значения по ключу. Каждому ключу соответствует максимум одно значение. Иными словами каждый ключ уникален. Контейнер шар предоставляет двунаправленные итераторы 619.2.1).
Контейнер тар требует, чтобы для типа ключа существовала операция < (517.1.4.1); он хранит элементы отсортированными, так что перебор элементов осуществляется упорядоченным образом. Для элементов, не имеющих очевидного критерия упорядочения, или в случаях, когда не требуется хранить элементы упорядоченным образом, можно предложить контейнер Ьазй тар 517.6).
17.4. Ассоциативные контейнеры 577 17.4.1.1. Типы Ассоциативный массив тар определяет традиционные типы (в16.3.1) плюс ряд типов, отражающих его специфику: сетрЫе<сйсзь Кеу, сйсьь Т, сйьь Стр=(сиь<Кеу>, сйаь А=а!!нонне<рай<сои!! К!у, Т» > сйьь юг!: !пар ( риЫсс: утины: брессеТКеу Ьеу фре! суресгеу' Т тарртс суре ! сурпсе/рве<сонь! Кеу, Т> из!не суре; суреИе~Стр Ьеу со!праге! урпсеХА аИосайсг суре! !!расе/!!ренате А с: ге~егепсе ге~етпсе ! С!россе~браните А: ! сонм ге3егепсе соим ге~егеисес ррейе1 опр!етепаитп йефпесс! йепан с суре!(еу' (тр!етеисасйп сйрпеИ2 сои!! йепиог! осрасеТ суре пате А:: ьйе суре иее суре ! сурессеу~урелате А:: сгсфегепсе суре с!!Де!енсе суре! буннгеу'за!::гегегье йепиог<йегасог> гегегзе йепиог; брессе~М::гегегие йепиог<сопт (!тасос> сонз! гегегзе йегасог; р.,.
) Обратите внимание на то, что га!ие гуре контейнера тар это пара (ключ,значение). Тип отображенных значений обозначен как таррес1 суре. Таким образом, шар есть последовательность элементов типа ра(г<соиз! Кеу, торрес! суре>. Как обычно, фактические типы нтераторов определяются конкретной реализацией. Поскольку шар, вероятнее всего, реализуется в виде дерева, то его итераторы призваны обеспечить проход по всем узлам дерева. Обратные итераторы конструируются из статшартных шаблонов гегете !сего!ос (и 19.2.5).
17.4.1.2. Итераторы Контейнер тар обеспечивает обычный набор функций, возвращающих итераторы (в16.3.2): сетр1асе<с1ат Кеу, с!аз! Т, ссаьь Стр = 1еьз<Кеу>, сйт А = аНосасог<рой<сопз! Кеу, Т» > с!аз! зМ:: тар ( риЫсс ! У ... !! атераторы: йегасог вел!и () ! санса йегасог Ьел(п ( ) соим; йегасог епа () ! сонь! Йегасог епсС() сонь!с Глава 17. Стандартные контейнеры 578 гегегзе 1!ега!ог гЬеййп (); сола! гегегзе йегагог гЬеа!п () сопзг; гегегзе нега!ог гепй (); соле! гегегзе 1(ега!ог геий() соле(1 У... Итерации по контейнеру тар есть итерации по последовательности элементов типа ра1г<сопзг Хеу, таррей гуре>. Например, можно распечатать записи телефонной книги следующим образом: иогйу'(тор<в!г1пд, питЬег>з раопе Ьооа) ( (урейеу тор<в!егия, питЬег>:: сола! 1!егатог С1; уог(С1р = раопе Ьооа.Ьеа!и () ! р ! = раопе Ьооа.епй() 1 вэр) сои!« р->Як! « ' ~!' « р->зесопй « '~п'; ) Итераторы ассоциативных массивов представляют элементы в порядке возрастания их ключей (Э)7 4 (.5), и поэтому телефонная книга рйоие Ьоой будет распечатана в лексикографическом порядке.
Мы обращаемся к первому элементу любой лары по идентификатору17гзт, а ко второму — по идентификатору зесоий независимо от их фактических типов: !етр!аге<с(азз Т1, с1азз Т2> з!гис! згй::раи ( гурейеу' Т1 у)гз! !уре; турейеу Т2 зесопй !уре; Т1 1)гз!1 Т2 зесоий; рагс(): 1)гзг(Т1 () ), зесоий(Т2() ) ( ) раи (соле! Т1а х, соле! Т2а у): утгзг(х), зесопй(у) () гетр(аге<с(азз 11, с(азз И> рап (соле! раи < 11, )г>а р): 17гз! (р.у)гз!), зесопй(р. зесопй) ( ) )' Последний конструктор предназначен для преобразования пар (э) 3.6.2).
Например: ра1г<1из, йоиЫе> у'(сааг с, т! 1) ( ра(г<сааг, 1иг> (с, 1); (г ... ге!иги х; У иреобразоваиие ра(г<сааг,ии> в ра(г<(п(,йоиЫе> ) В контейнере тар ключ является первым элементом в ларе, а отображенное значение — вторым. Полезность типа ра(г не ограничивается контейнером тар; он является полноправным классом стандартной библиотеки языка Сч-+. Определение раи расположено в заголовочном файле <ип11гу>. Также имеется функция для удобного составления пар: 17.4, Ассоциативные контейнеры 979 гетр!иге<с!аи Т1, с!авл Т2> ран< Т1, Т?> зМ:: тале рагг (Т1 (1, Т2 г?) ( ге!ига ра(г< Т1, Т2> (11, 12) з ) По умолчанию пара инициализируется умолчательными значениями типов ее элементов.
Это приводит к тому, что элементы встроенных типов инициализируются нулями (95.1.1), а элементы типа агг!пК инициализируются пустой строкой (920.3.4). Для типов без умолчательных конструкторов создание пар возможно лишь в форме явной инициализации. 17.4.1.3. Индексация Для контейнера иар характерной операцией является поиск по ключу в рамках операции индексации: гетр!азе<с!аи Кеу, с!аи Т, с!азз Стр = !еи<Кеу>, с!аи А=а!!осагог<ра!с<сопл! Кеу, Т» > с!аи тар ( риЫ!с: УА..
таррей гурей орегаиг(1 (сопл! !сеу !урез й) з УУ доступ к элементу с ключом к /У ... )' Операция индексации выполняет поиск по ключу, заданному в качестве индекса, и возврашает соответствуюшее отображенное значение. Если заданный в операции индексации ключ в контейнере не обнаруживается, элемент с этим ключом и умолчательным отображенным значением типа иарреК фуре внедряется в контейнер иар. Например: иоЫ?'( ) ( тар<згг!пл, !пл> тз УУ пустой массив типа тар иг х = т [ "Непгу" 1 з УУ создается новый вход для "Ненгу", инициался О, возвращает О и [ "Наггу" 1 = 7з г7 создается новый вход для "Ноггу", инициал-ся О, присваивает 7 и! у = и [ "Непгу" ] з УУ возвращает зяачение для входа "Непгу" и!"Наггу" 1 = 9з УУзаиеняем значение для входа "Наггу" на 9 ) В качестве более реалистичного примера рассмотрим задачу вычисления вырученных сумм для всех предметов, представленных в виде пар (имя предмета,значение): пай 100 !заттег 2 заы 3 зази 4 !заттег 7 паН 1000 паи 250 а также сумм по каждому предмету.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
