使用 Functors 对 Composite 进行条件迭代

Dave Handley

4.47/5 (7投票s)

2004年10月8日

5分钟阅读

44002

543

使用 functor 在迭代复合对象时条件性地返回值。

引言

我之前已经写了两篇关于复合模式的文章。第一篇构建了一个基本的复合体，并介绍了各种遍历复合体层次结构的方法。第二篇文章展示了一种相对干净的方法来迭代复合体，仅提取特定类型的对象。本文将扩展我第二篇文章的概念，允许使用 functor 在迭代过程中选择要返回的对象。

背景

我关于复合模式的第一篇文章是 Composites and Visitors。这篇文章提供了一个通用的复合体，以及用于对复合体进行浅层和深度迭代的各种基本迭代器。它还涵盖了一些关于在复合体上定义访问序列的策略。

我关于复合模式的第二篇文章是关于创建新的浅层和深层迭代器，这些迭代器仅返回特定类型的对象。本文可以在以下位置找到：Typed Iteration over a Composite。

本文是我第二篇文章的泛化。提供浅层和深层迭代器，这些迭代器返回从函数对象或 functor 返回 true 的对象。首先要解决的明显问题是“什么是 functor？”。简单来说，functor 是一个包含重载函数调用运算符 operator() 的类。functor 可以像对象一样传递，但又可以像函数一样使用：因此得名函数对象。它们实际上是一种面向对象的方式，可以做一些类似于函数指针的事情，但具有语法极其简单的明显优势。我的基本函数对象声明在复合基类内部，主要是为了能够访问模板参数，尽管没有理由不能在单独的文件中声明它。

class base_functor
{
public:
    virtual ~base_functor() {}    // Force base functor to be virtual
    // Pure virtual operator() and Clone
    virtual bool operator()( const T* value ) const = 0;
    virtual base_functor *Clone() const = 0;
};

当你继承 base_functor 时，你必须声明重载的函数调用运算符，以及一个 Clone 函数。函数调用运算符将执行繁重的工作，而 Clone 函数是一些“管道”工作，用于确保迭代器在需要时可以复制 functor。

例如，我创建了 2 个 functor，它们都声明为我根复合节点内的内部类。第一个是一个简单的类型比较 functor，它镜像了我上一篇文章中呈现的功能。

template <typename T>
class CTypeComparisonFunctor : public base_functor
{
public:
    virtual bool operator()( const CNodeBase* value ) const
    {
        return dynamic_cast<const T*>( value ) != NULL;
    }
    virtual base_functor *Clone() const
    {
        return new CTypeComparisonFunctor<T>( *this );
    }
};

如你所见，函数调用运算符只是对传入的对象执行测试转换，以查看它是否是正确的类型，如果是，则返回 true。这个 functor 不携带状态，因此复制可以留给默认构造函数。

第二个示例展示了一个携带状态的基本 functor。你可以从 ID 构建这个 functor，它只会返回 ID 小于给定值的节点。

class CIDFilterFunctor : public base_functor
{
public:
    CIDFilterFunctor( unsigned long filter ) : m_filter( filter ) {}
    CIDFilterFunctor( const CIDFilterFunctor &src ) : m_filter( src.m_filter ) {}
    CIDFilterFunctor &operator=( const CIDFilterFunctor &src )
    {
        if ( this != &src )
            m_filter = src.m_filter;
        return *this;
    }
    virtual bool operator()( const CNodeBase* value ) const
    {
        return value->GetId() < m_filter;
    }
    virtual CIDFilterFunctor *Clone() const
    {
        return new CIDFilterFunctor( *this );
    }
private:
    unsigned long m_filter;
};

这种类型的 functor 是最有趣的。例如，你可以编写一个只返回用户编辑过的对象的 functor，或者只返回在过去一小时内创建的对象。它提供了一种从大型复合体层次结构中提取对象集的新颖方法。

还有一种替代方法可以执行类似的搜索，即使用 find_if STL 算法。我将在文章的后面演示这两种条件迭代的方法。正如你将看到的，我开发的条件迭代器方法具有稍简洁的语法，但代价是迭代器更大。find_if 方法的语法更复杂，但不需要任何额外的实现工作，并且迭代器更小。我将选择权留给你，但我建议如果你预计会大量使用条件迭代器，那么就编写它们，否则就坚持使用 STL 算法方法。使用条件迭代器还有一个最终优势。使用 find_if 方法，你没有 begin 和 end 迭代器，因此无法轻易地将结果馈送到其他 STL 算法。拥有一个真正的 begin 和 end 迭代器（尽管只是基本的前向迭代器）可以让你使用更广泛的 STL 算法。

使用代码

首先，我将向你展示实际迭代器的代码。

浅层迭代器

