C++之list类的代码及其逻辑详解 （下）
1.iterator
首先我们typedef两个迭代器。
typedef _list_iterator iterator;typedef _list_iterator const_iterator;2. begin()
为什么要两个begin呢？这是因为当对象是 const 常量时，只能调用 const 成员函数。这个版本的 begin() 被声明为 const，保证了在常量对象上也能获取迭代器。
iterator begin(){return _head->_next;}const_iterator begin() const{return _head->_next;}3. end()
end函数的作用是返回哨兵头结点。
返回这个节点是因为end在设计的时候是被说明指向最后一个的下一个，所以在这里指向头结点。
这样设计还有三个好处：
- 无需区分空链表和非空链表的边界判断
- 遍历循环可以统一写成
for (auto it = begin(); it != end(); ++it) - 插入 / 删除操作在首尾位置时不需要特殊处理
iterator end(){return _head;}const_iterator end() const{return _head;}3. empty_init()
这个函数并不是 C++ 标准库中的标准函数。这个是我为了方便创建出来的。
作用是初始化list。因为是双向循环链表，所以要这么初始化。
void empty_init(){_head = new Node;_head->_prev = _head;_head->_next = _head;}4. 构造函数
这个是构造函数，就是利用我前面写的empty_init()来进行构造。
list(){empty_init();}5. 拷贝构造函数
拷贝构造函数用于创建一个新链表作为另一个链表的副本。他存在的目的是为了防止浅拷贝，首先通过 empty_init()来创建一个链表，然后通过范围for来把原链表（it）的值交给this指针指向的新链表。
PS:注意原链表中的值不会消失。
list(const list& it){empty_init();for (auto& e : it){push_back(e);}}6. swap()
就是通过系统自带的swap来实现两个链表的交换，
通过交换两个链表的哨兵头结点来实现链表的交换。
void swap(list& it){std::swap(_head, it._head);}7. 析构函数
先调用clear()函数清理元素，接着释放哨兵头结点。
~list(){clear();delete _head;_head = nullptr;}8. clear()
通过迭代器来把链表里面的元素删除。
void clear(){iterator it = begin();while (it != end()){it = erase(it);}}9. push_back()
这个就是调用insert()把x插入到链表的最后面。
PS：end是最后一个的下一个。所以是插入到end的前面。
void push_back(const T& x){insert(end(), x);}10. insert()
创建一个newnode，然后把它插入到pos的前面，又因为是双向循环链表，所以需要用到prev和next。
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->_next = cur;cur->_prev = newnode;newnode->_prev = prev;return newnode;}11. push_front()
这个就是调用insert()把x插入到链表的开头。
void push_front(const T& x){insert(begin(), x);}12. erase()
通过改变前后节点的方式来把pos节点释放。
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;return next;}13. pop_back()
使用erase来抛出最后一个元素节点。
void pop_back(){erase(--end());}14.pop_front()
使用erase来抛出开头第一个元素节点。
void pop_front(){erase(begin());}15. size()
通过迭代器循环的方式来遍历链表，获得链表大小。
PS:在这里我们使用size_t是因为他没有负数，它的设计初衷就是专门用来表示 “非负的计数或大小”。
size_t size(){size_t sz = 0;iterator it = begin();while (it != end()){++sz;++it;}return sz;}16. print()
首先获得链表的大小，然后然后通过while循环来解引用it来实现打印。
这个函数会完整打印链表中的所有元素，实现 “全部打印” 的效果。
void print(iterator it){size_t sz = size();while (sz--){cout << *it << \" \";++it;}cout << endl;}17. 总结
到这里我们的list就已经讲解完毕了。下面是我实现的完整代码：
#pragma once#include#includeusing namespace std;namespace struggle{templatestruct list_node{list_node* _next;list_node* _prev;T _val;list_node(const T& val = T()):_next(nullptr), _prev(nullptr), _val(val){}};templatestruct _list_iterator{typedef list_node Node;typedef _list_iterator 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;}};templateclass list{typedef list_node Node;public:typedef _list_iterator iterator;typedef _list_iterator const_iterator;iterator begin(){return _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->_prev = _head;_head->_next = _head;}list(){empty_init();}list(const list& it){empty_init();for (auto& e : it){push_back(e);}}void swap(list& it){std::swap(_head, it._head);}list& operator=(list it){swap(it);return *this;}~list(){clear();delete _head;_head = nullptr;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}void push_back(const T& x){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->_next = cur;cur->_prev = newnode;newnode->_prev = prev;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;return next;}void print(iterator it){size_t sz = size();while (sz--){cout << *it << \" \";++it;}cout << endl;}size_t size(){size_t sz = 0;iterator it = begin();while (it != end()){++sz;++it;}return sz;}private:Node* _head;};}
