PkXwmpgN 19 окт 2016 в 19:02

Acyclic Visitor

8 мин

9.5K

C++*Программирование*

+19

Комментарии 14

Shamov 20 окт 2016 в 11:43

А мне как раз нужна constexpr-функция для генерация уникального hash'а для типа. Собирался сам её делать. Всю неделю откладывал эту задачу, делая пока то, что можно сделать без неё. А говорят, что бога нет. Может его и нет, но конкретно мне он походу помогает…

Siemargl 20 окт 2016 в 12:48

Непонятно, зачем нужен dynamic_cast<geometry_visitor*>(&obj)) в типичной реализации, если obj.visit() — виртуальный? Соответственно, вызов виртуального метода быстрее, чем RTTI.
Ну и тогда проблемы, которая решается в статье, нет вообще.

PkXwmpgN 20 окт 2016 в 12:48

У obj нет метода visit. Если бы был, тогда нужна перегрузка для всех типов — это циклическая зависимость.
Про этот пример можно подробно прочитать в книге Andrei Alexandrescu. Modern c++ design.

Siemargl 20 окт 2016 в 14:46

А, действительно. Но как пишет Александреску — это самый неудачный паттерн, потому редко используемый.

В вашем примере в итоге весь выигрыш из-за неудачной реализации dynamic_cast, который вы с помощью 3х листов исходного кода, с блекджеком и шаблонами реализуете руками с помощью map<>.

На мой взгляд, не нужно множить сущности, http://ideone.com/K0KQhk вот реализация проще, расширяемая и более эффективная, т.к switch() отлично оптимизируется компилятором

Заголовок спойлера

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
enum e_type {
	ENTITY,
	GEOMETRY,
	MODEL
};

struct visitor_base;
struct visitable 
{
    virtual void accept(visitor_base & obj) = 0;
};

struct visitor_base
{
    virtual void visit(visitable &, enum e_type type) = 0;
};

struct entity : visitable
{
    void accept(visitor_base & obj)
    {
        obj.visit(*this, ENTITY);
    }
};

struct geometry : entity
{
	void accept(visitor_base & obj)
    {
        obj.visit(*this, GEOMETRY);
    }
};

struct model : geometry
{
    void accept(visitor_base & obj)
    {
        obj.visit(*this, MODEL);
    }
};

struct test_visitor : visitor_base
{
    void visit(visitable & obj, enum e_type type)
    {
		switch(type)
		{
			case	ENTITY:
				{
					entity	&ent = (entity&)obj;  // its enough safe
					cout << "Visited ENTITY" << endl;
					break;
				}
			case	GEOMETRY:
				{
					geometry	&geo = (geometry&)obj;
					cout << "Visited GEOMETRY" << endl;
					break;
				}
			case	MODEL:
				{
					model	&mod = (model&)obj;
					cout << "Visited MODEL" << endl;
					break;
				}
			default:
				// TRAP
				;
		}
	}
};

struct modern_visitor : test_visitor // extension for new objects
{
	// add new methods for new visitables, call parent otherwise
};


int main() {
	entity E;
	geometry G;
	model M;
	vector<entity*> vec = {&E, &G, &M};
	test_visitor visi;
	for_each(vec.begin(), vec.end(), [&](entity *i){ i->accept(visi); });

	// your code goes here
	return 0;
}

PkXwmpgN 20 окт 2016 в 15:23

Но как пишет Александреску — это самый неудачный паттерн, потому редко используемый

Это немного упрошенный пример, у Александреску более аккуратный, обобщенный шаблон (в Loki, dynamic_cast вынемен отдельно), но суть там такая же. Не такой уж он и неудачный.

Намой взгляд, возможности по расшерению и поддержке этой модели, такие же как и у Cyclic Visitor. Только вместо виртуальной функции мне нужно добавить поле в enum, вы же понимаете, что если я добавлю поле в enum все существующие visitor'ы нужно будет перекомпелировать. Что если это библиотека и у меня нет возможности добавить поле в enum, также как у меня может не быть возможности добавить виктуальную функцию в случаи с Cyclic Visitor и перекомпилировать все?

Siemargl 20 окт 2016 в 16:04

На самом деле, перекомпилировать не нужно. Это же Си — обычные константы!
Просто новые Визиторы должны видеть дополненный enum.

Вот интересно скорость сравнить — мой вариант сравнить с табличкой производительности.
Ассемблерный код switch я уже посмотрел — 2 инструкции сравнения )

Eivind 20 окт 2016 в 14:43

Я это вижу как-то так:

Код

#include <iostream>

template <class T>
struct visitor {
    virtual void visit( T& ) = 0;
};

template <class T, class... Base>
struct visitable : Base... {
    template <class Visitor>
    void accept( Visitor& obj )
    {
        static_cast<visitor<T>&>( obj ).visit( static_cast<T&>( *this ) );
    }
};

struct entity : visitable<entity> {
};

struct geometry : visitable<geometry, entity> {
};

struct model : visitable<model, geometry> {
};

struct test_visitor : visitor<entity>, visitor<geometry>, visitor<model> {
    void visit( entity& obj ) override
    {
        std::cout << "entity\n";
    }

    void visit( geometry& obj ) override
    {
        std::cout << "geometry\n";
    }

    void visit( model& obj ) override
    {
        std::cout << "model\n";
    }
};

