Идиомы С++. Static visitor

    Паттерн Visitor предлагает еще один способ отделить алгоритм обработки данных от самих данных. В этой статье я кратко опишу идею, стоящую за оригинальным паттерном, его С++ специфическую вариацию и приведу несколько простых примеров использования.

    Visitor


    Для начала вспомним как устроен классический Visitor. Мотивация этого паттерна довольно проста. Представьте себе, что нам в программе нужно обработать контейнер (дерево, граф) полиморфных указателей и выполнить для каждого объекта какой-то набор операций, причем этот набор должен быть разным для каждого конкретного типа. Также стоит отметить, что сами объекты ничего не должны знать об алгоритмах их обработки кроме того, что их может “навестить” обработчик.
    Например, объекты файловой системы: файлы, папки:

    class abstract_file_t
    {
    public:
    	virtual std::string name() const = 0;
    	virtual void accept(visitor_t& v) = 0;
    	virtual ~abstract_file_t(){}
    };
    
    ////////////////////////////////////////////////////////////////////////////
    
    class regular_file_t : public abstract_file_t
    {
    public:
    	std::string name() const;
    	void accept(visitor_t& v);
    	size_t size();
    };
    
    ////////////////////////////////////////////////////////////////////////////
    
    typedef std::vector<abstract_file_t*> file_vector_t;
    class directory_t : public abstract_file_t
    {
    public:
    	void accept(visitor_t& v);
    	std::string name() const;
    	file_vector_t& files();
    };
    
    

    Как видите, знание объектов файловой системы о том как с ними будут работать состоит лишь в том, что их может “навестить” объект с базовым типом visitor_t. В функции accept мы просто “впускаем посетителя”:

    void regular_file_t::accept(visitor_t& v) {v.visit(*this);}
    

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

    class visitor_t
    {
    public:
    	virtual void visit(regular_file_t& f) = 0;
    	virtual void visit(directory_t& dir) = 0;
    	virtual ~visitor_t(){}
    };
    
    class print_info_visitor_t : public visitor_t
    {
    public:
    	void visit(regular_file_t& f);
    	{
    		std::cout << "visiting concrete file. file name: " << f.name() <<
    			" file size: " << f.size() << std::endl;
    	}
    	void visit(directory_t& dir)
    	{
    		std::cout << "visiting directory. directory name: " << dir.name() << 
                      ". contains " << dir.files().size() << “files” << std::endl;		
    	}
    };
    


    Static visitor


    Суть Static visitor’а также заключается в отделении данных от алгоритмов обработки этих данных. Основное отличие заключается в том, что динамический полиморфизм классического Visitor’а заменяется на статический (отсюда, собственно, и название идиомы). С одной реализацией этого паттерна мы встречаемся практически каждый раз когда используем алгоритмы STL. Действительно, предикаты STL — отличный пример static visitor’а. Чтобы это стало совершенно очевидно рассмотрим следующий небольшой пример:

    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_;
    };
    
    ////////////////////////////////////////////////////////////////////////////////
    int main() 
    {
    	std::vector<person_t> person_vec;
    	person_vec.push_back(person_t("Person 1", 43));
    	person_vec.push_back(person_t("Person 2", 20));
    
    	auto it = std::find_if(
    		person_vec.begin(),	person_vec.end(), person_visitor_t(30));
    	if(it != person_vec.end())
    		std::cout << it->age() << std::endl;
    	return 0;
    }
    

    Очень похоже на то, что мы видели в первой главе, не правда ли?

    Примеры использования


    Boost Graph Library

    Идею предиката можно развить. Почему бы нам не дать возможность пользователю изменять поведение наших алгоритмов в некоторых ключевых точках с помощью предоставленного пользователем же “посетителя”? Допустим мы пишем библиотеку для работы с графами, состоящую из структур данных для хранения узлов и ребер и алгоритмов для обработки этих структур (Boost Graph Library). Для максимальной гибкости мы можем предоставлять два варианта каждого алгоритма. Один выполняющий действия по умолчанию и другой — позволяющий пользователю влиять на некоторые шаги алгоритма. Упрощенно это можно представить так:

    template<typename T>
    struct node_t
    {
    	node_t(){}
    	// Аналог функции accept
    	template<typename V>
    	void on_init(V& v) {v.on_init(t_);}
    	// Еще один accept
    	template<typename V>
    	void on_print(V& v) {v.on_print(t_);}
    	T t_;
    };
    
    

    Алгоритмы. Одна версия по умолчанию и одна с использованием Visitor’a

    template<typename T, typename Graph>
    void generate_graph(Graph& g, size_t size);
    
    template<typename T, typename Graph, typename Visitor>
    void generate_graph(Graph& g, Visitor& v, size_t size)
    {
    	for(size_t i = 0; i < size; ++i)
    	{
    		node_t<T> node;
    		node.on_init(v);
    		g.push_back(node);
    	}
    }
    
    ////////////////////////////////////////////////////////////////////////////////
    
    template<typename Graph>
    void print_graph(Graph& g);
    
    template<typename Graph, typename Visitor>
    void print_graph(Graph& g, Visitor& v)
    {
    	for(size_t i = 0; i < g.size(); ++i)
    	{
    		g[i].on_print(v);
    	}
    }
    
    

    Теперь код пользователя.

    struct person_t
    {
    	std::string name;
    	int age;
    };
    
    ////////////////////////////////////////////////////////////////////////////////
    // visitor
    struct person_visitor_t
    {
    	// visit()
    	void on_init(person_t& p)
    	{
    		p.name = "unknown";
    		p.age = 0;
    	}
    	// visit()
    	void on_print(const person_t& p)
    	{
    		std::cout << p.name << ", " << p.age << std::endl;
    	}
    };
    
    ////////////////////////////////////////////////////////////////////////////////
    
    int main() 
    {
    	person_visitor_t person_visitor;
    	
    	typedef std::vector<node_t<person_t> > person_vec_t;
    	person_vec_t graph;
    	
    	generate_graph<person_t>(graph, person_visitor, 10);
    	print_graph(graph, person_visitor);
    }
    
    

    Variant

    Еще один крайне интересный пример применения идиомы static visitor можно найти в boost::variant. Variant представляет собой статически типизированный union. Данные любого допустимого типа хранятся в одном и том же массиве байт. И “посещаем” мы по сути всегда этот, хранящийся внутри variant, массив, но “смотрим” на него каждый раз с точки зрения разных типов. Реализовать это можно как-то так (код максимально упрощен и передает лишь основную идею):

     template<
        typename T1 = default_param1,
        typename T2 = default_param2,
        typename T3 = default_param3
      >
      class variant
      {
    ...
       public:
    
        // Хорошо уже знакомый нам accept()
        template<typename Visitor>
        void apply_visitor(const Visitor& v)
        {
          switch(type_tag_) // Тэг хранящегося в данный момент типа
          {
          case 1: 
            apply1(v, T1());
            break;
          case 2:
           apply2(v, T2());
            break;
          case 3:
           apply3(v, T3());
            break;
          default:
            break;
          }
        }
    };
    
    

    Функции apply могут выглядеть следующим образом

        template<typename Visitor, typename U>
        void apply1(
          const Visitor& v, U u, typename std::enable_if<
            !std::is_same<U, default_param1>::value>::type* = 0)
        {
          // data_ - массив байт. 
          // В качестве visit() используется operator()
          v(*(T1*)(&data_[0])); 
        }
    
        // Перегрузка для типа по умолчанию.
        template<typename Visitor, typename U>
        void apply1(
          const Visitor& v, U u, typename std::enable_if<
            std::is_same<U, default_param1>::value>::type* = 0)
        { 
        }
    


    Здесь мы используем SFINAE, чтобы “включить” корректную функцию для текущего типа и “выключить” для параметров класса по умолчанию. Пользовательский же код совсем простой:

    struct visitor_t 
    {
      void operator()(int i)const ;
       void operator()(double d)const;
      void operator()(const std::string& s)const;  
    };
    
    variant<int, double> test_v(34);
    test_v.apply_visitor(visitor_t());
    
    Share post

    Similar posts

    Comments 15

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

      И вокруг мультиметодов в С++ хватает идиом, благо, мы можем возложить задачу диспетчеризации
      — на алгоритм обхода (сделав его полиморфным — тот же 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 ситуация немножко другая. Если уж посетитель полез в него, — то, наверно, не просто так; и тем более, что данные заведомо полиморфны. Поэтому двойная диспетчеризация начинается сразу с приёмника.
        0
        Тут стоит подчеркнуть, что у паттерна Посетитель есть две независимые стороны
        — разнести алгоритм работы с контейнером и алгоритм работы с элементом


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

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

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

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


            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.»
              0
              Во-первых, единственный объект тоже является контейнером самого себя с одним тривиальным способом обхода.

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


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

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


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

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


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

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

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

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

                  Это как с DOM и SAX. Доступ к содержимому можем дать напрямую (через самый примитивный интерфейс — линейный обход, и это будет Итератор), а можем обеспечить через колбеки (и это будет Посетитель).
                  В любом случае, клиентский код полиморфный относительно библиотечного. Только с Итератором он вообще без ограничений, а с Посетителем — имеет определённый интерфейс.
        +1
        Зачем в этом классе метод 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.
          0
          1. Именно в этом кусочке accept не нужна. Она оставлена из тех соображений, что вполне можно написать свой STL-like функцию алгоритм, в которой она уже будет использоваться аналогично тому, как используется в BGL.
          2. Конечно, структуру person_visitor_t можно и нужно переделать в промышленном коде. Здесь она написана так, как она написана, чтобы показать близость предикатов и визитора.
          3. Visitor вяжется с предикатами в том смысле что и то то является сходными механизмами диспетчеризации, отделения алгоритма от данных. Естественно ни один в один, но сходно. Об этом неплохо написано у товарища nickolaym в первом комментарии.
          0
          В .NET в этом плане все прозаичнее и double dispatch толком не нужен.
            +1
            По ссылке, считаю, что классическая реализация неверна из-за присутствия гребенки if-else'ов. Механизм выбора метода «посетителя» должен быть возложен на компилятор. Он может быть осонован на прегрузке методов с различными типами аргуметов, или же это могут быть функции с разными именами или как-то по-другому, дело удобства. Это важно, т.к. существенно уменьшается гибкость (подумайте, например, о тестах) и ухудшается поддержка из-за поддержки еще и гребенок.
            В целом фича с использованием dynamic покрывает, наверное, больше 90% случаев, но все же это немного другое, т.к. не используется условие, что сами объекты знают о том, что их может “навестить” некий обработчик. Иногда эта дополнительная гибкость может быть очень полезной.
              0
              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;
                  }
              

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

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


                    Ему нужно указать, что V — это некий IVisitor с методом visit(p), но тогда нужно уточнять тип p, и в наследнике Person этот тип поменять уже нельзя.

            Only users with full accounts can post comments. Log in, please.