Б. Страуструп - Язык программирования С++. Специальное издание, 3-изд. Бином. 2004 (1160791), страница 124
Текст из файла (страница 124)
Данный цикл является решающим для производительности поиска, а для обычных очевидных типов ключа, таких как я1г!пу и С-строка, перерасход времени на лишние сравнения может быть значительным. Для представления набора значений с одинаковым хэш-значением я мог бы воспользоваться зе1<Епй.у>. Однако если у нас есть хорошая хэш-функция (Ьаяй ()) и хэш-таблица подходящего размера, больпчинство таких множеств (зе1) будут иметь ровно один элемент. Поэтому я связал элементы этого множества вместе при помощи поля пех1 в зат<гш Епггу Я 17.8[27)).
Отметим, что Ь содержит указатели на элементы э, и что элементы добавляются к ж Вообще говоря, функция рияЬ ЬасЬ () может привести к перераспреде.пению памяти и тем самым сделать указатели на элементы неверными Я 16.3.5), однако в данном случае конструкторы Я 17.6.2) и гез!ге () предусмотрительно резервируют (операцией геяегие ()) достаточно памяти, чтобы не случилось неожиданного перераспределения. Глава 17.
Стандартные контейнеры 552 шЬ!!е (ло о/ егазег!) ( О фактически уничтожает удаленные злемен~пы 1/ (и ( — !].егаяез!) ( и.егаяе(й и[!]); — ло ой" егаяед; Ь.геяие (я); Я!!(Ь Ьеу!и (), Ь.ела)), О) игезегье (я*тих !оа<Ту //добавляет я укозтпелей на блие!) 1/обнуляет все элеленты !з !йб.б) // если для и нуэкно перераспределить пажять, // пусть это пронзойс)ет сейчас Зос (яие 1уре1= 0; !<илие (); !ьь) ( // повторное хэншрование: гйзе 1урей = Ьаяй (и(!).Ьеу)АЬ.я!зе (); //хэишрование и(!]пел! = Ь(и), // связь Ь(!!] = йи.Ьеу!и () + Ь гетр!а!в<с!азя Кеу, с!аяз Т, с!аяз Н = Наяй<Кеу>, с!азяЕС!= едиа! 1о<Кеу>, с!аязА = а!!оса1ог<рагг<соля1Кеу, Т» ио!с! ЬазЬ тар<Кеу, Т, Н, Е9, А>легаяе (Нега1огр); //удаляет элеиент, на который // указывает итершпор ( 11 !р — >егаяед ==)а!зе) по о/ егаяей++; р->е~ аяед = Ь ие; ) 17.6.2.3.
Хеширование Чтобы завершить ЬаяЬ тарсорега1ог(] (), нам нужно определить ЬазЬ () и еа (). По причинам, которые станут яснее в ~ 18.4, хэш-функцию лучше всего определить как орега1ог () объекта-функции; 1етр!а!в<с!азз Т> ззгис1ИаяЬ . ипагу /ипс1!оп<Т, з)ге ! ( яие 1орега1ог() (соля! Тййеу) сопя1; ); Хорошая хэш-функция берет ключ и возвращает целое число, так что различные ключи с высокой степенью вероятности отвечают различным числам.
Выбор хоро- шей хэш-функпни — это искусство. Однако часто приемлемой является операция исключающего ИЛИ с битами ключа, представленного как целое число: !урез!е/сйаг" Рсьаг, 1етр1а1е< > яие 1ИаяЬ<рсЬаг>зорега1ог () (сопя1 РсЬагй Ьеу) сопят зие 1гез = 0; ) При необходимости пользователь может «вручную> 'обратиться к гея(ге (); чтобы гарантировать, что размещение не произойдет в неподходяшее время. Я считаю, что функция геяие () очень важна во многих прикладных программах, но она не связана фундаментально с понятием хэш-таблицы. В некоторых стратегиях реализации она вообще не нужна.
Вся реальная работа делается где-то в другом месте (и только если ЬаяЬ шар мецяет размеры), поэтому егаяе (] реализуется тривиально: 563 17.6. Определение нового контейнера Иее 1 1еп = в(еео/(7), сопя1 айаг р = гип1егргег слег<сопя! сйогЬ(ййеу) // доступ к объекту как к // последовательиоспш войтов мй!1е (!еп — )!ее= (гев 1)"'рь+; //оспользоваиоеиелоиосленнох // значений со овалов ге1игп гея; Мы можем сделать что-то получше, когда больше узнаем о хзшируемых объектах. В частности, если объект содержит указатель, если объект большой, или если из-за требований к выравниванию членов в представлении остаются пустые места /едырыь), обьзчно мы можем что-нибудь улучшить (см. Я 17.8(29]).
С-строка — это указатель 1на символы), а строка в!пад содержит указатель, Следовательно, уместны специализации: !уребг/сйог*рсйаг; 1етр!осек> мяе 1Наяйссйлг'>:.орега!ог() (солв1сйаг'йеу) сопИ ( гиге ггея= О; Рс(~агр=йеу; мйве (*р)гея = (гея«1)""р++; ге1агп гея, //использую(пся Иелае знаиення символов гетр!авек> ясее 1 Навйся1г(пуьзорега1ог() (сопягягнлу8, йеу) сопИ загс ! гея = О, гуреде/яснпузсопв1 11ега1ог С1; С1р = йеу 6еу!п (), С1 епд = йеу.епс( (), //использую!пся 1)ель~в знаиеиоя съ кволое шй!!е р!=епд) гея = (гев«1)"'рн-, гесогп гея, 17.6.3.
Другие кэшированные ассоциативные контейнеры Для согласованности и полноты Ьаяй тар должны бы соответствовать ЬаяЬ ве1, Ьавй спи!1/шар и ЬаяЬ ти!1(ве1. Их определения очевидны, исходя пз Ьаяй тар, тар, ти(1!тар, яе1 и ти!Нве(, поэтому я оставлю их в качестве упражнений Я 17.8(341). Доступны хорошие свободно распространяемые и коммерческие реализации этих хэшпрованных ассоциативных контейнеров, Для реальных прозрамм их следует предпочитать версиям вроде моих, сконцентрированных на локальных проблемах. ) Реализация Ьаяй тар включает хэш-функции по крайней мере для целых и строковых ключей. Для более сложных типов ключей пользователю, вероятно, придется прибегнуть к помощи подходящих специализаций.
При выборе хэш-функции очень важно экспериментирование и измерение результата. Интуиция в этой области работает плохо. Чтобы завершить Ьаяй !пар, нам нужно определить итераторы и большое количество второстепенных тривиальных функций; это оставлено в качестве упражнения Я 17.8(341). Глава 17.
Стандартные контейнеры 17.7. Советы [1] По умолчанию, если вам нужен контейнер, используйте вектор (иес1ог); З 17.1.2. [2] Узнайте стоимость (сложпость, асимптотическую О-оценку) каждой операции, которой вы часто пользуетесь; ~ 17.1.2. [3] Интерфейс, реализация и представление контейнера — это различные понятия.
Не смешивайте их; ч !7.1.3. [4] Сортировать и искать можно в соответствии со множеством критериев; з 17.1А,1 [5] Не пользуйтесь С-строками в качестве ключа, если вы не обеспечили подходящего критерия сравнения; я 17.1А.1. [6] Вы можете определить критерий сравнения так, чтобы эквивалентные, но все же отличающиеся значения ключей, отображались в один и тот же ключ; Я 17.1А.1. [7] При вставке и удалении элементов предпочитайте операции с концом последовательности (Ьасй-операции); ~ 17,1.4.1. [6] Когда нужно производить много вставок и удалений из начала или середины контейнера, используйте списки (йя1); ~ 17.2.2. [9] Когда нужно главным образом обращагься к злемен ~ам по ключу, пользуйтесь тар и ти(йтар; я 17.4.1.
[10] Для достижения максимальной гибкости пользуйтесь минимальным набо-' ром операций; з 17.1.1. [11( Если элементы должны быть упорядочены, выбирайте тар, а не ЬаяЬ тар; ь 17.6.1. [12] Когда важна скорость поиска, выбирайте Ьаяй тар, а не тар; з 17.6,1, [13] Если для элементов невозможно определить операцию «меньше», между тар и ЬаяЬ тар выбирайте ЬаяЬ тар; ) 17.6.1. [14) Для проверки того, есть лп данный ключ в ассоциативном контейнере, пользуйтесь функциейу]лд (); я' 17А.1.6.
[15] Чтобы найти в ассоциативном контейнере элементы с данным ключом. пользуйтесь функцией едиа7 галде (); я 17А.1.6. [16] Когда нужно хранить несколько значений для одного ключа, пользуйтесь тий(тар; 5 17.4.2. [17] Когда сам ключ является единственным значением, которое нужно хранить, пользуйтесь яе! и тиЫяе1; ф 17А,З. 17.8. Упражнения Решения к некоторым упражнениям этой главы можно найти, заглянув в исходный текст вашей стандартной библиотеки. Но сделайте одолжение — попытайтесь найти собственные решения, прежде чем смотреть, как подошел к проблеме разработчик библиотеки. Потом посмотрите на собственную версию реализации контейнеров и их операций. 1.
(*2.5) Поймите, что означает О () Я 17.1.2). Проделайте измерения для операппй стандартных контейнеров, чтобы определить постоянные коэффициенты (множители перед О ()). 2. (*2) Многие телефонные номера не умещаются в тип 1опд. Напишите тнп рйопе питЬег и класс, обеспечивающий набор полезных операций с контейнером телефонных номеров типа рЬоле литЬег. 17.8.
Упражнения 565 3. (*2) Нызишите программу, которая бы заносила различные слова в файл в алфавит ном порядке. Сделайте две версии: пусть в одной слово будет просто последовательностью символов, разделенной символами-разделителями, а в другой — последовательностью символов, разделенной символами, не являющимися буквами. 4, (*2.5) Реализуйте простую карточную итру «солитер» (пасьянс «косынка»). 5.
(*1.5) Реализуйте простую проверку, является ли слово палнндромом («перевер тышем», то есть словом, в котором буквы располагаются симметрично, например: «наган», «казак», «боб»). Реализуйте простую проверку, является ли целое число палиндромом. Реализуйте простую проверку, является ли последовательность палиндромом. Обобщите. 6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
