list的介绍及使用（了解，后边细讲）
1.1 list的介绍（双向循环链表）
https://cplusplus.com/reference/list/list/?kw=list（list文档介绍）
1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
1.2 list的使用（可以对照模拟实现看，重要的都有，后边模拟实现都会讲）
list中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，已达到可扩展的能力。以下为list中一些常见的重要接口。
1.2.1 list的构造
1.2.2 list iterator的使用
此处，大家可暂时将迭代器理解成一个指针，该指针指向list中的某个节点。
【注意】
1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
2. rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动
1.2.3 list capacity
1.2.4 list element access
1.2.5 list modifiers
list中还有一些操作，需要用到时大家可参阅list的文档说明。
list的迭代器失效
注意，insert不会失效，迭代器依旧指向原来位置，erase会失效（删除后返回下一个地址），跟vector的迭代器失效类比，都是因为没有接收删除后的迭代器。insert不会失效，因为插入后返回新的节点地址，本身就指向新节点，不会失效
错误代码：
void TestListIterator1() { int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }; list<int> l(array, array+sizeof(array)/sizeof(array[0])); auto it = l.begin(); while (it != l.end()) { // erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给 其赋值 l.erase(it); ++it; } }改正后：
// 改正 void TestListIterator() { int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }; list<int> l(array, array+sizeof(array)/sizeof(array[0])); auto it = l.begin(); while (it != l.end()) { l.erase(it++); // it = l.erase(it);两种写法都对 } }
list的反向迭代器
ReverseIterator.h
template<class Iterator,class Ref,class Ptr> struct ReverseIterator { typedef ReverseIterator<Iterator, Ref, Ptr> Self; Iterator cur; ReverseIterator(Iterator it) :cur(it) { } Self& operator++() { --cur; return *this; } Ref operator*() { Iterator tmp = cur; --tmp; return *tmp; } Ptr operator->() { return &(operator*()); } bool operator!=(const Self& s) { return cur != s.cur; } };List.h
在list类内部多了一些改动，将反向迭代器的类重命名，并且新加两个成员函数
test.cpp
#define _CRT_SECURE_NO_WARNINGS 1 #include<iostream> #include<list> using namespace std; #include"List.h" int main() { jzy::list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); jzy::list<int>::reverse_iterator rit = lt.rbegin(); while (rit != lt.rend()) { cout << *rit << " "; ++rit; } cout << endl; return 0; }
可以看到反向迭代器起了作用，下面我来讲解反向迭代器的原理
反向迭代器可以理解成封装了正向迭代器，正向迭代器又封装了原生指针，反向迭代器++等价于正向迭代器--，反向迭代器解引用相当于正向迭代器--再解引用
因为反向迭代器的开始是正向迭代器结束位置，结束是正向的开始，所以反向迭代器要先--在解引用才是正确的值
反向迭代器的->也就是*拿到存放的值再取地址，和之前讲的是一个道理
typedef ReverseIterator<iterator, T&, T*> reverse_iterator; //typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator; reverse_iterator rbegin() { return reverse_iterator(end()); } reverse_iterator rend() { return reverse_iterator(begin()); }
反向迭代器在list类那里要多加一些东西，重命名反向迭代器这个类，当是普通反向迭代器的时候实例化iterator，T&,T*，当是const反向迭代器的时候，实例化参数是const_iterator,const T&,const T*
总体来讲，可以把反向迭代器看成适配器，当实例化参数是普通迭代器，会按照普通迭代器的行为进行操作，当参数是const时，会调用const的操作
list与vector的对比
vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同，其主要不同如下：
list模拟实现讲解（超详细）
定义结点结构体，结构体成员是前仆后继指针和元素data，还要写一个构造函数用来初始化结点
迭代器封装为一个类，类定义的对象存放每个节点的地址，也就是_node，相当于迭代器指针被封装成了一个类里存放，typedef是将类型重命名，将长的类型重命名为短的，记住类名不是类型，类名<类型>才是类型
这里模版有三个参数，第一个T是实例化类型，第二个和第三个参数是为了*和->，const类型会匹配T,constT& ,constT* ，正常类型会匹配T,T&,T*
这里将原生指针封装了一层包装在一个类里边，类定义的对象会通过操作指针前后移动来操作结点，解引用拿到对应结点的值，或者->拿到对应的地址
迭代器构造函数，当返回值是iterator类型时，会构造一个临时对象来操作
迭代器++，--，和日期类的原理类似，++it是当前指针往后走一步，this是it的地址，然后返回++之后的值，后置++，参数多传一个int就行，构造一个局部对象，指针向后走一步，返回走之前的值，迭代器--和++同理，无非是向前走
operator*是（*it）相当于拿到对应的值，我们就把it当成指针，*it当成解引用地址即可，这里是把指针封装到类里边，和前边string和vector的指针有所区分；->箭头相当于拿到存放对象的地址，当在list内部存放结构体时会用到
最简单的两个运算符重载，当判断不等于的时候会用到
list类要把上边两个类typedef后的类型写上去，方便等会用
迭代器的重载，当我们用begin（）或者end（）的时候，会调用这四个重载，普通对象调用普通迭代器，返回普通可修改指向对象的迭代器（这个对象可以用类名（），也可以直接返回Node*的结点指针（单参数的构造函数支持隐式类型转换），这两个写法都会生成一个临时对象，然后进行使用），const类型调用const迭代器，返回const不可修改指向对象的迭代器（慢慢理解这部分，其实没有想象的那么难）
list类的私有成员是_head，充当一个指针用来声明第一个哨兵位头结点
默认构造是初始化一个哨兵位头结点，结点内部存放前仆后继指针和data值（是某个类型的默认构造），然后让_head指向第一个哨兵位结点，并且_next和_prev都指向自己，完成哨兵位结点的初始化
析构函数先用clear清理，删除除了哨兵位结点的剩余存放有效数据的结点（释放了空间），最后释放哨兵位结点空间，_head置空就OK
拷贝构造，先初始化一个哨兵位结点，然后将要构造的对象内容依次给给e，尾插到新对象后边
赋值拷贝，先拷贝构造一个lt，将lt和新对象交换，lt是局部对象，出作用域会调用析构函数，新对象引用返回，完成赋值拷贝
insert插入，参数是迭代器指针（生成临时对象+2次拷贝构造）和要插入的值，cur指向要插入位置，prev存放要插入位置前边的指针，new一个新节点是要插入的新结点
三个指针相对位置是这样的，一般都是在某个位置之前插入，所以是这样的关系，然后按顺序链接这三个位置，前一个位置的后继指针和后一个位置的前驱指针都指向中间位置，最后返回插入节点的迭代器（单参数构造函数支持隐式类型转换）
删除很简单，不能删除哨兵位结点，找到要删除节点，记录要删除结点的前一个和后一个，链接两边的节点，最后释放要删除节点的空间，返回下一个节点的迭代器（会隐式类型转换成iterator类型的对象）
尾插，可以自己重新写逻辑，也可以复用insert逻辑，将第一个参数换成最后一个位置的迭代器，相当于在哨兵位节点之前插入，效果是一样的
头插，尾插，尾删是一样的，复用insert，erase逻辑就行
这部分在c语言实现数据结构链表那里讲的很详细了，想看的可以看看
代码样例讲解
这是一个很基础的尾插和打印对象逻辑，可以用第一个迭代器打印，也可以用第二个，范围for打印（范围for底层就是迭代器，无脑替换成迭代器进行打印），可以看到*it和it++，都是我们封装成类的功劳，原理很简单前面讲过
测试插入删除逻辑，可以看到不管是头插，头删，尾插，尾删都很清晰明了，clear是直接删除有效结点只剩哨兵位，所以打印不出来
可以看到，拷贝构造和赋值拷贝都完成了使命，前边讲的很详细，这里不再赘述
这里主要测试普通迭代器和const迭代器，各自调用各自，const迭代器不可修改对象，普通迭代器可以修改对象
最后一个样例，插入AA类对象，*it是拿到存放的结构体变量，.操作符访问结构体成员，拿到1:1，打印第二行是编译器会将*it转换成it.operator*()，效果是一样的
->箭头访问操作符会特殊处理一个箭头可以当做两个->->，并且编译器会转换成it.operator->()->_a1去访问，会特殊处理，这里当成特殊处理就好
list的模拟实现(代码）
要模拟实现list，必须要熟悉list的底层结构以及其接口的含义，通过上面的学习，这些内容已基本掌握，现在我们来模拟实现list。
test.cpp
#include<iostream> #include<list> #include<vector> #include<algorithm> using namespace std; #include"List.h" namespace jzy { void test_list1() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); list<int>::iterator it = lt.begin(); while (it != lt.end()) { //*it += 10; cout << *it << " "; ++it; } cout << endl; for (auto e : lt) { cout << e << " "; } cout << endl; } void test_list2() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); for (auto e : lt) { cout << e << " "; } cout << endl; lt.push_back(5); lt.push_front(0); for (auto e : lt) { cout << e << " "; } cout << endl; lt.pop_back(); lt.pop_front(); for (auto e : lt) { cout << e << " "; } cout << endl; lt.clear(); for (auto e : lt) { cout << e << " "; } cout << endl; lt.push_back(10); lt.push_back(20); for (auto e : lt) { cout << e << " "; } cout << endl; } void test_list3() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); for (auto e : lt) { cout << e << " "; } cout << endl; list<int> copy(lt); for (auto e : copy) { cout << e << " "; } cout << endl; list<int> lt1; lt1.push_back(10); lt1.push_back(20); lt1.push_back(30); lt1.push_back(40); lt = lt1; for (auto e : copy) { cout << e << " "; } cout << endl; } void print_list(const list<int>& lt) { list<int>::const_iterator it = lt.begin(); while (it != lt.end()) { //*it += 10; cout << *it << " "; ++it; } cout << endl; for (auto e : lt) { cout << e << " "; } cout << endl; } void test_list4() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); print_list(lt); list<int>::iterator it = lt.begin(); while (it != lt.end()) { *it += 10; cout << *it << " "; ++it; } cout << endl; } struct AA { int _a1; int _a2; AA(int a1 = 1, int a2 = 1) :_a1(a1) , _a2(a2) { } }; void test_list5() { list<AA> lt; AA aa1; lt.push_back(aa1); lt.push_back(AA()); AA aa2(2, 2); lt.push_back(aa2); lt.push_back(AA(2, 2)); list<AA>::iterator it = lt.begin(); cout << (*it)._a1 << ":" << (*it)._a2 << endl; cout << it.operator*()._a1 << ":" << it.operator*()._a2 << endl; cout << it->_a1 << ":" << it->_a2 << endl; cout << it.operator->()->_a1 << ":" << it.operator->()->_a2 << endl; cout << endl; } } int main() { jzy::test_list1(); return 0; }list.h
#pragma once #include<assert.h> namespace jzy { template<class T> struct ListNode { ListNode<T>* _next; ListNode<T>* _prev; T _data; ListNode(const T& x = T()) :_next(nullptr) , _prev(nullptr) , _data(x) { } }; template<class T, class Ref, class Ptr> struct __list_iterator { typedef ListNode<T> Node; typedef __list_iterator<T, Ref, Ptr> self; Node* _node; __list_iterator(Node* x) :_node(x) { } // ++it self& operator++() { _node = _node->_next; return *this; } // it++ 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; } Ref operator*() { return _node->_data; } Ptr operator->() { return &_node->_data; } bool operator!=(const self& s) { return _node != s._node; } bool operator==(const self& s) { return _node == s._node; } }; //template<class T> //struct __list_const_iterator //{ // typedef ListNode<T> Node; // typedef __list_const_iterator<T> self; // Node* _node; // __list_const_iterator(Node* x) // :_node(x) // {} // // ++it // self& operator++() // { // _node = _node->_next; // return *this; // } // // it++ // 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; // } // const T& operator*() // { // return _node->_data; // } // bool operator!=(const self& s) // { // return _node != s._node; // } // bool operator==(const self& s) // { // return _node == s._node; // } //}; template<class T> class list { typedef ListNode<T> Node; public: typedef __list_iterator<T, T&, T*> iterator; typedef __list_iterator<T, const T&, const T*> const_iterator; iterator begin() { //return iterator(_head->_next); return _head->_next; } iterator end() { return _head; } const_iterator begin() const { return _head->_next; } const_iterator end() const { return _head; } void empty_init() { _head = new Node; _head->_next = _head; _head->_prev = _head; } list() { empty_init(); } void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } } ~list() { clear(); delete _head; _head = nullptr; } list(const list<T>& lt) { empty_init(); for (const auto& e : lt) { push_back(e); } } // lt1 = lt2; // list<T>& operator=(const list<T>& lt) /*list<T>& operator=(list<T>& lt) { if (this != <) { clear(); for (const auto& e : lt) { push_back(e); } } return *this; }*/ void swap(list<T>& tmp) { std::swap(_head, tmp._head); } //list& operator=(list lt) list<T>& operator=(list<T> lt) { swap(lt); return *this; } void push_back(const T& x) { /*Node* newnode = new Node(x); Node* tail = _head->_prev; tail->_next = newnode; newnode->_prev = tail; newnode->_next = _head; _head->_prev = newnode;*/ insert(end(), x); } void push_front(const T& x) { insert(begin(), x); } void pop_back() { erase(--end()); } void pop_front() { erase(begin()); } // vector insert会导致迭代器失效 // list会不会？不会 iterator insert(iterator pos, const T& x) { Node* cur = pos._node; Node* prev = cur->_prev; Node* newnode = new Node(x); // prev newnode cur prev->_next = newnode; newnode->_prev = prev; newnode->_next = cur; cur->_prev = newnode; //return iterator(newnode); 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; }; }注意list的const迭代器可以实现为一个类，也可以实现为模版参数实例化后的结果，一般实现为后者，会少写很多冗余代码
以上就是我对list容器内容的讲解，很详细，欢迎大神交流！！！
![RGB565转BITMAP[C#---2]](https://i-blog.csdnimg.cn/direct/2c537c9272ce42a1a6289d60bc8ab89b.png)
![[MRCTF2020]Ez_bypass1(md5绕过)](https://i-blog.csdnimg.cn/direct/d6e2a3564a9a41fa9d1a19186573aa8c.png)
