Б. Страуструп - Язык программирования С++. Специальное издание, 3-изд. Бином. 2004 (1160791), страница 123
Текст из файла (страница 123)
Примеры применения тар, приведенные в этой книге до сих пор Я 3.7.4, ~ 6.1, э 17.4.1), могут быть преобразованы к использованию Ьаяй тар простой заменой имени тар на Ьаяй тар. Часто изменение тар на Ьаяй тар можно облегчить, используя 1урес/еЯ Например: что для больших контейнеров, где поиск играет очень большую роль, Ьаяй тар работает в 5-10 раз быстрее, чем тар, С другой стороны, Ьаяй тар с плохо подобранными хэш-функциями может оказаться гораздо медленнее, чем тар. Есть много способов построения хэш-таблицы. Интерфейс ЬаяЬ тар разработан так, чтобы отличаться от интерфейса стандартных ассоциативных контейнеров только тогда, когда это необходимо для выигрыша в быстродействия за счет кэширования.
Самое фундаментальное различие мезкду тар и Ьаяй тар заключается в том, что п/ар требует от типа своих элементов оператор <, в то время как Ьаяй тар требует == н хэ/п-функцию. Таким образом, Ьаяй тир должен отличаться от тар при создании не по умолчанию.
Например: 558 Глава 17. Стандартные контейнеры 1урес/е~/>акЬ гоар<к! Нпд, гесогс/> Марн Мар а>!с/!спасу; Оператор /урсс/е7 также полезен для сокрытия от пользователе>й точного типа словаря. Хотя это не совсем корректно, я представляю выигрыш и потери от применения тар и Ьакй тар как просто выигрыш во времени за счет памяти и наоборот.
Если эффективность не играет роли, не стоит тратить время, чтобы сделать выбор между ними: хорошо работать будут и тар, и Ьакй тар. Для больших и интенсивно используемых таблиц Ьакй тар имеет явное преимущество в скорости и должен использоваться, если нет дефицита памяти. И даже тогда, прежде чем выбрать «просто» тар, я бы рассмотрел другие способы экономии памяти.
Нужно произвести непосредственные замеры, чтобы не оптимизировать неверную программу. Ключ к эффективному хэшированню кроется в качестве хэ>п-функций. Если хорошая хэш-функция недостижима, тар может легко превзойти Ьакй тар по эффективности. Хэширование, основанное на С-строке, строке к/г!адили целом числе, обычно очень эффективно. Однако стоит помнить, что эффективность хэш-функций чрезвычайно зависит от собственно хзшируемых значений Я 17.8[351). Контейнер Ьакй тар нужно использовать там, где оператор < не определен или не подходит к предполагающемуся ключу. И наоборот, хэш-функция не определяет упорядочения так, как это делает <, поэтому тар нужно использовать, когда важно держать элементы отсортированными.
Как н тар, Ьазй тар обеспечивает операц>по /!пс/ [[, чтобы позволить программисту определить, был ли ключ вставлен. 17.6.2. Представление и конструирование Возможно много разных реализации Ьакй тар. Здесь я привожу одну, которая обеспечивает неплохую скорость, и наиболее важные операции которой довольно просты. Ключевые операции — это конструкторы, поиск (оператор [~), изменение размеров и удаление элемента (егаке [)). Простая реализация, выбранная здесь, основана на хзш-таблице, представляющей собою вектор указателей на записи (епгг/ек). Каждая запись хранит ключ Ьеу, значение па!ие, указатель на следующую запись (если она есть) с тем же хзш-значением, и бит егазес( («удален»); ключ значение удален следуя>щнй клк>ч значение удален следующий Выраженное в объявлениях, это выглядит следующим образом: /етр!а1е<с!акк Кеу, с!акк Т, с!акк Н = Оакй<Кеу>, с!акк Е«!= ециа! 1о<Кеу>, с1аккА = а!!оса1ог<ра!г <сопк/Кеу, Т» с1акк/гакЬ шар ( 0 ...
рг/оа1е />> предс>пакление к1гис1 Еп1гу ( 559 17.6. Определение нового контейнера (ьеу гуре Ьеу; тарред 1уре иа1; Ьоо! егазед; Еп1гу* пехт, // связь переполнения хэши Ел( у )Ьеу 1уре Й, тарред 1уре оЕпьгу' и) Йеу (Ь), иа! (и), егазед (/а!зе), лех1 (п) [) //действительныеэаписи //хэш-тадлицп: указатели ни и сес1ог<Еп1гу> и; оес1ог<Ел! у'> Ь; (етр!ате<с1азв Кеу, с1азз Т, с1азз Н = Назд<Кеу>, с1азз Е17 = еуиа1 1о<Кеу>, с!аззА = ауоса1ог<ра г <соле(Кеу, Т» > с!аззьазд тар( Ьазь тар(соле! Тд с(и = Т(),з!хе 1уреп=!01, сопя(Нд Ь =Н(), сопз1Е17д, е = Е(7 ()): с!и/аи!1 иа!ие (ди), Ь (л), ло о/ егазед (О), Ьазь.
(Ь), а) (е) ( зе1 1оад(); // ло улюлчанию и гезегие (та !вайд.з(хе ()); //реэервируем по.чять для рости ) со~две( !оас((/!оа1 т = 07 /!оа у= !0) (тах !оаь(= т, угош = у; ) рчниа1е. /)оа1 тах !оаь(; /!оа1угош; //удерживает и.э!хе()<=Ь.э(хе()*та )оад // при необходимости изменяем размеры //гегдхе(Ьисуе) соил(()'угош) //число записей во, занятых // стертылш элел~еньпилш з!хе 1уре по о/ егазес(; //хэш-функция // ровенапво Наздег Лазд; Йеу еуиа! еу; // значение ло улюлчаншо, используе чое // оператором П соле! Т Йе/аиН иа1ие; Стандартные ассоциативные контейнеры требуют, чтобы отображенный тнп имел значение по умолчанию (9 17.4.1.7). Это ограничение не является логически необ- Отметим бит егазес(. Способ, которым здесь обрабатывается несколько значений с одинаковым хэш-значением, затрудняет удаление элемента.
Поэтому вместо лействительного удаления при вызове функции егазе() я просто помечаю элемент егазеь! («удален>) и не обрашаю на него внимания, пока таблица не изменит размеры. В дополнение к главной структуре данных Ьаз/ь тар нуждается в некотором количестве алминистративных данных. Естественно, каждому конструктору нужно установить все ато. Например: Глава 17.
Стандартные контейнеры 560 ходимым и может причинить неудобства. Беря в качестве аргумента значение по умолчанию, можно написать: йазй тар к1ппд, ЫитЬег> рйопе Ьоой!; //по умолканикл ЫитЬег!) йакй тир<к!г!пу )уитйег>рйопе Ьоой2(НитЬег(411)); //лиумолкинит:!4итйег[41!) 17.6.2.1. Поиск Наконец мы можем ввести важнейшие операции поиска: гетр!а1е<с!акк Кеу, с!акз Т, с!аз я Н = Назй<Кеу>, с!аяз Е14= еуиа! 1о<Кеу>, с1акзА = а!!оса1ог ршг<сопз1Кеу, Т» > с1аккйазй тар( О..
таррей 1уре& орега1огП (соак1 йеу 1уре& й) !!ега1ог/!пй (сопя! Ьеу 1уре&), сопк1 Ыегагог/) пй (сопз1 йеу !уре&) солз1; //.. ), 1етр!а1е<с!азя Кеу, с!азя Т, с!азз Н = Накй <Кеу', с!аяз ЕС! = еуиа! 1о<Кеу>, с1акк А = аИоса1ог -ра!с<сопя! Кеу, Т» паяй тар<Кеу, Т,Н,Е14,А>зтаррей 1уре& 1урепате Ьазй тар<Кеу, Т,Н,ЕО,А>.:ореха!ос[) (сопз1 йеу 1уре& й) //хэ~и к!ке 1уре(= йакй (й)КЬ.в!хе (); // поиск среди записей, хэшироеанных по! // найдено // повторная вставка !ог )Епггу' р=ЬЯ; р, р = ->пех1) (/ (еу (й, р-> йеу)) ( (1(р->егакей)( р — >е~ азей =/а!зе; по о/ егазес! —; ге1игп р-> оа1 = Йе/аи!! оа1ие; ) ге!игл р — >иа1; //не найдено //ес«и сли~икол~ заполнено // роаиирлем //повторное кэширование (/ (яаке 1уре(й.з!хе ()*тих !оаа) <= сайке ()) ( гекгее (6 к!хе ()*ухою); ге1игп ореха!ос[] (й); // добавление за писа // указывает но новый элел~ент о,риз й Ьасй (Еп1гу (й, йе/аиН оа!ие, 6[!])); Ь[!] = &о Ьасй (); ге1игп Ь[!] — >оа1; В отличие от тар, йазй тар не опирается на проверку равенства, синтезированную из операции «меньше» Я 17.1А.1).
Это связано с вызовом функции ед () в цикле для Чтобы найти значение, орега1ог[] () использует хзш-функцию с целью нахождения индекса в хзш-таблице для ключа. Затем он просматривает записи, пока не найдет совпадающий ключ. Значение в этой записи п есть то, что мы ищем. Если найти его не удается, вводится значение по умолчанию: 561 17.6. Определение нового контейнера 17.6.2.2.
Удаление и повторное кэширование Когда таблица становится слишком заполненной, хэц!ированный поиск становится неэффективным. Чтобы снизить вероятность этого, при вызове оператора индексации (Ц) таблица автоматически изменяет размеры (операцией гез!яе ()). Операция зе1 !оач! () Я 17.6.2) предоставляет способ контроля над тем, когда и как происходит изменение размеров. Другие функции нужны для того, чтобы позволить программисту следить за состоянием Ьазй тар; 1етр!а1с<с!аяя Ксу, с!азя Т, с!аяя Н = НаяЬ<Кеу>, с!акяЕС2 — — сдиа! 1о Кеу>, с!аяяА = ауосасог<ра!г <сопягКеу, Т» > с1аяяЬаяЬ тар( ио!с! геягке (з!яс 1урс и); //устанавливает раэлчер хэш-табличы равным и // удаляет элсл~внт, на который // указывает итератор з!яе 1уре мкз () сопз1 ( ге!иго слезе () — по о/ егазсч1; ) // число элементов ясак гуре 6исйе1 соил! () сопя! ( ге!игл 6 я!хв (); ) //раэмерхэш-таблиды НаяЬсг Ьазь /ип () сопя1 ( гс1игп ЬаяЬ; ) //используемая //хэш-функция Ьеу едиа!Ьку сд() сопз1(гс1игпед;) // используемое //равенство ио!й е газе (Нега1ог роз!1!оп) Операция гез!яе () очень важна, довольно проста и потенциально дорога: 1етр!а1е с!аяяКсу, с1аяя Т, с!аязН=НазЬ<Ксу>, с!акя Е13 = едиа! 1о<Кеу>, с1аяя А = аНоса1ог<ра!г <сопя1Кеу, Т» > оо!с! ЬаяЬ тар<Кеу, Т, Н, Е12, А>сгеягхв (з!хс 1уре я) ( ясак 1уре 1=и.я!яе(~; (/(з <= 6 я!хе()) ге1игп; ! поиска элементов с тем же хэш-значением.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
