//List 链表实现

#include <iostream>

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

namespace UC
{
  template<class T>
  struct list_node
  {
  	list_node<T>* _next;
    list_node<T>* _prev;
    T _val
    list_nod(const T& val = T())
      :_val(val)
    {}
  };
  
  template<class T, class Ref, class Ptr>
  struct _list_iterator
  {
  	typedef list_node<T> Node;
    typedef _list_iterator<T, T&, T*> iterator;
    typedef _list_iterator<T, const T&, const T*> const_iterator;
    typedef _list_iterator<T, Ref, Ptr> 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 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 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<T>& It)
    {
    	init_list();
      for(auto& e : It)
      {
      	push_back(e);
      }
    }
    void swap(const list<T>& It)
    {
    	std :: swap(_head, It._head);
      std :: swap(_size, It._size)；
    }
    //拷贝构造
    list<T>&(const list<T> 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 <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <stdlib.h>

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

void test_OP()
{
	srand(time(0));
  const int N = 500000;
  
  vector<int> v;
  
  list<int> It;
  
  for(size_t i = 0; i < N; i++)
  {
  	auto e = rand();
    
    v.push_back(e);
    
    It.push_back(e);
  }
  
  //vector<int> 排序
  int begin1 = clock();
  sort(v.begin(), v..end());
  int end1 = clock();
  
  //list<int> 排序
  int begin2 = clock();
  It.sort();
  int end2 = clock();
  
  cout << "verctor sort :> " << end1 - begin1 << endl;
  cout << "list sort :> " << end2 - begin2 << endl;
}

int main()
{
  test_OP();
	return 0;
}