А. Александреску - Современное проектирование на C++ (1119444), страница 71
Текст из файла (страница 71)
Мультиметоды 11.6. Логарифмический двойной диспетчер Для того чтобы избежать глубоких зависимостей между классами, возникающих при грубой реализации двойного диспетчера, нужно поискать более динамичный подход. Вместо генерирования кода во время компиляции необходимо применить динамические структуры и алгоритмы, обеспечивающие диспетчеризацию вызовов функции во время выполнения программы в зависимости от типов ее параметров. Решить эту задачу позвзляет механизм йТГ1 (пзпзппе зуре Ыоппабоп), который дает возможность не только идентифицировать типы и выполнять их динамическое приведение, но и систематизировать их в ходе выполнения программы с помощью функции-члена Ьебоге из класса зтд:: туре зобо.
Эта функция упорядочивает отношения межау всеми типами, определенными в программе, позволяя осуществлять их быстрый поиск. Реализация такого класса является усовершенствованным решением задачи 31 из книги Скопа Мейерса "Моге ейесбче С++" (!996а): этап предварительных вычислений (сазйпд эзер) автоматизирован, а реализация максимально обобщена. Воспользуемся классом ОгдегедтуретпУо, описанным в главе 2. Этот класс представляет собой оболочку, обладающую функциональными возможностями класса зтд: гяуре (пУо. Кроме того, он имеет семантику значений и оператор "меньше*'.
Это позволяет хранить объекты класса огдегедтурехпУо в стандартных контейнерах. Именно эта особенность представляет для нас интерес. Подход, предложенный Мейерсом, прост: лля каждой пары объектов класса зтд: гяуре (про, подлежащих диспетчеризации, регистрируется указатель на функцию с двойным диспетчером. Этот диспетчер хранит информацию в объекте класса зад:;вар. Во время выполнения программы„когда двойному диспетчеру в качестве параметров передаются два неизвестных обьекта, он выполняет быстрый поиск типа (затрачивая логарифмическое время) и в случае успеха возвращает соответствующий указатель на функцию.
Определим структуру обобщенного механизма, основанного на этих принципах. Этот механизм представляет собой шаблонный класс с двумя аргументами (левым и правым). Назовем его ваззсоззратспег, поскольку мы будем использовать его в качестве основы для создания более сложных двойных диспетчеров. тевр1ате <с1азз вазеспз, с1ааа вазеяпз = вазеспз, гурепаве яеац1ттуре = чо(д> с1ааа ваззсоззратспег ( туреде1 зтд:: раз г<огдегедтуретпФо, огдегедтурехпТо> кеутуре; туредеУ яези1ттуре (>са11Ьасктуре)(вазеспэб, вазеяпэв); туредеУ са11Ьасктуре марредтуре; туредеб зтд::вар<кеутуре, марредтуре> мартуре; мартуре са11Ьаскмар ; рцЬ)зс: В качестве ключей карты используются объекты класса зтд::ра1г, состоящие из двух объектов класса огдегедтуретпуо.
Класс зтд::раз г поддерживает систематизацию, поэтому для него нам не нужен свой собственный функтор. Класс ваз(со(зратспег станет еще более общим, если сделать тип обратного вызова шаблонным. Обычно обратный вылов не обязан быль функцией. Он может быть, например, функтором (глава 5).
Класс ваэзсоз арагсйег может адаптировать функторы, преобразовывая определение их внутреннего типа са11ЬасМтуре в шаблонный параметр. 294 Часть П. Компоненты Значительное усовершенствование заключается в следующем: тип зЫ::шар изменен'и стал более эффективным. Мят Остерн (Мац Аизгет, 2000) выяснил, что стандартные ас- социативные контейнеры имеют более узкую область применения, чем принято думать. В частности, упорядоченный вектор в сочетании с алгоритмами бинарного поиска (например, алгоритмом зтй::1ошег осипа) может оказаться намного эффективнее, чем ассоциативный контейнер. Это происходит, когда количество обращений к его элементам намного превышает количество вставок.
Итак, следует внимательно изучить ситуации, в которых обычно применяются обьекты двойного диспетчера. Чаше всего лвойной диспетчер представляет собой структуру, в которую информа- ция редко записывается, но из которой часто считывается. Обычно программа лишь олнажды устанавливает обратные вызовы, а затем очень часто использует диспетчер. Это хорошо согласуется с использованием механизма виртуальных функций, который дополняется двойным диспетчером. Решение о том, какие функции являются вирту- альными, а какие нет, принимается на этапе компиляции.
На первый взпид упорздоченный вектор нам совершенно не подходит. Операции вставки и удаления элементов такого вектора выполняются за линейное время, и лвойной диспетчер никак не может повлиять на быстродействие этих операций. Зато этот вектор позволяет повысить скорость просмотра элемента примерно в два раза и намного снизить объем рабочего множества. Эти свойства очень полезны для двойной диспетчеризации.
Ьиблиотека (.о)о предусматривает использование упорядоченных векторов, опреде- ляя шаблонный класс лззосиестог, который может заменять собой класс зтб: ивар (он содержит те же самые функции-члены), реализованный на основе класса зтг(: гиестог. Класс лазосиестог отличается от класса зтг)::шар функциями егазе (функции лазосиестог::егазе аннулируют все итераторы внутри объекта). Кроме того, функции-члены (пзегт и егазе усложнены (выполняя операции вставки и уда- ления за линейное, а не постоянное время).
Поскольку класс лссозиестог совместим с классом зтг)::шар, для описания структуры, содержащейся в двойном диспетчере, мы будем также использовать термин ассациавивный массив (гпар). Ниже приводится новое определение класса ваз(со)зратсЬег. тешр1ате < с1азз вазеьЬэ, с1азз вазеяЬз = вазе~Ьз, турепаше яеви1ттуре = ио14, сурепаше са11Ьас)стуре = яези1гтуре (>)(вазегйзб, вазеяЬзе) > с1аьа ваз)со)зратсЬег туреоеУ зтб::ра1г<турехпФо, туретпбо> кеутуре; туредеу са11Ьас)стуре маррег)туре; туредеУ лззосиестог<кеутуре, марредтуре> мартуре; мартуре са11Ьасймар ; риЬ1(с: Легко определить и регистрирующую функцию. гешр1ате <...> с1азз ваз(соззратсЬег как и раньше 295 Глава 11.
Мультиметоды Сеар1ате <с1аьь 5оаеСЬь, 5оаеябь> чеза аоо(са!1Ьасктуре 1цп) ( сопьс кеутуре кеу(суре!0(ьоаесбь), сурезб(ьоаеяЬь)); са11Ьаскмар [кеу) = Гцп; Классы 5оаесЬь и 5оаеябь представляют собой конкретные типы, для которых выполняется диспетчеризация вызова. Как и класс ьсб::аар„ класс дььосчессог перетружает оператор Ц лля доступа к ключу, который соответствует типу, храняшемуся в ассоциативном массиве. Оператор [) возврашает ссылку на новый или найденный элемент, а функция адд связывает с ним параметр 1ип.
Рассмотрим пример, в котором используется функция дбд. суредеГ ваьзспзьрассбег<5Иаре> п)ьрассйег; О Заштриховывает пересечение прямоугольника и многоугольника чозд нассИпдяессапц1еро1у(5Иареа 1Ьь, 5Ьареа гбь) [ яессапц1ей гс = дупаачс саьс<яессапц)еа>(1Ьь); яо1уа р1 = дупаазс саьс<ро1уа>(гбь); ... используем ссылки гс и р1 ) о)ьрассбег Ньр; Ньр.ддд<яессапц1е, ро1у>(нассЬяессапц1еро1у); Функция-член, выполняюшая поиск типа и вызов, довольно проста.
сеар1асе <...> с1аьь ваь1спзьрасйсег ( как и раньше яеьц1стуре ао(ваьесбьа 1Ьь, ваьеябьй гбь) ( мартуре::зсегасог ! = са11Ьаскмар .Н пд( кеутуре(суреИ(1Ьь), сурезд(гбь)); 11 (1 == са11Ьаскмар .епдО) ( сбгои ьсд::гцпсчае еггог("Функция не найдена" ); гесцгп (з->ьесопд)(1Ьь, гйь); 11.6. 1. Логарифмический диспетчер и наследование Класс ваьзспсьрассИег неправильно работает с механизмом наследования. Если в нем зарегистрирована только функция нассбяессапд1еяо1у(5Иареа 1Ьь, карее гбь), то диспетчеризация распространяется лишь на объекты классов яессапд1 е и яо! у. Если, например, передать функции ваь)сп)ьрассбег:: ао ссылки на объекты классов яоцпдедяессапц1е и яо)у, то класс ваь1спз ьрассбег откажется выполнять вызов. Поведение класса ваьзсп!ьрассбег не согласуется с правилами наследования, в соответствии с которыми производные типы по умолчанию должны рассматриваться как базовые.
Было бы прекрасно, если бы кчасс ваьчспбьрассЬег принимал вызовы, параметрами которых являются объекты производных классов, поскольку эти вызовы вполне однозначны. 296 Часть Н. Компоненты Для решения этой проблемы нужно не так уж много, однако до сих пор она не ликвидирована окончательно. Таким образом, при регистрации всех пар типов в классе ваз1сп1зратсйег следует проявлять осторожность." 11.б.2. Логврифмический диспетчер и приведение типов Класс ваз(сп)зрагсйег полезен, однако не вполне хорош.
Зарегистрированная в нем функция, обрабатываюшая пересечение межлу объектами классов яесгапй)е и Ро1у, должна принимать аргументы базового типа бйареб. Предлагать клиентскому коду (реализации класса нассйяесгап91еяо1у) привести ссылки на объекты класса вйаре к правильному типу не совсем удобно и безопасно. С другой стороны, ассоциативный массив обратных вызовов не может хранить разные функции и типы функторов для каждого элемента, поэтому следует стремиться к их единообразному представлению. В параграфе 31 книги Мейерса "Моте Ейесг)хе С++" (Меуегз, 199ба) эта проблема уже обсуждалась.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