int main()
{
    entity e;
    geometry g;
    model m;

    test_visitor v;

    e.accept( v );
    g.accept( v );
    m.accept( v );
}

Siemargl 20 окт 2016 в 14:52

Это Cyclic Visitor, только завернут в шаблоны.

Eivind 20 окт 2016 в 14:54

Хотя вру, через ссылки на базовые классы работать не будет.

Eivind 20 окт 2016 в 16:26

Вот, теперь должно быть правильно:

Заголовок спойлера

#include <iostream>
#include <vector>

template <class T>
struct visitor_base {
    template <class R>
    void visit_base( R& obj )
    {
        static_cast<typename R::visitor_type&>( *this ).visit( obj );
    }
};

template <class T>
struct visitor : T::parent_visitor_type {
    virtual void visit( T& ) = 0;
};


template <class T, class Base = void>
struct visitable : Base {
    using parent_visitor_type = typename Base::visitor_type;
    using visitor_type        = visitor<T>;

    void accept( typename Base::visitor_base_type& obj ) override
    {
        obj.visit_base( static_cast<T&>( *this ) );
    }
};

template <class T>
struct visitable<T, void> {
    using parent_visitor_type = visitor_base<T>;
    using visitor_base_type   = visitor<T>;
    using visitor_type        = visitor_base_type;

    virtual void accept( visitor_base_type& obj )
    {
        obj.visit( static_cast<T&>( *this ) );
    }
};

struct entity : visitable<entity> {
};

struct geometry : visitable<geometry, entity> {
};

struct geometry2 : geometry {
};

struct model : visitable<model, geometry2> {
};

struct test_visitor : visitor<model> {
    void visit( entity& obj ) override
    {
        std::cout << "entity\n";
    }

    void visit( geometry& obj ) override
    {
        std::cout << "geometry\n";
    }

    void visit( model& obj ) override
    {
        std::cout << "model\n";
    }
};

int main()
{
    entity e;
    geometry g;
    geometry2 g2;
    model m;

    test_visitor v;

    e.accept( v );
    g.accept( v );
    g2.accept( v );
    m.accept( v );

    std::vector<entity*> vec{&e, &g, &g2, &m};
    for ( auto it : vec ) {
        it->accept( v );
    }
}

PkXwmpgN 20 окт 2016 в 16:57

А если у меня иерархия не линейная?

Скрытый текст

struct entity {};
struct geometry : entity {};
struct model : entity {};

Eivind 20 окт 2016 в 17:40

Да, без RTTI тогда никак.

Eivind 20 окт 2016 в 18:46

Впрочем, можно доработать методом из соседнего комментария

Заголовок спойлера

#include <iostream>
#include <type_traits>
#include <vector>

template <class T>
struct id {
    static id id_;
};

template <class T>
id<T> id<T>::id_;

template <class T>
struct visitor_base {
    using common_type = T;
    virtual void visit_base( T& obj, void* ptr ) = 0;
};

template <class T, class Base = void>
struct visitable : Base {
    void accept( typename Base::visitor_type& obj ) override
    {
        obj.visit_base( static_cast<T&>( *this ), &id<T>::id_ );
    }
};

template <class T>
struct visitable<T, void> {
    using visitor_type = visitor_base<T>;

    virtual void accept( visitor_type& obj )
    {
        obj.visit_base( static_cast<T&>( *this ), &id<T>::id_ );
    }
};

template <class...>
struct tag {
};

template <class T>
struct visitor_impl {
    virtual void visit( T& ) = 0;
};

template <class... Ts>
struct visitor : visitor_impl<Ts>..., std::common_type<Ts...>::type::visitor_type {
    using common_type = typename std::common_type<Ts...>::type::visitor_type::common_type;
    void visit_base( common_type& obj, void* ptr ) override
    {
        visit_( obj, ptr, tag<Ts...>() );
    }

private:
    void visit_( common_type& obj, void*, tag<> )
    {
    }

    template <class Head, class... Tail>
    void visit_( common_type& obj, void* ptr, tag<Head, Tail...> )
    {
        if ( ptr == &id<Head>::id_ ) {
            static_cast<visitor_impl<Head>&>( *this ).visit( static_cast<Head&>( obj ) );
        }
        else {
            visit_( obj, ptr, tag<Tail...>() );
        }
    }
};


struct entity : visitable<entity> {
};

struct geometry : visitable<geometry, entity> {
};

struct model : visitable<model, entity> {
};


struct test_visitor : visitor<entity, geometry, model> {
    void visit( entity& ) override
    {
        std::cout << "entity\n";
    }

    void visit( geometry& ) override
    {
        std::cout << "geometry\n";
    }

    void visit( model& ) override
    {
        std::cout << "model\n";
    }
};

int main()
{
    entity e;
    geometry g;
    model m;

    test_visitor v;

    e.accept( v );
    g.accept( v );
    m.accept( v );

    std::cout << "\n";

    std::vector<entity*> vec{&e, &g, &m};
    for ( auto it : vec ) {
        it->accept( v );
    }
}

antoshkka 20 окт 2016 в 19:10

Аналогичный CTTI есть в Boost http://boostorg.github.io/type_index/boost/typeindex/ctti_type_index.html

Только вот ему пока не хватает `constexpr` hash функции.

Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Acyclic Visitor

Комментарии 14

Публикации

Истории