list底层实现细节

一、部分代码展示

#pragma once
#include<cassert>
namespace bit
{template<class T>struct ListNode{ListNode<T>* _prev;ListNode<T>* _next;T _data;ListNode(const T& val = T()):_prev(nullptr), _next(nullptr), _data(val){}};// 迭代器// 添加Ref Ptr是为了const迭代器能复用配普通迭代器代码template<class T, class Ref, class Ptr>struct ListIterator{typedef ListNode<T> Node;typedef ListIterator<T, Ref, Ptr> Self;Node* _node;ListIterator(Node* node):_node(node){}// 迭代器不能写析构，因为资源不是迭代器的，迭代器只是用来遍历的// *it 返回值（类）的引用//T& operator*()Ref operator*(){return _node->_data;}// it-> 返回值（类）的指针//T* operator->()Ptr operator->(){return &_node->_data;}// ++itSelf& 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){return _node != it._node;}bool operator==(const Self& it){return _node == it._node;}};// const迭代器//template<class T>//struct ListConstIterator//{//	typedef ListNode<T> Node;//	typedef ListConstIterator<T> Self;//	Node* _node;//	ListConstIterator(Node* node)//		:_node(node)//	{}//	// *it//	const T& operator*()//	{//		return _node->_data;//	}//	// it->//	const T* operator->()//	{//		return &_node->_data;//	}//	// ++it//	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)//	{//		return _node != it._node;//	}//	bool operator==(const Self& it)//	{//		return _node == it._node;//	}//};// 链表template<class T>class list{typedef ListNode<T> Node;typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T*> const_iterator;public:void emptyinit(){_size = 0;_head = new Node;_head->_next = _head;_head->_prev = _head;}list(){emptyinit();}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}list(const list<T>& l){emptyinit();for (auto& e : l){push_back(e);}}void swap(list<T>& l){std::swap(_head, l._head);std::swap(_size, l._size);}list<T>& operator=(list<T> l){swap(l);return *this;}~list(){clear();delete _head;_head = nullptr;}iterator begin(){return iterator(_head->_next);}iterator end(){// 匿名构造return iterator(_head);}// const iterator代表迭代器不能被修改，无法++ --  T* const p1// 后面加const代表迭代器指向的内容不能修改		  const T* p2	const_iterator begin() const{return iterator(_head->_next);}const_iterator end() const{// 匿名构造return iterator(_head);}void insert(iterator pos, const T& val){Node* newnode = new Node(val);Node* cur = pos._node;Node* prev = cur->_prev;newnode->_next = cur;newnode->_prev = prev;cur->_prev = newnode;prev->_next = newnode;_size++;}iterator erase(iterator pos){Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;_size--;return iterator(next);}void push_front(const T& val){insert(begin(), val);}void push_back(const T& val){insert(end(), val);}void pop_front(){erase(begin());}void pop_back(){erase(--end());}size_t size() const{return _size;}bool empty(){return _size == 0;}private:Node* _head;size_t _size;};
}