Бьерн Страуструп. Язык программирования С++. Специальное издание (2011) (1004033), страница 123
Текст из файла (страница 123)
Однако встроенные массивы не знают собственных размеров, поэтому следить за их размерами должны пользователи. Кроме того, у встроенных массивов, в отличие от стандартных контейнеров, нет ни функций-членов, ни определяемых нми типов. Возможно, а иногда и полезно, снабдить обычный массив удобствами стандартного контейнера без изменения его низкоуровневой сущности; <етрдпе<с1ат Т, <п< тах> ягис1 с аггау ( <уре«еТ Т га1ие <уре< <уре<<е) Т* <1ега<ог; <уре«ег соль Т* солт Ьега<ог< <уре«еТ Тз геуегепсе < <уре«ау солт Тз сот< ге~егепсе< Т г [тах]; орега<ог Т' () (ге<игл Ю ) ге~егепсе орега<ог[] (р<П<(Щ' 1<) (гетгл »[1] < ] сот< гегегепсе прего<ос [] (р<пЩ <1) сот< (ге<игл »[1] 1 ) Глава 17. Стандартные контейнеры пега!ос Ьея!п () (гяигл»э ) соли( йегагог Ьея!и () сола! (ге(игп»Ч ) Йега1ог впд() (ге!игл и«тах1 ) сопл! йегогог впФО солзг (гетгп »+так; ) л!ге 1 з!хе() сопл! (ге1игп тох1 ) )г Для совместимости с обычными массивами я воспользовался знаковым типом рпч!(!)" 1 (816.1.2), а не беззнаковым в!хе 1 в качестве типа индекса.
Применение в!хе !могло привести к тонким неоднозначностям при использовании операции [) с объектами типа с аггау. Шаблон с акгау не входит в стандартную библиотеку. Он приведен в качестве примера того, как можно представить чужеродный контейнер под личиной стандартного контейнера. Его можно использовать со стандартными алгоритмами (глава 18), применяя Ьея!и (), ет!() и т.д. Он может быть размещен непосредственно в стеке без какого-либо косвенного вьщеления динамической памяти. Его можно передать написанной в С-стиле функции, ожидающей обычного указателя. Например: «таз (!лг* р, т( зе) 1 //функция в С-стиле ио!дв() ( с агтау<гпг, !О> а1 7'(а,а.з!ев() ); ~7 используем функцию в С-стиле с агту<!лг, !О>::Ьвплогр = Т)пд(а.Ьвкгл (), а.влд(), 777) г УС++)5Т1.
стиль г)' ... ) 17.6. Создание нового контейнера Стандартные контейнеры составляют полезный каркас (среду), к которому пользователь может добавлять свои собственные средства. Здесь я покажу создание контейнера, взаимозаменяемого со стандартными контейнерами. Его устройство будет вполне реалистичным, хотя и не оптимальным.
Интерфейс будет близок к существующим, широко применяемым и высококачественным реализациям понятия Ьавй тар. Используйте его для изучения, а на практике применяйте стандартные реализации. 17.6.1. Контейнер )зав)з пзар Контейнер тар — это ассоциативный контейнер, допускающий элементы почти что любого типа. Он обеспечивает эту возможность, опираясь лишь на операцию < для сравнения элементов (817.4.1.5). Однако если мы знаем больше о типе ключа, то мы можем ускорить поиск элементов, предоставив хэш-функцию и реализовав контейнер как хэш-таблицу. Хэш-функция (Ьозй-Хиос!!оп) — это функция, которая быстро преобразует значение в индекс таким образом, что дво различных значения редко когда приводят к одинаковому индексу.
Хэш-таблицы стандартно формируются размещением значения по его индексу, или «рядом» (если там уже размещено какое-то значение). Поиск 17.6. Создание нового контейнера ' // сравнение строк при помощи < // сравнение строк при помощи Хосазе()(З! 7.!.4.!) тор<в!с!ия, тз> т1; тор<в(Ппл, !и(, Мосоле> т2! йазй тор<в!с!ия, (пе> йт1! //хзшируем с Нозй<згг!пя>В (з!7.б.2.3) йозй тар<ю1пе,!из,й)сг> йпг2! //хэшируем с й)с!О; сравнение через операцию == йозй тир<за !пя, !пз, й!с(, ео!> йтЗ ! // хэшируем с й)сг(), сравнение через ед! Контейнер, использующий кэшированный поиск, реализуется при помощи одной или нескольких таблиц.
Кроме хранения элементов контейнер должен следить за тем, какие значения ассоциированы с хэш-значениями («индексами», согласно приведенному выше пояснению); это делается при помощи «хэш-таблицы», Для большинства реализаций хэш-таблиц производительность резко падает при увеличении плотности заполнения таблицы (скажем, на 75% и более).
Из-за этого йазй !пар автоматически изменяет свой размер при увеличении плотности заполнения. Так как изменение размера является затратной операцией, целесообразно задавать подходящий начальный размер. В результате в первом приближении йазй тар выглядит следующим образом: (етр1а!е<сйгзз Кеу, <1азз Т, с)авз Н = Нозй<Кеу>, с!от Егй = вонам го<К«у>, с(от А = одосо!ог<роп<сопв! К«у, Т» > с)азз йавй тар ( //кок тор, зо исключением: (урег!еГН Назйег! <урег!еГЕг2 йеу едиа1 ! Ьтй тар(сопя Ть г!»=Т(), з!и (уре и =101, сопи Нь й(Н(), соииЕМь =ЕЯ() ) ! гетр!о!в<с(азз 1п> йазй тор (1и)овг, 1п !азз, сот! Тв би =Т(), з!хе суре п =101, соиз! Нь й|=Н(), соизз ЕЦь =ЕД () ) ! )! В своей основе это интерфейс контейнера тар 617.4.1.4), за исключением того, что < заменена на == и добавлена хэш-функция.
Имеющиеся в данной книге примеры использования тар (В3.7.4, З6.1, З17.4.1) могут быть переконвертированы на применение йазй тар простейшей заменой имени тар на йтй тар. Это можно упростить еще сильнее, используя оператор гуре«(еу. Например: элемента, расположенного по своему индексу, занимает мало времени, а поиск элемента, расположенного «рядом», не намного больше, если конечно эффективно выполняется проверка на равенство.
Как следствие, не редки случаи, когда йазй тар обеспечивает в 5 — 10 раз более быстрый поиск для больших контейнеров, чем это делает тар. В то же время, если хэш-функция подобрана плохо, то йазй тар может оказаться более медленным, чем тар. Существует много способов реализовать хэш-таблицу. Интерфейс йазй тар обычно строится таким образом, чтобы он отличался от интерфейса стандартных ассоциативных контейнеров только тогда, когда это нужно для выигрыша в быстродействии за счет хэширования. Самое важное отличие йазй тар от тар состоит в том, что тар требует от типа своих элементов операцию <, а йазй тар — операцию == и хэш-функцню. Таким образом, йазй тар отличается от тар созданием объектов «не по умолчанию», Например: 996 Глава 17.
Стандартные контейнеры турет!е!' ааеа тор<а!с!ад, гесост(> Мар; Мар Жст!овалу; Оператор туреИеу позволяет скрыть от пользователей точный тип словаря. Хотя это и не совсем точно, но я представляю себе альтернативу тар/1тае1т тар как альтернативу память/время. Если эффективность не является главной проблемой, не тратьте время на выбор — хорошо подойдет любой из этих контейнеров.
Для больших и интенсивно применяемых таблиц 1теа тар имеет явное преимущество в скорости и должен использоваться во всех случаях, когда нет недостатка в памяти. И даже в последнем случае я не стал бы так сразу переключаться на тар, не рассмотрев дополнительных возможностей экономии памяти (требуются точные замеры для выбора оптимального варианта). Эффективное хэширование достигается лишь с помощью качественных хэш-функций. При не слишком качественной хэш-функции тар может легко превзойти аатй тар по быстродействию.
Обычно, хэширование на базе С-строк, строк типа еп!аК или целых чисел весьма эффективно. Однако нельзя забывать, что эффективность хэш-функций критически зависит от самих хэшируемых значений (817.8[35!). Контейнер ааей тар должен использоваться в случаях, когда операция < не определена или неприменима к выбранному типу ключа. Противоположная рекомендация — контейнер тар нужно использовать тогда, когда требуется держать элементы строго упорядоченным образом, ибо хэш-функция не задает упорядочения так, как это делает операция <. Так же как и тау, аае!т тар предоставляет функцию !)ас((), позволяющую программисту выяснить, содержится ли данный ключ в контейнере. 17.6.2.
Представление и конструирование Для ааз1т тар возможны разные реализации. Здесь я привожу такую реализацию, которая обеспечивает неплохую скорость и простоту наиболее важных опера- ций. Важнейшие из них — конструкторы, поиск (операция () ), изменение размеров и удаление элемента (ееаее1] ). Выбранная нами простая реализация основана на хэш-таблице, представляющей собой вектор указателей на записи.
Каждая запись содержит ключ (1сеу), значение (ее!ее), указатель на следующую (если имеется) запись с тем же хэш-значением, и флаг егазеФ (удален): В объявлении это выглядит следующим образом: тетр(аге<с!ат Кеу, с!ат Т, с1ат Н = Наеа<Кеу>, с!от ЕМ = ет!иа1 то<Кеу>, с1аи А = айосагос<ра1е<соаз( Кеу, Т» > ) 7.6. Создание нового контейнера 59г гУ внутреннее представление Епау* пехг; Еп!гу(йеу !уре й, торрес туре ю Еп!гу* п) : йеу(й), га1(г), егазей(/а!зе), пех!(и) () )' гесгог<Егагу> г! вес!ог<Еп!гу*> Ь; // ...
)1 )' // истинные входы //хэш-таблицог указатели внутрь ч Отметим поле егазеН. То, как здесь обрабатываются несколько значений с единственным хэш-значением, затрудняет удаление элемента. Поэтому вместо действительного удаления при вызове егазе() я просто помечаю элемент как егазе!! (удален) и игнорирую его пока таблица не изменит размер. В дополнение к главной структуре данных контейнер йазй тар нуждается еше и в некотором количестве административных данных. Естественно, каждый конструктор должен проинициализировать все эти данные. Например: зетр1те<сйззз Кеу, с1азз Т, с1азз Н = Назй<Кеу>, с(азз ЕЯ = ецио( !о<Кеу>, сйкззА = а[йса!ог<ра(г<сопмКеу, Т» > с(акт йазй тар ( // ...
йазй тар(сопм Ть й =Т(), зае !уреп =101, сопз! Н5 й =Н(), сопз( ЕЯь е =Еф() ) : гйуаи11 из/ие(0г), Ь(п), по о/' егазеб(0), йазй [й), ед(е) ( зе! йаИО; //все, что по умолчанию г. гезегге (тах йт!*Ь.з(хе () );,Уреэервирует память длл роста ) вой! зт йни! (71оа! т=а. 7, яоа! 0=1 . 6) [ тах йни! = т; Кгон = йо ) // ... сопл! Тгйзаи1! гойе! с1азз йазй Фнпр ( //... рг!га!е: мгис! Еппу ( йеу 1уре йеу; торрес зуре чай Ьоо( егазе0г ринге: фии тах йаЫ) ут !д ю; зае бра по оу" егазед! Назйег йазй; йьу ецио( ейч //сохраняем изйеО<=Ьзйе Оьтах 1оаг! //при необходимости меннем размер, гтйе(Ьисйег соил(О*Лгов) // количество входов в к занятых стертыми элементами // хэт<футаат р равенство // умолчательное значение, используемое операцией 1/ Глава ) 7.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
