组合与访问者 - 模板化方法
4.22/5 (11投票s)
2004 年 8 月 8 日
9分钟阅读
104312
503
一篇关于组合和访问者交互的模板化实现的探讨。
引言
本文提供了一个通用的模板化组合模式实现，包括深度和浅度迭代的迭代器。然后，它将此组合模式与 Loki 访问者（参见 Andrei Alexandrescu 关于 Loki 库的作品）集成，并详细介绍了不同的访问策略。
背景
组合模式是我最喜欢的设计模式之一。它提供了一个简单的树形结构实现。潜在的应用包括：图形系统中的场景层次结构；或表达式树的实现。尽管组合模式是一种非常强大的设计模式，并且被广泛应用于各种应用程序中，但我尚未见到任何优秀的通用实现。在解决这个问题时，我希望处理构建组合模式的许多关键问题。这些问题包括内存管理、迭代器的提供（用于在树的单个级别上迭代以及迭代整个树），以及提供简单的 API。为了实现这些目标，我使用了“好奇的递归模板模式”来提供一个基类，该基类的接口可以被继承类轻松使用。我试图在实现中尽量减少动态转换的使用，但不得不允许少量使用。深度迭代器需要 2 次动态转换，而向上导航树则需要 1 次动态转换。
组合模式上深度和浅度迭代器的实现遵循了创建与 STL 容器兼容的迭代器的常规技术。浅度迭代器是双向迭代器；而深度迭代器是单向迭代器。它们不完全兼容 STL，因为我没有继承 STL 迭代器类，这意味着它们不实现迭代器特性；然而，如果特定应用程序需要，这个添加应该是相对容易的。另一个可以进行大量改进的领域是，我实现了深度迭代器使其小巧，而不是高效。深度迭代器从一个特定节点开始，然后遍历所有子节点，之后再移动到兄弟节点。移动到下一个兄弟节点的过程需要搜索父节点的所有子列表以获取当前位置。这可以通过在深度迭代器类中存储一个 STL 列表迭代器并使用它来移动到下一个兄弟节点来改进。这个优化留作练习，尽管如果感兴趣的人足够多，我也会实现它。
我使用的访问者是 Alexandrescu 实现的 Loki 访问者。他创造了我所见过的最令人印象深刻的模板化访问者。只需一次动态转换即可接受访问者，他完全解耦了访问者和可访问类。这样做，这个实现巧妙地规避了 Gamma 等人描述的访问者模式唯一真正主要的问题。我在两个非常简单的方面扩展了他的工作。第一点是，如果你有一个类层次结构，Loki 访问者只会访问你指定访问发生级别的节点。通过在基类访问者中放置一些简单的代码，你可以让系统反复尝试访问基类，直到找到一个已实现的类。第二点涉及访问者与组合模式的集成。通常，在讨论访问者模式时，不会提及如何访问对象集合，如组合模式所定义的。通过在多个接口类中实现访问顺序，可以轻松地根据需要将访问顺序混合到每个访问者中。这就留下了一个非常干净的接口，访问者可以使用一行简单的代码访问整个组合模式层次结构。
visitor( composite );
Using the Code
要实现通用的组合模式，请像这样派生自 `CGenericTree` 类
class CNodeBase : public Types::CGenericTree<CNodeBase>
{
virtual CNodeBase *Clone() { return new CNodeBase( *this ); }
};
为了使组合模式可被 Loki 访问者访问，请使用
class CNodeBase : public Loki::BaseVisitable<>,
public Types::CGenericTree<CNodeBase>
{
DEFINE_VISITABLE()
virtual CNodeBase *Clone() { return new CNodeBase( *this ); }
};
在 `NodeBase.h` 源文件中可以看到 `CGenericTree` 用法的示例。在这里，我创建了一个简单的基类和两个派生类的层次结构，它们都可以被访问。请注意，`Clone` 函数的实现对于使组合树的复制和相等运算符能够正常工作是必需的。
实现通用的访问者稍微复杂一些。基本的 `Loki visitor` 实现如下
class CVisitorBase : public Loki::BaseVisitor,
public Loki::Visitor<CNodeBase>
{
virtual void Visit( CNodeBase &node ) {}
};
如果你查看 `VisitorBase.h`，你会看到 `CVisitorBase` 中定义的基类。在这里，你可以看到为了确保如果我们有一个类型，其 `visit` 函数在派生类中未实现，可以使用一个通用的基类 `Visit` 函数所需的附加（简单）代码。这在 `CVisitorDerived1` 中得到了演示。`CVisitorDerived2` 展示了一个完全定义的访问者。
现在，到了精彩的部分。通过混合使用 `GenericVisitor.h` 中的“好奇的递归模板”，你可以将普通的访问者变成访问给定顺序的树层次结构的函数对象。例如：
class CVisitorDerived2TopToBottom :
public CVisitorDerived2,
public Types::CVisitorTopToBottom<CVisitorDerived2TopToBottom,CNodeBase>
{
};
请注意，你不需要在此访问者的最终派生版本中实现任何代码，只需将两个基类混合在一起即可生成一个完全工作的访问者。访问者的使用也就变得极其简单了：
CVisitorDerived2TopToBottom visitor;
CNodeBase *head = ;// Some tree structure
visitor( head );
代码
为了完整起见，我包含了组合模式基类 `CGenericTree` 以及用于访问者的 3 个混合类（mix-in classes）的代码。我删除了 `const` 函数和迭代器，并稍微重新格式化了代码，使其更易于浏览。
#pragma once
#include <list>
#include <algorithm>
namespace Types {
template <typename T>
class CGenericTree
{
public:
// Forward declarations and friends
class shallow_iterator;
class deep_iterator;
friend class shallow_iterator;
friend class deep_iterator;
private:
// Typedefs
typedef typename T* _tptr;
typedef typename std::list<T*>::iterator container_iterator;
typedef typename std::list<T*>::const_iterator const_container_iterator;
public:
class shallow_iterator
{
friend class CGenericTree<T>;
public:
// Normal constructors and destructors
shallow_iterator() :
m_iterator() {}
shallow_iterator( const shallow_iterator &src ) :
m_iterator( src.m_iterator ) {}
shallow_iterator &operator=( const shallow_iterator &rhs )
{
if ( this != &rhs )
{
m_iterator = rhs.m_iterator;
}
return *this;
}
~shallow_iterator() {}
// Equality operator
bool operator==( const shallow_iterator &rhs ) const
{
return m_iterator == rhs.m_iterator;
}
bool operator!=( const shallow_iterator &rhs ) const
{
return m_iterator != rhs.m_iterator;
}
// Referencing operators
_tptr& operator*()
{
return *m_iterator;
}
_tptr* operator->()
{
return m_iterator.operator->();
}
// Increment/decrement operators
shallow_iterator& operator++()
{
++m_iterator;
return *this;
}
shallow_iterator operator++(int)
{
shallow_iterator tmp = *this;
++*this;
return tmp;
}
shallow_iterator& operator--()
{
--m_iterator;
return *this;
}
shallow_iterator operator--(int)
{
shallow_iterator tmp = *this;
--*this;
return tmp;
}
private:
// Private constructor off a normal iterator
explicit shallow_iterator( const container_iterator &iter ) :
m_iterator( iter ) {}
// Get the internal storage iterator
container_iterator GetIterator()
{
return m_iterator;
}
// Internal storage is a normal iterator
container_iterator m_iterator;
};
class deep_iterator
{
friend class CGenericTree<T>;
public:
// Normal constructors and destructors
deep_iterator() :
m_iterator( NULL ) {}
deep_iterator( const deep_iterator &src ) :
m_iterator( src.m_iterator ) {}
deep_iterator &operator=( const deep_iterator &rhs )
{
if ( this != &rhs )
{
m_iterator = rhs.m_iterator;
}
return *this;
}
~deep_iterator()
{
m_iterator = NULL;
}
// Equality operator
bool operator==( const deep_iterator &rhs ) const
{
return m_iterator == rhs.m_iterator;
}
bool operator!=( const deep_iterator &rhs ) const
{
return m_iterator != rhs.m_iterator;
}
// Referencing operators
_tptr& operator*()
{
return m_iterator;
}
_tptr* operator->()
{
return &**this;
}
// Increment operators
deep_iterator& operator++()
{
if ( m_iterator ) m_iterator = m_iterator->GetNext();
return *this;
}
deep_iterator operator++(int)
{
deep_iterator tmp = *this;
++*this;
return tmp;
}
private:
// Private constructor off a pointer
explicit deep_iterator( CGenericTree<T> *src ) :
m_iterator( dynamic_cast<T*> ( src ) ) {}
// Internal storage is simply a pointer
T* m_iterator;
};
private:
// Helper function for tree-deep iterators
T* GetNext();
T* GetNext( CGenericTree<T> *src );
public:
// Constructors and destructors
CGenericTree() : m_parent( NULL ) {}
CGenericTree( const CGenericTree &src );
CGenericTree &operator=( const CGenericTree &rhs );
~CGenericTree() { DeleteAllChildren(); }
virtual T* Clone() = 0;
private:
void CopyAllChildren( const CGenericTree &src );
void DeleteAllChildren();
public:
// Iterator begin/end functions
shallow_iterator begin_shallow()
{
return shallow_iterator( m_children.begin() );
}
shallow_iterator end_shallow()
{
return shallow_iterator( m_children.end() );
}
deep_iterator begin_deep()
{
return deep_iterator( this );
}
deep_iterator end_deep()
{
if ( m_parent )
return deep_iterator( m_parent->GetNext( this ) );
else
return deep_iterator( NULL );
}
// Tree navigation
T* GetParent();
unsigned int size() const
{
return (unsigned int) m_children.size();
}
bool empty() const
{
return m_children.empty();
}
// Add and remove entries from the tree
void DeleteFromTree();
void push_back( T* entry );
T* remove( T* entry );
T* remove( shallow_iterator iter );
T* remove( deep_iterator iter );
private:
// This list of children of this tree element
std::list<T*> m_children;
// The parent of this object
CGenericTree<T>* m_parent;
};
template <typename T>
T*
CGenericTree<T>::GetNext()
{
if ( m_children.empty() )
{
if ( m_parent )
return m_parent->GetNext( this );
else
return NULL;
}
return m_children.front();
}
template <typename T>
T*
CGenericTree<T>::GetNext( CGenericTree<T> *src )
{
T* entry = dynamic_cast<T*> ( src );
container_iterator iter = ++( find( m_children.begin(),
m_children.end(), entry ) );
if ( iter != m_children.end() )
return *iter;
if ( m_parent )
return m_parent->GetNext( this );
return NULL;
}
template <typename T>
CGenericTree<T>::CGenericTree( const CGenericTree<T> &src ) : m_parent( NULL )
{
CopyAllChildren( src );
}
template <typename T>
CGenericTree<T> &
CGenericTree<T>::operator=( const CGenericTree<T> &rhs )
{
if ( this != &rhs )
{
DeleteAllChildren();
m_parent = NULL;
CopyAllChildren( rhs );
}
return *this;
}
template <typename T>
void
CGenericTree<T>::CopyAllChildren( const CGenericTree<T> &src )
{
const_container_iterator iter = src.m_children.begin();
for ( ; iter != src.m_children.end(); ++iter )
push_back( (*iter)->Clone() );
}
template <typename T>
void
CGenericTree<T>::DeleteAllChildren()
{
container_iterator iter = m_children.begin();
for ( ; iter != m_children.end(); ++iter )
delete (*iter);
m_children.clear();
}
template <typename T>
void
CGenericTree<T>::DeleteFromTree()
{
if ( m_parent )
m_parent->remove( (T*) this );
delete this;
}
template <typename T>
T*
CGenericTree<T>::GetParent()
{
return dynamic_cast<T*> (m_parent);
}
template <typename T>
void
CGenericTree<T>::push_back( T* entry )
{
m_children.push_back( entry );
entry->m_parent = this;
}
template <typename T>
T*
CGenericTree<T>::remove( T* entry )
{
container_iterator iter = find( m_children.begin(), m_children.end(),
entry );
if ( iter != m_children.end() )
m_children.erase( iter );
entry->m_parent = NULL;
return entry;
}
template <typename T>
T*
CGenericTree<T>::remove( shallow_iterator iter )
{
if ( iter != end_shallow() )
m_children.erase( iter.GetIterator() );
(*iter)->m_parent = NULL;
return *iter;
}
template <typename T>
T*
CGenericTree<T>::remove( deep_iterator iter )
{
if ( (*iter)->m_parent )
(*iter)->m_parent->remove( (*iter) );
return *iter;
}
}
#pragma once
#include <Visitor.h>
namespace Types {
template <typename Visitor, typename BaseVisitable>
class CVisitorTopToBottom
{
public:
virtual ~CVisitorTopToBottom() {}
void operator()( BaseVisitable * );
};
template <typename Visitor, typename BaseVisitable>
class CVisitorBottomToTop
{
public:
virtual ~CVisitorBottomToTop() {}
void operator()( BaseVisitable * );
};
template <typename Visitor, typename BaseVisitable>
class CVisitorLeftToRight
{
public:
virtual ~CVisitorLeftToRight() {}
void operator()( BaseVisitable * );
};
template <typename Visitor, typename BaseVisitable>
void
CVisitorTopToBottom<Visitor, BaseVisitable>::operator()(
BaseVisitable *visitable )
{
// Visit this
visitable->Accept( *dynamic_cast<Visitor*>( this ) );
// Now visit all the children
if ( visitable->empty() )
return;
BaseVisitable::shallow_iterator iter = visitable->begin_shallow();
for ( ; iter != visitable->end_shallow(); ++iter )
(*this)(*iter);
}
template <typename Visitor, typename BaseVisitable>
void
CVisitorBottomToTop<Visitor, BaseVisitable>::operator()(
BaseVisitable *visitable )
{
// Visit all the children
if ( !visitable->empty() )
{
BaseVisitable::shallow_iterator iter = visitable->begin_shallow();
for ( ; iter != visitable->end_shallow(); ++iter )
(*this)(*iter);
}
// Now visit this
visitable->Accept( *dynamic_cast<Visitor*>( this ) );
}
template <typename Visitor, typename BaseVisitable>
void
CVisitorLeftToRight<Visitor, BaseVisitable>::operator()(
BaseVisitable *visitable )
{
// Visit the left hand child
if ( !visitable->empty() )
(*this)(*visitable->begin_shallow());
// Visit this
visitable->Accept( *dynamic_cast<Visitor*>( this ) );
// Visit the right hand child(ren)
if ( visitable->size() > 1 )
{
BaseVisitable::shallow_iterator iter = ++visitable->begin_shallow();
for ( ; iter != visitable->end_shallow(); ++iter )
(*this)(*iter);
}
}
}
关注点
本文中有几个值得关注的点，我将挑出一些我认为很巧妙的地方。
“好奇的递归模板模式”允许你将派生类的信息传递给通用基类。这可以以非常简单的方式使用，例如实现通用的引用计数机制（这是通常的书本示例）。我使用了该模式两次。第一次允许我将 `CGenericTree` 的接口变成基类可用的形式，而无需程序员不断担心动态转换。第二次用于实现访问者的混合策略（mix-in strategy）的分派，使我能够在不知道访问者最终实现的情况下，将可访问对象分派给访问者。
实现 STL 风格的迭代器既容易又极其有用。`CGenericTree` 中使用的两个迭代器可以被馈送到 STL 算法（例如 `find`）中，而无需额外考虑。我认为人们不经常实现迭代器的主要原因是其有时难以理解的语法。我的建议是，如果你卡住了，就看看别人的实现。我经常浏览 Microsoft 的列表实现以获取灵感。一个需要一些时间来习惯的棘手语法示例是：
const _ctptr* operator->() const { return &**this; }
`Loki` 是一个优秀的库。CodeProject 上还有其他关于例如单例、工厂或多重分派的文章。我对所有这些的建议是购买 Alexandrescu 的书并使用 `Loki` 库。
通用树是使用普通的 C++ 指针实现的，也可以使用 Boost 智能指针来实现。我以前这样做过一次，效果非常好，只是需要注意一些实现问题。例如，父指针必须是 `weak_ptr`，而存储必须使用 `shared_ptr`。另外，`weak_ptr` 在构造期间无法创建，因此如果你希望组合节点自动添加到树中，你必须使用某种工厂。
多重继承可以成为你的朋友，只需小心使用。我通过使用 Loki 访问者学会了多重继承有多好。我唯一建议要极力避免的多重继承是“菱形继承”。一般来说，我使用多重继承将新功能混合到类中，或者用作接口。在这两种情况下，它都是一个非常强大的工具，不必害怕。在本文中，多重继承已在各种地方使用。它被用来使一个对象既成为组合树的成员，又能被 Loki 访问者访问。它是 Loki 访问者的关键特性，为每种可访问类型使用一个小的基类。最后，它允许 Loki 访问者实现各种不同的策略来访问组合树。
最后，我建议看看深度迭代器中的 `++` 运算符以及 `GetNext()` 函数。这些函数（在我看来）实现了遍历所有树元素的最优方法，而无需存储除当前位置以外的任何状态。`GetNext()` 用于执行以下两个操作之一。如果我们有任何子节点，则向下进入列表中的第一个子节点。否则，递归地使用 `GetNext(this)` 到父节点的下一个兄弟节点。此函数会查找 `this` 在子列表中的位置，找到后返回下一个子节点；如果它是最后一个子节点，则向上移动到父节点进行 `GetNext(this)`。当我们用完了父节点时，我们使用 `NULL` 来表示 `end()`。请注意，`end_deep()` 函数的实现并不像返回 `NULL` 那么简单，因为我们允许深度迭代从根节点以外的节点开始和结束。因此，`end_deep()` 函数被实现为返回如果我们进行完整树迭代时，增量操作的值。这可以是 `NULL`，也可以是所需迭代范围之外的第一个节点。
后记
我从未完全理解许多 C++ 程序员对使用 RTTI 的偏执。它给应用程序带来的开销非常小，而且它的用途几乎是无限的；然而，似乎仍有人不喜欢内存占用增加几 KB 的想法。因此，我写了一个 `CGenericTree` 类的版本，它使用静态转换（static casts）向上进行继承层级转换，而不是向下进行动态转换（dynamic casts）。尽管这个版本可能速度更快，并且不需要 RTTI，但我还是建议使用主项目中包含的第一个版本。原因是，多年以后维护代码的程序员可能会犯一个错误，即不继承自 `CGenericTree` 而试图将其作为普通容器使用。在这种情况下，静态转换会灾难性地失败，而动态转换只会返回 `NULL`。这是一个细微的差别，但我认为后者更容易调试。
历史
- 2004 年 8 月 8 日 - 初始发布
- 2004 年 8 月 10 日 - 添加了无动态转换通用树的附加文件
- 2004 年 10 月 10 日 - 修改了模板以解决删除函数中的崩溃问题
许可证
本文未附加明确的许可证，但可能在文章文本或下载文件本身中包含使用条款。如有疑问，请通过下面的讨论区联系作者。
作者可能使用的许可证列表可以在此处找到。