如何在C++中实现自定义迭代器以满足 STL 协议？

作者

在 C++ 标准库中，容器、算法以及其他工具都依赖于迭代器提供的一组通用操作。要让自定义容器与 STL 兼容，必须实现符合迭代器概念的接口。下面以双向迭代器为例，说明实现步骤、关键细节以及常见陷阱。

1. 迭代器概念回顾

STL 定义了若干个迭代器层级：

  • Input Iterator（单向读取）
  • Output Iterator（单向写入）
  • Forward Iterator（可多次遍历，单向）
  • Bidirectional Iterator（前后移动）
  • Random Access Iterator（支持算术运算）

每一层级都继承前一层级的接口。例如，双向迭代器必须满足所有前向迭代器的需求，并额外提供 -- 操作。

2. 关键类型别名

实现迭代器时，需要在类内部声明若干类型别名：

using iterator_category = std::bidirectional_iterator_tag; // 迭代器类别
using value_type        = T;                               // 元素类型
using difference_type   = std::ptrdiff_t;                  // 差值类型
using pointer           = T*;                              // 指向元素的指针
using reference         = T&;                              // 对元素的引用

这些别名使得 std::iterator_traits 能够从迭代器类型提取必要信息。

3. 基本操作符

下面给出一个最小实现，假设我们有一个简单的链表节点结构：

template<typename T>
struct Node {
    T data;
    Node* prev;
    Node* next;
};

迭代器类：

template<typename T>
class ListIterator {
public:
    using iterator_category = std::bidirectional_iterator_tag;
    using value_type        = T;
    using difference_type   = std::ptrdiff_t;
    using pointer           = T*;
    using reference         = T&;

    // 构造
    explicit ListIterator(Node <T>* ptr = nullptr) : cur(ptr) {}

    // 解引用
    reference operator*() const { return cur->data; }
    pointer   operator->() const { return &(cur->data); }

    // 前缀 ++ / --
    ListIterator& operator++() { cur = cur->next; return *this; }
    ListIterator& operator--() { cur = cur->prev; return *this; }

    // 后缀 ++ / --
    ListIterator operator++(int) { ListIterator tmp = *this; ++(*this); return tmp; }
    ListIterator operator--(int) { ListIterator tmp = *this; --(*this); return tmp; }

    // 等价
    bool operator==(const ListIterator& other) const { return cur == other.cur; }
    bool operator!=(const ListIterator& other) const { return cur != other.cur; }

private:
    Node <T>* cur;
};

4. 与容器配合

在自定义链表类中提供 begin()、end() 等成员函数：

template<typename T>
class MyList {
public:
    using iterator = ListIterator <T>;

    MyList() : head(nullptr), tail(nullptr) {}

    void push_back(const T& value) {
        Node <T>* n = new Node<T>{value, tail, nullptr};
        if (tail) tail->next = n; else head = n;
        tail = n;
    }

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

private:
    Node <T>* head;
    Node <T>* tail;
};

5. 典型错误与排查

常见错误 说明 解决办法
迭代器不提供 iterator_category std::iterator_traits 访问不到类别 按照上面示例添加别名
operator++ 只返回右值 前缀返回 void 必须返回 *this
operator* 返回副本 会导致修改无效 返回引用 (reference)
end() 返回非 nullptr 的指针 会导致无限循环 统一使用 nullptr 作为终止标识
迭代器与容器生命周期不匹配 容器被销毁后迭代器悬空 仅在容器存活期间使用迭代器

6. 进一步扩展

  • 随机访问迭代器：需要实现算术运算 (operator+, operator-, operator[]) 并维护内部索引或指针差值。
  • const_iterator：在 const 成员函数中返回不允许修改的迭代器。可以通过 std::add_const 生成对应类型。
  • 逆向迭代器：可以包装已有迭代器并反转前后移动逻辑。

7. 小结

实现自定义迭代器的核心是：

  1. 声明标准的类型别名，使 iterator_traits 正确工作。
  2. 实现所有必需的运算符（取决于所需的迭代器类别）。
  3. 确保容器与迭代器生命周期匹配，避免悬空引用。
  4. 进行充分测试：使用 STL 算法（如 std::for_each, std::find_if）验证兼容性。

只要按上述步骤细心实现，即可让自定义容器在 C++ 标准库生态中与现有算法无缝协作。

发表评论