class functor_iterator
{
    friend class CGenericTree<T>;
public:
    // Normal constructors and destructors
    functor_iterator() : m_iterator(), m_end(), m_functor( NULL ) {}
    functor_iterator( const functor_iterator &src ) :
       m_iterator( src.m_iterator ), m_end( src.m_end ), 
       m_functor( src.m_functor->Clone() ) {}
    functor_iterator &operator=( const functor_iterator &rhs )
    {
        if ( this != &rhs )
        {
            m_iterator = rhs.m_iterator;
            m_end = rhs.m_end;
            m_functor = rhs.m_functor->Clone();
        }
        return *this;
    }
    ~functor_iterator()
    {
        if ( m_functor )
            delete m_functor;
    }
    // Equality operators
    bool operator==( const functor_iterator &rhs ) const
    {
        return m_iterator == rhs.m_iterator;
    }
    bool operator!=( const functor_iterator &rhs ) const
    {
        return m_iterator != rhs.m_iterator;
    }
    // Referencing operators
    _tptr& operator*()
    {
        return *m_iterator;
    }
    _tptr* operator->()
    {
        return &**this;
    }
    // Increment/decrement operators
    typename functor_iterator& operator++()
    {
        ++m_iterator;
        while ( m_iterator != m_end && m_functor && !(*m_functor)( *m_iterator ) )
            ++m_iterator;
        return *this;
    }
    typename functor_iterator operator++(int)
    {
        functor_iterator tmp = *this;
        ++*this;
        return tmp;
    }
private:
    // Private constructor off a container iterator
    explicit functor_iterator(
        const container_iterator &src,
        const container_iterator &end,
        const base_functor &functor ) :
        m_iterator( src ), m_end( end ), m_functor( functor.Clone() )
    {
        while ( m_iterator != m_end && m_functor && !(*m_functor )( *m_iterator ) )
            ++m_iterator;
    }
    // Internal storage is a normal iterator
    container_iterator m_iterator;
    container_iterator m_end;
    const base_functor *m_functor;
};
functor_iterator begin_functor( const base_functor &functor )
{
    return functor_iterator( m_children.begin(), m_children.end(), functor );
}
functor_iterator end_functor( const base_functor &functor )
{
    return functor_iterator( m_children.end(), m_children.end(), functor );
}

深层迭代器

class deep_functor_iterator
{
    friend class CGenericTree<T>;
public:
    // Normal constructors and destructors
    deep_functor_iterator() : m_iterator( NULL ), 
        m_end( NULL ), m_functor( NULL ) {}
    deep_functor_iterator( const deep_functor_iterator &src ) :
        m_iterator( src.m_iterator ), m_end( src.m_end ), 
        m_functor( src.m_functor->Clone() ) {}
    deep_functor_iterator &operator=( const deep_functor_iterator &rhs )
    {
        if ( this != &rhs )
        {
            m_iterator = rhs.m_iterator;
            m_end = rhs.m_end;
            m_functor = rhs.m_functor->Clone();
        }
        return *this;
    }
    ~deep_functor_iterator()
    {
        if ( m_functor )
            delete m_functor;
    }
    // Equality operators
    bool operator==( const deep_functor_iterator &rhs ) const
    {
        return m_iterator == rhs.m_iterator;
    }
    bool operator!=( const deep_functor_iterator &rhs ) const
    {
        return m_iterator != rhs.m_iterator;
    }
    // Referencing operators
    _tptr& operator*()
    {
        return m_iterator;
    }
    _tptr* operator->()
    {
        return &**this;
    }
    // Increment/decrement operators
    typename deep_functor_iterator& operator++()
    {
        increment();
        while ( m_iterator != m_end && m_functor && !(*m_functor)( m_iterator ) )
            increment();
        return *this;
    }
    typename deep_functor_iterator operator++(int)
    {
        deep_functor_iterator tmp = *this;
        ++*this;
        return tmp;
    }
private:
    // Private constructor off a container iterator
    explicit deep_functor_iterator( T *src, T *end, const base_functor &functor ) :
        m_iterator( src ), m_end( end ), m_functor( functor.Clone() )
    {
        while ( m_iterator != m_end && m_functor && !(*m_functor )( 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;
    const base_functor *m_functor;
};
deep_functor_iterator begin_deep_functor( const base_functor &functor )
{
    return deep_functor_iterator( static_cast<T*>(this), end_val(), functor );
}
deep_functor_iterator end_deep_functor( const base_functor &functor )
{
    return deep_functor_iterator( end_val(), end_val(), functor );
}

为了从 head 迭代整个树，只返回 ID 小于 6 的节点，你可以这样做：

CNodeBase::CIDFilterFunctor fun1( 6 );
CNodeBase::deep_functor_iterator iter_deep_functor = head->begin_deep_functor( fun1 );
for ( ; iter_deep_functor != head->end_deep_functor( fun1 ); ++iter_deep_functor )
    cout << (*iter_deep_functor)->GetId() 
         << " " << (*iter_deep_functor)->GetType() << endl;

使用 STL 算法执行类似操作：

CNodeBase::CIDFilterFunctor fun1( 6 );
CNodebase::deep_iterator iter = find_if( head->begin_deep(), head->end_deep(), fun1 );
for ( ; iter != head->end_deep(); iter = find_if( ++iter, head->end_deep(), fun1 ) )
    cout << (*iter)->GetId() << " " << (*iter)->GetType() << endl;

结论

复合体是一个非常强大的模式，可用于广泛的领域。通过在复合体中编写自定义迭代器，你可以极大地扩展该模式的威力。第一个也是最明显的迭代器实现是深层和浅层迭代器。它们分别迭代整个子树或对象下的单层子节点。可以使深层和浅层迭代器仅返回单个类型的对象。任何使用过复合模式的人可能都遇到过一个经典问题：不断需要执行类型转换才能获取对象，以便对派生类执行操作。使用类型化迭代将所有类型转换都放在基础迭代器中，从而消除了代码中的复杂性。

最后，这些概念可以扩展到允许迭代器接受 functor。functor 决定一个节点是否在特定迭代中返回。Functor 仅仅是具有重载函数调用运算符的类，这意味着它们同时充当对象和函数。使用基于 functor 的迭代器进行条件迭代是解决此问题的一种方法；然而，可以使用 find_if STL 算法解决相同的问题。两者在不同情况下都有其用途，并且由读者自行决定哪种更适合每种情况。

我希望通过过去三篇文章的介绍，我已经让你了解了复合模式的一些复杂性，并让你对自定义迭代器的强大功能有所了解。如果你对自定义迭代器有任何要求，请告诉我，我将考虑撰写一篇关于该主题的文章。

历史

2004 年 10 月 8 日：发布版本 1。