目录
一. List的数据结构
二. List实现的基本框架
1. list的结点结构类
2. List的迭代器类
正向迭代器
反向迭代器
3. List操作接口的实现
1. 默认成员函数
构造函数 和 析构函数
拷贝构造函数 和 赋值运算符重载
2. 修改相关函数接口
insert 和 erase
push_back 和 push_front
pop_front 和 pop_back
3. 迭代器相关接口
begin() 和 end()
rbegin() 和 rend()
4. 其他相关函数接口
swap
clear
Head_init
三. 完整源代码实现
一. List的数据结构
list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代，其底层是带头双向循环链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向 其前一个元素和后一个元素，即list实现上就是一个双向循环链表，list节点 有prev 和 next 两个指针。
使用链表存储数据，并不会将它们存储到一整块连续的内存空间中。恰恰相反，各元素占用的存储空间（又称为节点）是独立的、分散的，它们之间的线性关系通过指针来维持的
二. List实现的基本框架
List的实现需要实现三个类 （类模板形式）
list的结点结构类
List的迭代器类
List功能的实现类
1. list的结点结构类
对节点的定义如下：
//list结点类模板template <class T>struct listnode{ listnode* prev; listnode* next;T data; //结点的构造函数,完成对节点的初始化listnode(const T& val = T()) :prev(nullptr),next(nullptr),data(val){}};可以看到，list 容器定义的每个节点中，都包含 *prev、*next 和 data。其中，prev 指针用于指向前一个节点；next 指针用于指向后一个节点；data用于存储当前元素的值。
2. List的迭代器类
List 的迭代器迭代器有两种实现方式，具体应根据容器底层数据结构实现：
1. 原生态指针，比如：vector
2. 将原生态指针进行封装，因迭代器使用形式与指针完全相同，因此在自定义的类中须实现以下方法：
1. 指针可以解引用，迭代器的类中必须重载operator*()
2. 指针可以通过->访问其所指空间成员，迭代器类中必须重载oprator->()
3. 指针可以++向后移动，迭代器类中必须重载operator++()与operator++(int)至于 operator--()/operator--(int)释放需要重载，根据具体的结构来抉择，双向链表可以向前移动，所以需要重载，如果是forward_list就不需要重载--
4. 迭代器需要进行是否相等的比较，因此还需要重载operator==()与operator!=()
和 vector 容器迭代器的实现方式不同，由于 list 容器的元素并不是连续存储的，所以该容器迭代器中，必须包含一个可以指向 list 容器的指针，并且该指针还可以借助重载的 *、++、--、->、==、!= 等运算符，实现迭代器正确的递增、递减、取值等操作，以达到 vector 迭代器的同等效果
正向迭代器
list 容器正向迭代器的实现代码如下：
//list正向迭代器类template <class T, class Ref, class Ptr>struct _list_iterator{typedef listnode<T> Node; //在迭代器中实例化结点模板typedef _list_iterator<T, Ref, Ptr> self; //对迭代器的类型重命名，已达简化 //构造_list_iterator(Node* node = nullptr):_node(node){} // 迭代器支持移动// 前置++self& operator++(){_node = _node->next;return *this;}//后置++self operator++(int){self tmp(*this);++_node;return tmp;}//前置--self& operator--(){_node = _node->prev;return *this;}//后置--self operator--(int){self tmp(*this);--_node;return tmp;} // 具有指针类似行为Ref operator*(){return _node->data;} //当结点数据类型仍然为自定义结构时Ptr operator->(){return &_node->data;} // 迭代器支持比较bool operator!=(const self& s) const{return _node != s._node;}bool operator==(const self& s) const{return _node == s._node;} Node* _node;};
反向迭代器
list 容器反向迭代器的实现代码如下：
//list反向迭代器类template <class Iterator, class Ref, class Ptr>struct _list_reverse_iterator{typedef _list_reverse_iterator<Iterator, Ref, Ptr> self; //构造_list_reverse_iterator(Iterator it):_cur(it){} // 迭代器支持移动//前置++self& operator++(){--_cur;return *this;}//后置++self operator++(int){self tmp(*this);--_cur;return tmp;}//前置--self& operator--(){++_cur;return *this;}//后置--self operator--(int){self tmp(*this);++_cur;return tmp;} // 具有指针类似行为Ref operator*(){Iterator tmp = _cur;return *--tmp;}Ptr operator->(){return &(*_cur);} // 迭代器支持比较bool operator!=(const self& s) const{return _cur != s._cur;}bool operator==(const self& s) const{return _cur == s._cur;}Iterator _cur;};
3. List操作接口的实现
1. 默认成员函数
构造函数 和 析构函数
以下，创建了空的 list 容器（即无参的构造函数），但它也包含有 1 个节点。
除此之外，list 模板类中还提供有带参的构造函数，它们的实现过程大致分为以下 2 步：
1. 调用 Head_init() 函数，构造带有头节点的空 list 容器链表；
2. 将各个参数按照次序插入到空的 list 容器链表中。
//构造函数list(){Head_init(); //初始化头结点} //构造n个值为val的节点链表的构造函数list(int n, const T& val = T()){Head_init(); //对链表头结点初始化while (n--) //依次尾插n各值为val的结点{push_back(val);}}//迭代器区间构造template <class Iterator>list(Iterator first, Iterator last){Head_init();while (first != last){push_back(*first);++first;}} //析构函数~list(){clear(); //清空链表结点delete _head; //释放头结点_head = nullptr; //头结点置空}
拷贝构造函数 和 赋值运算符重载
//拷贝构造list(const list<T>& lt){Head_init(); //初始化for (const auto& e : lt){push_back(e);}} //赋值运算符重载list<T>& operator=(list<T> lt){swap(lt); //交换两者数据，交换两者头结点的指针即可return *this;}
2. 修改相关函数接口
insert 和 erase
insert : 通过在指定位置的元素之前插入新元素(插入位置是任意的)
//在pos位置插入一个结点iterator insert(iterator pos, const T& val){Node* newnode = new Node(val); //申请一个新节点Node* curnode = pos._node; //pos位置的结点newnode->prev = curnode->prev; //先与当前结点的前一个结点链接上curnode->prev->next = newnode;newnode->next = curnode; //在与当前结点链接curnode->prev = newnode;return newnode; //返回新插入结点的迭代器}
说明：此在list中进行插入时是不会导致list的迭代 器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响
注意：节点的连接顺序，先连后断
erase: 删除所指向的位置的结点（删除位置是任意的）
//删除pos位置的结点iterator erase(iterator pos){assert(pos != end());Node* curnode = pos._node; //保存要删除的结点Node* nextnode = curnode->next; //删除结点的下一结点curnode->prev->next = nextnode;nextnode->prev = curnode->prev;delete curnode;return nextnode; //返回删除结点的后一个结点的迭代器}说明：list 在删除一个结点时会存在迭代器失效，(即被删除的那个位置的迭代器失效)，
push_back 和 push_front
尾插
在end()迭代器所在的位置的前一个结点之后插入新的结点
//尾插void push_back(const T& val){/*Node* newnode = new Node(val);Node* tail = _head->prev;tail->next = newnode;newnode->prev = tail;newnode->next = _head;_head->prev = newnode;*/ //复用insertinsert(end(), val);}在end()位置之前插入一个结点（即在尾部插入结点）
头插
在begin()迭代器所在的位置之前插入新的结点
//头插void push_front(const T& val){insert(begin(), val); //复用insert}
pop_front 和 pop_back
头删
删除begin()迭代器所在的位置的结点
//头删void pop_front(){erase(begin()); //复用erase}
尾删
删除end()迭代器所在的位置的前一个结点
//尾删void pop_back(){erase(--end()); }
3. 迭代器相关接口
begin() 和 end()
iterator begin(){return iterator(_head->next);//构造匿名对象 //return _head->next; //隐式类型转换}iterator end(){return iterator(_head); //return _head; } //const的迭代器const_iterator begin() const{return const_iterator(_head->next); //return _head->next;}const_iterator end() const{return const_iterator(_head); //return _head;}
rbegin() 和 rend()
reverse_iterator rbegin() {return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());} //const的反向迭代器const_reverse_iterator rbegin() const{return const_reverse_iterator(end());}const_reverse_iterator rend() const{return const_reverse_iterator(begin());}
4. 其他相关函数接口
swap
用于交换两对象的数据的内容，实际改变头结点的指针的指向
void swap(list<T>& tmp){std::swap(_head, tmp._head);}clear
清空链表结点（头结点除外）
void clear(){iterator it = begin();while (it != end()){it = erase(it);}}Head_init
初始化头结点
//初始化头结点 void Head_init(){_head = new Node; //申请一个空白结点（头结点）_head->next = _head; _head->prev = _head;}三. 完整源代码实现
//list结点类template <class T>struct listnode{T data;listnode* prev;listnode* next;listnode(const T& val = T()):data(val),prev(nullptr),next(nullptr){}};//list正向迭代器类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* node):_node(node){}//前置++self& operator++(){_node = _node->next;return *this;}//后置++self operator++(int){self tmp(*this);++_node;return tmp;}//前置--self& operator--(){_node = _node->prev;return *this;}//后置--self operator--(int){self tmp(*this);--_node;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;}};//list反向迭代器类template <class Iterator, class Ref, class Ptr>struct _list_reverse_iterator{typedef _list_reverse_iterator<Iterator, Ref, Ptr> self;_list_reverse_iterator(Iterator it):_cur(it){}//前置++self& operator++(){--_cur;return *this;}//后置++self operator++(int){self tmp(*this);--_cur;return tmp;}//前置--self& operator--(){++_cur;return *this;}//后置--self operator--(int){self tmp(*this);++_cur;return tmp;}Ref operator*(){Iterator tmp = _cur;return *--tmp;}Ptr operator->(){return &(*_cur);}bool operator!=(const self& s){return _cur != s._cur;}bool operator==(const self& s){return _cur == s._cur;}Iterator _cur;};//list类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;typedef _list_reverse_iterator<iterator, T&, T*> reverse_iterator;typedef _list_reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;iterator begin(){return iterator(_head->next);}iterator end(){return iterator(_head);}const_iterator begin() const{return const_iterator(_head->next);}const_iterator end() const{return const_iterator(_head);}reverse_iterator rbegin() {return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}const_reverse_iterator rbegin() const{return const_reverse_iterator(end());}const_reverse_iterator rend() const{return const_reverse_iterator(begin());}void Head_init(){_head = new Node;_head->next = _head;_head->prev = _head;}//构造函数list(){Head_init();}list(int n, const T& val = T()){Head_init();while (n--){push_back(val);}}//迭代器区间构造template <class Iterator>list(Iterator first, Iterator last){Head_init();while (first != last){push_back(*first);++first;}}//拷贝构造list(const list<T>& lt){Head_init();for (const auto& e : lt){push_back(e);}}void swap(list<T>& tmp){std::swap(_head, tmp._head);}//赋值运算符重载list<T>& operator=(list<T> lt){swap(lt);return *this;}//析构~list(){clear();delete _head;_head = nullptr;}//在pos位置插入一个结点iterator insert(iterator pos, const T& val){Node* newnode = new Node(val);Node* curnode = pos._node;newnode->prev = curnode->prev;curnode->prev->next = newnode;newnode->next = curnode;curnode->prev = newnode;return newnode;}//删除pos位置的结点iterator erase(iterator pos){assert(pos != end());Node* curnode = pos._node;Node* nextnode = curnode->next;curnode->prev->next = nextnode;nextnode->prev = curnode->prev;delete curnode;return nextnode;}//尾插void push_back(const T& val){/*Node* newnode = new Node(val);Node* tail = _head->prev;tail->next = newnode;newnode->prev = tail;newnode->next = _head;_head->prev = newnode;*/insert(end(), val);}//头插void push_front(const T& val){insert(begin(), val);}//尾删void pop_back(){erase(--end());}//头删void pop_front(){erase(begin());}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}private:Node* _head;};
