C++ 如何快速实现一个容器的迭代器

引言

C++的标准库中的容器都会提供迭代器，如果一个容器满足forward_range，那么这个容器一般会提供以下成员类型和函数：

• iterator
• const_iterator
• begin
• end
• begin
• cend

如果该容器还满足bidirectional_range，那么该容器还会额外提供以下成员类型和函数：

• reversed_iterator
• const_reversed_iterator
• rbegin
• rend
• rcbegin
• rcend

笔者曾经在网上搜索过如何实现C++迭代器的文章，但是大多数文章都只是实现了一个最普通的迭代器，从学习原理的角度来说是非常好的，但是相比于标准库或者其他工业化的库来说可能是非常不完整的，所以笔者打算在本文中尽可能将容器中的迭代器部分完整地实现出来。

大多数人可能由于种种原因，C++的标准还停留在C++11，所以我们这里分别使用C++11和最新的标准来编写迭代器。

什么是迭代器

我们这里引用cppreference原话：

Iterators are a generalization of pointers that allow a C++ program to work with different data structures (for example, containers and ranges (since C++20)) in a uniform manner.

从定义不难看出，迭代器是一个泛化的指针。

指针

既然迭代器是泛化的指针，那么我们可以通过指针来了解迭代器。我们知道指针共有两个位置可以添加const关键字，共有4种可能，我们将他们对应到迭代器类型：

• iterator => T *
• const_iterator => const T *
• const iterator => T * const
• const const_iterator => const T * const

对于指针类型，const在前面表示说不可以通过该指针去修改所指的变量，而const在后面则表示该指针只能指向某个变量，不能修改指针本身，但是可以修改变量。我们在实现迭代器成员类型和函数的时候只需要关注前两者即可，后面的可以按照C++正常的写法来，可以加const的地方直接加上即可。

基于C++11的具体实现

由于我们的重点在于迭代器部分，所以我们尽可能地选取一个简单的数据结构来实现容器，这里我们实现一个双链表。同时我们也假设读者阅读过关于迭代器实现的文章，对迭代器的核心实现有一定的了解。

首先定义一下链表基本的实现：

template <typename T>
class LinkList {
    
    struct ListNodeBase {

        ListNodeBase* m_next;
        ListNodeBase* m_prev;

        ListNodeBase() { reset(); }

        void reset() { m_prev = m_next = this; }
    };

    struct ListNode : ListNodeBase {
        T m_value;
    };

    // 循环链表头结点，next指向第一个元素，prev指向最后一个元素
    ListNodeBase m_header;  
}

接下来是实现迭代器部分，对于很多容器来说，iterator和const_iterator是两个不同类，但是实际上这两个类里面的实现几乎是完全一样的，这也许很容易让人想到继承的写法，但是在C++中我们还有一个更好的方法，那就是使用模板，使用模板的代码量也许会少于使用继承。如果读者是一个非常排斥使用模板的人，不妨尝试着去接受一下，毕竟模板是C++中非常重要的一部分，同时作者也相信在注释和自身基本功到位的情况下，模板的编写和维护也不是非常困难的。

template <bool Const>
struct LinkListIterator {
    // ...
};

using iterator = LinkListIterator<false>