Pull to refresh

Comments 15

Тут стоит подчеркнуть, что у паттерна Посетитель есть две независимые стороны
разнести алгоритм работы с контейнером и алгоритм работы с элементом
реализовать мультиметод (произвольный тип приёмника, произвольный тип посетителя)

И вокруг мультиметодов в С++ хватает идиом, благо, мы можем возложить задачу диспетчеризации
— на алгоритм обхода (сделав его полиморфным — тот же std::for_each — времени компиляции, или ::qsort — времени исполнения)
— на аргументы мультиметода (двойная диспетчеризация по-ООПшному с виртуальными функциями, по-сишному с перебором тэгов, или вообще без двойной диспетчеризации, сразу по парам тэгов)

Такой взгляд позволит нам отстроиться от жёстких канонов:
Алгоритм контейнера может передавать посетителя элементам, а может передавать элементы посетителю.
В общем-то, разницы нет.
Будет там IVisitor::send(IData*) --> IData::receive(TheVisitor*) --> TheData::receive(TheVisitor*),
или наоборот, IData::send(IVisitor*) --> IVisitor::receive(TheData*) --> TheVisitor::receive(TheData*)
или сразу, launch(ILeft*, IRight*) --> land(TheLeft*, TheRight*)

Суть паттерна в том, что у нас есть много независимых объектов-посетителей и много сгруппированных объектов-данных, и алгоритм, позволяющий передружить одного посетителя со всеми данными.
Из того, что посетители не сгруппированы, мы ослабляем требования к их типу. То есть, посетителям очень естественно быть полиморфными без ограничений, а полиморфность данных — это уже по обстоятельствам (фиксированный тип, фиксированный вариант, произвольная иерархия).
В противном случае мы получаем другой паттерн — сигналы-слоты, когда однотипные аргументы рассылаются коллекции полиморфных приёмников.
Ну а раз так, то диспетчеризацию удобно начинать с интерфейса посетителя, IVisitor::send(IData*), где IData полиморфный или нет.

Опять же, кто знает, — нужно в данном конкретном месте посетителю знать конкретные типы своих аргументов, или нет?
Если, например, посетитель тупо считает количество визитов, то мультиметод (посетитель, данные) сведётся к простому (посетитель, void*).
А в случае с boost::variant ситуация немножко другая. Если уж посетитель полез в него, — то, наверно, не просто так; и тем более, что данные заведомо полиморфны. Поэтому двойная диспетчеризация начинается сразу с приёмника.
Тут стоит подчеркнуть, что у паттерна Посетитель есть две независимые стороны
— разнести алгоритм работы с контейнером и алгоритм работы с элементом


Разнести алгоритм работы с контейнером и элементом призван паттерн Итератор. Паттерну Посетитель вообще безразличны какие-то контейнеры, графы, деревья, etc. Просто множественная диспетчеризация.
Не так.
Итератор и Посетитель, конечно, ходят рука об руку.

Но для Итератора контейнер является пассивной сущностью, и смысл Итератора — нарезать алгоритм обхода из монолитного на кусочки-продолжения. Таким образом, любой алгоритм обхода выворачивается наизнанку и превращается в линейный цикл for.

А для Посетителя — сам алгоритм обхода как был монолитным (и сколь угодно сложным), так и остался активной сущностью.
В него делается инъекция «что нужно делать с конкретным элементом», причём эта инъекция может быть и простой, не влияющей на ход выполнения (как функтор в for_each), так и управляющей (предикат) и даже составной… В пределе мы получим паттерн Шаблонный Метод.

Вообще, паттерны поведения удобнее рассматривать не с объектной, а с функциональной стороны.
К чёрту объекты-посетители. Есть функция-посетитель. Даже нет, есть функтор (в теоркатовом смысле), поскольку он отображает формальный или фактический тип аргумента на сигнатуру перегруженной функции.
Итератор и Посетитель, конечно, ходят рука об руку.


Visitor вполне может применятся даже к единственному объекту, «контейнеры» и «обходы» вообще к нему никаким боком. На эту тему есть хорошая статья (или глава из книжки) Вендевурда (Vandevoorde), но сходу не могу нагуглить. Тогда приведу цитату другого известного плюсиста, из «My Most Important C++ Aha! Moments… Ever» by Scott Meyers: «Then, one day, I made a fundamental realization: the Visitor Pattern has nothing to do with visitation... Because I was so fixated on the pattern’s name, I couldn’t get past the idea that Visitor had something to do with visitation or iteration or something like that.»
Во-первых, единственный объект тоже является контейнером самого себя с одним тривиальным способом обхода.

