C++ ——>std :: list__链表解析

//List 链表实现

#include 

using std :: cout;
using std :: endl;

namespace UC
{
  template
  struct list_node
  {
  	list_node* _next;
    list_node* _prev;
    T _val
    list_nod(const T& val = T())
      :_val(val)
    {}
  };
  
  template
  struct _list_iterator
  {
  	typedef list_node Node;
    typedef _list_iterator iterator;
    typedef _list_iterator const_iterator;
    typedef _list_iterator Self;
    Node* _node;
    _list_iterator(Node* node)
      :_node(node)
    {}
    _list_iterator() {}
    _list_iterator(const iterator& x)
      :_node(x._node)
    {}
    Ref operator*()
    {
    	return _node->_val;
    }
    Ptr operator->()
    {
    	return &_node->_val;
    }
    Self& operator++()
    {
    	_node = _node->_next;
      
      return *this;
    }
    Seld operator++(int)
    {
    	Self tamp(*this);
      
      _node = _node->_next;
      
      return tamp;
    }
    Self& operator--()
    {
      _node = _node->_prev;
      
    	return *this;
    }
    Self operator--(int)
    {
      Self tamp(*this);
      
      _node = _node->_prev;
      
    	return tamp;
    }
    bool operator!=()
    {
    	return _node != _node->_val;
    }
    bool operator==()
    {
      return _node == _node->_val;
    }
  };
  
  template
	class list
  {
    typedef list_node Node;
    public:
    typedef _list_iterator iterator;
    typedef _list_iterator const_iterator;
    
    iterator begin()
    {
    	return iterator(_head->_next);
    }
    iterator end()
    {
    	return _head;
    }
    const_iterator begin() const
    {
      return const_iterator(_head->_prev);
    }
    const_iterator end() const
    {
    	return _head;
    }
    list()
    {
   		init_list();
    }
    list(const list& It)
    {
    	init_list();
      for(auto& e : It)
      {
      	push_back(e);
      }
    }
    void swap(const list& It)
    {
    	std :: swap(_head, It._head);
      std :: swap(_size, It._size)；
    }
    //拷贝构造
    list&(const list It)
    {
    	swap(It);
      
      return *this;
    }
		//接口实现
    //尾插
    void服务器托管网 push_back(const T& x)
    {
    	insert(end(), x);
    }
    //头插
    void push_front(const T& x)
    {
    	insert(begin(), x);
    }
    //尾删
    void pop_back()
    {
    	earse(--end());
    }
    //头删
    void pop_front()
    {
    	earse(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 = cur;
      
      ++_size;
      
      return newNode;
    }
    iterator earse(iterator pos)
    {
      assert(pos != end());
      Node* cur = pos._node;
    	Node* next = cur->_next;
      Node* Prev = cur->_prev;
      
      Prev->_next = next;
      next->_prev = Prev;
      
      --_size;
      
      return next;
    }
    size_t size() const
    {
    	return _size;
    }
    void init_list()
    {
    	_head = new Node;
      _head = _head->_next;
      _head = _head->_prev;
    }
    void clear()
    {
			iterator it = begin();
      while(it != end())
      	it = earse(it);
      
      _size = 0;
    }
    ~list()
    {
      clear();
      
      delete _head;
      _head = nullptr;
    }
    private:
    size_t _size;
    Node* _head;
  }
}

//测试
#include 
#include 
#include 
#include 
#include 

using std :: cout;
using std :: endl;
using std :: vector;
using std :: list;

void test_OP()
{
	srand(time(0));
  const int N = 500000;
  
  vector v;
  
  list It;
  
  for(size_t i = 0; i  排序
  int begin1 = clock();
  sort(v.begin(), v..end());
  int end1 = clock();
  
  //list 排序
  int begin2 = clock();
  It.sort();
  int end2 = clock();
  
  cout  "  "