# C++ 如何快速實現一個容器的迭代器 ## 引言 C++的標準庫中的容器都會提供迭代器，如果一個容器滿足forward_range，那麼這個容器一般會提供以下成員類型和函數： - iterator - const_iterator - begin - end - begin - cend 如果該 ...

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>;
using const_iterator = LinkListIterator<true>;

我們使用一個bool類型的變數（Const）來讓LinkListIterator在二者之間進行切換，當該變數為true時，他是const_iterator，否則是iterator。

迭代器一般會定義以下成員類型：

value_type
reference
pointer
difference_type
iterator_category

value_type在容器的迭代器中一般是當前容器元素的類型。
reference在容器的迭代器中一般是當前容器元素的引用類型。
pointer在容器的迭代器中一般是當前容器元素的指針類型，C++20之後無需定義。
difference_type表示兩個迭代器距離的類型，在容器中一般是ptrdiff_t。
iterator_category表示該迭代器的種類。

需要註意的是，容器中的迭代器並不能夠代表所有的情況，比如迭代器reference並不一定是引用類型，iterator_category也僅僅只是一個必要條件。

using value_type = typename std::conditional<Const, const T, T>::type;
using reference = value_type&;
using pointer = value_type*;   
using difference_type = std::ptrdiff_t;
using iterator_category = std::bidirectional_iterator_tag;

然後是定義構造函數：

node_type* m_ptr;

LinkListIterator() = default;

LinkListIterator(const LinkListIterator&) = default;

LinkListIterator(node_type* ptr) : m_ptr(ptr) { }

// 我們可以使用一個int* 來初始化一個const int*
// 同理，我們可以使用iterator來初始化一個const_iterator
template <bool IsConst, typename = typename std::enable_if<(Const && !IsConst)>::type>
LinkListIterator(const LinkListIterator<IsConst>& other) 
    : m_ptr(other.m_ptr) { }

C++迭代器的操作一般是基於運算符的，所以我們需要對相應的運算符進行重載。bidirectional_iterator需要重載以下操作符。

// C++11
bool operator==(const LinkListIterator& other) const {
    return m_ptr == other.m_ptr;
}

bool operator!=(const LinkListIterator& other) const {
    return !this->operator==(other);
}

reference operator*() const { return m_ptr->m_value; }

pointer operator->() const { return &this->operator*(); }

LinkListIterator& operator++() {
    m_ptr = m_ptr->m_next;
    return *this;
}

// it++
LinkListIterator operator++(int) {
    auto old = *this;
    ++*this;
    return old;
}

// --it
LinkListIterator& operator--() {
    m_ptr = m_ptr->m_prev;
    return *this;
}

// it--
LinkListIterator operator--(int) {
    auto old = *this;
    --*this;
    return old;
}

到此為止，一個雙鏈表的迭代器就全部實現完畢了，至於reversed_iterator，標準庫為我們提供了std::reverse_iterator，我們只需要將我們的迭代器傳給它即可。

using iterator = LinkListIterator<false>;
using const_iterator = LinkListIterator<true>;
using reverse_iterator = std::reverse_iterator<iterator>;
using const_reverse_iterator = std::reverse_iterator<const_iterator>;

最後我們提供一下相關的成員函數：

iterator begin() { return m_header.m_next; }
iterator end() { return &m_header; }

const_iterator begin() const { return const_cast<LinkList&>(*this).begin(); }
const_iterator end() const { return const_cast<LinkList&>(*this).end(); }

const_iterator cbegin() const { return begin(); }
const_iterator cend() const { return end(); }

reverse_iterator rbegin() { return end(); }
reverse_iterator rend() { return begin(); }

const_reverse_iterator rbegin() const { return end(); }
const_reverse_iterator rend() const { return begin(); }

const_reverse_iterator rcbegin() const { return end(); }
const_reverse_iterator rcend() const { return begin(); }

由於const版本的重載實現和non-const版本是完全一致的，並且我們也提供了構造函數使得iterator可以轉化為const_iterator，所以我們直接使用const_cast實現了const版本的重載。

基於C++23的具體實現

隨著技術的不斷進步，很多時候我們不必再使用以往繁瑣的方式來實現我們想要的東西。既然reverse_iterator可以直接使用標準庫的組件完成，那麼const_iterator是否也可以使用類似的方法來實現呢？畢竟看起來我們只需要對iterator進行簡單封裝就可以把它變成一個const_iterator。

答案是肯定的，那就是std::const_iterator。當然這個東西涉及的細節還是非常多的，不是看起來那麼簡單，讀者有興趣的話可以自行閱讀相關文獻。

我們來嘗試簡化一下上述代碼：

// template <bool Const>
struct LinkListIterator {
    using value_type = T;
    using reference = value_type&;
    // using pointer = value_type*;
    using difference_type = ptrdiff_t;
    using iterator_category = std::bidirectional_iterator_tag;

    // 我們可以使用一個int* 來初始化一個const int*
    // 同理，我們可以使用iterator來初始化一個const_iterator
    // template <bool IsConst, typename = typename std::enable_if<(Const && !IsConst)>::type>
    // LinkListIterator(const LinkListIterator<IsConst>& other) 
    //     : m_ptr(other.m_ptr) { }

};

using iterator = LinkListIterator;
using const_iterator = std::const_iterator<iterator>;
using reverse_iterator = std::reverse_iterator<iterator>;
using const_reverse_iterator = std::reverse_iterator<const_iterator>;

我們只需要實現一個普通的iterator即可，因為標準庫已經為我們提供了新的組件，同時額外的構造函數也自然不再需要。

pointer這一成員類型也是不必要的，std::iterator_traits會自動幫我們推導。沒有pointer之後我們可以直接使用auto來完成->運算符重載。

auto operator->() const { return &this->operator*(); }

同時對於==這一運算符，許多實現無非就是簡單比較每一個成員欄位是否相等，而!=等於運算符往往也是等價於==運算結果取反。

bool operator==(const LinkListIterator& other) const = default;

// 不寫則自動生成
// bool operator!=(const LinkListIterator& other) const { ... }

預設生成的==運算符的，有如下規則：

A class can define operator== as defaulted, with a return value of bool. This will generate an equality comparison of each base class and member subobject, in their declaration order. Two objects are equal if the values of their base classes and members are equal. The test will short-circuit if an inequality is found in members or base classes earlier in declaration order.

需要註意的是，數組類型的比較是按照range的規則來的，即比較數組中每一個元素是否相等，而非將數組看成一個指針進行比較：

struct F
{
    int data[2];
    constexpr F(int a, int b) : data{a, b} { }
    constexpr bool operator==(const F&) const = default;
};

constexpr F f1(1, 2), f2(3, 4), f3(1, 2);

static_assert(f1 != f2);
static_assert(f1 == f3);

我們的簡化過程到此為止就結束了，剩下的部分保持不變即可。關於簡化之後的代碼，讀者可以點擊這裡獲取。