Б. Страуструп - Язык программирования С++. Специальное издание, 3-изд. Бином. 2004 (1160791), страница 108
Текст из файла (страница 108)
Это позволяет оптимизировать реализацию контейнеров и позволяет пользователям писать код, независящий от того, какой конкретный контейнер используется. Проектирование контейнеров, как правило, отвечает одному нз указанных двух критериев. Контейнерную и алгоритмическую часть стандартной библиотеки (ее часто называют БТЕ) можно рассматривать как решение проблемы одновременного обеспечения универсальности и эффективности.
Следующие разделы покажут сильные и слабые стороны двух традиционных стилей контейнеров, чтобы понять проектное решение, выбранное для стандартных контейнеров. Глава 16. Организация библиотеки и контейнеры 492 Оба класса обеспечивают операции, близкие к идеальным в использовании, и для обоих классов мы можем выбрать подходящее представление, не беспокоясь о других видах контейнеров.
Это позволяет реализовать операции почти что оптимально. В частности, наиболее употребительные операции, такие как ри1 () для ХЫ! и орега1ог[) () для Ъес1ог, невелики и легко встраиваются. Обычное использование болыпинства видов контейнеров — это проход (итерация) по контейнеру, перебор элементов одного за другим. Обычно это делается путем определения класса итератора, подходящего для данного вида контейнеров (см. 9 11.5 и 9 11.14[7)).
Однако пользователю, перебирающему контейнер, часто нет дела, хранятся данные в объекте Е!в1 или»ес1ог. В этом случае код с, итерацией не должен зависеть от того, используется АЫ1 нли Уес!ог. Желательно, чтобы в обоих случаях работал один и тот же фрагмент кода. Решение таково: определить класс итератора, обеспечивающий операцию «получение следующего элемента», которую можно реализовать для любого контейнера. Например: 1етр!ото<с!аээ Т» с!авв !1ог ( //оби(ай интер<(эейс !айстрактнай класс э 2.э.«, О !2.3) риЫ!с: // возвратить О, если элементов больше нет Ыггиа1 Т "/1гэ1() =О; //указатель на первый элемент ойтиа! Т' пех1 () = О; //указатель на следувлций элеиент Теперь мы можем обеспечить реализацию для векторов и списков // реализация Уес1ог 1етр1а1е<с1авв Т» с1авэ Ъес1ог ног риЫ1<Т1ог< Ть ( 1гес1ог<Т Ь и, гйее 1тйех; //индекс текущегоэлеленти риЫ!с: (ес1ог дог(1 ес1ог<Т 8,'оо): о(ии),!пйех(0)() Т "/(гэ1 () ( ге1игп (ив!ее ()) ? йо(1пйех=О): 0; ) Т * пех1 () ( геьигп (+«1пйех<ив1ее ()) ? Ьи(!пиес): О; ) 1етр1а1е<с!авв Т с!аээ 1лэ1 11ог: риЫ!с?1ог<Т» ( //реализация ! М1 А!в1<Т>Ь !э1; Т1в1<Тнх1пи р; // указывает на текуи(ай зле«гент риЫ!«г 1лэ1 11ог(/1э1<Т»8) Т */гге! (); Т' пех1 (); Или графически, используя пунктирные линии для выражения отношения <реали- зовано с использованием»: Уес1ог Тлв1 А А авЗ 16.2.
Проектирование контейнеров Внутренняя структура двух итераторов совершенно различна, но пользователей это пе касается. Теперь мы можем написать программу, итерируюшую все что угодно, для чего мы реализовали Пег. 1-1апример: щГсоиаГХГог<спаг»й й, свагГегт~ ( га1с = О; ~ог ~сааг*р =аЯгзм з;р; р алехг Я(1"(р -Фегт1с++; гениса с; Однако здесь есть одна загвоздка. Операции над итератором йог просты, и все же они привносят затраты на вызов (виртуальной) функции. Во многих случаях эти затраты незначительны по сравнению с другими действиями. Однако итерация простого контейнера во многих быстродействующих системах — критическая операция, а вызов функции во много раз дороже, чем целочисленное сло»кение или разыменованне указателя, которые выполняет функция пех1 ~) для пес1ог и Йзб Следовательно, эта модель для стандартной библиотеки не подхолит или, по крайней мере, не идеальна.
Тем не менее эта контейнерно-итераторная модель успешно используется во многих системах, В течение многих лет она была моей излюбленной для большинства прикладных программ. Ее достоинства и недостатки могут быть подытожены следующим образом; + Индивидуальные контейнеры просты и эффективны.
От контейнеров не требуется большой общности. Итераторы и классы-оболочки (5 25.7.1) могут использоваться для помещения независимо разработанных контейнеров в «общие рамки». + Общность использования обеспечивается через итераторы (а не через общий контейнерный тип; з 16.2.2). Для одних и тех же контейнеров можно определить разные итераторы, служащие разным потреоностям. Контейнеры по умолчанию безопасны с точки зрения типов и однородны (то есть вге элементы в контейнере относятся к одному и тому же типу). Разнородные контейнеры можно создать как однородные контейнеры указателей на общий базовый класс.
+ Контейнеры неинтрузивны (чтобы стать элеьчентом контейнера объект не обязан иметь особый базовый класс или поле связи). Неинтрузивные контейнеры хорошо работают со встроенными типами и структурами, заданными внешне жестким образом, — Каждый доступ к нтератору приводит к вызову виртуальной функции. По сравнению г.
простой встроенной функцией эти затраты могут быть значительны. — Иерархия классов итераторов имеет тенденцию становиться запутанной. Контейнеры не имеют ничего общего между собой, и объекты в контейнерах также не имеют ничего общего. Это усложняет создание универсальных служб, например, таких как персистентность и объектный ввод/вывод. Здесь + обозначает достоинство, а — обозначает недостаток. Я придаю большое значение гибкости, которую обеспечивают итераторы.
Общий интерфейс, такой как Ног, может быть создан гораздо позже проектирования и реализации контейнеров (здесь это Ъес1ог и 2хз1). При проектировании мы обычно сначала Глава 16. Организация библиотеки н контейнеры 494 изобретаем что-нибудь достаточно конкретное. Например, мы проектируем массив и изобретаем список, Только позднее мы открываем абстракцию, которая объединяет в данном контексте и массивы, и списки. Фактически мы можем делать такую «позднюю абстракцию» неоднократно. Предположим, мы хотим представить множество, Множество — это отличная от 11ог абстракция, н все же мы можем создать интерфейс Яе! для контейнеров Уес1ог и Егв1 способом, очень похожим на тот, которым мы ввели интерфейс 11огдля Уес1ог н Е!в1.
Уес1ог Е!в1 д» ль Ве1 Ейог лк --'. Уес1ог ве1 Уес1ог 11ог Е!в! ве1 Е!з1 !1ог Таким образом, поздняя абстракция с использованием абстрактных классов позволяет нам обеспечить разные реализации понятия, даже когда межлу реализациями нет большого сходства. Например, списки и вектора имеют некоторую очевидную общность, но мы можем также легко реализовать 11ог и для !в1геат. По логике два последних пункта в списке являются главными недостатками данного подхода То есть даже если устранить для итераторов и подобных контейнерных интерфейсов затраты времени на вызов функций (что в некоторых случаях возможно), этот подход не станет идеальным для стандартной библиотеки. Неннтрузивные контейнеры влекут за собой небольшой перерасход времени и памяти по сравнению с интрузивными.
Я не вижу здесь проблемы. Если это станет проблемой, итератор вроде 11ог может быть создан и для интрузивного контейнера (9 1б,б(111). 16.2.2. Контейнеры с общим базовым классом Интрузивный контейнер можно определить без использования шаблонов или дру- гих способов параметризации объявления типа. Например: вГгис1 1лпй ( Е!пй* рге Е!пй* вис //-. ), с!аяв Е!вг ( Е!пй* Аеас(, Е!пй' сиге // текущий элемент рив!!с Е!пй* нег (), //удаляет и возвращает текущий элелгепт во!г(риг (Е!пй ) // вставляет перед текущие алел~ствол //- ); Теперь Е!в! — это список структур Е!пй, и он может солержать объекты любых типов, производных о г Е!пй. Например; с!а ее ЬНр; риЬ!!с Е!пй ( /* ...
'/ ); воЫДЕ!в1* !вг) 16.2. Проектирование контейнеров т611е )Е1пу*ро = 1эг-эуе1 ))) 1 1г" )БИр* рэ = дупат?с саэ1кБЫр'> )ро)) 1 ,Ч 5Ыр должен быть // полиморфным 1у ?блб?) ?/ испольэуем 5Ыр ) е?эе( ,?? проблема, делаем нто-нибудь другое В подобном стиле определяет свои стандартные контейнеры Яппи)а, так что для языков, поддерживающих объектно-ориентированное программирование, этот подход можно считать исконным. В настоящее время общий класс для всех объектов обычно называют 061ес1 или как-нибудь вроде этого.
Класс ОЬгес1 как правило обеспечивает другие общие услуги, а не только служит связью в контейнерах. Часто, по не обязательно, этот подход распространяют на общие контейнерные типы: с1иээ Соп1агпег: риис ОЬ?ес11 риЫ?с. Ыг1иа?ОЬ?ес1' уе1 )); Ыггиа? ооИ ри1 )ОЬ?е с1 '); о1этиа1 061есс'й орега1ог() )эгее 1), ?? удаляет и воэвращает текуи1ий элемент ?? вставляепг перед текущим элементом //индексания Отметим, что эти операции, предоставляемые классом Соп1а?пег, виртуальны, так что индивидуальные контейнеры могут их соответствующим образом замещать: с1авэ Е?э1 риЫ!с Соп1а1пег) риЫ?с. ОЬ?ес1' уе1 1); во ау ри1 )ОЬ1 ес1 *); 0 с1аеэ Тес?ог риЫ?с Соп1атег) риЫ1с ОЬ?есг "б орега1ог() (э?ее 1); ??" ); Сразу же возникает одна проблема.
Какие операции мы хотим получить от класса Сон 1а(пег? Мы можем обеспечить только те операции, которые поддерживают все контейнеры. Однако пересечение наборов операций во всех контейнерах — это до смешного узкий интерфейс. Фактически, во многих представляющих интерес случаях это пересечение вообгпе пусто. Поэтому, реально оценивая ситуацию, мы должны предоставить объединение ключевых операций по всему множеству контейнеров, которые мы намереваемся поддержать.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
