复合对象的类型化迭代

• 下载源文件 - 8.14 Kb
• 下载演示项目 - 51.9 Kb

引言

复合模式是一种非常强大的模式，它允许多态对象树了解其结构。为了使该模式成功，通常需要实现各种迭代器来遍历该层次结构。本文讨论了类型化迭代的问题。通过在前一篇文章的基础上进行开发，我构建了一组树迭代器，它们只返回特定类型的子节点。

背景

在之前一篇关于复合模式和访问者模式的文章中，我讨论了创建通用复合树并对该树应用不同访问策略的问题。在这两篇文章的第一篇中，我想讨论类型化迭代的问题。第二篇文章将把这个概念推广到使用函数对象来限制迭代返回的树节点。类型化迭代尤其有用，因为它处理了将条目向下转换为特定基类型。此外，由于迭代器本质上符合STL标准，因此可以根据需要将它们馈送到STL算法中。

复合模式经常用于表达式树或3D图形应用程序等领域。在图形应用程序中，场景信息通常存储在复合对象中。类型化迭代器允许您遍历场景层次结构，只提取材质节点或几何体节点。如果您正在运行一个将对所有几何体节点进行三角剖分的三角剖分访问者，这将特别有用。

使用代码

要理解如何使用复合树，您应该阅读我之前的文章。本质上，迭代器非常简单。与传统迭代器相比，主要的变化是在begin和operator++函数中，使用一个简单的while循环进行迭代，直到我们获得正确类型的条目。它们还必须检查以确保我们没有到达列表的末尾。我们不能依赖用户与end()进行比较，因为列表中的最后一项可能不是我们所需的类型；因此，迭代器必须携带end()的值。这有两个小缺点。第一个是迭代器的大小是传统迭代器的两倍。第二个是在迭代过程中列表增长，迭代器将失效。第二个问题与某些STL容器（如vector或关联容器）存在的问题相同。在代码展示中，我从类中剥离了许多无关的细节（如const版本），并稍作格式调整。如果您想查看完整的原始代码，请下载源代码。

浅层迭代器

template <typename T>
class CGenericTree
{
public:
    // Typed shallow iterator
    template <typename child>
    class typed_iterator
    {
        friend class CGenericTree<T>;
    public:
        // Normal constructors and destructors
        typed_iterator<child>() :
            m_iterator(),
            m_end() {}
        typed_iterator<child>( const typed_iterator<child> &src ) :
            m_iterator( src.m_iterator ),
            m_end( src.m_end ) {}
        typed_iterator<child> &operator=( const typed_iterator<child> &rhs )
        {
            if ( this != &rhs )
            {
                m_iterator = rhs.m_iterator;
                m_end = src.m_end;
            }
            return *this;
        }
        ~typed_iterator<child>() {}
        // Equality operator
        bool operator==( const typed_iterator<child> &rhs ) const
        {
            return m_iterator == rhs.m_iterator;
        }
        bool operator!=( const typed_iterator<child> &rhs ) const
        {
            return m_iterator != rhs.m_iterator;
        }
        // Referencing operators
        child* operator*()
        {
            return dynamic_cast<child*>( *m_iterator );
        }
        child** operator->()
        {
            return &**this;
        }
        // Increment/decrement operators
        typename typed_iterator<child>& operator++();
        typename typed_iterator<child> operator++(int)
        {
            typed_iterator<child> tmp = *this;
            ++*this;
            return tmp;
        }
    private:
        // Private constructor off a normal iterator
        explicit typed_iterator<child>( const container_iterator &iter,
            const container_iterator &end );
        // Internal storage is a normal iterator
        container_iterator m_iterator;
        container_iterator m_end;
    };
    template <typename child>
    typename typed_iterator<child> begin_typed()
    {
        return typed_iterator<child>( m_children.begin(), m_children.end() );
    }
    template <typename child>
    typename typed_iterator<child> end_typed()
    {
        return typed_iterator<child>( m_children.end(), m_children.end() );
    }
    // Rest of class definition
};

template <typename T>
template <typename child>
typename CGenericTree<T>::typed_iterator<child>&
CGenericTree<T>::typed_iterator<child>::operator++()
{
    ++m_iterator;
    // Now increment until we either get the correct type or reach the end
    while ( m_iterator != m_end && !dynamic_cast<child*>( *m_iterator ) )
        ++m_iterator;
    return *this;
}

template <typename T>
template <typename child>
CGenericTree<T>::typed_iterator<child>::typed_iterator(
    const container_iterator &iter, const container_iterator &end ) :
m_iterator( iter ),
m_end( end )
{
    // Now increment until we either get the correct type or reach the end
    while ( m_iterator != m_end && !dynamic_cast<CHILD*>( *m_iterator ) )
        ++m_iterator;
}

