前文:List介绍
- list是可以在常数范围内在任意位置插入和删除的序列式容器，并且该容器可以前后双向迭代
- list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前面一个元素和后一个元素
- list与forward_list非常相似:最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效
- 与其他的序列式容器相比，list通常在任意位置进行插入，移除元素的执行效率更好
- 与其他序列式容器相比，list和forward_list最大的缺陷式不支持任意位置的随机访问。
在模拟实现list过程中，为了避免跟库中list发生冲突，需要创建个命名空间，在命名空间中实现list。
namespace ls { class list { }; }
list的底层是双向链表结构，而链表是通过每个独立的节点利用指针连接在一起的数据结构。节点是组成链表基本单位。模拟实现带头双向循环链表，为了适应不同的数据类型，选择采用类模板。
一、搭建创建List武器库
1.1 创建节点ListNode
template<class T> struct ListNode { ListNode<T>* _next; ListNode<T>* _prev; T _data; //创建节点，是传数据创建的 ListNode(const T& x = T()) :_next(nullptr) ,_prev(nullptr) ,_data(x) {} };
具体说明：为了适应不同类型的节点，将创建节点设计成类模板。访问限定符一般选用struct，由于默认访问权限是公开的，节点里面数据都是可以使用。当然使用class也是可以的，只需要将访问限定符设置为public。
节点对象实例化一般是传个数值，但是为了考虑类型和是否传参，可以设置一个全缺省构造函数
1.2 迭代器ListIterator
链表通过每个节点连接在一起，但这不能保证节点间地址是连续的。对此虽然原生指针是天然的迭代器，但是建立在物理空间连续的情况下
1.2.1 自定义类型迭代器
list<T> ::iterator it = lt.begin(); while (it != lt.end()) { *it += 10; cout << *it; it++; }
由于链表节点间物理空间不连续，使用原生指针作为迭代器不能满足++或–操作。节点间又是通过指针连接在一起的，那么可以将指针封装到类中，通过运算符重载重新定义运算符的行为，达成我们的需求。不采用内置类型迭代器，选择自定义类型迭代器，其中自定义类型迭代器内部是通过指针实现的。
template<class T> struct ListIterator { typedef ListNode<T> Node; typedef ListIterator<T> Self; Node* _node; ListIterator(Node* node) :_node(node) {} }
注意事项:
- 将通过
ListIterator类模板模拟实现迭代器，通过采用struct公开迭代器里面的数据ListIterator(Node* node)，这里迭代器的实现还是依赖指针，只是通过类封装改变运算符的行为，参数部分是传递指针类型（关键）- 其中迭代器是作为指向作用，申请资源不属于迭代器，而属于链表，不需要考虑析构的问题，迭代器就是玩数据
- 数据公开意味着，内部数据可以被任意修改。没人会去跳过封装，使用内部的数据，没有意义。不同编译器中底层实现是不一样的(实现逻辑、名称)，这本身就是一种隐式设置为私有的作用
1.2.2 交换语句
void swap(list<T>& it) { std::swap(_head, it._head); std::swap(_size, it._size); }
1.2.3 迭代器运算符重载
1.2.3.1 前置++与后置++
//前缀++ Self& operator++() { _node = _node->_next; return *this; } //后缀++ Self operator++(int) { //构造一个tmp临时变量 Self tmp(*this); _node = _node->_next; return tmp; }
1.2.3.2 前置–与后缀–
Self& operator--() { _node = _node->_prev; return *this; } //后缀-- Self operator--(int) { //构造一个tmp临时变量 Self tmp(*this); _node = _node->_prev; return tmp; }
具体说明:有拷贝构造就需要考虑深浅拷贝的问题。这里需要使用到浅拷贝，指向同一块空间，并且不需要考虑重复析构的问题，也说明了浅拷贝并都是坏处。临时对象tmp同指向一块空间，调用完临时对象被销毁，指向空间资源保留。这也导致了返回类型是指针还是引用。
1.2.3.4 *运算符重载
T& operator* () { return _node->_data; }
1.2.3.5 ==与!=运算符重载
//通过指针指向的节点去判断是否相等 bool operator==(const Self& it) { return _node == it._node; } bool operator!=(const Self& it) { return _node != it._node; }
具体说明：
- 关于形参部分使用
const修饰，其一为了提醒对象顺序问题，其二在while(it != lt.end())中lt.end()调用返回临时对象具有常性，在参数部分进行接收将权限降低。- 迭代器间的比较并不是比较指向数据，而是比较迭代器指向的位置
二、正式模拟实现List
2.1 武器库使用
前面知识是为了我们实现List提供武器库
template<class T> class list { typedef ListNode<T> Node; public: typedef ListIterator<T> Iterator; private: //创建哨兵位 Node* _head; size_t _size; };
武器使用:
- 关于
typedef ListNode Node与typedef ListIterator Iterator这两个类可以当作武器库，主要是为List类提供服务。那么对于ListIterator类来说ListNode Node也是当作一个武器进行使用。- 对于带头双向循环链表，成员对象需要哨兵位和记录个数对象。
2.2 获得List开头和结尾迭代器
Iterator begin() { //return Iterator(_head->_next); return _head->_next; } Iterator end() { //return Iterator(_head); return _head; }
具体说明:
- 由于正在使用自定义类型的迭代器，返回类型为Iterator自定义类型。返回类型可以写成Node*类型，单参数的拷贝构造函数支持隐式类型转换。
需要注意:
- 返回值没有传引用返回，由于该接口功能是返回开头和节点迭代器，如果传引用返回，会影响下一次调用该节点。我们不需要拿到这个位置的迭代器，只需要拿到这个位置的信息。
小插曲:隐式类型转换
list<int> :: Iterator it = (lt._head->_next);
由于_ head属于list类中的私有对象，不能直接的访问私有成员，通过公共接口访问。不同编译器底层实现是不同的，这也体现了封装的重要性。
2.3 关于迭代器失效
关于vector学习，我们知道在扩容或缩容的时候，可能会出现迭代器失效的问题。在list这里insert不会出现迭代器失效，但是erase就会出现迭代器失效。
关于解决不同编译器下erase导致迭代器失效的问题。方法有两个：迭代器失效以后，不要直接使用，如何要使用按照规则重新更新使用，返回被删除数据的迭代器。
2.4 insert
void insert(Iterator pos, const T& val) { Node* newnode = new Node(val); Node* cur = pos._node; Node* prev = cur->_prev; newnode->_next = cur; newnode-> _prev = prev; cur->_prev = newnode; prev->_next = newnode; _size++; }
这里跟数据结构实现双向链表任意位置插入数据的逻辑是一样的，不同的地方就是这里使用迭代器。
2.5 erase
//这些需要使用迭代器作为返回类型，怕出现迭代器失效 Iterator& erase(Iterator pos) { Node* cur = pos._node; Node* next = cur->_next; Node* prev = cur->_prev; delete cur; next->_prev = prev; prev->_next = next; _size--; //注意点 return Iterator(next); }
具体说明:这里跟数据结构实现双向链表任意位置删除数据的逻辑是一样的。
需要注意：返回类型需要使用迭代器类型，怕出现迭代器失效，返回下一个位置的迭代器
2.6 复用insert与erase完成插入与删除
void push_back(const T& val) { insert(end(), val); } void pop_back() { erase(--end()); } void push_front(const T& val) { insert(begin(), val); } void pop_front() { erase(begin()); }
具体说明：
- 在vector实现push_back和pop_back时，通过begin和end得到迭代器指向的位置。返回变量为具有常性的临时变量，不能通过++或–对其修改。
- 在List中迭代器可以进行++或–操作，由于不是对临时对象本身进行修改，而是在运算符重载中改变了运算符的行为，修改是临时对象指向的内容。在vector中修改是对象本身当然是不信的。
2.7 operator->重载
给出场景:关于之前类模板实例化中模板参数为内置类型，这次将T改为自定义类型，注意A是自定义类型。
struct A { int a1 = 0, a2 = 0; A(int a1,int a2) :a1(1) ,a2(2) {} }; list<A> lt; list<A> ::Iterator it = lt.begin(); lt.push_back(A(1,2)); lt.push_back({3,3}); while (it != lt.end()) { cout << *it; it++; }
在进行cout << *it中得到该类对象，并没有得到内部数据，对此有两个解决措施:
(*it).a1直接访问成员- 流插入的运算符重载
我们希望得到的效果是第二种写法，第一种感觉会冗余
- 第一种:(*it).a1
- 第二种:it->_a1
重点梳理:
//返回A类型对象指针，很合理啦 T* operator->() { return &_node->_data; }
【C++】C++ STL 探索：List使用与背后底层逻辑（二）https://developer.aliyun.com/article/1617349
