この記事では、RTTIを使用せずにAcyclic Visitorビヘイビアーデザインパターンを実装するためのオプションの1つを見ていきます。
Visitorのビヘイビアデザインパターンの主な目的は、オブジェクトの階層構造に抽象的な機能を導入することです。
テンプレートの実装は、2つのカテゴリに分類できます。
- 巡回ビジター 。 関数のオーバーロードメカニズムに基づきます。 巡回依存のため（訪問先の階層では訪問者のタイプを明確にする必要があり、訪問者は階層内のすべてのクラスを明確にする必要があります）、スコープは安定した階層（新しいクラスが追加されることはほとんどありません）にのみ制限されます。
- 非周期的訪問者 。 動的データ型識別（ RTTI ）に基づきます。 訪問された階層に制限はありませんが、動的な識別の使用により、パフォーマンスが低下します。
典型的な巡回訪問者の実装
struct entity; struct geometry; struct model; struct visitor { virtual bool visit(entity &) = 0; virtual bool visit(geometry &) = 0; virtual bool visit(model &) = 0; }; struct entity { public: virtual ~entity() {} virtual void accept(visitor & obj) { obj.visit(*this); } }; struct geometry : entity { public: void accept(visitor & obj) { obj.visit(*this); } }; struct model : geometry { public: void accept(visitor & obj) { obj.visit(*this); } }; struct test_visitor : visitor { public: void visit(entity & obj) { // something } void visit(geometry & obj) { // something } void visit(model & obj) { // something } };
RTTIを使用したAcyclic Visitorの典型的な実装
template<typename _Visitable> struct visitor { virtual void visit(_Visitable &) = 0; }; struct visitor_base { virtual ~visitor_base(){} }; struct entity { public: virtual ~entity() {} virtual void accept(visitor_base & obj) { using entity_visitor = visitor<entity>; if(entity_visitor * ev = dynamic_cast<entity_visitor*>(&obj)) ev->visit(*this); } }; struct geometry : entity { public: virtual void accept(visitor_base & obj) { using geometry_visitor = visitor<geometry>; if(geometry_visitor * gv = dynamic_cast<geometry_visitor*>(&obj)) gv->visit(*this); } }; struct model : geometry { public: virtual void accept(visitor_base & obj) { using model_visitor = visitor<model>; if(model_visitor * mv = dynamic_cast<model_visitor*>(&obj)) mv->visit(*this); } }; struct test_visitor : visitor_base, visitor<entity>, visitor<geometry>, visitor<model> { public: void visit(entity & obj) { // something } void visit(geometry & obj) { // something } void visit(model & obj) { // something } };
性能
300万個の要素の配列で簡単な操作を実行する
| 模様 | 時間（ミリ秒） |
|---|---|
| 巡回訪問者 | 11.3 |
| 非周期的訪問者（RTTI） | 220.4 |
動的識別を使用した訪問者は、通常のテンプレートよりもパフォーマンスがはるかに劣っていることがわかります。 私たちの主なタスクは、テンプレートを非循環に保ちながら、RTTIのないバージョンにパフォーマンスを近づけることです。
実装
主な考え方は、階層からの一連の訪問済みクラスに対して、訪問者は、訪問済みクラスのタイプの一意の識別子に基づいて、訪問者の対応するメソッドを呼び出すコンバーターメソッドを含む特別な遅延バインディングテーブル（ vtbl ）を生成することです。
したがって、2つのサブタスクがあります
- 一意のタイプ識別子を取得する
- 遅延リンクテーブルを生成する
タイプの一意の識別子
この問題を解決するために、小さなCTTIヘッダーのみのライブラリを使用します。 一意の識別子として、一意の文字列型名に基づいて計算されたハッシュを使用します。
namespace detail { using hash_type = std::uint64_t; template<typename _Base, typename _Specific> struct tag {}; template<typename _Base, typename _Specific> inline constexpr hash_type get_hash() { using tag_type = tag<typename std::remove_cv<_Base>::type, typename std::remove_cv<_Specific>::type>; return ctti::unnamed_type_id<tag_type>().hash(); } } /* detail */
オブジェクトを多相的に処理し、オブジェクトの正確なタイプがわからないという事実に基づいて、階層内の各クラスは一意の識別子を取得するメカニズムを処理する必要があります。 識別子を返す仮想メソッドを追加します。
template <typename _Base> struct visitable { using base_type = _Base; }; // // #define VISITABLE(Specific) \ static constexpr detail::hash_type hash__ = detail::get_hash<base_type, Specific>(); \ virtual detail::hash_type get_hash() const \ {\ return hash__; \ }
例
struct entity : visitable<entity> { public: VISITABLE(entity); public: virtual ~entity() {} }; struct geometry : entity { public: VISITABLE(geometry); }; struct model : geometry { public: VISITABLE(model); };
遅延リンクテーブルの生成
コンバーターメソッドのコンテナーとして、訪問型の一意の識別子をキーとして持つ標準の結合マップコンテナーを使用します。
namespace detail { template<typename _Visitor, typename _Base> struct vtbl_traits { // . // using base_type = _Base; // using visitor_type = _Visitor; // - using function_type = void(visitor_type::*)(base_type &); }; template<typename _Traits> struct vtbl { using base_type = typename _Traits::base_type; using function_type = typename _Traits::function_type; using visitor_type = typename _Traits::visitor_type; // template<typename _Specific> void put(function_type function) { vtbl_[get_hash<base_type, _Specific>()] = function; } // function_type get(const hash_type & hash) const { auto it = vtbl_.find(hash); return it != vtbl_.end() ? it->second : nullptr; } private: std::map<hash_type, function_type> vtbl_; }; } /* detail */
ダラ訪問するクラスのリスト用のテーブルを生成する必要があります
namespace detail { // _Traits // _Specifics template<typename _Traits, typename... _Specifics> struct vtbl_builder { // using vtbl_type = vtbl<_Traits>; // using visitor_type = typename _Traits::visitor_type; // using base_type = typename _Traits::base_type; template<typename... _Targets> struct targets {}; vtbl_builder() { // put_thunk(targets<_Specifics...>()); } const auto * get_vtbl() const { return &vtbl_; } private: template<typename _Specific, typename... _Tail> void put_thunk(targets<_Specific, _Tail...>) { // // . // using specific_type = constancy_t<base_type, _Specific>; using is_put = typename has_visit_method<visitor_type, specific_type>::type; put_thunk(targets<_Specific, _Tail...>(), is_put()); } // // thunk template<typename _Specific, typename... _Tail> void put_thunk(targets<_Specific, _Tail...>, std::true_type) { vtbl_.template put<_Specific>(&visitor_type::template thunk<base_type, _Specific>); put_thunk(targets<_Tail...>()); } // // , template<typename _Specific, typename... _Tail> void put_thunk(targets<_Specific, _Tail...>, std::false_type) { put_thunk(targets<_Tail...>()); } void put_thunk(targets<>) {} private: vtbl_type vtbl_; }; // template<typename _Traits, typename... _Specifics> inline const auto * get_vtbl() { static vtbl_builder<_Traits, typename std::remove_cv<_Specifics>::type...> builder; return builder.get_vtbl(); } } /* detail */
別の型の定数に基づいて型に定数を追加します
template<typename _From, typename _To> using constancy_t = typename std::conditional<std::is_const<_From>::value, const _To, _To>::type;
メソッドの可用性を確認する
template<typename _Visitor, typename _Specific> struct has_visit_method { template<typename _Class, typename _Param> static auto test(_Param * p) -> decltype(std::declval<_Class>().visit(*p), std::true_type()); template<typename, typename> static std::false_type test(...); using type = decltype(test<_Visitor, _Specific>(nullptr)); static constexpr const bool value = std::is_same<std::true_type, type>::value; };
変換方法を決定し、オブジェクト処理メカニズムを説明することは私たちに残っています
template<typename _Base> struct visitor_traits { // using base_type = _Base; }; // template<typename _Visitor, typename _Traits> struct visitor { using visitor_type = _Visitor; using traits_type = _Traits; // -, template<typename _Base, typename _Specific> void thunk(_Base & base) { using specific_type = detail::constancy_t<_Base, _Specific>; static_cast<visitor_type*>(this)->visit(static_cast<specific_type&>(base)); } // template<typename _Base> void operator()(_Base & base) { // , // . static_assert(std::is_base_of<typename traits_type::base_type, _Base>::value, ""); // . // _Base // using base_type = detail::constancy_t<_Base, typename traits_type::base_type>; using traits_type = detail::vtbl_traits<visitor_type, base_type>; // . // get_vtbl const auto * vtbl = static_cast<visitor_type*>(this)->template get_vtbl<traits_type>(); // , // , if(auto thunk = vtbl->get(base.get_hash())) (static_cast<visitor_type*>(this)->*thunk)(base); } }; // // - #define VISIT(...) \ template<typename _Traits> \ const auto * get_vtbl() const \ { \ return detail::get_vtbl<_Traits, __VA_ARGS__>(); \ }
例
struct entity : visitable<entity> { public: VISITABLE(entity); public: virtual ~entity() {} }; struct geometry : entity { public: VISITABLE(geometry); }; struct model : geometry { public: VISITABLE(model); }; template<typename _Visitor> using visitor_entities = visitor<_Visitor, visitor_traits<entity>>; struct test_visitor : visitor_entities<test_visitor> { public: VISIT(entity, geometry, model); public: void visit(const entity & obj) { // something } void visit(const geometry & obj) { // something } void visit(const model & obj) { // something } }; int main() { const entity & ref_entity = entity(); const entity & ref_model = model(); const entity & ref_geometry = geometry(); test_visitor test; test(ref_entity); test(ref_model); test(ref_geometry); }
性能
遅延バインディングテーブルの異なる標準コンテナを使用した同じテストでのパフォーマンス
| 模様 | 時間（ミリ秒） |
|---|---|
| 巡回訪問者 | 11.3 |
| 非周期的訪問者（RTTI） | 220.4 |
| 地図を持つ非周期的訪問者 | 23.2 |
| unordered_mapを使用した非周期的な訪問者 | 44.5 |
| 並べ替えベクトルを持つ非周期的ビジター | 31.1 |
»プロジェクトコードはGitHubにあります 。
私はコメントや提案に喜んでいるでしょう（yegorov.alex@gmail.comで可能です）
よろしくお願いします！