C++语言·list链表(下)

还是之前说的，因为要写模板，为了避免链接出现问题，我们将所有内容都写到一个文件中去。首先就是画出链表的框架

链表本身只需要一个头节点就足以找到整条链表，而需要它拼接的节点我们再写一个模板。而我们知道list是一个带头双向循环链表，所以再写节点模板是时候将要表现出来双向，在写链表模板的时候要表现出带头和循环。

之所以要把ListNode设定成struct而不是class，因为再list中的成员函数中要反复访问节点中的成员变量，所以ListNode中的成员变量和成员函数都要设置成public公有的，所以干脆就直接写成struct了。

本节的重点也是难点就是链表的迭代器

1. 迭代器

构造析构还有那些接口我们已经熟的不能再熟了，之后再说，这里我们直接进入重点。

之前 string 和 vector 的迭代器我们都是直接 typdef 出来的，那list的迭代器可不可以也这样做。

答案当然是不行，前两者都是因为它们的存储空间是在物理上连续的，所以在 ++iterator的时候可以直接访问到下一块内存，显然链表是不行的，因此我们要给链表的迭代器特别写一个类出来，为了重载iterator的 ++iterator *iterator等行为

这里不建议把这个迭代器写成list的内部类，因为写成内部类之后迭代器不是list的友元啊，之后操作迭代器就会变得异常麻烦。

链表的迭代器我们选择用节点的指针。现在我们将迭代器的结构描绘出来，然后记得在list类中typedef一下，达到容器中迭代器的名称一致。

下面我们实现迭代器类，主要就是重载迭代器的几种操作方式

我们的迭代器是不去支持 + 或 - 的因为这个效率很低，就是在O(N)时间复杂度的遍历链表，拷贝构造，析构和赋值也都不需要写，让编译器自动生成浅拷贝就行，因为迭代器的目的是去访问节点，而不是去修改，也不要释放。当然，解引用访问到某个节点之后进行的修改不是说迭代器在修改节点数据，而是利用迭代器访问到了节点之后，在节点中修改它的数据。

其实迭代器这个东西就是一种封装，Node*指针无法直接完成下一块空间的访问，因此我们就将Node*封装到迭代器中，并且在迭代器中重载实现访问下一块空间的方法。

1.1 begin() end()

end()取出的迭代器就是那个头节点或者说哨兵位，因为迭代器都是左闭右开的嘛

1.2 const_iterator

因为迭代器跟指针的效果是类似的，const迭代器起到一个迭代器本身可以修改但是其指向内容不能修改的效果，所以const迭代器我们不能在iterator前面简单加一个const，而是要再写一个专门的ListConstIterator类。

这个类其实和普通的内容都基本一样，我们只需要在*运算符重载的函数前面加const限制返回值就好了。

不过我更推荐的是将const和非const的迭代器类用模板写在一起

在list类中实例迭代器的时候将它们区分开

那个Ptr模板是重载->操作符用的，具体内容可以到最后完整代码中查看

2. 构造析构赋值操作符重载

2.1 默认构造

默认构造就是建立出那个头节点，或者说哨兵位。

2.2 析构

我们先写一个清空容器的函数clear，析构就是把容器清空之后再把头节点哨兵位释放掉。

2.3 拷贝构造

2.4 赋值操作符重载

2.5 initializer_list构造

3. 插入与删除

3.1 随机位置插入

双向链表的插入逻辑我就不讲了，详见数据结构章节的链表讲解

数据结构·双向链表-CSDN博客文章浏览阅读1k次，点赞18次，收藏16次。本节讲解了双向链表的结构，以及实现了一个双向链表及功能，不得不说双向链表比单链表写起来简单多了，没有那么多繁琐的条件判断https://blog.csdn.net/atlanteep/article/details/135880386 这里要说的问题就是链表插入时的迭代器会不会失效，事实上是不会的，因为链表不涉及扩容和数据位置的挪动，所以在插入数据的时候迭代器是不会失效的。

但是在STL标准中，为了各个容器的一致，链表insert也会返回第一个新插入元素的迭代器

3.2 随机位置的删除

随机位置的删除我们要先断言一下，不能说把哨兵位都给删了。

删除节点是会造成迭代器失效的，STL标准中要返回被删除的最后一个元素之后那个元素的迭代器。

3.3 头插头删、尾插尾删

这个纯白给的，只不过注意一下尾删时，要删除哨兵位的前一个节点，而不是删end()位置的节点。

4. 完整代码

#include<assert.h>namespace atl
{template<class T>struct ListNode{ListNode<T>* _next;ListNode<T>* _prev;T _data;ListNode(const T& data = T()):_next(nullptr), _prev(nullptr), _data(data){}};template<class T,class Ref,class Ptr>struct ListIterator{typedef ListNode<T> Node;typedef ListIterator<T, Ref, Ptr> Self;Node* _node;ListIterator() = default;ListIterator(Node* node):_node(node){}//++iteratorSelf& operator++(){_node = _node->_next;return *this;}//iterator++Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}//--iteratorSelf& operator--(){_node = _node->_prev;return *this;}//iterator--Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}//*iteratorRef operator*(){return _node->_data;}//iterator->Ptr operator->(){return &_node->_data;}//iterator!=iteratorbool operator!=(const Self& it){return _node != it._node;}//iterator==iteratorbool operator==(const Self& it){return _node == it._node;}};template<class T>class list{typedef ListNode<T> Node;public://迭代器typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T*> const_iterator;iterator begin(){return iterator(_head->_next);}const_iterator begin() const{return const_iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator end()const{return const_iterator(_head);}//默认构造list(){_head = new Node();_head->_next = _head;_head->_prev = _head;}//析构void clear(){auto it = begin();while (it != end()){it = erase(it);}}~list(){clear();delete _head;_head = nullptr;}//拷贝构造list(const list<T>& lt){//创建头节点_head = new Node();_head->_next = _head;_head->_prev = _head;for (const auto& e : lt){push_back(e);}}//赋值操作符重载list<T>& operator=(list<T> lt){std::swap(_head, lt._head);return *this;}//initializer_list构造list(initializer_list<T> il){//创建头节点_head = new Node();_head->_next = _head;_head->_prev = _head;for (const auto& e : il){push_back(e);}}//没有迭代器失效//随机位置插入iterator insert(iterator pos,const T& x){Node* cur = pos._node;Node* newnode = new Node(x);newnode->_prev = cur->_prev;newnode->_next = cur;cur->_prev->_next = newnode;cur->_prev = newnode;return iterator(newnode);}//有迭代器失效//随机位置删除iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;//记录将要返回的迭代器iterator it((cur->_next));cur->_next->_prev = cur->_prev;cur->_prev->_next = cur->_next;delete cur;return it;}//尾插void push_back(const T& x){insert(end(), x);}//尾删void pop_back(){erase(--end());}//头插void push_front(const T& x){insert(begin(), x);}//头删void pop_front(){erase(begin());}private:Node* _head;};
}

C++语言·list链表(下)