11.6. Логарифмический двойной диспетчер

Для того чтобы избежать глубоких зависимостей между классами, возникающих при грубой реализации двойного диспетчера, нужно поискать более динамичный подход. Вместо генерирования кода во время компиляции необходимо применить динамические структуры и алгоритмы, обеспечивающие диспетчеризацию вызовов функции во время выполнения программы в зависимости от типов ее параметров.

Решить эту задачу позволяет механизм RTTI (rantime type infomiation), который дает возможность не только идентифицировать типы и выполнять их динамическое приведение, но и систематизировать их в ходе выполнения программы с помощью функции-члена before из класса std: :type info. Эта функция упорядочивает отношения между всеми типами, определенными в программе, позволяя осуществлять их быстрый поиск.

Реализация такого класса является усовершенствованным решением задачи 31 из книги Скотта Мейерса "Моте effective С-Ы-" (1996а): этап предварительных вычислений (casting step) автоматизирован, а реализация максимально обобщена.

Воспользуемся классом OrderedTypelnfo, описанным в главе 2. Этот класс представляет собой оболочку, обладающую функциональными возможностями класса std: :type info. Кроме того, он имеет семантику значений и оператор "меньше". Это позволяет хранить объекты класса OrderedTypelnfo в стандартных контейнерах. Именно эта особенность представляет для нас интерес.

Подход, предложенный Мейерсом, прост: для каждой пары объектов класса std: :type info, подлежащих диспетчеризации, регистрируется указатель на функцию с двойным диспетчером. Этот диспетчер хранит информацию в объекте класса std:: map. Во время выполнения программы, когда двойному диспетчеру в качестве параметров передаются два неизвестных объекта, он выполняет быстрый поиск типа (затрачивая логарифмическое время) и в случае успеха возвращает соответствующий указатель на функцию.

Определим структуру обобщенного механизма, основанного на этих принципах. Этот механизм представляет собой шаблонный класс с двумя аргументами (левым и правым). Назовем его BasicDispatcher, поскольку мы будем использовать его в качестве основы для создания более сложных двойных диспетчеров.

template <class BaseLhs, class BaseRhs = BaseLhs,

typename ResultType = void> class BasicDispatcher {

typedef std::pair<OrderedTypelnfo, OrderedTypelnfo> KeyType;

typedef ResultType C*CallbackType)(BaseLhs*, BaseRhs*); typedef CallbackType MappedType; typedef std::map<KeyType, MappedType> MapType; MapType callbackMap ; public:

}; "

В качестве ключей карты используются объекты класса std: :pai г, состояшие из двух объектов класса OrderedTypelnfo. Класс std:: pai г поддерживает систематизацию, поэтому для него нам не нужен свой собственный функтор.

Класс BasicDispatcher станет еще более общим, если сделать тип обратного вызова шаблонным. Обычно обратный вызов не обязан бьпъ функцией. Он может бьпъ, например, функтором (глава 5). Класс BasicDispatcher может адаптировать функторы, преобразовывая определение их внутреннего типа Cal 1 Ьасктуре в шаблонный параметр.

Значительное усовершенствование заключается в следующем: тип std: :map изменен и стал более эффективным. Мэтг Остерн (Matt Austem, 2000) выяснил, что стандартные ассоциативные контейнеры имеют более узкую область применения, чем принято думать. В частности, упорядоченный вектор в сочетании с алгоритмами бинарного поиска (например, алгоритмом std::lower bound) может оказаться намного эффективнее, чем ассоциативный котейнер. Это происходит, когда количество обращений к его элементам намного превышает количество вставок. Итак, следует внимательно изучить ситуации, в которых обычно применяются объекты двойного диспетчера.

Чаще всего двойной диспетчер представляет собой структуру, в которую информация редко записывается, но из которой часто считывается. Обычно профамма лишь однажды устанавливает обратные вызовы, а затем очень часто использует диспетчер. Это хорошо согласуется с использованием механизма виртуальных функций, который дополняется двойным диспетчером. Решение о том, какие функции являются виртуальными, а какие нет, принимается на этапе компиляции.

