C++——list(2)

作者：几冬雪来

时间：2023年9月28日

内容：C++——list内容讲解

前言：

list的const迭代器：

const的iterator：

const迭代器：

operator->:

拷贝构造：

迭代器接口补充：

代码：

结尾：

前言：

在上一篇博客中我们讲解了list的新接口，list与vector，string的区别所在。更加进一步的说明了list的迭代器的书写，而在今天我们将借由list迭代器来对list的const迭代器进行详细的讲解与说明。

list的const迭代器：

在学习list的const迭代器之前，我们先来回顾一下list的迭代器。

list，string和vector的迭代器访问的是指针，所以所有的容器都希望提供像指针一样去访问容器的方式。

在string和vector只需要提供原生指针即可。

string和vector使用的原生指针，在这里typedef T*就是iterator，因为普通的指针完美的符合这个行为。

并且string和vector的物理空间是连续的。

因此它的解引用访问的就是该处的数据，进行++就是访问下一个数据。

const的iterator：

那么在这里，const的iterator是什么，它使用的指针和vector，string有什么不同？

相较于二者，const的iterator有所不同。

在const的使用中分为两种，一种是指针不能被修改，另外一种是指向的内容不能被修改。

像上图在*之前的const修饰的都是指向的内容不能被修改，都是它自己是可以被修改的。所以的迭代器都要符合。

string和vector的不同是因为二者的底层结构占了便宜，因为它们的空间是连续的，而list则是不连续的。

const迭代器：

在list中因为空间是不连续的，因此它的指针不能直接使用。这个时候就要借助一个类来封装，来控制它的行为。

那么如果控制它的行为呢？我们可以重载它的operator*和operator++，这样就能控制它这里的行为。

在这里我们就将封装的迭代器类型进行一个typedef来达到我们的目标。

接下来我们进行讲解const迭代器，这里我们要使用的const是指向的内容不能被修改，而它自己本身是可以被修改的。

这个地方很多人都会这样去写。

在普通迭代器的对象前加上一个const，这里的const影响的是我们的对象，对象不能被修改。因此在后面运行代码的时候就不能调++等操作。

既然这条路走不通，那么我们该如何实现呢？这个地方就需要去控制operator*来达到这个目的。

为了解决问题，在定义处我们又定义了一个新的类，这个新的类和原先的类基本一致。唯一有不同的点就是在operator*处。

那么是哪个地方不同，我们就来对比一下。

对比两个类中的operator*，我们不难看出二者的返回值不一样，新的类对比原先的类，在返回值处多了一个const。

但是如果真的要这样写的话，那就太冗余了。

这里有没有什么好办法呢？是有的，在这里我们可以通过一个类型去控制这个返回值，也就是增加一个模板参数。

类似这里，我们就添加了一个模板参数，同时将operator*的返回值更改为Ref。那么这里的Ref是什么呢？

从上面的类模板中我们是不知道的，这个时候就要看下面的iterator的书写了。

在这个地方普通的iterator的Ref代表的是T引用，而const iterator在这个地方则是代表的const T引用。

这也就完成了想要的通过一个类模板给不同的实例化，其实这里本质上我们还是写了两个类，因为我们给了不同的模板参数。

同时因为是不同的类，因此原先的类就不能使用了，在这个地方就需要我们对新的类进行typedef一下。

这里将新的类typedef为self，同时在下面operator++和operator*等涉及到这个返回值的都要对其进行修改。

operator->:

接下来来讲解一下list中的operator->接口。

这个地方有人就要问了，在我们还在学C语言的时候不是有讲解过->和&之间的关系，虽然书写的代码不同，但是结果是相同的。

在list迭代器中刚刚书写了解引用的操作，为什么还要加入->？

为了解答问题，在这里我们写了一个链表，链表的类型是自定义类型。然后接下来我们要对类型进行访问。

然后来看一下访问的代码。

在这里我们迭代器模拟的是一个指向结构的指针。

因为上面迭代器的类型是自定义类型，因此这个地方数据模拟的就是自定义类型的指针。所以代码就要用到->了。