Во-вторых, повторюсь: Посетитель — это и идея инъекции алгоритма в алгоритм (полиморфизм со стороны посетителя), и идея взаимодействия с невидимыми извне разнотипными объектами (полиморфизм с принимающей стороны).
Педалировать какую-то одну грань и упускать другую — было бы странно.
Так что Скотт Мейерс мог бы сказать и второе «ага!»: осознать, что Посетитель всё-таки имеет отношение к посещению.
Во-первых, единственный объект тоже является контейнером самого себя с одним тривиальным способом обхода.


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

Посетитель — это и идея инъекции алгоритма в алгоритм (полиморфизм со стороны посетителя), и идея взаимодействия с невидимыми извне разнотипными объектами (полиморфизм с принимающей стороны).
Педалировать какую-то одну грань и упускать другую — было бы странно.


Я не упускаю ни одну из этих твоих граней — двойная диспетчеризация (читай, «полиморфизм») по типу-объекта и по типу-операции — но по прежнему считаю, что к каким-либо контейнерам или деревьям паттерн не имеет никакого отношения. Единственный пример, который GoF придумали для своей книжки, был связан с обходом синтаксического дерева; вот они и назвали паттерн «Visitor».

это и идея инъекции алгоритма в алгоритм (полиморфизм со стороны посетителя), и идея взаимодействия с невидимыми извне разнотипными объектами (полиморфизм с принимающей стороны).


Это твоя идея. Моя идея, например, в том, что Посетитель транспонирует иерархию из n исходных классов с m операциями над этими классами в параллельную иерархию из m классов-операций (визиторы), каждый с n методами посещения (по одному на каждый класс исходной иерархии). И всё это как вариант решения т.н. expression problem: в ООП добавление метода в иерархию является ломающим изменением, а добавление класса — нет. Поэтому операцию добавления функции в иерархию классов сводят к добавлению класса в навешенную иерархию визиторов. Ситуация дуальна — теперь сложно добавлять классы в исходную иерархию, так как требуется добавлять функции посещения (ломающее изменение) в иерархию визиторов.
Ты прав, и спасибо за вот такой разворот мысли (про транспонирование иерархии).

Но вот смотри, проблема «как бы так извернуться, чтобы мультиметод легко масштабировать было» специфична для определённого способа реализации мультиметодов: на виртуальных функциях.
Возьмём другую реализацию — например, сиплюсплюсные шаблоны и перегрузка, — естественно, это уже времени компиляции, — и нам внезапно становится пофиг, что легче добавлять: строку или столбец в матрицу операций×операндов.

И да, чтобы совсем опечалить. Если у нас типы выстраиваются в неограниченную древовидную иерархию классов, то для одноаргументной полиморфной функция (она же — виртуальная) легко указать закон выбора: вверх по иерархии до первого найденного суперкласса (на таблицах виртуальных функций за единичное время, понятное дело); для двухаргументной уже возможны варианты (вверх по иерархии с доминированием первого аргумента — двойная диспетчеризация; с доминированием второго аргумента; точное совпадение типов или идите все к чёрту; по списку до первого удачного совпадения; и ещё пара экзотических схем)… для трёх и более аргументов — соответственно, даже если мы играем в [двойную] диспетчеризацию, то разнообразие растёт факториально.
И реализации тоже варьируются.

Может быть, ГоФ вообще этой проблематикой не запаривались, а?
Может быть, Посетитель — это, всё-таки, паттерн поведения, а не паттерн паттерн-матчинга, пардон мой френч?

Это как с DOM и SAX. Доступ к содержимому можем дать напрямую (через самый примитивный интерфейс — линейный обход, и это будет Итератор), а можем обеспечить через колбеки (и это будет Посетитель).
В любом случае, клиентский код полиморфный относительно библиотечного. Только с Итератором он вообще без ограничений, а с Посетителем — имеет определённый интерфейс.
Зачем в этом классе метод accept?
class person_t
{
public:
    person_t(const std::string& name, size_t age)
        : name_(name), age_(age){}

    template<typename Visitor>
    void accept(Visitor& v) {v.visit(*this);}
    size_t age() const {return age_;}
private:
    std::string name_;
    size_t age_;
};

Он же нигде не используется.

