list(c++)
前言
这里我们学习的是gcc下STL版本的list。STL里的list容器底层是一个双向带头节点的一个链表，不再是单链表，单链表实际运用很少，更多的是双向带头链表。
正文
list使用
默认成员函数
| 构造函数 | 接口说明 |
| list (size_type n, const value_type& val = value_type()) | 构造的list中包含n个值为val的元素 |
| list() | 构造空的list |
| list (const list& x) | 拷贝构造函数 |
| list (InputIterator first, InputIterator last) | 用[first, last)区间中的元素构造list |
迭代器
| 函数声明 | 接口说明 |
| begin + end | 返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器 |
| rbegin + rend | 返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的 reverse_iterator,即begin位置 |
容量
| 函数声明 | 接口说明 |
| empty | 检测list是否为空，是返回true，否则返回false |
| size | 返回list中有效节点的个 |
增删查改
| 函数声明 | 接口说明 |
| push_front | 在list首元素前插入值为val的元素 |
| pop_front | 删除list中第一个元素 |
| push_back | 在list尾部插入值为val的元素 |
| pop_back | 删除list中最后一个元素 |
| insert | 在list position 位置中插入值为val的元素 |
| erase | 删除list position位置的元素 |
| swap | 交换两个list中的元素 |
| clear | 清空list中的有效元素 |
代码演示
这里list使用很简单，我就不一个一个演示了。就用一个测试案例测试下吧
void Print(const li::list<int>& lt)
{li::list<int>::const_iterator it = lt.begin();while (it != lt.end()){//(*it)++;cout << *it << " ";++it;}
}
void list_test01()
{li::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);Print(lt);cout << endl;//这里是拷贝构造 内置类型 浅拷贝 li::list<int>::iterator it = lt.begin();while (it != lt.end()){(*it)++;cout << *it << " ";++it;}
}这里我就简单测试下，需要注意的是，erase之后迭代器被释放失效，记得用返回值接受。clear这里底层上就是释放掉了所有的节点，只留下一个头节点。因为链表结构决定了它是可以部分删除容量的，不像连续地址的顺序表。因此，list的clear就直接删除节点了，而不是仅仅清除数据。
list模拟实现
成员变量
template<class T>
struct list_node
{list_node<T>* _next;list_node<T>* _prev;T _val;list_node(const T& x = T()):_next(nullptr),_prev(nullptr),_val(x){}
};
template<class T>
class list
{typedef list_node<T> Node;//...//private:Node* _head;size_t _size;}从链表开始，就有点复杂了，使用很多封装和重命名。这里我们需要先实现一个结构体(结点)，
这里需要重名命下这个类模板，这是为啥呢？这是一个习惯问题。祖师爷在研究STL的时候，他自己也是从c语言过度来的，虽然类模板也是它老人家研究出来的。但是在声明一个变量的时候，加上一个模板，很容易忘记，尤其习惯了c语言的命名变量的语法。所以，这里重命名下是一种习惯问题，并且也可以简化代码。这也是一个好习惯，因为你的模板可不一定只有一个，如果你的leader突然让你改一下这个容器，增加一个模板，你难不成一个一个该吗？这时候重命名就香很多了，只需要改一下。
这里还有一个size,有这个参数我们就可以很直观的观察链表，和判断链表是否为空。有利于我们更直观的使用链表和调试。
默认成员函数
void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(){empty_init();}//不能用const引用void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}list<T>& operator=(list<T> lt){swap(lt);return *this;}list(const list<T>& lt){empty_init();for (auto& e : lt){push_back(e);}}~list(){clear();delete _head;_head = nullptr;}
这里构造函数里面套了一个函数初始化，这也是向库里版本靠齐。这里的赋值重载是用的现代写法，直接swap交换，传统的写法是直接手搓一遍(不推荐)。这里的拷贝构造函数里面复用了push_back，析构函数复用了clear()，这也体现list的高度封装性，其实库里的比这里还复杂。动态内存分配也不是new而是封装了一个空间配置器，就是效率高点。我在vector的博客也提及过。我们学习STL的代码，强烈不建议一行一行看，否则你会直接想放弃的。这里我们先知道个大体逻辑。到下文会解释clear和push_back()这两个函数，其实push_back里面也是套用了insert的。就像套娃一样，这里的代码。
迭代器
重点 重点 重点 重要的事说三遍，list的迭代器可谓是学习list的重点也是一个难点，先问一下，如何设计list的迭代器？可以像vector里那样吗？直接指针吗？可是这里是一个自定义类型呀？解引用也不是结点的值呀？因此，这里肯定是要对*赋值重载的。所以，就可以先否定直接指针了，这肯定不行的！既然要赋值重载，那我们就肯定要自定义类型呀？对，这里的迭代器就是一个自定义类型，里面包含着一个结点指针，还有构造函数，完成初始化。这里不介绍反向迭代器，因为反向迭代器的设计和正向有点不一样，这里我们先学习正向迭代器，正向迭代器就够喝一壶了。
template<class T,class Ref,class Ptr>
struct _list_iterator
{typedef list_node<T> Node;typedef _list_iterator<T,Ref,Ptr> self;Node* _node;_list_iterator(Node* node):_node(node){}Ref operator*(){return _node->_val;}Ptr operator->(){return &(_node->_val);}self& operator++(){_node = _node->_next;return *this;}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;}bool operator!=(const self& it) const{return _node != it._node;}bool operator==(const self& it) const{return _node == it._node;}
};这里先给大家看一下完整版的迭代器设计，是不是很蒙，发现和我想的有点不一样呀!
struct _list_iterator
{
typedef list_node<T> Node;
Node* _node;
_list_iterator(Node* node):_node(node){}
};这里先看我上面这个代码，是不是发现又看懂了。这里我们学习迭代器需要一步一步拆开学，他的设计其实有点难理解。我们上面讲了，迭代器需要设计成一个自定义类型，需要包装一下结点的指针，以便我们访问。这里的代码是一个雏形，有了这个雏形，对于begin(),end()，我们就完成的差不多了。但还需要大大的完善。这里还要对*，++等运算符赋值重载。那为啥有三个模板呢？这里是根据需求来设定的。首先*赋值重载返回的就是数据本身，所以数据的类型模板，我们需要你上传，直接引用，即使结构体的数据还是什么其他自定义类型数据，都可以返回正确的值。最后一个模板为啥要传一个指针呢？迭代器模仿的是指针的行为？既然是指针那么就可以用箭头访问结构体。所以，这里的迭代器也满足了这种要求。使用箭头访问结点的元素。同理，自己上传一个指针，这样后续更改代码，我们只用修改这部分代码。这里是如何设计const修饰的迭代器呢？这时候我们的模板就香很多了，我们这需要在上传模板的时候加上一个 const,这样子你需要什么我就返回什么。这也证明我们为啥要搞三个模板，就是因为，后面的代码设计是需要使用的。其实刚开始学这里的迭代器的时候，我也很蒙蔽，但是学到后面，你才发现祖师爷的这套设计有多厉害！这里的命名也是向库里靠拢的，建议大家以后命名也尽量向库里靠拢。
typedef list_node<T> Node;
public:typedef _list_iterator<T,T&,T*> iterator;typedef _list_iterator<T, const T&,const T*> const_iterator;iterator begin(){return _head->_next; //单参数的构造函数支持隐式类型转换//return iterator(_head->_next);}iterator end(){return _head;}const_iterator begin() const{return _head->_next; }const_iterator end() const{return _head;}虽然这里链表里的迭代器看起来很简单，和vector差不多。但底层是很复杂的，这里也体现了迭代器的重要。为啥我们要用迭代器遍历数据，祖师爷为啥要研究出个迭代器。就是因为，有了迭代器，我们可以统一用法访问任何容器的任何形式数据。不像数组就要用下标，链表就要用指针。不方便程序员的开发。有了迭代器，STL里的任何容器都可以用迭代器访问。从list开始，迭代器才真正开始上难度，而不是简单的复用指针，这里我们学习list的迭代器的时候，不仅仅要懂list迭代器是如何实现，更要体会的是祖师爷设计的理念和思想。更重要的是人家这种思想，极大提高了编程简化。其实学习c++，c++意义不仅仅在利用c++开发软件和编写底层系统上，而且c++的设计的语法和理念为其他语言提供了模板，很多语言都有c++的影子，尤其像java语言，可以说是一个接近满分的抄作业选手。
容量
bool empty(){return _size == 0;}size_t size(){return _size;}这里就是简单返回，没啥好说的。
增删查改
void clear()
{iterator it = begin();while (it != end()){it = erase(it);}_size = 0;
}
void push_back(const T& x)
{/*Node* tail = _head->_prev;Node* newNode = new Node(x);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());
}
iterator insert(iterator pos, const T& x)
{Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;Node* newNode = new Node(x);prev->_next = newNode;newNode->_prev = prev;newNode->_next = cur;cur->_prev = newNode;_size++;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;_size--;return next;
}
void swap(list<T>& lt)
{std::swap(_head, lt._head);std::swap(_size, lt._size);
}这里要说一下，push_back和pop_back分别内部调用了insert和erase， 这里增删查改不用一个一个写，库里就是把大量重复的代码，封装起来。以后使用到这段代码就调用这个封装的函数，几乎全是封装。实际上，底层还是那几个指针交换位置。
源码
#pragma once
#include <assert.h>
#include <iostream>
namespace li
{template<class T>struct list_node{list_node<T>* _next;list_node<T>* _prev;T _val;list_node(const T& x = T()):_next(nullptr),_prev(nullptr),_val(x){}};template<class T,class Ref,class Ptr>struct _list_iterator{typedef list_node<T> Node;typedef _list_iterator<T,Ref,Ptr> self;Node* _node;_list_iterator(Node* node):_node(node){}Ref operator*(){return _node->_val;}Ptr operator->(){return &(_node->_val);}self& operator++(){_node = _node->_next;return *this;}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;}bool operator!=(const self& it) const{return _node != it._node;}bool operator==(const self& it) const{return _node == it._node;}};template<class T>class list{typedef list_node<T> Node;public:typedef _list_iterator<T,T&,T*> iterator;typedef _list_iterator<T, const T&,const T*> const_iterator;iterator begin(){return _head->_next; //单参数的构造函数支持隐式类型转换//return iterator(_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;_size = 0;}list(){empty_init();}//不能用const引用void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}list<T>& operator=(list<T> lt){swap(lt);return *this;}list(const list<T>& lt){empty_init();for (auto& e : lt){push_back(e);}}~list(){clear();delete _head;_head = nullptr;}bool empty(){return _size == 0;}size_t size(){return _size;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}_size = 0;}void push_back(const T& x){/*Node* tail = _head->_prev;Node* newNode = new Node(x);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());}iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;Node* newNode = new Node(x);prev->_next = newNode;newNode->_prev = prev;newNode->_next = cur;cur->_prev = newNode;_size++;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;_size--;return next;}private:Node* _head;size_t _size;};
}
总结
学习list，学会使用是其次，更重要的是理解list底层的编写的理念和设计。这才是最终要的，关于list的学习，其中最重要的就是他的迭代器的设计，这里是最难的。其他部分都是高度的重复，像增删查改就是简单的链表编写。