Б. Страуструп - Язык программирования С++. Специальное издание, 3-изд. Бином. 2004 (1160791), страница 122
Текст из файла (страница 122)
Лргумент типа Ьаяс я1г!пйг(глава 20) делает то же самое, только символ 'О' дает битовое значение О, символ ' !' — битовое значение 1, а другие символы приводят к генерации нсклзочення тиа(11( агритеп1. 11о умолчанию для инициализации используется полная строка. Однако в стиле конструктора Ьаяс ИПпд (9 20.3А) пользователь может определить, что должен использоваться только диапазон символов от роя до конца строки или до роя+и. Например: 553 ! 7.5. Почти контейнеры оо/д/'() ( Ьнке/<10> Ы; //вге 0 6!/ке/< !б> Ь2 = Охаааа; // /О/О/О/010/О/010 Ыуке!<32> 60 = Охаааа; //ООООООООООООО000/О/О/О/О/О/О/О/О Ьияе1<10>Ь4(к/ппд("10/О/О/010")); ///О/О/010/О Ьа/ке1<10> Ьб (з1г!пи ( 10110!1!О/!110), 4); // О/ ! / О/ / I /О Ь!/ке1<!О> Ьб(к/г!п0( !О!!О//!О!!!/О), 2, В), //00//О/! /О/ 611ке!<!0 Ь7 (к/г/пи ("пОа000')) // тиа/Ы абаяат/ !недопустил~ьш аргуллонт) Ь/Ме/</О> ЬВ ="пди000"; //ошибка: нет преобразования к/пни в Ьнке/ Ключевая идея при проектировании Ы/яе1 заключается в тола что для битовых набо- ров, умец/ающихся в одно слово, может быть обеспечена оптимизированная реализа- ция.
Интерфейс отражает это допущение. 17.5.3.2. Операции с битами Класс Ь!!яе/ обеспечивает операции для доступа к отдельным б/и ам и для манипули- рования всеми битами в наборе: !етр/а1е<ихе 1)7> сIаья к/дсЬ!!зе1( риЫЬх // .. // операис//л с битовым набором: сереге//се орега1ог(] (ките 1рок) Ь!!ке1й орега1огй= (соим Ьйке1й к)/ 6!!ке1йорега1ог)= (сопк1Ь/1ке1йв); Ь!1ке/5 орега1ог"= (сопк1ЬИке/йк), Ьике1й орега1ог< = (к/хе !п), Ь/!ке1й орега1ог»= (к/ее 1п); // создание дополншпельного набора О создание сдвинутого набора //создание сдвинутого новара Оператор индексации Д генерирует исключение ои1 о/ галие, если индекс выходит за пределы набора.
Непроверяемой индексации нет. Ь//ке/й ке/ (); Ьнке/й ке! (к!ге гроз, ш1 иа! = !); Ь/тке/й геке/ (); анке!й геке1(к/ге 1рок) Ь!/ке1й///р (), Ь!1ке/йЯЛр (к!ге 1рок) Ьнке1 орега!ог- () сопят ( ге1игп Ь//ке1<М> (*/Ык)Яр (), ) ЬИке1 орега1ог < (козе 1 п) сопк1 ( ге1игп Ы!ке1<///> ('!Ык)«=п; ) Ь!!ке/ орега1ог» (к/хе ! и) сопк1 ( ге1и гп Ь/1 ке1 <М> (*!!//к)»=п; ) О 6(/] //и // Иг/И //шклиочающее ИЛИ //логический сдвиг влево //!сзаполнениел~ нулями) //логический сдвиг вправо // (с заполнениелл нулялш) //у ивановка всех битов в / // Ь(рок]= / // установка всех битов в О // Ь(рок]=0 // изл/е пение значения каждого бигпа // изменение значения 6(рок] 554 Глава 17, Стандартные контейнеры Значение Ь!1яеЫ, возвращаемое этими операциями, — это *16!я, Оператор, возвращающий Ь|1яе! (а не Ь!1яеЫ), делает копию '1Ь!я, применяет свою операцию к копии и возвращает результат.
В частности, » и «являчотся операторами сдвига, а не операциями ввода/вывола. Оператор вывода для Ь!1яе! — это «, принимающий оя1геат и Ь!1яе1 3 17.5.3.3). Прн сдвиге битов применяется логический (а не циклический) сдвиг. Это приводит к тому, что некоторые биты «выпадают из конца>, а некоторые позиции заполнякжся значениями по умолчанию — нулями. Отметим, что поскольку я!ге 1 — беззнаковый тип, на отрицательное число сдвинуть невозможно.
Однако это ведет к тому, что Ь«-1 пытается сдвинуть Ь на очень большое положительное число и тем самым обнуляет все биты Ь. Ваш компилятор лолжен пожаловаться на это. ! 7.5.3.3. Другие операции Кроме того, класс Ь!1яе! поддерживает такие операции как в!ге (), ==, ввод/вывод н т. дл 1етр!а1е<ягге 1!и'> с!аяя 611яе1 ( риЬ!!с. // .. иля!улеч( !илу 1и и!илу() соля1; 1етр!а1е<с!авв СЬ, с1аяя Тг, и!аяяА> Ьая!с я1плу<СЬ, Тг А> 1о в1плу () саля1; я!2е 1соил1() соля!; // число бит со значением! ваяв !я!ге () солв1 ( ге!игл гч'; ) //число бит Ьао! орега1ог== (саля1 Ь!1вв18 я) саля!; Ьво! орега1ог! = (соля! Ьйяе18 я) салв1; Ьво(1ея! (и!ге 1роя) соля!; //Ьив, если 6(роя) равно ! Ьоо! алу () соля!, // 1те, если хо~ля би один бит равен ! Ьоо! лоле () соля!, // 1те, если ни один бшп неравен ! В Операции 1о и!ой() и 1о в(г!лу() обеспечивают обращение операций конструирования.
Этим операциям отдали предпочтение перед преобразованиями, чтобы избежать неочевидных преобразований. Если в значении Ь!1яе1 так много значащих битов, что их не представить в илв!илес( 1олй, операция !о и!илу () сгенерирует исключение оиечу(очи еггог. Операция 1о я1г!лд () производит строку желаемого типа, содержащую последовательность символов '0' и '!', Ьаячс я1г(лд — это шаблон, используемый для реализацпи строк (глава 20), Мы можем использовать 1о я(г(пу, чтобы написать двоичное 'представление целого: ио!<! Ьглагу (!л1ч) ( Ь!1яе1<8'я!гвоЯлй> Ь = Ь //лредлолагается 8-битний байт // (св. также у 22.2) саи1 «Ь 1етр1а1е 1о в1плу< слаг, сааг 1гайя<сьаг>, а!!оса1ог<сдаг» () « 'ччл'; К сожалению, вызов явно квалифицированного шаблона члена требует довольно сложного и редкого синтаксиса Я ВА3.6).
555 17.5. Почти контейнеры Вдобавок к функциям-членам Ь((зе( обеспечивает двоичное & (логическое «И»), ) (логическое «ИЛИ>), («исключающее ИЛИ») и обычные операторы ввода/вывода: 1етр1а(с<нее 1Х> Ьвяе1<Х> к(й;прего(ог& (сопя(6уке1<М>&, сопя( Ьике1<Х>&); 1етр!а1е<ике 1Х> Ь(уке1<М> к!й..орега1ог) (сопз1ЬНке(<Х>&, солв16!!ке1<М>&) 1етр(а(е<ягее 1М> Ь!(яе(<М> к1йсорега1ог" (сопк1ЬВке(<М &, сопя(Ытке1<М>&)' 1етр(п1е<с(акк сааг Т, с(акк Тг, яссе 1М> Ьатс (я!геат<сбаг Т, Тг>& к(й орега1ог» (Ьак!с (кггеат<сдагТ, Тг &,Ы(ке1<М>&); 1етр!а(е с(акк сааг Т, с(акв Тг,з!ке (Х> Ьакйс ок1геат<сдаг Т, Тг & в(йсореган>г«(Ьикгс оз(геат<сдагТ, Тг>&, сопк1 Ьйке1<Х>&); Поэтому мы мох<ем выдать битовый набор без преобразования его в строку. Например: Эта программа выводит биты, представляя нх снмволамн 2Т и '!' слева направо, са- мый старший бит — самый левый.
17.5.4. Встроенные массивы Встроенный массив предоставляет индексацию н итераторы с произвольным доступом в виде обычных указателей (ч 2.7.2). Однако сам массив не знает собственных размеров, поэтому следить за его размерами должны пользователи. Вообще говоря, массивы не обеспечивают стандартных типов и операций- !левов. Возможно, и иногда полезно, представить обычный массив в таком виде, который обеспечил бы удобства стандартного контейнера без изменения его природы на низком уровне: !етр(иге<с(аяк Т, (п(тах> к1гис1с аггау( (урейет Т оа!ие 1уре; 1урейе( Т * Вега 1о г, 1урейе) сопя! Т* сопя( Нега1ог; (урейе(' Т& гегегелсе; 1урейе( солк1Т& сопк1 ге)егепсе; Т о[тих), орега1ог Т" )) ( ге1игл о; ) геХегелсе орега1ог[) (р(гй(Д ! !) ( ге!игл о[1); ) соля( ге~егелсе орега(ог[) (р(гй((! 1!) солк1 ( ге(иги о[(); ) Пега!ос Ьефп () ( ге(игп о; ) сои я1 !1его1ог Ьеу!л () сопк1 ( ге1игп о; ) оойй Ь!лагу (!л( !) ( 6 узе 1<8'к(ееог (!п()> Ь = Ь сои! «Ь « '~а'; ) (( предполагается 8-дитньп( боот (сл.
также у 22.2) Глава 17. Стандартные контейнеры 556 Ьега1ог епй () ( ге1игп оьтах; ) сопя1 йега1ог епй () сопя! ( ге!игп о«тая; ) рггу 1есее () сопв1 ( ге1игп тах; ) Для совместимости с массивами я воспользовался знаковым типом р1гй(11" 1Я 1б.1.2), а не беззнаковым з1ге !в качестве типа индекса, Применение могло бы привести к тонким двусмысленностям при использовании [] с объектами с аггау.
1Т)аблон с аггау не является частью стандартной библиотеки, он представлен здесь в качестве примера «впихивания» чужеродного контейнера в рамки стандартных контейнеров. Его можно использовать со стандартными алгоритмами (глава 18), применяя Ьеа1п (), епй () и т. п. Такой контейнер можно разместить в стеке без всякого неявного динамического распределения памяти.
Его также можно передавать функппям, написанным в стиле С, аргумент которых — указатель. Например: оо1й/(1п1* р, 1и! вх); // функция в стиле С оо(йа () ( с аггау<1п1, 10>а; ,/(а, аяйхе ()); с аггау<1п1, 10>-11ега1ог р =алый (а.Ьеут (), а.епй (), 777), //используется гтпль С // глпиль Сьь/5Т1 17.6. Определение нового контейнера Стандартные контейнеры обеспечивают основу, к которой пользователь может добавлять свои механизмы. Здесь я покажу, как создать контейнер, чтобы в использовании он был взаимозаменяем со стандартными контейнерами. Его реализация будет реалистичной, но не оптимальной.
Интерфейс вьюирается из тех соображении, чтобы оц был поближе к существующим, широко доступным и высококачественным реализациям понятия ЬазЬ тар. Используйте приведенный здесь ЬазЬ тар для изучения общих вопросов, а потом применяйте поддерживаемый ЬаяЬ тар.
17.6.1. (чав(з пзар Контейнер тар — зто ассоциативный контейнер, принимающий элементы почти любого типа. Он обеспечивает такую возможность, опираясь для сравнения элементов только на операцию «меньше» (у 17.4.1.) .. Однако если мы знаем больше о типе ключа, то нередко можем ускорить поиск элементов, введя хэш-функцию и реализовав контейнер как хэш-таблицу. Хэш-функция — это функция, которая по значению быстро вычисляет индекс таким образом, что два различных значения редко соответствуют одинаковому индексу.
В основном хэш-таблицы реализуются размещением значения по его индексу, если там у>хе не расположилось другое значение, и «рядом» в противном случае. Поиск элемента, расположенного по своему индексу, занимает мало времени, а поиск элемента, расположенного «рядом», если такой существует, тоже не очень долог, при условии,что пропштка ца равенство проводится сравнительно быстро. И потому не так уж странно, 557 17.6. Определение нового контейнера // сравнение строк при полощи оператора < О сравнение си прок при поло/ци ////осияв() (я /7.!А./) шар<я(ллу, /п(> т1; тир<я(г!пу, !пб Носаяе> т2; //хзшировиние при полои(и Наьу<ь1ппу>() // (4 /7.5.2.3), сравнение при полслци == //хз/иирование при полощи Ь!с1(), // сравнение при полшщн == О кэширование при лолоьци Ь(с((), //сравнение при полощи еу!() Ьа»Ь шар<я(г!пу, /п( /пп/; Ьияй тир<я(г(пу, !л1, /ус(> т2, ЬаьЬ гпир<я1Ппу, !л1, Ь(с(, еу!> т2; Контейнер, использующий хэшированный поиск, реализуется при помощи одной или более таблиц.
Кроме хранения своих элементов контейнер должен следить, какие значения связаны с каждым хэшированным значением («ицдекс» в обьясненпи, приведенном выше); это делается прн помощи хэп!-таблицы. Большинство реализаций хэш-таблиц существенно снижают быстродействие, если эта таблица становится «слишком полной» вЂ” заполненной, скажем, на 75%. Поэтому определенный следующим образом Ьаяй тар автоматически изменяет размер, когда становится слишком полным.
Однако изменение размера может оказаться дорогим, поэтому полезно иметь возможность задать первоначальный размер. Итак, в первом приближении ЬаяЬ тар выглядит следу/ошим образом: 1етр!а/с<с!аяя Кеу, с1аья Т с/аяя Н = Наяд <Кеу>, с1аяя Е<с = ели а! (о<Кеу>, с/аяя А = а!!оса 1ог<ра!г <сопя1Кеу, Т» > с1аяяЬаяЬ тар( //как шар, эа исклюненнеш: 1уре<(с/Н На слег; 1уре//е/Е(/Ьеу едиа!; Ьаьд тар (сопя1 Тйуи= Т(~, ягее 1урел=/О!, сопя1Нй Ь|Н(/ соптЕ~& =ЕД (/й 1етр1а/е<с!аья (п> Ьаьй тар (/и//гь1!л !аь(, сопя( Тй Ыи = Т!(, ь!ее Фуре л = !О!, сопя1Н5 ЬТ= Н ('„соль( Е95 =Е(4 Щ; ), В своей основе это интерфейс тар Я 17А,1.4) с <, замененным на ==, и хэппфункцисй.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
