如何在C++中实现双向链表迭代器的const兼容性

作者

在实现自定义双向链表（DoublyLinkedList）时，往往需要提供 iterator 与 const_iterator。如果仅仅复制一份代码来实现两者，会导致维护成本提高并且出现不一致的bug。下面给出一种简洁、可维护的实现方式，使得 iterator 与 const_iterator 在实现细节上共用代码，并保持 const 兼容。

1. 设计思路

  • 内部实现共享：让 iterator 与 const_iterator 共享一个内部实现类 IterImpl。
  • 使用指针类型别名：通过模板参数决定指针类型 (T* 或 const T*)。
  • 提供适配函数：在 iterator 的 operator*、operator-> 等中返回对应的引用或指针。
  • 保证 const‑安全：所有 const_iterator 的操作均返回 const T& 或 const T*。

2. 代码实现

#include <iostream>
#include <cassert>

template <typename T>
class DoublyLinkedList {
private:
    struct Node {
        T data;
        Node* prev;
        Node* next;
        Node(const T& v) : data(v), prev(nullptr), next(nullptr) {}
    };

    Node* head;
    Node* tail;
    size_t sz;

    /* 共享实现类 */
    template <typename U>
    struct IterImpl {
        Node* cur;

        IterImpl(Node* n = nullptr) : cur(n) {}

        // 前置递增
        IterImpl& operator++() {
            assert(cur && "Increment past end");
            cur = cur->next;
            return *this;
        }

        // 后置递增
        IterImpl operator++(int) {
            IterImpl tmp = *this;
            ++(*this);
            return tmp;
        }

        // 前置递减
        IterImpl& operator--() {
            assert(cur && "Decrement past begin");
            cur = cur->prev;
            return *this;
        }

        // 后置递减
        IterImpl operator--(int) {
            IterImpl tmp = *this;
            --(*this);
            return tmp;
        }

        // 相等比较
        bool operator==(const IterImpl& other) const {
            return cur == other.cur;
        }
        bool operator!=(const IterImpl& other) const {
            return !(*this == other);
        }
    };

public:
    using iterator = IterImpl <T>;
    using const_iterator = IterImpl<const T>;

    DoublyLinkedList() : head(nullptr), tail(nullptr), sz(0) {}
    ~DoublyLinkedList() { clear(); }

    size_t size() const { return sz; }

    void push_back(const T& value) {
        Node* n = new Node(value);
        if (!head) { head = tail = n; }
        else {
            tail->next = n;
            n->prev = tail;
            tail = n;
        }
        ++sz;
    }

    /* 返回 iterator */
    iterator begin() { return iterator(head); }
    iterator end() { return iterator(nullptr); }

    /* 返回 const_iterator */
    const_iterator begin() const { return const_iterator(head); }
    const_iterator end() const { return const_iterator(nullptr); }
    const_iterator cbegin() const { return const_iterator(head); }
    const_iterator cend() const { return const_iterator(nullptr); }

    /* 清空列表 */
    void clear() {
        Node* cur = head;
        while (cur) {
            Node* nxt = cur->next;
            delete cur;
            cur = nxt;
        }
        head = tail = nullptr;
        sz = 0;
    }
};

/* 测试代码 */
int main() {
    DoublyLinkedList <int> list;
    for (int i = 1; i <= 5; ++i) list.push_back(i);

    std::cout << "Non-const iteration: ";
    for (auto it = list.begin(); it != list.end(); ++it)
        std::cout << *it << ' ';
    std::cout << '\n';

    std::cout << "Const iteration: ";
    for (auto cit = list.cbegin(); cit != list.cend(); ++cit)
        std::cout << *cit << ' ';
    std::cout << '\n';

    /* 验证 const_iterator 不能修改元素 */
    // *list.begin() = 10;  // 编译错误
    return 0;
}

3. 关键点说明

  1. 共享实现：IterImpl 接受模板参数 U，如果 U 为 T，则返回 T&；如果为 const T，则返回 const T&。在 operator*、operator-> 的实现中，可以直接使用 U 类型。
  2. const 兼容：const_iterator 实际上只是 IterImpl<const T>，所有操作都保持 const。同时，iterator 也可以隐式转换为 const_iterator，符合 STL 习惯。
  3. 简洁维护：所有迭代器行为集中在 IterImpl，只需要改动一次即可影响两种迭代器。避免了代码重复。
  4. 安全性：使用 assert 保障 ++/-- 的边界检查。可根据需求改为异常抛出。

4. 进一步优化

  • 双向遍历：可以在 operator-- 里返回 *this 的引用。
  • 随机访问：如果需要支持 +、-，可以在 IterImpl 里实现相应运算符。
  • 性能：使用 std::unique_ptr 管理节点可避免手动 delete。

通过上述实现，C++ 双向链表的 iterator 与 const_iterator 既保持了 const‑安全，又避免了代码重复，是一个既简洁又易维护的设计范例。

发表评论