山东川畅科技联系 网站设计中国企业500强营业收入

一. list的结构

其实按照习惯来说，应该要专门出一篇博客来写

list的模拟实现，但是其实list与vector以及string的主要区别在于迭代器的设计。

所以就偷个懒直接写迭代器的部分了。

这里先声明以下，我这里就是进行一下模拟实现，STL中的list的iterator虽然并不是这样实现的，但是实现逻辑和结构都大差不差

这里就先贴上list类的结构：

namespace list
{template<class T>struct list_node{list_node<T>* _prev;list_node<T>* _next;T _val;//节点的构造函数list_node(const T& val = T()):_prev(nullptr), _next(nullptr), _val(val){}};template<class T>class list{public:list(){//链表的默认构造list_node<T>* head = new list_node<T>;//初始化哨兵位_head = head;_head->_next = _head;_head->_prev = _head;_size = 0;}~list(){}private:list_node<T>* _head;};
}

这个其实和我们之前写的双向带头循环链表一样。

二. 迭代器的区别

迭代器的区别，落到实质问题上
还是容器与容器的区别，也就是vector与list的区别

vector中的iterator是这样去实现的。

首先：

typedef T* iterator;

这里先重命名

iterator begin(){return _start;}iterator end(){return _finish;}

随后直接设计end与begin的函数。

之后就能发现，范围for与迭代器能直接进行使用了。

因为我们实现vector指针的方法是直接将内置类型指针进行改名。

而内置类型指针支持++，所以可以直接运行程序了。
但我们想想list肯定就不支持这样的操作了

vector能这这样，是因为数据存储在内存空间中连续时，正好可以进行使用。

但是list的问题是，内存空间是不连续的
这样的话再用指针内部支持的++算法就不太合适了。

所以我们今天就是为了来模拟实现list的迭代器的实现。

首先的目标就是实现下面这个代码的跑动。

	list::list<int>::iterator it = l1.begin();while (it != l1.end()){std::cout << *it;++it;}

三. 迭代器的实现

我们首先来看，我们最难解决的问题就是it的前置++
因为vector和list最重要的问题就是运算的方式不一样。

那我们想要用我们自己的方式进行++。
这个时候就应该想到了我们模拟实现类的时候最常用的东西：重载运算符

重载运算符在哪里能用：自定义类型
所以我们这个时候应该自然而然的想到自己写一个类，来充当iterator
从而实现我们想要的++方式。

i. 类的设计

    template<class T>struct __list_iterator{list_node<T>* _node;__list_iterator(list_node<T>* node):_node(node){}};

基本上大致结构是这样。

其中list_node就是双链表的节点结构。（上面写过）

这里添加个typedef

        template<class T>class list{public:typedef __list_iterator<T> iterator;

这个typedef和vefctor的使用没有什么大区别了。

现在来专注实现上面代码的所有的重载即可

ii. ++重载

  __list_iterator<T>& operator++(){_node = _node->_next;return *this;}

这个就是我们以前写的双链表和单链表的部分了。

iii. !=重载

 bool operator!=(const __list_iterator<T>& node){return _node != node._node;}

iiii. begin()

注意：这里的end和begin都是在list中的

因为迭代器执行时，会在list中寻找begin和end

 iterator begin(){return iterator(_head->_next);}

这里我们需要返回的是迭代器的类型

所以需要调用一下迭代器的构造函数

iiiii. end()

 iterator end(){return _head;}

我们发现begin需要调用构造函数

但是这边end却没有调用

因为单参数的构造函数返回时
如果返回的类型和需要返回的类型不同
就会主动调用需要返回类型的构造函数进行转换

iiiii. operator*

 T& operator*(){return _node->_val;}

四.测试

这里就直接写一个push_back的方法

  void push_back(const T& val){insert(end(), val);}void insert(iterator pos, const T& val){list_node<T>* new_node = new list_node<T>(val);_size++;pos._node->_prev->_next = new_node;new_node->_prev = pos._node->_prev;new_node->_next = pos._node;pos._node->_prev = new_node;}

接下来进行测试即可

	list::list<int> l1;l1.push_back(1);l1.push_back(1);l1.push_back(1);l1.push_back(1);l1.push_back(1);list::list<int>::iterator it = l1.begin();while (it != l1.end()){std::cout << *it;++it;}

这里能发现程序完美执行了。

五. const迭代器的实现

我们在使用STL中自带的迭代器时

应该经常能用到const迭代器。

const_iterator

这里我们首先要清楚const_iterator实现的是什么：

我们清楚效果是：指向的内容不能修改，但是迭代器本身可以修改。

所以实现的类型就是const T* ptr

而不是T* const ptr

那我们要达成这种效果。
可以从函数的返回值上入手

平常使用函数时，基本上都是通过重载符*
来进行对应值的修改

 const T& operator*(){return _node->_val;}

那我们这样不就可以了吗。。

i. 实现

typedef __list_iterator<T>const_iterator;

这里在list中重命名一下。

    template<class T>struct __list_const_iterator{list_node<T>* _node;__list_const_iterator(list_node<T>* node):_node(node){}const T& operator*(){return _node->_val;}__list_const_iterator<T>& operator++(){_node = _node->_next;return *this;}bool operator!=(const  __list_const_iterator<T>& node){return _node != node._node;}};

之后再把这个类丢进去。

但是这样会发现，实现的太过繁杂了。

这里就来个优化版本。

ii 优化实现

这里先直接上结果

list中的重命名：

 typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*>const_iterator;

具体实现：

    template<class T, class ref>struct __list_iterator{list_node<T>* _node;__list_iterator(list_node<T>* node):_node(node){}ref& operator*(){return _node->_val;}__list_iterator<T, ref, ptr>& operator++(){_node = _node->_next;return *this;}bool operator!=(const  __list_iterator<T, ref, ptr>& node){return _node != node._node;}};

这里是给模板新添加了一个参数。

从而实现const与普通的两种类型迭代器的实现。

六. 整体代码

//迭代器部分template<class T,class ref>struct __list_iterator{list_node<T>* _node;__list_iterator(list_node<T>* node):_node(node)ref& operator*(){return _node->_val;}__list_iterator<T,ref>& operator++(){_node = _node->_next;return *this;}__list_iterator<T, ref>& operator++(int){__list_iterator<T, ref>(*this);_node = _node->_next;return *this;}__list_iterator<T, ref>& operator--(){_node = _node->_prev;return *this;}__list_iterator<T, ref>& operator--(int){__list_iterator<T, ref>(*this);_node = _node->_prev;return *this;}bool operator!=(const  __list_iterator<T, ref>& node){return _node != node._node;}};

//list中的public命名部分
typedef __list_iterator<T,T&,T*> iterator;
typedef __list_iterator<T, const T&,const T*>const_iterator;