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);

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

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/552929.html

標籤：其他

上一篇：分享一下mybatisPlus新代碼生成器3.5.1以上

下一篇：返回列表