【C++进阶(五)】STL大法--list模拟实现以及list和vector的对比

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

template<class T>
class List
{
  typedef list_node<T> node;
public:
  List()
  {
    _head = new node;
    _head->_next=_head;
    _head->_prev=_head;
  }
private:
  node* _head;
}

void emptyinit()//创建并初始化哨兵位的头节点,方便给构造和拷贝构造复用
  {
    _head = new node;
    _head->_next = _head;
    _head->_prev = _head;
  }
template<class InputTterator>//有参的构造
List(InputTterator first, InputTterator last)
{
  emptyinit();
  while (first != last)
  {
    push_back(*first);
    first++;
  }
}

void clear()//清空数据,除了头节点
{
  iterator it = begin();
  while (it != end())
  {
    it = erase(it);//erase会返回下一个节点的迭代器
  }
}
~List()//_head也要被删除掉
{
  clear();
  delete _head;
  _head = nullptr;
}

//lt2(lt1)
List(const List<T>& lt)//完成深拷贝
{
  emptyinit();
  List<T> tmp(lt.begin(), lt.end());//用lt1的迭代器区间去构造一下tmp
  ::swap(_head, tmp._head);
}

template<class T>
struct __list_iterator
{
  typedef list_node<T> node;
  typedef __list_iterator iterator;
  node* _node;
}

__list_iterator(node* nnode)
  :_node(nnode)
  {}

iterator& operator++()//前置++
{
  _node = _node->_next;
  return *this;
}
iterator& operator++(int)//后置++
{
  iterator tmp = *this;
  _node = _node->_next;
  return tmp;
}
iterator& operator--()//前置--
{
  _node = _node->_prev;
  return *this;
}
iterator& operator--(int)//后置--
{
  iterator tmp = *this;
  _node = _node->_prev;
  return tmp;
}

bool operator!=(const iterator& it)const
{
  return _node != it._node;
}
bool operator==(const iterator& it)const
{
  return _node == it._node;
}

//可读可写
T& operator*()
{
  return _node->_data;
}
//可读可写
T* operator->()
{
  return &(operator*());
}

return &(_node->_data);

template<class T>
class List
{
  typedef list_node<T> node;
  typedef __list_iterator<T> iterator;
private:
  node* _head;

iterator begin()
{
  //iterator tmp(_head->_next);
  //return tmp;
  return iterator(_head->_next);//使用了匿名对象
}
iterator end()
{
  //iterator tmp(_head);
  //return tmp;
  return iterator(_head);
}

template<class T, class Ref, class Ptr>
struct __list_iterator//迭代器不需要析函数
{
  typedef list_node<T> node;
  typedef __list_iterator iterator;
  node* _node;
}

//按模板参数来
Ref operator*()
{
  return _node->_data;
}
Ptr operator->()
{
  return &(operator*());
}

template<class T>
class List
{
  typedef list_node<T> node;
  typedef __list_iterator<T, T&, T*> iterator;
  typedef __list_iterator<T, const T&, const T*> const_iterator;
private:
  node* _head;
}

const_iterator begin()const
{
  return const_iterator(_head->_next);
}
iterator begin()
{
  return iterator(_head->_next);//使用了匿名对象
}
const_iterator end()const
{
  return const_iterator(_head);
}
iterator end()
{
  return iterator(_head);
}

void print_list(const list<int>& lt)
{
  auto it = lt.begin();
  while (it != lt.end())
  {
    //*it = 10;
    cout << *it << " ";
    ++it;
  }
  cout << endl;
}