list
本节目标
1. list的介绍及使用
1.1 list的介绍
1.2 list的使用
1.3 模拟list节点的结构
1.4 list类的封装
补充：list的自带排序函数
1. sort
2. unique
2. list的迭代器
2.1 list的迭代器失效问题
2.2 迭代器的分类
2.3 迭代器的模拟实现
2.3.1 普通迭代器
2.3.2 const迭代器（难）
2.3.3 模拟迭代器完整版
3. list模拟实现完整代码
3.1 list.h
3.2 Test.cpp
4. 模拟实现的注意事项
4.1 深拷贝的问题
4.2 类名和类型的问题
5. vector与list的优缺点
1. vector优点与缺点
2. list优点与缺点
本节目标
本节将会讲述list的使用，以及list的底层实现，对于底层实现，list的底层就是我们之前学过数据结构中的链表，因此这就与vector的结构相差很大，迭代器的部分也与vector有很大差别，迭代器的相关内容极为重要，也是本节的难点；此外也会有vector与list两者之间进行对比，下面开始正文。
注：本文的模拟实现会贯穿全文而不是集中在某一小节
1.list的介绍及使用
1.1 list的介绍
对于list类来说，其中的大多数函数功能都与string、vector相同，大部分实用的成员函数也是非常相似，因此我们在这里也是简单明了的查看文档：list文档 。通过文档我们可以更加直观的了解成员函数的功能。
list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。即底层是双向带头循环链表。
list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)
通过这个结构我们已经知道，list的迭代器实现起来将会困难一些，原因是其节点的地址是不连续的，其次也会存在对节点的类型
1.2list的使用
对于使用这里，与vector调用方式是一样的，无论是push_back，还是find等，查上面的文档就好了。而对于list的重要的部分，是模拟实现中的问题。
1.3模拟list节点的结构
对于一个双向带头循环链表的节点的结构，为了存入prev、next指针以及数据，我们需要一个类来封装这几个变量，这个类在C语言中也可以称为结构体，但实际上又有所区别，在这个节点类中，虽然没有成员函数，但是却有着公有和私有的区别，因此为了便于实现，我们采用struct公有的类封装；此外类也需要实现构造函数。由于我们不知道存入什么变量，因此会用到模板。
template<class T> struct list_node { list_node<T>* _next;//这里不写<T>也没有错误 list_node<T>* _prev; T _data; list_node(const T& x)//构造函数 :_next(nullptr) ,_prev(nullptr) ,_data(x) }
1.4 list类的封装
对于list类来讲，私有的成员变量是指向头结点的指针。
template<class T> class list { typedef list_node<T> node; //将节点重命名一下 public: //成员函数： //…… private: node* _head;//指向头结点的指针变量 }
补充：list的自带排序函数
1. sort
之前的vector类，可以用到算法库的排序sort，但当查看list的文档，发现其自带一个排序函数:
由于list是链表结构，而算法库中的排序的底层是快速排序，不能实现链表的排序，因此设计了一个list自带的排序，通过前面的学习，list排序有纯粹的暴力插入排序，也有更好的归并排序，而这个list的sort的底层就是归并排序。
然而，对于实际来说，通过将list的值赋值给vector之后调用算法库sort的时间还是要比只接归并排序快的，因此在这里排序还是推荐拷贝到vector后调用算法库的排序。
那就验证一下看看哪个更快：(代码放这里，自己也可以动手试一下)
void test_op() { srand(time(0)); const int N = 1000000; vector<int> v; v.reserve(N); list<int> lt1; list<int> lt2; for (int i = 0; i < N; ++i) { auto e = rand(); //v.push_back(e); lt1.push_back(e); lt2.push_back(e); } // 拷贝到vector排序，排完以后再拷贝回来 int begin1 = clock(); for (auto e : lt1) { v.push_back(e); } sort(v.begin(), v.end()); size_t i = 0; for (auto& e : lt1) { e = v[i++]; } int end1 = clock(); int begin2 = clock(); // sort(lt.begin(), lt.end()); lt2.sort(); int end2 = clock(); printf("vector sort:%d\n", end1 - begin1); printf("list sort:%d\n", end2 - begin2); }
debug下：
但我们发现没有明显区别，别急，看看release下的：
release下：
很明显，vector比list的快很多。这里补充一下，release是优化后的代码运行的时间，当我们编译完代码打包好，代码也会以release的版本供给客户所使用。
2. unique
sort实现了之后，我们也来了解一下另一个特有的成员函数：unique：去重函数，由于这has必须建立在有序的基础上才能使用，因此我们也可以想象得到底层是如何实现的，毕竟刚学C语言的时候经常会自己写出那种的代码，那么接下来就看一下怎么使用吧：
1. 本来无序：
2. 有序之后：
可见，调用unique的前提是数据必须有序。
2.list的迭代器
2.1list的迭代器失效问题
在上一节的vector中，我们讲述了迭代器失效的问题，vector的insert和erase都会导致迭代器失效，insert是 。因为挪动空间导致，erase是因为删掉之后不存在这个元素导致。而对于list来讲，list的insert是不会失效的，因为list的insert并没有移动空间，而是直接插入节点，而erase由于删除的原因也会造成list中的迭代器失效。
因此这里只有erase会造成list迭代器失效。而解决这一问题就可以根据返回值来改变失效后的迭代器。
这样，删除之后也不会造成失效了。
2.2迭代器的分类
1、单向迭代器：只能++，不能–。例如单链表，哈希表；
2、双向迭代器：既能++也能–。例如双向链表；
3、随机访问迭代器：能+±-，也能+和-。例如vector和string。
迭代器是内嵌类型（内部类或定义在类里）
2.3迭代器的模拟实现
对于list结构，已经提到过是双向带头循环链表，而对于迭代器的begin和end又是左闭右开区间，因此模拟实现时begin在_head->next的位置，end在_head的位置，因为最后一个节点的下一个就是_head。
对于list的迭代器，与vector有很大的不同，因为每一个节点都是通过指针的方式链接的，因此迭代器的++和–并不是单一的地址++与–，而是以解引用的方式进行，也就是说需要多一个运算符重载，那么既然又多了一个需求，对于迭代器我们也就有必要也封装成类供给list类使用。
迭代器的类：（这个可以先不看）
template<class T, class Ref, class Ptr> struct __list_iterator { typedef list_node<T> node; typedef __list_iterator<T, Ref, Ptr> Self; node* _pnode; __list_iterator(node* p)//构造 :_pnode(p) {} }
2.3.1 普通迭代器
实现普通迭代器，我们用不到上面的三个模板参数，只需要一个T就够了，因此在这里为了更好的理解，我们不看上面迭代器的类，在这里自己造一个。
template<class T> struct __list_iterator { typedef list_node<T> node; node* _pnode;//改变的就是这个唯一成员变量 __list_iterator(node* p)//拷贝构造 :_pnode(p) {} T& operator*() { return _pnode->_data;//解引用的运算符重载 } __list_iterator<T>& operator++()//前置 { _pnode = _pnode->_next; return *this; } __list_iterator<T>& operator++(int)//后置 { __list_iterator<T> it(*this);//拷贝构造 _pnode = _pnode->_next; return it; } __list_iterator<T>& operator--()//前置,后置和上面的一样 { _pnode = _pnode->_prev; return *this; } bool operator!=(const __list_iterator<T>& it) { return _pnode != it._pnode; } }
因此我们可以看到普通的迭代器除了封装之外没有什么难点。
2.3.2 const迭代器（难）
那么对于const迭代器来说，vector是在解引用的时候直接加上const就可以了，但list明显不能像vector那样直截了当，这也是这一节最难以实现的部分。
其与vector对比，对于const的list迭代器来说，因为本身是以类的方式进行，而const实际上就代表迭代器指向的内容不可改变，也就是说只需要改变普通迭代器的解引用运算符重载就可以了，因此我们实现const有两种思路可行，一是再写一个类，只将普通迭代器运算符重载的函数换成const类型，也就是这样：多加了一个const类型的迭代器的类。
template<class T> struct __list_const_iterator { typedef list_node<T> node; node* _pnode;//改变的就是这个唯一成员变量 __list_const_iterator(node* p)//拷贝构造 :_pnode(p) {} const T& operator*()//只对这个进行修改 { return _pnode->_data;//解引用的运算符重载 } __list_const_iterator<T>& operator++()//前置 { _pnode = _pnode->_next; return *this; } __list_const_iterator<T>& operator++(int)//后置 { __list_iterator<T> it(*this);//拷贝构造 _pnode = _pnode->_next; return it; } __list_const_iterator<T>& operator--()//前置,后置和上面的一样 { _pnode = _pnode->_prev; return *this; } bool operator!=(const __list_const_iterator<T>& it) { return _pnode != it._pnode; } }
但我们发现这种方式会产生很多的代码冗余，因为除了解引用运算符重载，别的都没有变化，因此大佬在设计这里的时候用到了多个模板参数，通过传入的类型不同，就将这个迭代器的类转化成const的和非const的：
//typedef __list_iterator<T, T&> iterator; //typedef __list_iterator<T, const T&> const_iterator; template<class T, class Ref>//模仿大佬在STL中的写法，能避免副本造成的代码冗余 struct __list_iterator//封装成类的迭代器 { typedef list_node<T> node; typedef __list_iterator<T, Ref> Self; node* _pnode; __list_iterator(node* p) :_pnode(p) {} // iterator it // *it // ++it Ref operator*()//const迭代器看这个 { return _pnode->_data; } 那么能不能重载一个T&？ 像下面： const iterator *it ++it 不能调++了，因为const不能调用非const，那这个时候可不可以将++的运算符继续重载？ 不能，++是写的函数，不可能把他变成const， 因此像下面这样重载，可以解引用，但是不能++， 所以换思路，可以将迭代器这整个类再写一个const版本的出来，就是会产生代码冗余 //const T& operator*() const //{ // return _pnode->_data; //} Self& operator++()//前置 { _pnode = _pnode->_next; return *this; } Self& operator--()//前置 { _pnode = _pnode->_prev; return *this; } bool operator!=(const Self& it) { return _pnode != it._pnode; } };
即这样的一个迭代器类通过在list类中传入对应的类型就可以实现const和非const。
总结一下实现const的迭代器的两种方法：
- 重新写一个类，不过里面只有一个函数是不一样的，会造成代码冗余
- 利用模板参数！将一个类通过传入的类型不同能够自动演化出不同的类。
2.3.3 模拟迭代器完整版
如果对于list<T>，这个T是一个类，并且有两个成员变量，翻入list中是如何迭代的呢？
struct Pos { int _row; int _col; Pos(int row=0, int col=0) :_row(row) ,_col(col) {} };
我们可以在通过迭代器进行这样的访问：
list<Pos> lt(1,2); list<Pos>::iterator it = lt.begin(); while(it != lt.end()) { cout <<(*it)._row<<":"<<(*it)._col<<endl; ++it; }
但事实上，我们在C/C++中有另一种方式：->即直接it->_row;下面的Ptr就是。
因此我们也需要考虑如何将这样的运算符也重载进去，只需要在类中再加一个模板参数，到现在三个模板参数，已经齐了。这也是我们最终的迭代器的类：
//typedef __list_iterator<T, T&, T*> iterator; //typedef __list_iterator<T, const T&, const T*> const_iterator; template<class T, class Ref, class Ptr>//模仿大佬在STL中的写法，能避免副本造成的代码冗余 struct __list_iterator//封装成类的迭代器 { typedef list_node<T> node; typedef __list_iterator<T, Ref, Ptr> Self; node* _pnode; __list_iterator(node* p) :_pnode(p) {} // iterator it // *it // ++it Ref operator*()//const迭代器看这个 { return _pnode->_data; } Ptr operator->()//const迭代器看这个 { return &_pnode->_data; } Self& operator++()//前置 { _pnode = _pnode->_next; return *this; } Self& operator++(int)//后置 //自己加的，这里写成T对于自己加的Pos会报错 { //Self it = *this; Self it(*this); _pnode = _pnode->_next; return it; } Self& operator--()//前置 { _pnode = _pnode->_prev; return *this; } bool operator!=(const Self& it) const { return _pnode != it._pnode; } bool operator==(const Self& it) const { return _pnode == it._pnode; } };
但意的是，->返回的值仍然是一个指针，那我们调用时确是一个函数：那返回时不应该是it->->_row吗？
这是因为编译器做了一定程度的优化，将两个->变成了一个，因此，我们直接写成两个->也是对的
这样就完成了我们整个迭代器类的封装。
