list的模拟实现

1.结构

2.用3个类实现list

3.单个节点的定义

4.迭代器的定义

5.list类的实现

6.vector与list的区别

1.结构

list底层是一个带头双向循环链表

2.用3个类实现list

1.链表中的单个节点

2.迭代器

3.list

由于链表中的迭代器已经不是原生指针，所以将迭代器单独封装成一个类。

list的迭代器是双向迭代器，不能够像string和vector那样的随机迭代器那样可以+3 -3，只能够++和--

3.单个节点的定义

template<class T>
class listnode
{
public:T _data;listnode<T>* _prev;listnode<T>* _next;listnode(const T& x = T()):_data(x),_prev(nullptr),_next(nullptr){}};

4.迭代器的定义

//Ref是T的引用但不知道是不是const迭代器,所以写成模版的形式
//Ptr是T的指针但不知道是不是const迭代器,所以写成模版的形式
//这样就不用单独写一个const迭代器了
template<class T, class Ref, class Ptr>
class list_iterator
{
public:typedef listnode<T> Node;typedef list_iterator<T, Ref, Ptr> Self;Node* _node;//这里的构造函数是为了一会方便提供list类里的begin和end的接口//begin和end接口写在list类里是因为：在List类里才有真正的链表结构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--(){_node = _node->_prev;return *this;}Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}Self& operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const Self& s) const{return _node != s._node;}bool operator==(const Self& s) const{return _node == s._node;}};

5.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;//构造哨兵位头结点List(){_head = new Node;_head->prev = _head;_head->next = _head;_size = 0;}iterator begin(){//隐式类型转换，利用迭代器类里的构造函数return _head->next;}iterator end(){//隐式类型转换return _head;}const_iterator begin() const{//隐式类型转换return _head->next;}const_iterator end() const{//隐式类型转换return _head;}void push_back(const T& x){/*Node* newnode = new Node(x);Node* prev = _head->_prev;Node* cur = _head;newnode->_prev = prev;newnode->_next = cur;prev->_next = newnode;cur->_prev = newnode;*/insert(end(), x);}void insert(iterator pos, const T& x){Node* prev = pos->_prev;Node* cur = pos;Node* newnode = new Node(x);newnode->_prev = prev;newnode->_next = cur;prev->_next = newnode;cur->_prev = newnode;_size++;}//返回被删除元素的下一个元素的迭代器，防止迭代器失效iterator erase(iterator pos){Node* prev = pos->_prev;Node* next = pos->_next;prev->_next = next;next->_prev = prev;delete pos;_size--;return next;}//拷贝构造List(const List<T>& s1){_head = new Node;_head->prev = _head;_head->next = _head;_size = 0;for (auto s : s1){push_back(s);}}void swap(List<T> sl){std::swap(_head, sl._head);std::swap(_size, sl._size);}List<T>& operator=(List<T> s1){swap(s1);return *this;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}~List(){clear();delete _head;_head = nullptr;}int size() const{return _size;}bool empty() const{return _size == 0;}private:Node* _head;int _size;
};