List源码模拟与分析

//结点类
  template<class T>
  struct list_node
  {
    list_node<T>* _prev;//声明类型
    list_node<T>* _next;
    T _data;
    list_node(const T& val = T())
      //用const引用匿名对象的话会延长生命周期
      :_prev(nullptr)
      ,_next(nullptr)
      ,_data(val)
    {
    }
  };

//迭代器类,其实就是对原生指针进行封装
  //模拟指针
  template<class T, class Ref,class Ptr >
  struct _list_iterator
  {
    typedef list_node<T> node;
    typedef _list_iterator<T,Ref,Ptr> self;
    //这里为什么要定义一个self呢
    //这是因为后面的迭代器在++ --
    //等运算的时候返回的是迭代器
    node* _node;
    _list_iterator(node* p)
      :_node(p)
    {
    }
    Ref operator*()//我们的迭代器是可以解引用的
      //得到的是data
    {
      return _node->_data;
    }
    Ptr operator->()//不重载const迭代器
    {
      return &_node->_data;
    }
    self& operator++()
    {
      _node = _node->_next;
      return *this;
    }
    self& operator--()
    {
      _node = _node->_prev;
      return *this;
    }
    self& operator++(int)
    {
      //后置++，先用在++
      self tmp(*this);
      _node = _node->_next;
      return tmp;
    }
    //加int是为了区分
    //因为前置和后置的运算符一样
    //语法规定加int是后置++
    self& operator--(int)
    {
      //后置--
      self tmp(*this);
      _node = _node->_prev;
      return tmp;
    }
    bool operator!=(const self& s)
      //比较的是相同类型的指针
    {
      return _node != s._node;
    }
    bool operator==(const self& s)
    {
      return _node == s._node;
    }
  };

//list源码本身是一个带头双向循环链表
  //但是list的核心还有一个是迭代器的封装，迭代器类
  template<class T>
  class list
  {
    typedef list_node<T> node;
    //这里其实就已经声明了结点类的类型了
    //对结点类的模板的结点类型重命名
  public:
    typedef _list_iterator<T,T&,T*> iterator;
    //这里其实就已经声明了结点类的类型了
    //对迭代器类的模板的迭代器类型重命名
    /*typedef const  _list_iterator const_iterator;*/
    //对const迭代器类的模板的迭代器类型重命名
    //但是这是错误的，因为我们这是修饰的是迭代器不能修改
    typedef  _list_iterator<T, const T&, const T*> const_iterator;
    iterator begin()
    {
      return iterator(_head->_next);
    }
    const_iterator begin() const
    {
      return const_iterator(_head->_next);
    }
    iterator end()
    //指向尾部节点的下一个节点
    //那么就是头结点
    {
      return iterator(_head);
    }
    const_iterator end() const
      //const对象返回const迭代器
    {
      return const_iterator(_head);
    }
    //迭代器区间构造list
    //函数模板
    template<class iterator>
    list(iterator first,iterator last)
    {
      empty_init();
      while (first != last)//重载了迭代器
      {
        push_back(*first);
        ++first;
      }
    }
    list()
      //无参构造
    {
      //指向自己
      /*_head = new node;
      _head->_next = _head;
      _head->_prev = _head;*/
      empty_init();
    }
    void swap(list<T>& tmp)
    {
      std::swap(_head,tmp->_head);
    }
    //拷贝构造
    list(const list<T>& it)
    {
      empty_init();
      list<T> tmp(it.begin(),it.end());
      swap(tmp);
    }
    //重载list链表运算符=
    list<T>& operator=(list<T> val)
      //传值，我们不改变他，不过这里传值的时候
      //去调用了拷贝构造，而我们的节点都是new出来的
      //其实这就说明了我们的传值过来数据已经在堆上了
      //所以要注意
      //但是因为已经创建好了对象，那么可以把头结点
      //连接到新链表上
    {
      swap(val);
      return *this;
    }
    void empty_init()
    {
      _head = new node;
      _head->_next = _head;
      _head->_prev = _head;
    }
    void push_back(const T& val)
    {
      /*node* tail = _head->prev;
      node* new_node = new node;
      tail->next = new_node;
      new_node->prev = tail
      new_node->next = _head;
      _head->prev = new_node;*/
      insert(end(),val);
    }
    void push_front(const T& val)
    {
      insert(begin(),val);
    }
    void pop_back()
    {
      erase(--end());
    }
    void pop_front()
    {
      erase(begin());
    }
    void insert(iterator pos, const T& val)
      //用迭代器进行插入
      //在pos位置之前插入,需要存下地址
    {
      node* cur = pos._node;
      node* prev = cur->_prev;//找到pos位置之前的节点
      node* new_node = new node(val);
      prev->_next = new_node;
      new_node->_prev = prev;
      new_node->_next = cur;
      cur->_prev = new_node;
    }
    void erase(iterator pos)
      //删除pos位置的节点
    {
      assert(pos != end());
      node* cur = pos._node;//节点类是在封装迭代器类里
      node* prev = pos._node->_prev;
      node* next = pos._node->_next;
      prev->_next = next;
      next->_prev = prev;
      delete cur;
    }
    ~list()
    {
      clear();
      delete _head;
      _head = nullptr;
    }
    void clear()
      //不用const
      //const的对象的const的迭代器
      //指的是迭代器里的内容不能修改
      //也就不能去释放
    {
      iterator it = begin();
      while (it != end())
      {
        erase(it++);
      }
    }
    void print_list()
    {
      node* cur = _head;
      while (cur->_next != _head)
      {
        std::cout << cur->_next->_data<<" ";
        cur = cur->_next;
      }
      std::cout << std::endl;
    }
  private:
    node* _head;
  };
}

