C++迭代器模式及其实现（非常详细）

迭代器模式（Iterator Pattern）提供一种统一的方式来遍历集合对象中的元素，而无须暴露集合的内部表示方式。该模式将遍历操作封装在一个独立的迭代器对象中，从而可以对集合进行迭代而不暴露其底层结构。

迭代器模式的角色组成包括抽象迭代器（Iterator）和具体迭代器（Concrete Iterator）。抽象迭代器定义了遍历聚合对象所需的方法，例如 hasNext() 和 next() 方法等。具体迭代器则是实现迭代器接口的具体实现类，负责具体的遍历逻辑，保存当前遍历的位置信息，并可以根据需要向前或向后遍历集合元素。

迭代器模式的本质是控制访问聚合对象中的元素。通过封装、隔离和统一接口，迭代器模式实现了对集合的遍历行为的灵活性和扩展性。它使客户端代码与具体集合解耦，提高了代码的可维护性和可复用性。

在 C++11 标准库中提供了一个通用的模板类 std::iterator，它提供了一种通用的迭代器定义方式。通过继承 std::iterator，可以方便地定义自己的迭代器类型以满足特定容器的遍历需求，并且以此实现的迭代器可以和 STL 中提供的算法相互配合。

考虑到 C++11 标准库中提供了对应功能，本文不对迭代器模式以新的方式进行实现。下面给出一个使用 std::iterator 实现的迭代器示例。

avlIterator 是平衡二叉树（AVL）容器的迭代器模块。迭代器从 std::iterator 继承，内部维护了 AVL 节点的指针 p_node__，以及一个用于循环遍历处理的栈 m_stack__，代码如下：

//container/avl.hpp

class avlIterator:public std::iterator<std::forward_iterator_tag,node_t >
{
friend class avl;
private:
    node_t      *p_node__;
    std::stack< node_t * > m_stack__;
public:
    avlIterator__(node_t * node):p_node__(node){}
    avlIterator__(const avlIterator__&b):
      p_node__(b.p_node__),m_stack__(b.m_stack__){}

在模块中需要针对 ++ 操作符进行重载，满足迭代器的 ++ 操作。重载方法的内部实际使用树的遍历操作，每次执行一个节点的变动，将中间的状态通过 m_stack__ 进行维护。当前的节点保存 p_node__，代码如下：

// container/avl.hpp
    avlIterator& operator++()
    {
        node_t* top = nullptr;
        if (m_stack__.size() > 0) {
            top = m_stack__.back();
            // 优先访问左子树
            if ((top == nullptr) ||
                (top != nullptr &&
                 top->p_left != p_node__ &&
                 top->p_right != p_node__ && p_node__->p_left != nullptr)) {
                m_stack__.push_back(p_node__);
                p_node__ = p_node__->p_left;
                return *this;
            }
            // 访问右子树
            if (top != nullptr &&
                top->p_right != p_node__ && p_node__->p_right != nullptr) {
                m_stack__.push_back(p_node__);
                p_node__ = p_node__->p_right;
                return *this;
            }
            p_node__ = top;
            m_stack__.pop_back();
        }

        if (m_stack__.size() > 0) {
            // 递归调用以弹出栈顶
            return operator++();
        } else {
            // 满足 end() 条件
            p_node__ = nullptr;
            return *this;
        }
    }

    avlIterator operator++(int)
    {
        avlIterator tmp(*this);
        operator++();
        return tmp;
    }

    bool operator==(const avlIterator& b) const
    {
        return p_node__ == b.p_node__;
    }

    bool operator!=(const avlIterator& b) const
    {
        return p_node__ != b.p_node__;
    }

针对 * 和 -> 操作进行重载，实现迭代器的解引用和指针操作，代码如下：

    value_type&operator * (){return p_node__->m_data;}
    value_type * operator->(){return&p_node__->m_data;}
};

通过以上方式就可完成迭代器的实现，在AVL容器中增加两种方法 begin 和 end，用于获取迭代器的开始和终止位置。对于 AVL 方法的实现，代码如下：

iterator begin(){return iterator(proot);}
iterator end(){return iterator(nullptr);}

C++迭代器模式及其实现（非常详细）

相关文章