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 LinkListIte