初步了解list

面试题：为什么会有list？

答：为了解决vector的缺点

vector的缺点：

插入数据需要挪动数据；
插入数据需要增容；
注：
vector和string都是数组，在哪个位置插入数据，后面的数据是要往后挪动位置的；所以时间复杂度是o(n);
而list是链表，插入数据时o(1);

vector、list优点

vector支持下标随机访问；
list头插尾插不需要挪动数据、效率高；并且不需要增容

list结构

本质是带头双向循环链表；
列表种类有哪些？
答：带头、不带头；循环、不循环；单向、双向；这样2^3组合种；

只要一个容器支持迭代器，就可以用范围for遍历；

迭代器的分类

从支持的接口角度：
单向(forward_list)、双向(list)、随机(vector);
一般从使用场景分类：
正向、反向、正向const、方向const；

list的简单运用

#define _CRT_SECURE_NO_WARNINGS#include<iostream>
#include<list>using namespace std;void print_list(const list<int>& l)
{list<int>::const_iterator it = l.begin();while (it != l.end()){cout << *it << " ";it++;}cout << endl;}void test_vector1()
{list<int> l;l.push_back(1);l.push_back(1);l.push_back(1);l.push_back(1);l.push_back(1);l.push_back(1);list<int>::iterator it = l.begin();while (it != l.end()){cout << *it << " ";it++;}cout << endl;//拷贝list<int> l1(l);print_list(l1);
}void test_vector2()
{//insert、erase//vector的迭代器失效insert、erase都会、list只用erase会迭代器失效list<int> l1;l1.push_back(1);l1.push_back(20);l1.push_back(3);l1.push_back(5);l1.push_back(8);l1.push_back(10);print_list(l1);list<int>::iterator pos = find(l1.begin(), l1.end(), 20);//现在pos就是begin()开始往后面找,里面数值为20的迭代器l1.insert(pos, 22);for (auto e : l1){cout << e << " ";e++;}cout << endl;l1.erase(pos);l1.insert(pos,11);print_list(l1);}int main()
{test_vector2();return 0; 
}

insert、erase、迭代器失效（和vector的区别）

插在这个pos位置

erase

1、这个pos的所指向的仍是指向20的这个迭代器没有变化，因为他是列表；
2、如果是vector或者string那么在insert之后再用pos会发生迭代器失效，为什么？
答：迭代器失效：因为insert之后pos所指向的内容发生了改变，vector和string本质是一个数组中间插入一个数后面数的位置都要改变、pos这个迭代器指向的地址上的内容改变了就会报错，如果发生了增容、那更加错了、增容的话原本这个数组的地址就变了；
而list是列表，列表和数组（数据结构上的内容），列表是里面存了一个数值、然后还存了一个指向下一个列表的指针，所以插入值后pos指向的位置始终不变、只是插入的新的这个数据里面有个指针指向了pos；

3、erase的话、list和vector都会存在迭代器失效
erase，list是这个pos迭代器，本质就是pos这个指针指向的空间被销毁了；
vector道理相似；

class和struct

struct和class是一样的，只是struct默认是public，class默认是private；
struct内数据默认是public类型的，class内数据默认是private类型的；
struct变量放在栈上，而class变量放在堆上，因此struct变量会自动释放，而class变量需要手动释放；

list的迭代器

是另一个struct出来的，不是列表里面的next和prev指针；


list::iterator it = lt.begin()

为什么这个迭代器的构造函数不用深拷贝？

描述：这个迭代器就不用深拷贝了，用默认的浅拷贝就行了

答：这里直接让他两指向同一个空间，不会像vector、string要深拷贝、比如v1(v2),这个v1、v2浅拷贝的话就是他们内部指针指的位置都一样了，那就是v1释放空间v2也没了，但是迭代器用不到这个功能；

tmp 是一个在函数内部创建的局部变量，但它的引用被返回给调用者。当函数执行完毕或者离开 tmp 的作用域时，tmp 对象本身并不会被销毁，因为它的引用仍然存在于调用者的上下文中。
这意味着，即使超出了包含 tmp 的作用域，tmp 对象仍然存在，并且可以通过返回的引用进行访问。只有当调用者不再使用返回的引用时，tmp 对象才会被销毁。

模拟list

注：

delete和delete[]区别是前者释放单个对象、后者释放数组对象

具体代码

写一个列表的结构体

构造函数以及其中的成员函数

	template<class T>//struct__list_node,两个_这种取名方式一般表示一会这个会在别的里面用，在这里就表示，list类里面直接用的类外面定义的struct __list_code这个结构体struct __list_node{__list_node<T>* _next; // 别忘了这里要写<T>__list_node<T>* _prev;T _data;//列表需要构造函数来初始化__list_node(const T& x = T())//这个T(),指的是没有传值过来那就直接为0:_data(x),_next(nullptr)  ,_prev(nullptr){}};

迭代器

主要用到list里面的两个指针，分别指向前后_next、_prev;

	//struct迭代器__list_iteratortemplate<class T>struct __list_iterator{typedef __list_node<T> Node;Node* _node;//构造函数，struct怎么写构造函数、就是看这个里面成员函数有哪些__list_iterator(Node* node):_node(node){}//构造传的是里面的成员函数、拷贝是传的类或者说这个结构体//浅拷贝，这个是默认函数、不用写的__list_iterator(const __list_iterator<T>& it){_node = it._node;}// operator*，读_node中的data,data的类型是T,所以函数返回值类型是TT& operator*(){return _node->_data;}//++__list_iterator<T>& operator++(){_node = _node->_next;return *this;}//后置++__list_iterator<T> operator++(int) //后置++里面就放个int，这是设计出来的伪参数，用来区分前后置用的{__list_iterator<T> tmp(*this); //直接拷贝函数、这个不用写、因为是浅拷贝，深拷贝才要写_node = _node->_next; //++(*this);return tmp;}//--__list_iterator<T>& operator--() {_node = _node->_prev; //_node是指针return *this; //*this就是迭代器，this是指针指向迭代器}__list_iterator<T>& operator--(int) //后置++里面就放个int，这是设计出来的伪参数，用来区分前后置用的{__list_iterator<T> tmp(*this); //直接拷贝函数、这个不用写、因为是浅拷贝，深拷贝才要写//node = _node->_next;--(*this);return tmp;}//!=,两个迭代器之间不相等、迭代器里面的成员函数是_node,比的是这两个，就是他指向一个列表的地址，看这两个地址一样吗bool operator!=(const __list_iterator<T>& it){return _node != it._node;}T* operator->(){return& _node->_data;//返回这个地址//指向这个地址，调用时第一个->返回其地址、第二个->返回地址上的值，迭代器做了优化，调用只需要一个->}};

class类

template<class T>
class list
{typedef __list_node<T> Node;
public:typedef __list_iterator<T> iterator; // 放public里面不然外面动不了T，就是用不了模板，私有的不能用//迭代器用节点的指针就行了iterator begin(){return iterator(_head->_next);//注意这里返回的是迭代器，不是_head头部指针、这个是list类里面的成员变量//现在是把头部指针_head传过去，然后迭代器调用他的拷贝函数;//这里面就是构造函数、因为传过去的是Node类型;}iterator end(){return iterator(_head);}//构造函数list(){_head = new Node;//new node //这里面不用写成Node[]，是因为[]是数组用的，这个就里面就开辟一个指针指向的地址空间，[]是一个数组的空间_head->_next = _head;_head->_prev = _head;}void push_back(const T& x = T()){Node* tail = _head->_prev;Node* newnode = new Node(x);tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode; }private:Node* _head;
};

两个测试案例

	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()){cout << *it << " ";++it;}cout << endl;}struct Date{int _year = 0;int _month = 1;int _day = 2;};void test_list2(){list<Date> lt;lt.push_back(Date());lt.push_back(Date());list<Date>::iterator it = lt.begin();//调用data，因为现在模板T就是date，传参传过去date是可以的while (it != lt.end()){cout << it->_year << " " << it->_month << " " << it->_day;++it;}cout << endl;}

报错

修改