Б. Страуструп - Язык программирования С++. Специальное издание, 3-изд. Бином. 2004 (1160791), страница 119
Текст из файла (страница 119)
17.4.1. Ассоциативные массивы Ассоциативный массив тар — это последовательность пар (ключ, значение), которая обеспечивает быстрое получение значения по ключу, Каждому ключу соответствует максимум одно значение. Инымп словами. каждый ключ в ассоциативном массиве уникален. Контейнер тар предоставляет двунаправленные нтераторы (9 19.2.1). Ассоциативный массив требует, чтобы для типов ключа (9 17А,1) супгествовала операция <меньше> (9 17,14.1); он хранит свои элементы отсортированными (по ключу) так, что перебор происходит по порядку.
Для элсментов, не имеющих очевидного понятия порядка, или в том случае, когда нет необходимости держать контейнер отсортированным, мы можем рассмотреть использование !гаяй тар (9 17.6). 17.4.1.1. Типы Ассоциативный массив имеет обычные типы членов контейнера (9 16.3.1) н несколь- ко, отражающих его специфику: 1етр1а1е<с!аяя Кеу с!аяя Т с! аяя Стр = !еяя<Кеу> с!аяя А = ауосагог<рог г <сопя1 Кеу, Т» > с1аяя ягйстар ( риб!!с. // типы ! 1урейе)Кеу беу 1уре; 1урейе~7таррей 1уре; 1урейеТ ра!г<сопя1 Кеу, Т> иа1ие 1уре; гурейе(Стр беу сотраге; гурейе~А ивосп1ог 1уре; 1урейеТ1урепате Асге~егепсе геТегелсе, гурейез 1урепатеА сопля! ге)егепсе соля1 ге(егепсе; 1урейеТ!тр!епгеп1аг!оп йе3пей! Нега1ог, 1урейе~!тр!етепгаг!оп йейпейу солИ Иега1ог; 1урейе1 1уреггитеА;тйее 1уре Иее 1уре; 1урейеТ1урепатеА<Щегепсе гуре йЦегепсе 1уре, 1урейе) ягй>геиегяе веги!ос<пег!ног> геиегяе Вега!ог, 1урейе) я!йсгеоегяе Пеги1ог<сопя1 11ега1ог> солИ геиегяе Нега1ог, Отметим, что иа!ие 1уре контейнера тар — это рагг, пара (ключ, значение).
Тип отображенных значений обозначен как таррей 1уре. Таким образом, тар — это последовательносль пар ра!с<со!ге! Кеу, таррес! 1уре>. Глава 17. Стандартные контейнеры 540 Как обычно, фактические типы итераторов определяются при реализации (ппр)ешепса!)оп-с(е1(пе<(). Поскольку тар, скорее всего, реализована с использованием какой-нибудь формы дерева, эти итераторы обычно обеспечивают некоторый способ прохода по дереву. Реверсивные итераторы конструируются из стандартных шаблонов геиегие !1ега1ог Я 19.2.5).
17.4.1.2. Итераторы и пары Контейнер тар обеспечивает обычный набор функций, возвращающих итераторы Я 16.3.2): !етр!а!е<с1азз Кеу, с1азя Т, с1азя Стр = 1езв<Кеу>, с1аязА = пупса!от<риг <соля! Кеу, Т» > с!авз тар ( риб1!и: //- // атераторьн пега!от Ьеу!и (); сопя! йтта1ог беу!л () салий !!ига!от еп!1 (); сопи! !!ига!отел!1 ()сопи!; тепзгие Нега1ог тЬеу!и (); сопв1 !епегве 11ета1оггбеу!п () солз1; геивгве 1!егп!ог тип<1 (); сопя! гепегве 1!ига!ог геп6 () сопи!; //-.
); Итерация по тар — это просто итерация по последовательности пар ра1т<сопз1Кеу, таррев! 1уре>. Например, мы могли бы распечатать записи в телефонной книге: оо1в(Ятар<вгг1лу, питЬе! >2, рбопе Ьооб) ( !урз<1е~тар<з!плу, питЬят>:сопв1 !!ега1ог С1; /ог (СТр = рбапе Ьооб.беу!и ~; р)=рбопз Ьооб епа' ();.н.р) саи1 «р — >иг!ги! « '~!' «р — >весов!1 « '~п'; Итератор для ассоциативного массива предоставляет элементы в порядке возрастания их ключей Я 17А.1.5), поэтому пункты телефоннои книги рйопе Ьоой будут выведены в лексикографическом порядке.
Мы обращаемся к первому элементу любой пары ра!т как кфгз1, а ко второму как к зесопс( независимо от того, какого типа они в действительности; 1ет р1а1з<с!азв Т1, и1 азз Т2> в!гас! в1й:.ра1т ( 1урег1е/Т1/!гв! туре; 1уре<1е~Т2 взсопг( 1уре; Т! /)гяг; Т2 зесол!1; 541 17.4, Ассоциативные контейнеры ра(г() 3!ге!(Т! ()), яесопс((Т2())() ра(г (сопи ! Т! й х, сопи! Т2й у) ./!ги! (х), весел с( (у) ( ) 1етр(а1е<с(аяи 1(, с(азя 1г> ра!г (соптра(г<((, г>йр) 71гз! (р/)гз!), иесопч((р яесопа!) ( ) Последний конструктор существует для того, чтобы позволить преобразования в инициализаторе Я 13.6.2). Например: ра!г !и1, с(оиЫе>!(с(час с,!и! !) раи<с(чаг, (п!> х (с, !) //.- ге1игп х; // требуется преобразование раа<сяаг, го1> в ра!г<(п(, доиЫс> В отображении ключ является первым элементом в паре, а отображенное значенне— вторым.
Полезность класса ра(гне ограничивается реализацией тар; он является полноправным классом стандартной библиотеки. Определение ра(г находится в заголовочном файле <и(!(!(у>. Также обеспечена функция, позволяющая удобным образом создавать ра и". 1етр(а!е<с1ази Т(, с1авз Т2> раи Т(, Т2> я(г(ста(ее ра1г (Т1 !1, Т2 !2) ге1игп ран Т(, Т2>(11, !2); Пара ра!г по умолчанию инициализируется значениями по умолчанию для типов ее элементов.
В частности, это приводит к тому, что элементы встроенных типов инициализируются нулями Я 5. ).1), а с~роки в1г!пд — пустыми строками Я 20ЗА). Тип, не имеющий конструктора по умолчанию, лиожет быть элементом пары ра(г только при условии, что она явно инициализирована. 17.4.1.3. Индексация Типичная операция с ассоциативным массивом — это ассоциативный поиск при помощи оператора индексации (()): 1етр!а1е<с(авя Кеу, с!аяи Т с1аив Стр = (еии<Кеу>, с!азв А = а((оса!ог ра(г <сопя1 Кеу, Т» ' с(аяя !пар ( риЫ1с.
таррес( 1урей орега1ог() (сопв1 йеу 1урей (!), //доступ к элементу и ключом (ч Оператор индексации выполняет поиск по ключу, заданному в качестве индекса, и возвращает соответствующее значение. Если ключ не найден, в ассоциативный массив вставляется элемент с этим ключом и значением по улюлчанию типа терре(( 1уре. Например: оо(г( Т() Глава 17. Стандартные контейнеры 542 //сначала ассоциативныймассив пуст //создаем новую запись для "Генри', // инициализируем его нузелл и возврасцаел~ 0 // создаел~ новую запись для "Гарри, // инициализируем его нулем и присваиваелл 7 //возвраи(аелл значение из записи 'Генри' // заменяем значение записи "Гарри' на 9 тар<з1ггла, лл1> т; !п1 х = т('Генри~! т)" Гарри" ) = Г; ш1 у = т('Генри' ); т! Гарри' ) = 9, Как чуть более реалистичный пример, рассмотрим программу, подсчитывающую общую стоимость предметов, представленных в форме пар (название предмета, стоимость), например: па!! 100 Иаттег 2 зав 8 зато 4 Иаттег Г паП !000 ла!! 250 и также подсчитывающую сумму по каждому предмету.
Основная работа может быть выполнена при считывании пар в ассоциативный массив: оо!д геас!!1етз (тир<в!ггпу, гпг>й т) ( тмпд вогд; лп1 оа1 = 0; в!и1е (сгп» воп1»оа!]т(вогд) ч= оа1; тар<з1г1па, ш1> 1Ы; геад11етз (1Ы) ш1 1о1а1 = 0; 1урес!е/тар<з1плу, ш1>зсопз1 Иега1огСС /ог )С1 р = 1Ы.Ьеалл )); р~=гЫ.епл( (); -н р) ( 1о1а! += р->зесопс(; сои1 «р — >/лгз! « 'л Г «р- зесопс! « 'чул' сои1 « "— — — — — — — — ул1о1арлГ «1о1а! «~,п'; ге1игл ~с!п; При выщсуказанном входе мы получим на выходе: Иапипег 9 лал! 1250 зав 7 1ога! 1366' Отметим, что предметы печатаются в лексикографическом порядке Я 17А.1, 9 17А.1.5).
Операция индексации т(вогс() определяет соответствующую пару (з1г/лп, лл1) и возвращает ссылку на ее часть 1л1. Эта программа пользуется тем, что в новом злементе по умолчанию значение ш1устанавливается в О. Ассоциативный массив, сконструированный функцией геас!11ет (), затем может быть выведен при помощи обычного цикла: 1л1 талл () ( 543 17.4. Ассоциативные контейнеры Операция индексации должна найти в ассоциативнолг массиве ключ.
Это, конечно, не так лешево, как индексация массива целылг числом. Цена равна О (!оу (злее о/ тар)), что лля многих прикладных программ приегмлемо, Для тех, кому зто не годится, выходом может послужить хэшируемый контейнер Я 17.6). Когла ключ не находится, операция индексации добавляет элемент по умолчанию. Поэтолгу для константных ассоциативных массивов не существует версии орегагог() (). Более того, индексация может использоваться, только если торрес! !дре (тип отображенного значения) имеет значение по умолчанию. Бели программист просто хочет посмотреть, существует ли такой ключ, для поиска ключа йед без изменения ассоциативного массива можно воспользоваться операцией Япс) () Я 17.4.1.6). 17.4.1.4.
Конструкторы Класс тар обеспечивает обычный комплект конструкторов и т. и. (ф 16.3А): !етр1а!е<с1аккКеу, с!акк Т, с1акк Стр = 1екк<Кеу>, с!аккл = айоса!ог<ра!с<сопя!Кеу, Т» > с!акк тар ( ри!>!!сг //- //сконсаугуарояапгь/скопарояапгь/уничтожить: ехр!!с!! тар (сопя! Стрй с = Стр (), сопя!Ай А ()); !етр1а!е<с1акь 1п> тар зп/ггк1, 1п !акг, сопя! Стрй с= Стр (), сопя! Ай = А ())г тар (сопя! тарй), -тар (); тарй орега!ог= (сопя! тарйг //- ); Копирование контейнера требует выделения памяти для алементов и создания копии каждого элемента Я 16.3.4), Это может оказаться очень дорого, н делать зто нужно лишь при необходимости.
Поэтому контейнеры, такие как ассоциативные массивы, часто передают по ссылке. Конструктор члена шаблона принимает последовательность пар рагг<сопз! Кеу, Т>, описанных парой итераторов для чтения. Функцггей !пяег! () (ф 17А.1.7) конструктор вставляет элементы из последовательности в ассопиативный массив. 17.4.1.5. Сравнения Чтобы нагйти в ассоциативном массиве элемент поданному ключу, операции массива должны сравнивать ключи. К тому же итераторы перемещаются по ассоциативволгу массиву в порядке возрастания значений клгоча, и при вставке, как правило, ключи тоже будут сравниваться (чтобы поместить элемент в структуру дерева, представлятощего ассоциативный массив). По умолчанию используемое для ключей сравнение -- это < (<лгсньше>), но можно обеспечить альтернативу в виде параметра пгаблона илп аргумента конструктора гсм.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
