文章目录
一、list的介绍二、迭代器1、list的迭代器失效问题2、迭代器的功能分类3、list迭代器的模拟实现 三、增删查改1、insert和erase2、push_back和push_front3、pop_back和pop_front 四、list的构造函数1、构造2、赋值重载 3、析构类名和类型的区别五、list和vector的对比1.vector2、list 六、模拟实现list整体代码
一、list的介绍
列表是一种顺序容器，它允许在序列中的任何位置执行常量时间插入和删除操作，并允许在两个方向上进行迭代。
它的底层是一个带头双向循环链表，我们直接来看一看整体框架：
// List的节点类template<class T>struct ListNode{ ListNode(const T& val = T()) :_val(val) ,_pPre(nullptr) ,_pNext(nullptr) {} ListNode<T>* _pPre; ListNode<T>* _pNext; T _val;};template<class T>class list{typedef list_node<T> node;public: //迭代器typedef __list_iterator<T> iterator; typedef __list_const_iterator<T> const_iterator; //构造list(){_head = new node(T());_head->_next = _head;_head->_prev = _head;}private:node* _head; size_t _size;};二、迭代器
1、list的迭代器失效问题
insert，迭代器不失效。
earse失效。
2、迭代器的功能分类
1、单向迭代器：只能++，不能–。例如单链表，哈希表；
2、双向迭代器：既能++也能–。例如双向链表；
3、随机访问迭代器：能+±-，也能+和-。例如vector和string。
迭代器是内嵌类型（内部类或定义在类里）
3、list迭代器的模拟实现
1、list迭代器的引入
对于vector和string类而言，物理空间是连续的，原生的指针就是迭代器了（不一定哦，只是可能，版本可能不同），解引用就是数据了。但是对于这里的list而言，空间是不连续的，我们知道，迭代器有两个特征：1.解引用 2.++ /–
此时如果解引用是拿不到数据的（空间不连续），更不用说++指向下一个结点了。所以，对于list的迭代器，原生指针已经不符合我们的需求了，我们需要去进行特殊处理：进行类的封装。 我们可以通过类的封装以及运算符重载支持，这样就可以实现像内置类型一样的运算符。
2.普通迭代器
//用类封装迭代器template <class T>struct __list_iterator{ typedef list_node<T> node; //用节点的指针进行构造 __list_iterator(node* p) :_pnode(p) {} //迭代器运算符的重载 T& operator*() { return _pnode->_data; } __list_iterator<T>& operator++()//返回值不要写成node* operator++()，因为迭代器++返回迭代器 { //return _pnode->_next; _pnode=_pnode->_next; return *this;//返回的是迭代器 } bool operator!=(const __list_iterator<T>& it) { return _pnode != it._pnode; }public: node* _pnode;//封装一个节点的指针};注意：对于迭代器的拷贝构造和赋值重载我们并不需要自己去手动实现，编译器默认生成的就是浅拷贝，而我们需要的就是浅拷贝，这也说明了，并不是说如果有指针就需要我们去实现深拷贝。另外，迭代器通过结构体指针访问修改链表，所以，对于迭代器我们并不需要构造函数，结点的释放由链表管理。
3.const迭代器
const迭代器的错误写法：
typedef __list_iterator<T> iterator;const list<T>::iterator it=lt.begin();因为typedef后，const修饰的是迭代器it，只能调用operator*(),调不了operator++()。
正确写法：想实现const迭代器，，需要再写一个const版本迭代器的类。
//用类封装const迭代器template <class T>struct __list_const_iterator{ typedef list_node<T> node; //用节点的指针进行构造 __list_const_iterator(node* p) :_pnode(p) {} //迭代器运算符的重载 const T& operator*()const { return _pnode->_data; } __list_const_iterator<T>& operator++()//返回值不要写成node*，因为迭代器++肯定返回迭代器 { //return _pnode->_next;//返回类型错误的 _pnode = _pnode->_next; return *this;//返回的是迭代器 } __list_const_iterator<T>& operator--() { _pnode = _pnode->_prev; return *this; } bool operator!=(const __list_const_iterator<T>& it)const { return _pnode != it._pnode; }public: node* _pnode;//封装一个节点的指针}; typedef __list_const_iterator<T> const_iterator;如果是这样子去实现的话，我们就会发现，这两个迭代器的实现并没有多大的区别，唯一的区别就在于operator*的不同。const迭代器和普通迭代器的唯一区别就是普通迭代器返回T&，可读可写，const迭代器返回const T&,可读不可写，上面的代码存在很大的问题：代码冗余，所以我们应该去解决这个问题：我们可以参考源码的实现：类模板参数解决这个问题，这也是迭代器的强大之处
//用类封装普通/const迭代器template <class T,class Ref>struct __list_iterator{ typedef list_node<T> node; typedef __list_iterator<T,Ref> Self; //用节点的指针进行构造 __list_iterator(node* p) :_pnode(p) {} //迭代器运算符的重载 Ref operator*() { return _pnode->_data; } Self& operator++()//返回值不要写成node*，因为迭代器++肯定返回迭代器啊，你返回节点指针类型不对 { //return _pnode->_next;//返回类型错误的 _pnode=_pnode->_next; return *this;//返回的是迭代器 } Self& operator--() { _pnode = _pnode->_prev; return *this; } bool operator!=(const Self& it) { return _pnode != it._pnode; }public: node* _pnode;//封装一个节点的指针}; typedef __list_iterator<T, T&> iterator;typedef __list_iterator<T, const T&> const_iterator;4、迭代器operator->的重载
迭代器的用法就是模拟指针的行为，如果现在有一个指向结构的指针，那么就需要用到->来解引用。
//*的重载：返回节点的数据Ref operator*(){ return _pnode->_data;}//->的重载：返回数据的指针T* operator->(){ return &_pnode->_data;}但是operator->使用T*做返回值类型，这样无论是普通迭代器和const迭代器都能修改，所以operator->的返回值类型应该改为泛型：
template <class T, class Ref,class Ptr>Ptr operator->(){ return &_pnode->_data;}typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;5、迭代器价值
1、封装底层实现，不暴露底层实现的细节；
2、多种容器提供统一的访问方式，降低使用成本；
C语言没有运算符重载和引用等语法，是实现不了迭代器的。
三、增删查改
1、insert和erase
insert：在pos位置上一个插入，返回插入位置的迭代器，对于list的insert迭代器不会失效，vector失效是因为扩容导致pos位置造成野指针问题。
iterator insert(iterator pos,const T& x){node* newnode = new node(x);node* cur = pos._pnode;node* prev = cur->_prev;newnode->_prev = prev;prev->_next = newnode;newnode->_next = cur;cur->_prev = newnode;++_size;return iterator(newnode);}erase:这里的带头（哨兵位）头结点不可删除，返回值是删除位置的下一个，对于list的erase迭代器是失效的
iterator erase(iterator pos){assert(pos != end());node* prev = pos._pnode->_prev;node* next = pos._pnode->_next;prev->_next = next;next->_prev = prev;delete pos._pnode;--_size;return iterator(next);}2、push_back和push_front
void push_back(const T& x){/*node* newnode = new node(x);node* tail = _head->_prev;newnode->_prev = tail;tial->_next = newnode;newnode->_next = _head;_head->_prev = newnode;*/insert(end(), x);}void push_front(const T& x){insert(begin(), x);}3、pop_back和pop_front
尾删和头删，复用erase即可
void pop_front(){erase(begin());}void pop_back(){erase(--end());}四、list的构造函数
1、构造
默认构造：
list(){ _head = new node(T());_head->_next = _head;_head->_prev = _head;_size = 0;}我们可以用empty_initialize()来封装初始化，方便复用，不用每次都写：
void empty_initialize(){ _head = new node(T()); _head->_next = _head;_head->_prev = _head;_size = 0;}迭代器区间构造：
//迭代器区间构造template <class InputIterator>list(InputIterator first, InputIterator last){empty_initialize();while (first != last){push_back(*first);++first;}}拷贝构造：
传统写法
list(const list<T>& lt){empty_initialize();for (const auto& e : lt){push_back(e);}}用范围for进行尾插，但是要注意要加上&，范围for是*it赋值给给e，又是一个拷贝，e是T类型对象，依次取得容器中的数据，T如果是string类型，不断拷贝，push_back之后又销毁。
现代写法
void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}list(const list<T>& lt){empty_initialize();list<T> tmp(lt.begin(), lt.end());swap(tmp);}2、赋值重载
传统写法
list<T>& operator=(list<T>& lt){if (this != <){clear();for (const auto& e : lt){push_back(e);}}return *this;}现代写法
list<T>& operator=(list<T> lt){swap(lt);return *this;}3、析构
对于list，有单独的clear()接口，list的析构可以直接复用clear()，同时还需要我们去释放掉头结点：
~list(){clear(); delete _head;_head = nullptr;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}类名和类型的区别
普通类：类名等于类型
类模板：类名不等价于类型，例如list类模板类名是list,类型list等。
所以我们平常写函数形参和返回值时，总会带上形参和返回值的类型：
// 赋值运算符重载list<T>& operator=(list<T> lt){ swap(lt); return *this;}五、list和vector的对比
1.vector
vector的优点（结构牛逼）：
1、支持下标的随机访问；
2、尾插尾删效率高（当然扩容的那一次尾插会较慢）；
3、CPU高速缓存命中高（数据从缓存加载至CPU中，会加载连续的一段数据，vector因为结构连续，高速缓存命中高）。
vector的缺点：
1、非尾插尾删效率低；
2、扩容有消耗，并存在一定的空间浪费。
vector迭代器失效问题：
insert/erase均失效。（如果string的insert和erase形参是迭代器，那么也会失效，但是大部分接口是下标传参，不考虑失效问题，只有几个接口是迭代器传参，需要注意迭代器失效问题）
2、list
list的优点：
1、按需申请释放，无需扩容；
2、任意位置插入删除时间O(1)；（这里说的是插入删除，不要加上查找的时间）
list的缺点：
1、不支持下标的随机访问；
2、CPU高速缓存命中率低；
3、每一个节点除了存储数据外，还需要额外存储两个指针。
| vector | list | |
|---|---|---|
| 底 层 结 构 | 动态顺序表，一段连续空间 | 带头结点的双向循环链表 |
| 随 机 访 问 | 支持随机访问，访问某个元素效率O(1) | 不支持随机访问，访问某个元素效率O(N) |
| 插 入 和 删 除 | 任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N)，插入时有可能需要增容，增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低 | 任意位置插入和删除效率高，不需要搬移元素，时间复杂度为O(1) |
| 空 间 利 用 率 | 底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高 | 底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低 |
| 迭 代 器 | 原生态指针 | 对原生态指针(节点指针)进行封装 |
| 迭 代 器 失 效 | 在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效 | 插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响 |
| 使 用 场 景 | 需要高效存储，支持随机访问，不关心插入删除效率 | 大量插入和删除操作，不关心随机访问 |
六、模拟实现list整体代码
namespace fx{ // List的节点类 template<class T> struct ListNode { ListNode(const T& val = T()) :_val(val) ,_pPre(nullptr) ,_pNext(nullptr) {} ListNode<T>* _pPre; ListNode<T>* _pNext; T _val; }; //List的迭代器类 template<class T, class Ref, class Ptr> class ListIterator { typedef ListNode<T>* PNode; typedef ListIterator<T, Ref, Ptr> Self; public: ListIterator(PNode pNode = nullptr) :_pNode(pNode) {} ListIterator(const Self& l) { _pNode = l._pNode; } Ref operator*() { return _pNode->_val } Ptr operator->() { } Self& operator++() { return _pNode->_pNext; } Self operator++(int) { Self tmp(*this); _pNode = _pNode->_pNext; return tmp; } Self& operator--() { return _pNode->_pPre; } Self& operator--(int) { Self tmp(*this); _pNode = _pNode->_pPre; return tmp; } bool operator!=(const Self& l) { return _pNode != l._pNode; } bool operator==(const Self& l) { return _pNode == l._pNode; } private: PNode _pNode; }; //list类 template<class T> class list { typedef ListNode<T> Node; typedef Node* PNode; public: typedef ListIterator<T, T&, T*> iterator; typedef ListIterator<T, const T&, const T*> const_iterator; public: /// // List的构造 void CreateHead() { Node* _pHead = new Node; _pHead->_pNext = _pHead; _pHead->_pPre = _pHead; _size = 0; } list() { CreateHead(); } list(int n, const T& value = T()) { CreateHead(); for (int i = 0; i < n; ++i) { push_back(value); } } template <class Iterator> list(Iterator first, Iterator last) { CreateHead(); wihle(first != last) { push_back(*first); ++first; } } list(const list<T>& l) { CreateHead(); for (auto& e : lt) { push_back(e); } } list<T>& operator=(const list<T> l) { swap(l); return *this; } ~list() { clear(); delete _head; _head = nullptr; } /// // List Iterator iterator begin() { return _pHead->_pNext; } iterator end() { return _pHead; } const_iterator begin() { return _head->_next; } const_iterator end() { return _pHead; } /// // List Capacity size_t size()const { return _size; } bool empty()const { return _size == 0; } // List Access T& front() { return *begin(); } const T& front()const { return *begin(); } T& back() { return _head->_prev->_val; } const T& back()const { return _head->_prev->_val; } // List Modify 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()); } // 在pos位置前插入值为val的节点 iterator insert(iterator pos, const T& val) { Node* newnode = new Node; Node* cur = pos._node; Node* prev = cur->_prev; newnode->_next = cur; cur->_prev = newnode; newnode->_prev = prev; prev->_next = newnode; ++_size; } // 删除pos位置的节点，返回该节点的下一个位置 iterator erase(iterator pos) { assert(pos != end()); Node* prev = pos._node->_prev; Node* next = pos._node->_next; prev->_next = next; next->_prev = prev; delete pos._node; --_size; } void clear() { auto it = begin(); while (it != end()) { it = erase(it); } } void swap(list<T>& l) { std::swap(_head, lt._head); std::swap(_size, lt._size); } private: PNode _pHead; size_t _size; };};