Аннотация:
Очень часто в программах встречаются сложные структуры, представляющие собой дерево или граф, состоящий из разнотипных узлов. И, конечно же, при этом имеется необходимость обрабатывать этот граф. Самое очевидное решение — добавить в базовый класс виртуальный метод, который перекрыть в наследниках для выполнения нужного действия и осуществления дальнейшей навигации по дереву.
Однако у этого приема есть серьезный недостаток: в нем структура данных оказывается увязанной с обрабатывающими ее алгоритмами. Если нам понадобится алгоритм, отличный от реализованного, то придется добавлять еще один виртуальный метод. Еще хуже, если классы, составляющие дерево, содержатся в недоступном для модификации коде.
Одним из вариантов решения проблемы высокой связности в данном случае является паттерн Посетитель.
АК>Авторы: АК> Андрей Корявченко
АК>Аннотация: АК>Очень часто в программах встречаются сложные структуры, представляющие собой дерево или граф, состоящий из разнотипных узлов. И, конечно же, при этом имеется необходимость обрабатывать этот граф. Самое очевидное решение — добавить в базовый класс виртуальный метод, который перекрыть в наследниках для выполнения нужного действия и осуществления дальнейшей навигации по дереву. АК>Однако у этого приема есть серьезный недостаток: в нем структура данных оказывается увязанной с обрабатывающими ее алгоритмами. Если нам понадобится алгоритм, отличный от реализованного, то придется добавлять еще один виртуальный метод. Еще хуже, если классы, составляющие дерево, содержатся в недоступном для модификации коде. АК>Одним из вариантов решения проблемы высокой связности в данном случае является паттерн Посетитель.
Я могу ошибаться но когда этот патерн становился известным — то мотивация использования была совсем другая ?
Здравствуйте, Дм.Григорьев, Вы писали:
ДГ> Кстати, а зачем нужна эта статья, если в книге все разжевано?
Я бы не сказал, что в книге уж так все подробно разжевано.
Здравствуйте, DangerRSDN, Вы писали:
DRS>А зачем внутри класса лишний раз дергать функции get_Type1Nodes и get_Type2Nodes:
Нет там в реальности никакого лишнего дерганья — JIT без проблем с такой ситуацией справляется и устраняет лишний вызов. А гибкость кода при прямом обращении к полям снижается — мало ли какую логику понадобится в свойства вставить? Например ленивую инициализацию коллекций.
Возник вопрос о целесообразности IContextVisitor<,>, то есть о возможности передачи параметра в метод Visit(…).
Какие есть резумные примеры передачи дополнительно параметра? Не лучше ли его обработку возложить на сам Посетитель?
Help will always be given at Hogwarts to those who ask for it.
Здравствуйте, _FRED_, Вы писали:
_FR>Возник вопрос о целесообразности IContextVisitor<,>, то есть о возможности передачи параметра в метод Visit(…). _FR>Какие есть резумные примеры передачи дополнительно параметра?
Когда в процессе обработки нужно состояние.
_FR> Не лучше ли его обработку возложить на сам Посетитель?
В смысле? Хранить состояние в полях посетителя? Не очень хороший дизайн, потому что чреват нарушениями инвариантов. И несовместим с функциональным стилем.
... << RSDN@Home 1.2.0 alpha rev. 725 on Windows Vista 6.0.6000.0>>
Здравствуйте, AndrewVK, Вы писали:
AVK>Не очень хороший дизайн, потому что чреват нарушениями инвариантов. И несовместим с функциональным стилем.
Спасибо. Не обратил внимание, что реализация Visit(…) никак на контекст не влияет, а просто передаёт его visitor-у, так же, как и this. В таком разрезе вопрос снят
Help will always be given at Hogwarts to those who ask for it.
Тупо не понимаю , почему "сложные структуры, представляющие собой дерево или граф, состоящий из разнотипных узлов. И, конечно же, при этом имеется необходимость обрабатывать этот граф." речь идет о стрктурах данных ?
Двойная диспечеризация, разделение алгоритма обработки от структуры и структура и метод обхода данных это все строго ортогональные вещи, почему например этот патерн декларируется для обхода дерева и не может применяться для обхода списка или массива?
Здравствуйте, minorlogic, Вы писали:
M>речь идет о стрктурах данных ?
Речь идет о структуре экземпляров классов в памяти.
M>Двойная диспечеризация, разделение алгоритма обработки от структуры и структура и метод обхода данных это все строго ортогональные вещи
Конечно. Поэтому в статье я постарался максимально разделить эти понятия.
M>, почему например этот патерн декларируется для обхода дерева и не может применяться для обхода списка или массива?
Там нигде не написано, что он не может применятся для обхода списка. Просто деревья — наиболее распространенный случай применения.
... << RSDN@Home 1.2.0 alpha rev. 725 on Windows Vista 6.0.6000.0>>
Здравствуйте, AndrewVK, Вы писали:
AVK>Там нигде не написано, что он не может применятся для обхода списка. Просто деревья — наиболее распространенный случай применения.
Но например для меня очевидно , что обход дерева и операция с элементом дерева это Ортогональные вещи. Как пример разделения моей уверенности может служить архитектура STL , где обход дерева или массива скрыты за итераторами.
В примере на википедии рассматривается только двойная диспечирезация и нет речи об структурах данных. Кстати в примере "VisitorBase" это очевидно обычный итератор по дереву который еще и двойную диспечеризацию прокидывает. Так же сразу очевидны недостатки и ограниченность этого паттерна , в невозможности расширять базовую иерархию классов и поощрение плохой функциональной декомпозиции базового класса (речь идет о том что функциональность не полностью прописанна через интерфейс и приходится кастить тип наверх).
Здравствуйте, minorlogic, Вы писали:
M>Но например для меня очевидно , что обход дерева и операция с элементом дерева это Ортогональные вещи.
Ну да. И что?
M>В примере на википедии рассматривается только двойная диспечирезация и нет речи об структурах данных.
Ну, с википедией это не ко мне.
M> Кстати в примере "VisitorBase" это очевидно обычный итератор по дереву который еще и двойную диспечеризацию прокидывает.
В этом и суть — объединение итератора и посетителя в случае, если итератор этот единственно возможный.
... << RSDN@Home 1.2.0 alpha rev. 725 on Windows Vista 6.0.6000.0>>
Здравствуйте, AndrewVK, Вы писали:
AVK>Здравствуйте, minorlogic, Вы писали:
M>>Но например для меня очевидно , что обход дерева и операция с элементом дерева это Ортогональные вещи.
AVK>Ну да. И что?
В том что я не вижу пользы от Объединения ортогональных вещей , какая польза от объединения зеленого и шершавого ?
M>> Кстати в примере "VisitorBase" это очевидно обычный итератор по дереву который еще и двойную диспечеризацию прокидывает.
AVK>В этом и суть — объединение итератора и посетителя в случае, если итератор этот единственно возможный.
В этом месте я начинаю терять суть патерна , в чем его польза ? Он как бы состоит из 2-х отдельных приемов. Двойная диспечирезация имеет довольно ограниченное применение. В статье нет реального примера где была бы продемонстрированна его полезность и преимущества. На данный момент меня интересует именно это, кажется с технической частю все более не менее понятно.
Здравствуйте, minorlogic, Вы писали:
M>В том что я не вижу пользы от Объединения ортогональных вещей
Ради бога. Это тебя беспокоит? Хочешь поговорить об этом?
AVK>>В этом и суть — объединение итератора и посетителя в случае, если итератор этот единственно возможный.
M>В этом месте я начинаю терять суть патерна , в чем его польза ?
В том, что это самое примитивное решение, позволяющее это сделать. То что есть и другие — никто не спорит.
M>В статье нет реального примера где была бы продемонстрированна его полезность и преимущества.
Статья не о двойной диспетчеризации, а о паттерне Посетитель. И упоминается она там исключительно в контексте одной из возможных реализаций этого паттерна.
... << RSDN@Home 1.2.0 alpha rev. 725 on Windows Vista 6.0.6000.0>>
M>>В этом месте я начинаю терять суть патерна , в чем его польза ?
AVK>В том, что это самое примитивное решение, позволяющее это сделать. То что есть и другие — никто не спорит.
что ЭТО ? и какие преимущества дает делая ЭТО ?
M>>В статье нет реального примера где была бы продемонстрированна его полезность и преимущества.
AVK>Статья не о двойной диспетчеризации, а о паттерне Посетитель. И упоминается она там исключительно в контексте одной из возможных реализаций этого паттерна.
Вот и суть патерна от меня ускользает , я попробую еще почитать на тему. Суть двойной диспечирезации вроде как ясна ...
Здравствуйте, minorlogic, Вы писали:
AVK>>В том, что это самое примитивное решение, позволяющее это сделать. То что есть и другие — никто не спорит.
M>что ЭТО ?
Такое решение.
M> и какие преимущества дает делая ЭТО ?
Отсутствие необходимости повторения логики итератора.
AVK>>Статья не о двойной диспетчеризации, а о паттерне Посетитель. И упоминается она там исключительно в контексте одной из возможных реализаций этого паттерна.
M>Вот и суть патерна от меня ускользает
Суть паттерна описана в первой главе.
M>, я попробую еще почитать на тему. Суть двойной диспечирезации вроде как ясна ...
Еще раз — двойная диспетчеризация это просто способ реализации, не более того. Именно ради иллюстрации этого первые примеры двойную диспетчеризацию не используют. Суть визитора предельно проста — это замена виртуального метода в базовом классе, который не работает с приватными данными напрямую, а на внешний класс с алгоритмом обработки, причем наличие явного контракта визитора гарантирует реализацию обработки для всех возможных типов за счет статической проверки компилятором.
... << RSDN@Home 1.2.0 alpha rev. 725 on Windows Vista 6.0.6000.0>>
Здравствуйте, Mika Soukhov, Вы писали:
MS>Не очень халяльный способ писать такой код:
Извини, я не правоверный мусульманин, потому поинтересуюсь, что в нем такого нехаляльного?
MS>При этом, одну из описанных тобой проблем (модификация классов дерева), которую решает Visitor, таким кодом не решить.
Честно говоря не понял.
... << RSDN@Home 1.2.0 alpha rev. 725 on Windows Vista 6.0.6000.0>>
Здравствуйте, AndrewVK, Вы писали:
MS>>При этом, одну из описанных тобой проблем (модификация классов дерева), которую решает Visitor, таким кодом не решить.
AVK>Честно говоря не понял.
Здравствуйте, AndrewVK, Вы писали:
AVK>Здравствуйте, Mika Soukhov, Вы писали:
MS>>Не очень халяльный способ писать такой код:
AVK>Извини, я не правоверный мусульманин, потому поинтересуюсь, что в нем такого нехаляльного?
MS>>При этом, одну из описанных тобой проблем (модификация классов дерева), которую решает Visitor, таким кодом не решить.
AVK>Честно говоря не понял.
У тебя написано:
Однако у кода в этом примере есть серьезный недостаток: в нем структура данных оказывается увязанной с обрабатывающими ее алгоритмами. Если нам понадобится алгоритм, отличный от реализованного, то придется добавлять еще один виртуальный метод. Еще хуже, если классы, составляющие дерево, содержатся в недоступном для модификации коде.
Но, если написать интерфейс IVisitor таким образом, как у тебя (тоесть, на каждый тип TypeXNode добавлять соответствующий метод), то код класса TypeXNode необходимо модифицировать в любом случае. А именно — добавлять вызов конкретного метода.
Лично мне не совсем понятно, почему не написать один базовый интерфейс-контракт, поместить его в соответствующй сборку, и никогда ее не трогать:
Это уберет и проблему с разбуханием одного супер-класса, и проблему с вызовом конкретного метода под конкретный класс, и проблему с модификацией сборок.
Хм, довольно странный визитор, который лишен главной прелести обычного — контроля за тем, что реализованы все методы. Но если список типов заранее неизвестен, то можно и так, хотя при таком раскладе лучше вообще отказаться от метода Accept за полной его ненадобностью в условиях дотнета.
... << RSDN@Home 1.2.0 alpha rev. 725 on Windows Vista 6.0.6000.0>>
MS>Однако у кода в этом примере есть серьезный недостаток: в нем структура данных оказывается увязанной с обрабатывающими ее алгоритмами. Если нам понадобится алгоритм, отличный от реализованного, то придется добавлять еще один виртуальный метод. Еще хуже, если классы, составляющие дерево, содержатся в недоступном для модификации коде.
Ну да. В случае же, если в этих классах реализован визитор, для добавления нового алгоритма нет нужны перекомпилировать эти классы.
MS>Но, если написать интерфейс IVisitor таким образом, как у тебя (тоесть, на каждый тип TypeXNode добавлять соответствующий метод), то код класса TypeXNode необходимо модифицировать в любом случае.
Читай внимательнее:
Если нам понадобится алгоритм, отличный от реализованного
Алгортитм, а не новый тип ноды. Для заранее (на момент компиляции) неизвестного набора классов визитор подходит плохо. Как, впрочем, и решения вроде алгебраических типов с паттерн-матчингом. В этом случае нужно чисто динамическое решение, например что то вроде мультиметодов.
MS>Лично мне не совсем понятно, почему не написать один базовый интерфейс-контракт, поместить его в соответствующй сборку, и никогда ее не трогать: MS>
Пара вопросов по визитору, сразу предупрежу — пишу на Delphi.
Первый вопрос — В чем смысл введения интерфейса IVisitor? Почему не создать базовый класс для операции, ведь в нем может быть логика, которую в случае интерфейса придется продублировать во всех реализациях?
Поясню, имеем структуру:
TComponent = class
end;
TControl = class(TComponent)
end;
TButton = class(TControl)
end;
TComponentVisitor = class
public
procedure VisitComponent(AComponent: TComponent); virtual;{ Пустая процедура, базовая заглушка }procedure VisitControl(AControl: TControl); virtual; { По умолчанию вызывает - VisitComponent(AControl) }procedure VisitButton(AButton: TButton); virtual; { По умолчанию вызывает - VisitControl(AButton) }end;
Теперь если мы хотим реализовать операцию над всеми компонентами нам достаточно перекрыть метод VisitComponent, а не все три метода.
Второй вопрос — Как реализовать визитора, если классы из приведенной ранее структуры находятся в разных модулях, например (Components.pas, Controls.pas, Buttons.pas)?
Здравствуйте, byterus, Вы писали:
B>Первый вопрос — В чем смысл введения интерфейса IVisitor? Почему не создать базовый класс для операции, ведь в нем может быть логика, которую в случае интерфейса придется продублировать во всех реализациях?
Вот когда такая логика понадобится, тогда и можно создать. А покуда она не нужна — лучше использовать интерфейс.
B>Второй вопрос — Как реализовать визитора, если классы из приведенной ранее структуры находятся в разных модулях, например (Components.pas, Controls.pas, Buttons.pas)?
Здравствуйте, AndrewVK, Вы писали:
B>>Второй вопрос — Как реализовать визитора, если классы из приведенной ранее структуры находятся в разных модулях, например (Components.pas, Controls.pas, Buttons.pas)?
AVK>И в чем проблема
Проблема в том что приходится применять приведение типов, и прочие "некрасивые" вещи. Я понимаю что эта задача чисто и красиво не решается, но хочется узнать как это делают другие. Может быть вообще, в таких иерархиях применение визитора противопоказанно.
Имеем простую иерархию — Component->Control->Button. Каждый класс находится в своем модуле, Component ничего не знает про Control, Control ничего не знает про Button. Теперь мы захотели применить паттерн посетитель имеющий ранее приведенный интерфейс:
TComponentVisitor = class
public
procedure VisitComponent(AComponent: TComponent); virtual;
procedure VisitControl(AControl: TControl); virtual;
procedure VisitButton(AButton: TButton); virtual;
end;
Поместили класс в модуль Components.pas.
Все красиво, но по причине циклической зависимости модулей работать не может Цепляемся за Controls.pas и Buttons.pas.
Идем другим путем:
TComponentVisitor = class
public
procedure VisitComponent(AComponent: TComponent); virtual;
procedure VisitControl(AControl: TComponent); virtual;
procedure VisitButton(AButton: TComponent); virtual;
end;
Все замечательно компилируется, но в метдах VisitControl и VisitButton мы утратили информацию о типах, придется приводить пришедший объект к компоненту и к кнопке соответственно.
Я не понял? Зачем в визиторе Component и Control? В визиторе нужно указывать только те классы, экземпляры которых реально используются.
B>Все красиво, но по причине циклической зависимости модулей работать не может Цепляемся за Controls.pas и Buttons.pas.
Так в Паскале, ЕМНИП, есть forward declaration.
... << RSDN@Home 1.2.0 alpha rev. 725 on Windows Vista 6.0.6000.0>>
Здравствуйте, AndrewVK, Вы писали:
AVK>Я не понял? Зачем в визиторе Component и Control? В визиторе нужно указывать только те классы, экземпляры которых реально используются.
Зря Вы так, а если операция называется AlignControls? Не проще ли использовать VisitControl?
B>>Все красиво, но по причине циклической зависимости модулей работать не может Цепляемся за Controls.pas и Buttons.pas.
AVK>Так в Паскале, ЕМНИП, есть forward declaration.
Классы находятся в разных модулях, причем здесь упреждающие объявления?
Еще раз поясню — "красиво", здесь врятли получится, хочется узнать, как это грамотно реализовать и выбрать меньшее из зол.
Здравствуйте, byterus, Вы писали:
AVK>>Я не понял? Зачем в визиторе Component и Control? В визиторе нужно указывать только те классы, экземпляры которых реально используются. B>Зря Вы так, а если операция называется AlignControls? Не проще ли использовать VisitControl?
А зачем? Смысл визитора как раз и состоит в том, чтобы обрабатывать в зависимсости от конкретного типа. Если же алгоритм опирается на базовые классы, тут нужно что то иное.
... << RSDN@Home 1.2.0 alpha rev. 725 on Windows Vista 6.0.6000.0>>
Здравствуйте, AndrewVK, Вы писали:
AVK>>>Я не понял? Зачем в визиторе Component и Control? В визиторе нужно указывать только те классы, экземпляры которых реально используются. B>>Зря Вы так, а если операция называется AlignControls? Не проще ли использовать VisitControl?
AVK>А зачем? Смысл визитора как раз и состоит в том, чтобы обрабатывать в зависимсости от конкретного типа.
По отношению к Component`у — Control можно считать "конкретным" типом? По моему, Вы заранее предполагаете об использовании, на самом деле операции могут быть самые разные, о которых, мы даже предпопложить не можем
AVK>Если же алгоритм опирается на базовые классы, тут нужно что то иное.
Вариантов не много, либо операция в классе, либо внешняя (в посетителе).
Здравствуйте, byterus, Вы писали:
AVK>>А зачем? Смысл визитора как раз и состоит в том, чтобы обрабатывать в зависимсости от конкретного типа. B>По отношению к Component`у — Control можно считать "конкретным" типом?
Нет.
B> По моему, Вы заранее предполагаете об использовании, на самом деле операции могут быть самые разные, о которых, мы даже предпопложить не можем
Понимаешь, Посетитель это не серебряная пуля, я вполне конкретная штука для вполне конкретных ситуаций. Оптимален он в том случае, я, собственно, об этом уже писал, когда на этапе компиляции нам известны все конечные типы. Когда они неизвестны (в твоеми случае модули компилируются независимо) посетителя конечно можно подрихтовать (как тут и приводили пример), но я совсем не уверен, что имеет смысл городить этот огород, при том что, скажем, хеш с указателями на функции будет несильно уступать и не требует изначальной доработки классов полиморфной структуры.
... << RSDN@Home 1.2.0 alpha rev. 725 on Windows Vista 6.0.6000.0>>
Здравствуйте, AndrewVK, Вы писали:
AVK>Понимаешь, Посетитель это не серебряная пуля, я вполне конкретная штука для вполне конкретных ситуаций. Оптимален он в том случае, я, собственно, об этом уже писал, когда на этапе компиляции нам известны все конечные типы. Когда они неизвестны (в твоеми случае модули компилируются независимо) посетителя конечно можно подрихтовать (как тут и приводили пример), но я совсем не уверен, что имеет смысл городить этот огород, при том что, скажем, хеш с указателями на функции будет несильно уступать и не требует изначальной доработки классов полиморфной структуры.
Спасибо! Будем искать варианты
P.S. Кстати, в методы VisitXXX необязательно передавать объект, можно передавать набор скаляров, разумеется, в каких то случаях этот набор будет избыточен, в других недостаточен.