因此上面的这一串代码就能改编为下面这样。

而因为在这里使用了->，所以在迭代器中我们要加入operator->来辅助我们完成。

那么再将它的代码写出来。

先比较与我们operator解引用时候书写的代码，operator->明显有着不同之处。首先是返回值，解引用的返回值是Ref，而->的返回值是T*。

同时二者return的内容也是不同，->与解引用相比多了一个&符号。

这两种情况就导致了operator->的返回值略显奇怪。

根据上图进行解释。

在operator*和operator->处return的_node->_val的值都是我们这里自定义类型A。但是因为返回值的不同，解引用的代码可以装换为对A的解引用，然后就能访问它里面的值。

可operator->不同，它的返回值是T*转换的结果是A*也就是A的指针，而我们没办法通过A*去访问A里面的值。

因此理论上来说正确的代码应该这样写。

这个地方需要两个->才能真正访问我们里面的数据，第一个->是去调用operator->返回的是A*，然后第二个->就是去访问A里面的值。

但是如果是这样书写的话，可读性极差。而我们的运算符重载正好要求可读性，那么编译器就进行了一个特殊处理，在这里省略了一个->。

那么接下来一个问题就是它的const该怎么写，案例来说这里的返回值是const T*。

解决这个问题的话，我们可以新增加一个模板参数来区分它们。

拷贝构造：

接下来我们来讲解list的拷贝构造。

通过两篇博客我们可以发现list的迭代器和vector与string多多少少有些不同，但是它们有一点是相同的，那就是在拷贝构造的时候都会出现深浅拷贝的问题。

为了处理深浅拷贝的问题，在这个地方如果要将lt1给lt2，首先就要开空间，给出各个指向的是什么。

开好空间之后，接下来就要遍历数据了。在这个地方有一个要注意的点，那就是正常情况下因为不清楚T的对象不确定是vector，string还是其他的，因此在遍历条件处要加引用操作符。

最后再将lt1里面的数据插入到lt2，这样就能完成我们的深拷贝了。

同样的我们也可以对我们的代码进行优化。

因为在list迭代器中多次运用到开空间的操作，因此我们可以将它单独拿出来写一个接口，方便以后的调用。

迭代器接口补充：

再在最后，将我们平时迭代器用到的代码，比如erase，insert等等都写上，到这里我们的迭代器就正式完成了。

代码：

using namespace std;
#include<>
#pragma once  
#include<assert.h>namespace bit
{template<class T>struct list_node{list_node<T>* _next;list_node<T>* _prev;T _val;list_node(const T& val = T()):_next(nullptr),_prev(nullptr),_val(val){}}; template<class T,class Ref,class Ptr>struct __list_iterator{typedef list_node<T> Node;typedef __list_iterator<T, Ref> self; Node* _node;__list_iterator(Node* _node):_node(node){}   iterator begin(){return _head->_next;}iterator end(){return _head;}Ref operator*(){return _node->_val;}self& operator++(){_node = _node->_next;return *this;}Ptr operator->(){return &_node->_val;}self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}self& operator--(){_node = _node->_prev;return *this;}self operator==(int){self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const Ref& it){return _node != it._node;}bool operator==(const Ref& it){return _node == it._node;}};template<class T>class list{typedef list_node<T> Node;public:typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T,const T&, const T*> const_iterator;/*typedef const __list_iterator<T> const_iterator;*/list(){empty_init()}~list(){clear();delete _head;_head = nullptr;}void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;}list(const list<T>& lt){empty_init();for (auto& e : lt){push_back(e);}}void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}list<T>& operator=(list<T> lt){swap(lt); return *this;}void clear(){ iterator it = begin();while (it != end()){it = erase(it);}}void push_back(const T& x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(--end());}void pop_front(){erase(begin()); }iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);prev->_next = newnode;newnode->_next = cur;cur->_prev = newnode;newnode->_prev = prev; return newnode;}iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;return next;}private:Node* _head;};}