C++中list各种基本接口的模拟实现

一、基本框架

        这里我们使用三个类，分别实现链表节点本身、迭代器的构建以及各种接口的实现与提供

二、难点

        因为我们的链表在内存中不是连续存储的，所以不能够使用原生指针作为迭代器，所以需要单独封装一个类，来实现迭代器比如解引用、++、--、->、！=等运算符的重载，其实就是将原生指针版迭代器的各种运算符重载使其能够支持类

        在一个就是关于iterator和const_iterator的实现问题，比较简单的方法可以是先实现一个iterator，在复制一份，将其中的解引用和箭头更改为const版本；但翻阅原码可以发现原码以一种类模版的方式实现：即让编译器生成对应的类。两种方法在效率上没有区别，但第二种相对更加简洁。

三、还有一个可以注意一下的小点是struct默认是公有，class默认是私有，因此迭代器作为非常常用的类可以将它写为struct，访问更加方便

using namespace std;
//list就是带头双向循环链表
//链表在空间上的存储是不连续的，不能使用原生指针作为迭代器
namespace wjl
{template <class T>class list_node{public:T _data;list_node<T>* _next;list_node<T>* _prev;list_node(const T& data = T()): _data(data), _next(nullptr), _prev(nullptr){}};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->_data;}Ptr operator->(){return &_node->_data;}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& s){return _node != s._node;}};template <class T>class list{typedef list_node<T> Node;public://这里原码所采取的方式是提供类模版给编译器，让编译器生成两个类/*typedef list_iterator<T> iterator;typedef list_const_iterator<T> const_iterator;*///这里就是编译器的写法：用类模版实例化出不同的迭代器类型，本质是模版复用实例化typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;//这里将哨兵位后第一个节点视为头结点iterator begin(){//最传统的写法iterator it(_head->_next);return it;}const_iterator begin() const{return _head->_next;}//这里将哨兵位视为尾节点iterator end(){//单参数构造函数支持隐式类型转换return _head;//或者采用匿名结构体//return iterator(_head);}const_iterator end() const{return _head;}void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(const list<T>& lt){empty_init();for (auto& e : lt){push_back(e);}}list(initializer_list<int> lt){empty_init();//这里范围for不知道lt类型一定要用别名for (auto& e : lt){push_back(e);}}~list(){clear();delete _head;_head = nullptr;cout << "~list()" << endl;}void clear(){auto it = begin();while (it != end()){it = erase(it);//这里it就是下一个位置的迭代器}}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;}void push_back(const T& x){////通过_head找到尾节点//Node* newnode = new Node(x);//这里前面的list_node要写构造函数，否则编译器会将其视为类型转换////_head->_prev->_next = newnode;//newnode->_prev = _head->_prev;//newnode->_next = _head;//_head->_prev = newnode;//++_size;insert(end(), x);}void push_front(const T& x){insert(begin(), x);}iterator insert(iterator pos, const T& x){//在pos之前插入Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);newnode->_prev = prev;newnode->_next = cur;prev->_next = newnode;cur->_prev = newnode;_size++;return newnode;}iterator erase(iterator pos){assert(pos != end());Node* next = (pos._node)->_next;Node* prev = (pos._node)->_prev;prev->_next = next;next->_prev = prev;delete pos._node;_size--;return next;}void pop_back(){erase(--end());}void pop_front(){erase(begin());}int size() const{return _size;}bool empty() const{return _size == 0;}private://这里的头结点就是哨兵位，不放数据。Node* _head;int _size;};