template<class T>
  struct list_node
  {
    list_node<T>* _prev;//声明类型
    list_node<T>* _next;
    T _data;
    list_node(const T& val = T())
      //用const引用匿名对象的话会延长生命周期
      :_prev(nullptr)
      ,_next(nullptr)
      ,_data(val)
    {
    }
  };
  //迭代器类,其实就是对原生指针进行封装
  //模拟指针
  template<class T, class Ref,class Ptr >
  struct _list_iterator
  {
    typedef list_node<T> node;
    typedef _list_iterator<T,Ref,Ptr> self;
    //这里为什么要定义一个self呢
    //这是因为后面的迭代器在++ --
    //等运算的时候返回的是迭代器
    node* _node;
    _list_iterator(node* p)
      :_node(p)
    {
    }
    Ref operator*()//我们的迭代器是可以解引用的
      //得到的是data
    {
      return _node->_data;
    }
    Ptr operator->()//不重载const迭代器
    {
      return &_node->_data;
    }
    self& operator++()
    {
      _node = _node->_next;
      return *this;
    }
    self& operator--()
    {
      _node = _node->_prev;
      return *this;
    }
    self& operator++(int)
    {
      //后置++，先用在++
      self tmp(*this);
      _node = _node->_next;
      return tmp;
    }
    //加int是为了区分
    //因为前置和后置的运算符一样
    //语法规定加int是后置++
    self& operator--(int)
    {
      //后置--
      self tmp(*this);
      _node = _node->_prev;
      return tmp;
    }
    bool operator!=(const self& s)
      //比较的是相同类型的指针
    {
      return _node != s._node;
    }
    bool operator==(const self& s)
    {
      return _node == s._node;
    }
  };
  //list源码本身是一个带头双向循环链表
  //但是list的核心还有一个是迭代器的封装，迭代器类
  template<class T>
  class list
  {
    typedef list_node<T> node;
    //这里其实就已经声明了结点类的类型了
    //对结点类的模板的结点类型重命名
  public:
    typedef _list_iterator<T,T&,T*> iterator;
    //这里其实就已经声明了结点类的类型了
    //对迭代器类的模板的迭代器类型重命名
    /*typedef const  _list_iterator const_iterator;*/
    //对const迭代器类的模板的迭代器类型重命名
    //但是这是错误的，因为我们这是修饰的是迭代器不能修改
    typedef  _list_iterator<T, const T&, const T*> const_iterator;
    iterator begin()
    {
      return iterator(_head->_next);
    }
    const_iterator begin() const
    {
      return const_iterator(_head->_next);
    }
    iterator end()
    //指向尾部节点的下一个节点
    //那么就是头结点
    {
      return iterator(_head);
    }
    const_iterator end() const
      //const对象返回const迭代器
    {
      return const_iterator(_head);
    }
    //迭代器区间构造list
    //函数模板
    template<class iterator>
    list(iterator first,iterator last)
    {
      empty_init();
      while (first != last)//重载了迭代器
      {
        push_back(*first);
        ++first;
      }
    }
    list()
      //无参构造
    {
      //指向自己
      /*_head = new node;
      _head->_next = _head;
      _head->_prev = _head;*/
      empty_init();
    }
    void swap(list<T>& tmp)
    {
      std::swap(_head,tmp->_head);
    }
    //拷贝构造
    list(const list<T>& it)
    {
      empty_init();
      list<T> tmp(it.begin(),it.end());
      swap(tmp);
    }
    //重载list链表运算符=
    list<T>& operator=(list<T> val)
      //传值，我们不改变他，不过这里传值的时候
      //去调用了拷贝构造，而我们的节点都是new出来的
      //其实这就说明了我们的传值过来数据已经在堆上了
      //所以要注意
      //但是因为已经创建好了对象，那么可以把头结点
      //连接到新链表上
    {
      swap(val);
      return *this;
    }
    void empty_init()
    {
      _head = new node;
      _head->_next = _head;
      _head->_prev = _head;
    }
    void push_back(const T& val)
    {
      /*node* tail = _head->prev;
      node* new_node = new node;
      tail->next = new_node;
      new_node->prev = tail
      new_node->next = _head;
      _head->prev = new_node;*/
      insert(end(),val);
    }
    void push_front(const T& val)
    {
      insert(begin(),val);
    }
    void pop_back()
    {
      erase(--end());
    }
    void pop_front()
    {
      erase(begin());
    }
    void insert(iterator pos, const T& val)
      //用迭代器进行插入
      //在pos位置之前插入,需要存下地址
    {
      node* cur = pos._node;
      node* prev = cur->_prev;//找到pos位置之前的节点
      node* new_node = new node(val);
      prev->_next = new_node;
      new_node->_prev = prev;
      new_node->_next = cur;
      cur->_prev = new_node;
    }
    void erase(iterator pos)
      //删除pos位置的节点
    {
      assert(pos != end());
      node* cur = pos._node;//节点类是在封装迭代器类里
      node* prev = pos._node->_prev;
      node* next = pos._node->_next;
      prev->_next = next;
      next->_prev = prev;
      delete cur;
    }
    ~list()
    {
      clear();
      delete _head;
      _head = nullptr;
    }
    void clear()
      //不用const
      //const的对象的const的迭代器
      //指的是迭代器里的内容不能修改
      //也就不能去释放
    {
      iterator it = begin();
      while (it != end())
      {
        erase(it++);
      }
    }
    void print_list()
    {
      node* cur = _head;
      while (cur->_next != _head)
      {
        std::cout << cur->_next->_data<<" ";
        cur = cur->_next;
      }
      std::cout << std::endl;
    }
  private:
    node* _head;
  };
}