На первый взгляд упорядоченный вектор нам совершенно не подходит. Операции вставки и удаления элементов такого вектора выполняются за линейное время, и двойной диспетчер никак не может повлиять на быстродействие этих операций. Зато этот вектор позволяет повысить скорость просмотра элемента примерно в два раза и намного снизить объем рабочего множества. Эти свойства очень полезны для двойной диспетчеризации.

Библиотека Loki предусматривает использование упорядоченных векторов, определяя шаблонный класс AssocVector, который может заменять собой класс std::тар (он содержит те же самые функции-члены), реализованный на основе класса std::vector. Класс AssocVector отличается от класса std::map функциями erase (функции AssocVector::erase аннулируют все итераторы внутри объекта). Кроме того, функции-члены insert и erase усложнены (выполняя операции вставки и удаления за линейное, а не постоянное время). Поскольку класс Accosvector совместим с классом std: :map, для описания структуры, содержащейся в двойном диспетчере, мы будем также использовать термин ассоциативный массив (тар).

Ниже приводится новое определение класса BasicDispatcher.

template <

class BaseLhs,

class BaseRhs = BaseLhs,

typename ResultType = void,

typename CallbackType = ResultType (*)(BaseLhs&, BaseRhs&)

>

class BasicDispatcher {

typedef std::pair<Typelnfo, Typelnfo> кеутуре;

typedef CallbackType MappedType; typedef Assocvector<KeyType, MappedType> MapType; мартуpe callbackMap ; public:

}; ""

Легко определить и регистрирующую функцию.

template <...>

class BasicDispatcher

... как и раньше ... Глава 11. Мультиметоды 295

template <class SomeLhs, SomeRhs>

void Add(CallЬасктуре fun)

const кеутуре keyCtypeidCSomeLhs), typeidCSomeRhs)); callbackMap [key] = fun;

Классы SomeLhs и SomeRhs представл5пот собой конкретные типы, для которых выполняется диспетчеризация вызова. Как и класс std: :map, класс AssocVector перегружает оператор [] для доступа к ключу, который соответствует типу, хранящемуся в ассоциативном массиве. Оператор [] возвращает ссылку на новый или найденный элемент, а функция Add связывает с ним параметр fun.

Рассмотрим пример, в котором используется функция Add.

typedef BasicDispatcher<Shape> Dispatcher;

Заштриховывает пересечение прямоугольника и многоугольника void HatchingRectanglePolyCShape& Ihs, Shape& rhs)

Rectangle* rc = dynamic cast<Rectangle&>Clhs); Poly& pi = dynamic cast<Poly&>Crhs); ... используем ссылки rc и pi ...

Dispatcher disp;

disp.Add<Rectangle, Poly>CHatchRectanglePoly);

Функция-член, выполняющая поиск типа и вызов, довольно проста.

template <...>

class BasicDispathcer

... как и раньше ...

ResultType GoCBaseLhs& Ihs, BaseRhs& rhs) {

MapType::iterator i = callbackMap .findC

KeyTypeCtypeidClhs), typeidCrhs)); if (i == callbackMap .endC)) {

throw std::runtime errorC"Фyнкция не найдена");

return Ci->second)Clhs, rhs);

11.6.1. Логарифмический диспетчер и наследование

Класс BasicDispatcher неправильно работает с механизмом наследования. Если в нем зарегистрирована только функция HatchRectanglePolyCshape& Ihs, Shape& rhs), то диспетчеризация распространяется лищь на объекты классов Rectangle и Poly. Если, например, передать функции BasicDispatcher: :Go ссьшки на объекты классов RoundedRectangle и Poly, то класс BasicDispatcher откажется выполнять вызов.

Поведение класса BasicDispatcher не согласуется с правилами наследования, в соответствии с которыми производные типы по умолчанию должны рассматриваться как базовые. Было бы прекрасно, если бы класс BasicDispatcher принимал вызовы, параметрами которых являются объекты производных классов, поскольку эти вызовы вполне однозначны.