**如何在C++中实现双向链表的迭代器？**

作者

实现一个可与标准容器接口兼容的双向链表迭代器，是理解 STL 迭代器机制的关键练习。下面将从需求定义、设计原则、关键成员函数实现、异常安全以及性能细节几个方面，系统性地演示完整代码。

1. 需求与设计原则

  1. 满足标准迭代器要求

    • IteratorCategory: std::bidirectional_iterator_tag
    • 支持 ++, --, *, ->, ==, !=
    • 常量与非常量迭代器互相兼容

  2. 异常安全

    • 所有成员函数均不抛出异常，或抛出时保证不破坏对象状态

  3. 移动语义

    • 对 std::move 和 std::forward 友好，支持在 push_back/push_front 等操作中直接构造元素

  4. 可与标准算法配合

    • 通过 iterator_traits 能获得 difference_type、value_type 等信息

2. 双向链表基本节点与容器

template <typename T>
struct ListNode {
    T value;
    ListNode* prev;
    ListNode* next;

    ListNode(const T& v) : value(v), prev(nullptr), next(nullptr) {}
    ListNode(T&& v) : value(std::move(v)), prev(nullptr), next(nullptr) {}
};
template <typename T>
class List {
public:
    using node_ptr = ListNode <T>*;

    List() : head_(nullptr), tail_(nullptr), sz_(0) {}
    ~List() { clear(); }

    // 仅演示基本插入/删除与迭代器相关接口
    void push_back(const T& value);
    void push_back(T&& value);
    void pop_back();
    void clear();

    // 迭代器类型
    template <bool Const>
    class Iterator;

    using iterator       = Iterator <false>;
    using const_iterator = Iterator <true>;

    iterator begin() { return iterator(head_, this); }
    iterator end()   { return iterator(nullptr, this); }

    const_iterator begin() const { return const_iterator(head_, this); }
    const_iterator end()   const { return const_iterator(nullptr, this); }

    const_iterator cbegin() const { return const_iterator(head_, this); }
    const_iterator cend()   const { return const_iterator(nullptr, this); }

private:
    node_ptr head_;
    node_ptr tail_;
    std::size_t sz_;
};

3. 迭代器实现

我们用模板布尔参数 Const 来区分 const 与非 const 迭代器，内部通过 std::conditional_t 计算成员类型。 

template <typename T>
template <bool Const>
class List <T>::Iterator {
    using node_ptr = ListNode <T>*;
    using const_node_ptr = std::conditional_t<Const, const ListNode<T>*, ListNode<T>*>;

public:
    // 迭代器类型定义，满足 iterator_traits
    using iterator_category = std::bidirectional_iterator_tag;
    using value_type        = std::conditional_t<Const, const T, T>;
    using difference_type   = std::ptrdiff_t;
    using pointer           = std::conditional_t<Const, const T*, T*>;
    using reference         = std::conditional_t<Const, const T&, T&>;

    // 构造器
    Iterator(const_node_ptr node, const List <T>* parent) 
        : node_(const_cast <node_ptr>(node)), parent_(parent) {}

    // 拷贝/移动
    Iterator(const Iterator& other) noexcept = default;
    Iterator& operator=(const Iterator& other) noexcept = default;

    // 前置 ++/--
    Iterator& operator++() { node_ = node_->next; return *this; }
    Iterator& operator--() { 
        if (node_ == nullptr) node_ = parent_->tail_; // 退回到尾
        else node_ = node_->prev; 
        return *this; 
    }

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

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

    // 比较
    bool operator==(const Iterator& other) const noexcept {
        return node_ == other.node_;
    }
    bool operator!=(const Iterator& other) const noexcept {
        return node_ != other.node_;
    }

private:
    node_ptr node_;
    const List <T>* parent_;
};

关键点解析

  1. const 与非 const 的转换
    `Iterator

    ` 可以隐式转换为 `Iterator` 通过 `operator Iterator() const noexcept`（可自行添加）。这样 `std::copy` 等算法可以接受 const_iterator。

  2. --end() 的特殊处理
    当 node_ == nullptr（指向 end()）时，递减需跳转到 tail_，保证 --end() 成功。

  3. 异常安全
    所有成员函数不涉及任何可能抛出异常的操作，满足强异常安全。

4. 容器操作实现（示例）

template <typename T>
void List <T>::push_back(const T& value) {
    auto* n = new ListNode <T>(value);
    if (!tail_) { head_ = tail_ = n; }
    else { tail_->next = n; n->prev = tail_; tail_ = n; }
    ++sz_;
}

template <typename T>
void List <T>::push_back(T&& value) {
    auto* n = new ListNode <T>(std::move(value));
    if (!tail_) { head_ = tail_ = n; }
    else { tail_->next = n; n->prev = tail_; tail_ = n; }
    ++sz_;
}

template <typename T>
void List <T>::pop_back() {
    if (!tail_) return;
    node_ptr old = tail_;
    tail_ = tail_->prev;
    if (tail_) tail_->next = nullptr;
    else head_ = nullptr;
    delete old;
    --sz_;
}

template <typename T>
void List <T>::clear() {
    node_ptr cur = head_;
    while (cur) {
        node_ptr nxt = cur->next;
        delete cur;
        cur = nxt;
    }
    head_ = tail_ = nullptr;
    sz_ = 0;
}

5. 与标准算法配合的示例

List <int> lst;
for (int i = 0; i < 5; ++i) lst.push_back(i);

std::for_each(lst.begin(), lst.end(), [](int x){ std::cout << x << ' '; });
// 输出: 0 1 2 3 4 

// reverse
std::reverse(lst.begin(), lst.end());
for (auto v : lst) std::cout << v << ' ';  // 输出: 4 3 2 1 0

6. 性能与优化建议

  1. 节点分配

    • 采用对象池或 std::pmr::monotonic_buffer_resource 可以减少分配次数。

  2. 迭代器失效规则

    • 在插入/删除时，只会失效对应节点相关的迭代器，保持其余迭代器安全。

  3. 与 std::list 的对比

    • std::list 的节点结构包含 allocator_type，在高频插入/删除时会产生额外开销；我们的实现可按需加入自定义 allocator。

  4. 并发访问

    • 若需多线程读写，建议使用读写锁或采用 lock‑free 的链表实现。

7. 结语

通过上述步骤，我们完整实现了一个符合 STL 迭代器接口、具备异常安全与移动语义的双向链表迭代器。该实现既可作为教学案例，也能直接用于需要自定义链表结构的项目。希望本文能帮助你更深入地理解迭代器机制，并在实际编码中灵活运用。

发表评论