struct person_visitor_t
{
    person_visitor_t(size_t age_limit) : age_limit_(age_limit){}
    bool operator()(const person_t& p) {return visit(p);}
    bool visit(const person_t& p) {return p.age() < age_limit_;}
    size_t age_limit_;
};

Это структуру можно немного переделать:

struct person_visitor_t
{
    person_visitor_t(size_t age_limit) : age_limit_(age_limit){}
    bool operator()(const person_t& p) {return p.age() < age_limit_;}
    size_t age_limit_;
};

И ничего не изменится, станет только короче и понятнее.
Что-то не вяжутся у меня предикаты STL и visitor.
1. Именно в этом кусочке accept не нужна. Она оставлена из тех соображений, что вполне можно написать свой STL-like функцию алгоритм, в которой она уже будет использоваться аналогично тому, как используется в BGL.
2. Конечно, структуру person_visitor_t можно и нужно переделать в промышленном коде. Здесь она написана так, как она написана, чтобы показать близость предикатов и визитора.
3. Visitor вяжется с предикатами в том смысле что и то то является сходными механизмами диспетчеризации, отделения алгоритма от данных. Естественно ни один в один, но сходно. Об этом неплохо написано у товарища nickolaym в первом комментарии.
По ссылке, считаю, что классическая реализация неверна из-за присутствия гребенки if-else'ов. Механизм выбора метода «посетителя» должен быть возложен на компилятор. Он может быть осонован на прегрузке методов с различными типами аргуметов, или же это могут быть функции с разными именами или как-то по-другому, дело удобства. Это важно, т.к. существенно уменьшается гибкость (подумайте, например, о тестах) и ухудшается поддержка из-за поддержки еще и гребенок.
В целом фича с использованием dynamic покрывает, наверное, больше 90% случаев, но все же это немного другое, т.к. не используется условие, что сами объекты знают о том, что их может “навестить” некий обработчик. Иногда эта дополнительная гибкость может быть очень полезной.
double dispatch толком не нужен.

Рефлектор 7.1 упал на методе с dynamic. Показал перед смертью, что внутри Visitor создан вспомогательный класс с полем типа CallSite<Action, CallSite, Visitor, object>>

ILDASM показывает простыню вызовов внутри цикла, в числе которых
CSharpArgumentInfo::Create
RuntimeBinder.Binder::InvokeMember
CallSite<Action<CallSite, Visitor,object>>::Invoke
и ещё 5 касающихся вспомогательного класса, которые я постеснялся сюда копипастить из-за их страшного вида.

Однако, не всё так плохо. Я замерил скорость этой конструкции относительно «гребёнки». Последняя лишь в 5-10 раз быстрее.

Скрытый текст
    class Program
    {
        static void Main(string[] args)
        {
            var pl = new List<Person>();
            var r = new Random();
            for (int i = 0; i < 1000000; i++)
            {
                pl.Add(r.Next(100) < 50 ? (Person)new Man() : new Woman());
            }
            var p = new Man {Children = pl.ToArray()};
            var v = new Visitor();
            var sw = new Stopwatch();
            sw.Start();
            v.Process(p);
            sw.Stop();
            Console.WriteLine(sw.ElapsedMilliseconds);

            sw = new Stopwatch();
            sw.Start();
            v.Process2(p);
            sw.Stop();
            Console.WriteLine(sw.ElapsedMilliseconds);
        }
    }

    public abstract class Person
    {
        public IList<Person> Children { get; set; }
    }
    public class Man : Person { }
    public class Woman : Person { }

    public class Visitor
    {
        public void Process(Person person)
        {
            foreach (dynamic p in person.Children)
                Visit(p);
        }

        public void Process2(Person person)
        {
            foreach (var p in person.Children)
            {
                var m = p as Man;
                if (m != null) Visit(m);
                else Visit((Woman)p);
            }
        }

        void Visit(Man m) { mc++; }
        void Visit(Woman w) { wc++; }
        private int mc, wc;
    }

Вывод вышеприведённой программы
в debug:
106
17

в release:
105
11
Что-то мне кажется, что вариант со static visitor'ом будет столь же быстр, как и гребенка. Нельзя ли на шарпах его же реализовать через generic'и?
Нет, на шарпе так не сделаешь. C# не допускает синтаксическую подстановку, типа такой
  template<typename V>
  void accept(V& visitor) { visitor.visit(*this); }


Ему нужно указать, что V — это некий IVisitor с методом visit(p), но тогда нужно уточнять тип p, и в наследнике Person этот тип поменять уже нельзя.
Only those users with full accounts are able to leave comments. Log in, please.