波奇学C++:stl的list模拟实现

list是双向带头链表。所以迭代器end()相当于哨兵卫的头。

list不支持+和[]重载，原因在于list空间不是连续的，+和[]的代价比较大。

访问第n个节点，只能用for循环，++来实现

list<int> l;
l.push_back(0);
l.push_back(1);
l.push_back(2);
l.push_back(3);
auto li=l.begin();
//访问第3个节点
for(size_t i=0;i<3;i++)
{li++;
}

list的insert不会失效，但是erase会迭代器失效。

list是双向迭代器

迭代器可以简单分为：单向迭代器(forward)++，双向迭代器(bidirectional) ++/-- 随机迭代器(random acess)+/-/++/--

不同的数据结构的迭代器决定了可以使用不同的算法。其中随机迭代器代器的范围最广，可以用的算法最多。

std:sort只能是随机迭代器用，list不能使用，list也有自己的sort算法但是效率并不高。

list实现

大概思路先不考虑迭代器，链表分为两个类，一个类表示节点，另外一个类表示链表。

节点模板类

template<class T>struct list_node{list_node<T>* _next;list_node<T>* _prev;T _val;list_node(const T& val = T()):_next(nullptr),_prev(nullptr),_val(val){}};

这里有个注意的点，模板类的类名不是类型，list_node只是类名，不是对应的自定义类型，所以是

list_node<T>* _next;而不是list_node* _next。

编译器优化 

拷贝构造写类名也可以

模拟实现的代码

namespace my_list
{template<class T> struct list_node{list_node<T>* _prev;list_node<T>* _next;T _val;list_node(const T& val=T()):_next(nullptr),_prev(nullptr),_val(val){}};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;}self& operator++(){_node = _node->_next;return *this;}self& operator--(){_node = _node->_prev;return *this;}bool operator!=(const self& it){return _node != it._node;}self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}Ptr operator->(){return &_node->_val;}};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; }iterator end(){return _head;}const_iterator const_begin(){return _head->_next;}const_iterator const_end(){return _head;}void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;}list(){empty_init();}~list(){clear();delete _head;_head = nullptr;}list(const list<T>& lt){empty_init();for (auto& e : lt){push_back(e);} }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(){clear();delete _head;_head = nullptr;}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_begin(){erase(begin());}iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;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 clear(){iterator it = begin();while (it != end()){it=erase(it);}}size_t size(){size_t sz = 0;iterator it = begin();while (it != end()){sz++;}return sz;}private:Node* _head;Node* _tail;};
}