深层迭代器

template <typename T>
class CGenericTree
{
    // Typed deep iterator
    template <typename child>
    class typed_deep_iterator
    {
        friend class CGenericTree<T>;
    public:
        // Normal constructors and destructors
        typed_deep_iterator<child>() : m_iterator( NULL ), m_end( NULL ) {}
        typed_deep_iterator<child>( const typed_deep_iterator<child> &src ) :
            m_iterator( src.m_iterator ), m_end( src.m_end ) {}
        typed_deep_iterator<child> 
          &operator=( const typed_deep_iterator<child> &rhs )
        {
            if ( this != &rhs )
            {
                m_iterator = rhs.m_iterator;
                m_end = rhs.m_end;
            }
            return *this;
        }
        ~typed_deep_iterator<child>()
        {
            m_iterator = NULL;
            m_end = NULL;
        }
        // Equality operator
        bool operator==( const typed_deep_iterator<child> &rhs ) const
        {
            return m_iterator == rhs.m_iterator;
        }
        bool operator!=( const typed_deep_iterator<child> &rhs ) const
        {
            return m_iterator != rhs.m_iterator;
        }
        // Referencing operators
        child* operator*()
        {
            return dynamic_cast<child*>( m_iterator );
        }
        child** operator->()
        {
            return &**this;
        }
        // Increment operators
        typed_deep_iterator<child>& operator++()
        {
            increment();
            while( m_iterator != m_end && !dynamic_cast<child*>( m_iterator ) )
                increment();
            return *this;
        }
        typed_deep_iterator<child> operator++(int)
        {
            typed_deep_iterator tmp = *this;
            ++*this;
            return tmp;
        }
    private:
        // Private constructor off a pointer
        explicit typed_deep_iterator<child>( T *src, T *end ) :
            m_iterator( src ), m_end( end )
        {
            while ( m_iterator != m_end && !dynamic_cast<child*>( m_iterator ) )
                increment();
        }
        // Private increment operator
        void increment()
        {
            if ( m_iterator )
                m_iterator = m_iterator->GetNext();
        }
        // Internal storage is simply a pointer
        T* m_iterator;
        T* m_end;
    };
    template < typename child>
    typename typed_deep_iterator<child> begin_deep_typed()
    {
        return typed_deep_iterator<child>( static_cast<T*>(this), end_val() );
    }
    template <typename child>
    typename typed_deep_iterator<child> end_deep_typed()
    {
        return typed_deep_iterator<child>( end_val(), end_val() );
    }
    // Rest of class definition
};

这段代码演示了如何迭代节点head的子节点，只返回类型为CNodeDerived1的节点。

    CNodeBase::typed_iterator<CNodeDerived1> iter = 
                             head->begin_typed<CNodeDerived1>();
    for ( ; iter != head->end_typed<CNodeDerived1>(); ++iter )
        cout << (*iter)->GetId() << " " << (*iter)->GetType() << endl;

下一个示例执行相同的操作，但使用了深层迭代。

    CNodeBase::typed_deep_iterator<CNodeDerived1> iter = 
                         head->begin_deep_typed<CNodeDerived1>();
    for ( ; iter != head->end_deep_typed<CNodeDerived1>(); ++iter )
        cout << (*iter)->GetId() << " " << (*iter)->GetType() << endl;

关注点

有几点需要注意。第一点是模板中定义模板所需的语法。在我编写这个类的时候，这一点曾让我困惑。特别是，在类外部定义函数体时的语法。我特意在typed_iterator的类定义外部写了一些函数来演示这一点。请注意，您必须使用template <typename T>语法两次。一次用于外部类，一次用于内部类。一旦理解了这一点，其余的就会变得明朗。

第二点需要注意是使用成员函数模板来生成必要的begin和end函数，以便与类型化迭代器配合使用。这也有一些语法上的奇特之处，最值得注意的是，在使用时，您必须指定模板参数（这与其他大多数函数模板不同）。这是因为begin函数和end函数仅在返回类型上有所不同，因此编译器的静态多态无法解析正确的函数。在使用时，您将执行iter = begin<MyType>()。

更敏锐的读者会注意到，通过将基类型作为模板参数传入，类型化迭代器可以被用作标准的浅层或深层迭代器。乍一看，这似乎是一种浪费；然而，有一种方法可以使用显式模板实例化来更有效地实现这一点。除非有读者提出具体要求，否则我不会在此详细介绍。

历史

• 2004年10月6日：版本1发布。
• 2004年10月10日：版本2发布，以解决remove函数中的崩溃问题。