Бьерн Страуструп. Язык программирования С++. Специальное издание (2011) (1004033), страница 124
Текст из файла (страница 124)
Стандартные контейнеры Стандартные ассоциативные контейнеры требуют, чтобы отображенный тип имел умолчательное значение (517.4.1.7). Такое ограничение не является логически необходимым и может причинять неудобства. Указывая умолчательное значение в качестве аргумента, можно написать: лаза пар<я!г/пк, ХитЬег> раоне Ьооа1! лаза тор<я!г!пя, МитЬег> раоне Ьооа2 (МитЬег (411) ); 17.б.2.1. Поиск Наконец мы можем ввести важнейшие операции поиска: гетр!а!е<с1ат Кеу, сгазз Т, с1ат Н = Наза<Кеу>, егозя ЕД = ег!иа! (о<Кеу>, с!вяз А = айосагог<ра[г<сопт Кеу, Т» > сгат лаза тар ( // ... тарред гуре а орегагог [ ] ( сопя! Ьеу гуре а й ) ; пега!окутай (сант Ьеу !урез); сопя! 1!ега!огЯпй (сопя! Иеу !урез) сопя!; // ...
!етр(аге<с(азз Кеу, с1ат Т, сгазз Н = Наза<Кеу>, с1азз ЕД = ет!иа1 !о<Кеу>, с1азя А = аИоса!от<розг<сопя! Кеу, Т» > зурепате Ьаяа тар<Кеу, Т,Н,Ей,А>:: тарред !урез лаза тар<Кеу, Т, Н, ЕЯ, А >:: орегагог [ ] ( сопят Иеу !урез Ь ) ( злге туре г' = Ьаза (Ь) вАЬ.я!ге() т // хэш // поиск среди входов, хэшированных в ! // найдено аког (Еп!гу* р = Ь [т] т р; р = р->пел!) г7'(еа(й,р->йеу) ) (Т(р->егаяег() ( р->егаяеФ = Тигле; но оТ егазетг- —; гегигп р->иа1 = Иегаиг! га!ие; ) генон р->го!1 ) У повторная вставка // не найдено: (Т(я[ге гуре(Ь.з!ге() *так 1оаИ <=г.я!ге() ) ( гез!ге (Ь.я!ге() *Кгош) ! ге!игн орега!ог [] (Ь); ! // слишком плотное заполнение У расширяем /У рехэшируем Чтобы найти га1ие, операция [1 использует хэш-функцию с целью нахождения индекса в хэш-таблице для ключа (Ьеу).
Затем просматриваются записи до тех пор, пока не будет найден совпадающий йеу. Значение га1ие в этой записи и есть то, что мы ищем. Если оно не находится, вставляется умолчательное значение: 17.6. Создание нового контейнера г.ризй Ьасй (Епоу(сс, сгезаисс гасив, Ь [с] ) ) с д добавляем Епоу Ь[с) = зг.Ьасй() с д указываем но новый элемент гесигп Ь [11->гаН ) В отличие от тар, Ьазй тар не опирается на проверку эквивалентности, синтезированную из операции сравнения на меньше [817.1.4.1). Это связано с вызовом функции ед () в цикле просмотра элементов с одинаковым хэш-значением.
Данный цикл критически важен для производительности поиска, а для обычных типов ключа, таких как зсг1лК или С-строка, перерасход времени на лишние сравнения может быть значительным. Я мог бы использовать зес<Елггу> для представления множества записей с одинаковыми хэш-значениями. Однако если у нас есть хорошая хэш-функция [Ьазй () ) и хэш-таблица подходящего размера [Ь), то большинство таких множеств будут содержать ровно один элемент. Поэтому я связал элементы этого множества между собой с помощью поля лехс каждой записи Елсгу (817.8[27]).
Заметим, что Ь содержит указатели на элементы вектора г и что элементы добавляются в к Вообще говоря, функция ризй Ьасй () может вызвать перераспределение памяти и, тем самым, сделать указатели недействительными (неверными) (816.3.5). Однако в данном случае конструкторы (817.6.2) и функция гез1зе() применяют гезегзе() с целью аккуратного резервирования памяти, предотвращающего ее неожиданные перераспределения. сетрсасе<с1азз Кеу, с1ат Т, ссазз Н = Назй<Кеу>, с1ат ЕД = едиас со<Кеу>, ссат А = а11осасог<расг<сопзс Кеу, Т» > с1азз йазй тар ( УУ ...
гоЫ гез(ге(з(зе суре п) с дразмер хэш-таблицы - в и д удаление указуемого эл-та зоЫ егазе (ссегасог роз1боп ) зсзе суре зсге() солт (гесигп г.зсзе()-ло о3' егазесгс) дчисло элементов зсзе суре Ьисйес соил( () сопи (гесигп Ь.зйе () с ) д размер хэш-таблицы У применяемая хэш<функция д равенство Назйег Ьазйуип () солт ( гесит Ьазй с ) Ьеу ециас Йеу ец О сопзс ( гесигл ецс ) У ...
): Операция гез1зе () очень важна, достаточно проста и потенциально дорога: 17.6.2.2. Операции егазе() и гез[хео Хэшированный поиск становится неэффективным, когда таблица переполняется. Чтобы снизить вероятность этого, таблица автоматически изменяет размер при помощи функции гез(ге(), вызываемой из операции индексации. Операция зес 1оаК() ($17.6.2) обеспечивает контроль за этим процессом [как и когда происходит изменение размера таблицы).
Другие функции позволяют программисту следить за состоянием йазй тар: Глава ] 7. Стандартные контейнеры 600 <етр<а<е<с<аии Кеу, с<ая Т, с<аии Н = Наий<Кеу>, с<аии ЕЯ = едиа! <о<Кеу>, с!аиз А = а<<оса<ог<ра<г<сопи< Кеу, Т» > чоЫ йаий тар<Кеу, Т,Н,ЕЯ,А><:геи<ге(и<ге <урез) ( и1ге ~ре! = и. и<ге () < [< (и <= Ь.яге () ) ге<ига< //реально уопраняет "удаленные" элементы <«й<1е (по оу' егаие«) ( [Т(г [ — -1] . егаие<[) ( г.егаие(г.ЬеКЫ П»1) < --по о!' егаие«< ) ) Ь.геяге(и) < <Ш(Ь.Ьее<п[),Ь.еп«(],[)) < //обнуляем входы Д!8бб) и.
геиегге [и*тех 1оа«); //если и нулсдоется в памяти, делаем это сейчас //рехэширование )ог[яге <уре1= О< 1<».яге[) «»») ( яге <уре й' = йаий [и[1] .Ьеу) АЬ.яге() < //хэширование »[1] .пех< = Ь[й] < р связь Ь[й] = ьг[<]< ) При необходимости пользователь может «вручную» вызвать гааге(), чтобы избавиться от неожиданных вызовов этой функции.
Функция геи[ге [) крайне важна во многих приложениях, но она не является принципиально фундаментальной для хэш-таблиц. В некоторых реализациях она вообше не применяется. Вся реальная работа делается в другом месте [и только если йазй <пар изменяет размеры), так что функция егаие () тривиальна: <етр!а<е<с1ази Кеу, с<пи Т, с<аии Н = Наий<Кеу>, с<вяз Е[Е = еоиа< <о<Кеу>, с<аиз А = айоса<ог<ра<г<сопя Кеу, Т» > гоЫ йазй тар<Кеу, Т,Н, Е<й,А> «егаие(дега<о< р) ( <Т(р->егаие<< ==/а<ие] по оу егаие<<+»< р->егаиеИ = иие< ) 17.6.2.3.
Хэшироввние Чтобы закончить с йаий тар:: орега<ог [ ] ( ), нам еше нужно определить функции йаий [) и е<7() . По причинам, которые станут яснее в 5]8.4, хзш-функцию лучше всего определить в виде функции орега<ог() () класса функциональных объектов: <етр<а<е<с1аии Т> и<гис<Наий< ипагу ~ипс<<оп<Т,и<ге <> ( яге < орега<ог () [сопи< Ть йеу) сопя< 601 17.6. Создание нового контейнера Хорошая хэш-функция берет ключ и возврашает целое число таким образом, что различные ключи с высокой степенью вероятности отвечают различным числам. Выбор хорошей хэш-функции — это искусство.
Часто, однако, вполне приемлемой является операция «исключаюшее ИЛИ» над битовым представлением ключа: <етр1а<е<с!ат Т> и!ге <На<Ь<Т>::орега<ог() (сопи< Тг Ьеу) сопи ( яге <геи = О< яге < <еп = ягеоу[Т) < сопи< сьаг* р = ге(п<егрге< сои<сопи< сваг*> ( ьЬеу) <«Ь<1е(<ел--) геи = (геи«1) "*р««< гепап ге<< Применение ге<п<егрге< спи< Я6.2.7) служит четким указанием на то, что выполняется нечто исключительное, и что в случаях, когда о хэшируемых объектах имеется более подробная информация, можно поступить лучше.
В частности, если объекты содержат указатели, являются очень большими или имеют внутри пустые места из-за требований к выравниванию их полей, мы можем что-ннбудь улучшить (см. 5! 7.8]29]). С-строка — это указатель, а строки иптпя содержат указатели. Следовательно, уместны специализации: <урейе1 сваг* Рсваг< <етр<а<е<> яге < На<Ь<Р<ваг>::орега<ог() (сопи< Р<Ьагг Ьеу) сопи< ( яге <геи=О; РсЬаг р = Ьеу< лЬйе(*р) геи = (геи«1) ""р+«< ге<ага ге<< <етр1а<е<> яге < НаиЬ<и<г!лд>: <орега<ог () (сопи< илтляи Ьеу) сопя ( яге <ге<=О; <уре«е~'и< <лО:: соли< вега<от С1< С1 р = Ьеу.
Ьея(п ( ) < С1 еле = Ьеу.еле() < тЬЫе (р! =еле) геи = (геи«1) "«р««< ге<игл гею Реализация Ьаий тар должна включать хэш-функции по крайней мере для целых и строковых ключей. Для других типов ключей пользователю придется прибегнуть к иным специализациям. При выборе хэш-функций большое значение имеют эксперимент и замер результатов. Интуиция в этой области работает плохо.
Глава 17. Стандартные контейнеры 602 Для завершения контейнера йатй тар требуется определить еше итераторы и большое число вспомогательных функций; оставляем это в качестве упражнения Я17.8[34[). 17.6.3. Другие кэшированные ассоциативные контейнеры Для полноты и согласованности помимо йазй тар должны быть еще йазй зег, йазй ти!птари йазй тиЬЬсд Их определения вытекаюточевиднымобразомизопределений йазй тар, тар, ти1итар, веги ти(гЬег, так что я оставляю это в качестве упражнения (817.8[34[). Доступны хорошие коммерческие и свободно распространяемые реализации этих хэшированных ассоциативных контейнеров. Для реальных применений их следует предпочесть версиям вроде моих, сконцентрированных на локальных проблемах. 17.7.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
