五、list结构的完善

上面我们对节点结构、正向与反向迭代器结构实现原理及注意点一一做了介绍，最后一步也是最重要的一步，那就是将list结构完善起来，实现list的功能。

1.构造函数

list的成员变量是一个节点类，在构造头节点时，需要将这单个头节点构造成一个双向循环链表；

//构造函数
list()
{
  _head = new Node;     //new一个节点出来
  _head->_prev = _head; 
  _head->_next = _head; //_prev 和 _next 同时指向了头结点，形成了双向循链表
}

2.拷贝构造

拷贝构造是用一个已有对象去构造出另一个对象，首先将待构造对象进行初始化，然后利用迭代器区间去构造一个和lt1一样的临时的tmp对象，再进行数据的交换，达到深拷贝的目的。

//拷贝构造 --- 现代写法 lt2(lt1)
list(const list<T>& lt)
{
  _head = new Node;
  _head->_prev = _head;
  _head->_next = _head;
  list<T> tmp(lt.begin(), lt.end());
  std::swap(_head, tmp._head);
}

3.迭代器区间构造

通过传过来的迭代器区间进行初始化

//迭代器区间构造
template<class IputIterator>
list(IputIterator first, IputIterator last)
{
  _head = new Node;
  _head->_prev = _head;
  _head->_next = _head;
  while (first != last)
  {
    push_back(*first);//尾插数据，会根据不同类型的迭代器进行调用
    ++first;
  }
}

4.用n个val构造

通过用n个val来对对象进行初始化，需要注意这里的T( )是一个匿名对象，作为val的缺省参数，因为我们并不知道传给val的是一个对象还是一个整形（或其他），给缺省参数的好处在于，对于自定义类型编译器会去调用自定义类型的构造函数来对val进行初始化，如果是内置类型，它也是有自己的构造函数

//我们常常对内置类型的定义是这样的
int i = 10;
//但其实也可以这样定义
int i = int(10);

//用n个val个构造              
list(int n, const T& val = T())                
{                          
  _head = new Node;
  _head->_prev = _head;
  _head->_next = _head;
  for (int i = 0; i < n; i++)
  {
    push_back(val);
  }
}

对于用n个val进行初始化和迭代器区间初始化，起初我是这样写的（为了和库一致），测试时却出现问题：非法的间接寻址

//迭代器区间初始化
template<class IputIterator>
list(IputIterator first, IputIterator last){...}
//用n个val初始化
list(size_t n, const T& val = T()) {...}   
//测试日期类
struct Date
{
  int _year;
  int _month;
  int _day;
  Date(int year = 1, int month = 1, int day = 1)
    :_year(year)
    , _month(month)
    , _day(day)
  {}
};
void test_list4()
{
  list<Date> lt1(5, Date(2022, 6, 21));//1
  for (auto e : lt1)
  {
    cout << e._year << "/" << e._month << "/" << e._day << endl;
  }
  cout << endl;
  list<int> lt2(5, 1);//2
  for (auto e : lt2)
  {
    cout << e << " ";
  }
  cout << endl;
}

5.赋值重载

//赋值重载 --- 现代写法 lt2 = lt1
list<T>& operator=(list<T> lt)
{
  std::swap(_head, lt._head);
  return *this;
}

6.析构函数

析构函数可以结合着erase函数看

~list()
{
  clear();
  delete _head;
  _head = nullptr;
}
void clear()
{
  iterator it = begin();
  while (it != end())
  {
    //写法1
    erase(it++); //it是一个正向迭代器，采用后置++传给erase
    //写法2
    iterator del = it++;
    delete del._node;
    //写法3
    iterator del = it++;
    erase(del);
  }
  _head->_prev = _head;
  _head->_next = _head;
}

7.迭代器的实现

在list类中，我们typedef了正向与反向迭代器，解释一下其目的及作用

//正向迭代器

typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;

//反向迭代器

typedef __list_reverse_iterator<iterator, T&, T*> reverse_iterator;
typedef __list_reverse_iterator<iterator, const T&, const T*>const_reverse_iterator;

list是一个类模板，参数列表是T类型（未知类型）正向与反向迭代器分别都有三个参数，在list内重命名相当于内嵌定义，显示传参，我们对迭代器中需要返回值的地方不能进行类型的准确判断，通过这种显示传参，确定了迭代器三个参数的基本对于类型。

对于正向迭代器，我们显示传参<T、T&、T*>如果是const迭代器，再重新typedef一个const迭代器；

对于反向迭代器，我们是需要正向迭代器去构造，所有显示传参就可以给到<iterator, T&, T*>

namespace mlg
{
    template<class T>
    class list
    {
      typedef ListNode<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 iterator(_head);//返回头节点
        }
        const_iterator begin()const
        {
          return const_iterator(_head->_next);//返回头节点的下一个结点
        }
        const_iterator end()const
        {
          return const_iterator(_head);//返回头节点
        }
        //反向迭代器
        typedef __list_reverse_iterator<iterator, T&, T*> reverse_iterator;
        typedef __list_reverse_iterator<iterator, const T&, const T*>const_reverse_iterator;
        reverse_iterator rbegin()
        {
          return reverse_iterator(end());   //返回正向迭代器的结束位置
          //return reverse_iterator(_head); //等价与正向迭代器的头节点
        }
        reverse_iterator rend()
        {
          return reverse_iterator(begin());        //返回正向迭代器的起始位置
          //return reverse_iterator(_head->_next); //等价于正向迭代器头节点的下一个结点
        }
        const_reverse_iterator rbegin()const
        {
          return const_reverse_iterator(end());   //返回正向迭代器的结束位置
          //return const_reverse_iterator(_head); //等价与正向迭代器的头节点
        }
        const_reverse_iterator rend()const
        {
          return const_reverse_iterator(begin());        //返回正向迭代器的起始位置
          //return const_reverse_iterator(_head->_next); //等价于正向迭代器头节点的下一个结点
        }
    };
}

8.增删查改

//头插
void push_front(const T& x)
{
  insert(begin(), x);
}
//尾插
void push_back(const T& x)
{
  /*
  Node* tail = _head->_prev;
  Node* newnode = new Node(x);
  tail->_next = newnode;
  newnode->_prev = tail;
  newnode->_next = _head;
  _head->_prev = newnode;
  */
  insert(end(), x);
}
//头删
void pop_front()
{
  erase(begin());
}
//尾删
void pop_back()
{
  erase(--end());
}
//在pos位置插入元素x
iterator insert(iterator pos, const T& x)
{
  Node* cur = pos._node;    
  Node* prev = cur->_prev;     
  Node* newnode = new Node(x); 
  prev->_next = newnode;      
  newnode->_prev = prev;
  newnode->_next = cur;
  cur->_prev = newnode;
  return iterator(newnode);//在pos位置插入返回的是新插入的节点位置
}
//在pos位置删除元素
iterator erase(iterator pos)
{
  assert(pos != end());
  Node* prev = pos._node->_prev;
  Node* next = pos._node->_next;
  delete pos._node;
  prev->_next = next;
  next->_prev = prev;
  return iterator(next);//返回的是删除pos位置节点的下一个节点
}

六、完整代码

1.ListNode.h

#pragma once
namespace mlg
{
  template<class T>
  struct ListNode
  {
    ListNode<T>* _prev;
    ListNode<T>* _next;
    T _data;
    ListNode(const T& data= T())
      :_prev(nullptr)
      ,_next(nullptr)
      ,_data(data)
    {}
  };
}

2.iterator.h

#pragma once
namespace mlg
{
  template<class T,class Ref,class Ptr>
  struct __list_iterator
  {
    typedef ListNode<T> Node;
    typedef __list_iterator<T, Ref, Ptr> self;
    typedef Ref reference;
    typedef Ptr pointer;
    Node* _node;
    __list_iterator(Node* x)
      :_node(x)
    {}
    Ref operator*()
    {
      return _node->_data;
    }
    Ptr operator->()
    {
      return &_node->_data;
    }
    //++it
    self& operator++()
    {
      _node = _node->_next;
      return *this;
    }
    //it++
    self operator++(int)
    {
      self tmp(*this);
      _node = _node->_next;
      return tmp;
    }
    //--it
    self& operator--()
    {
      _node = _node->_prev;
      return *this;
    }
    //it--
    self operator--(int)
    {
      self tmp(*this);
      _node = _node->_prev;
      return tmp;
    }
    bool operator==(const self& it)const
    {
      return _node == it._node;
    }
    bool operator!=(const self& it)const
    {
      return _node != it._node;
    }
  };
}

3.reverse_iterator.h

#pragma once
namespace mlg
{
    template<class Iterator,class Ref,class Ptr>
  class __list_reverse_iterator
  {
    typedef __list_reverse_iterator<Iterator, Ref, Ptr> self;
  public:
    __list_reverse_iterator(Iterator it)
      :_it(it)
    {}
    Ref operator*()
    {
      Iterator prev = _it;
      return *--prev;
    }
    Ptr operator->() {return &operator*();}
    //++it
    self& operator++()
    {
      --_it;
      return *this;
    }
    //it++
    self operator++(int)
    {
      self tmp(*this);
      _it--;
      return tmp;
    }
    //--it
    self& operator--()
    {
      ++_it;
      return *this;
    }
    //it--
    self operator--(int)
    {
      self tmp(*this);
      _it++;
      return tmp;
    }
    bool operator!=(const self& rit)const {return _it != rit._it;}
    bool operator==(const self& rit)const {return _it == rit._it;}
  private:
    Iterator _it;
  };
}

4.list.h

#pragma once
#include "ListNode.h"
#include "iterator.h"
#include "reverse_iterator.h"
namespace mlg
{
  template<class T>
  class list
  {
    typedef ListNode<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 iterator(_head);}
    const_iterator begin()const {return const_iterator(_head->_next);}
    const_iterator end()const {return const_iterator(_head);}
    //反向迭代器
    typedef __list_reverse_iterator<iterator, T&, T*> reverse_iterator;
    typedef __list_reverse_iterator<iterator, const T&, const T*> const_reverse_iterator;
    reverse_iterator rbegin() {return reverse_iterator(end());}
    reverse_iterator rend() {return reverse_iterator(begin());}
    const_reverse_iterator rbegin()const {return const_reverse_iterator(end());}
    const_reverse_iterator rend()const {return const_reverse_iterator(begin());}
    //构造函数
    list()
    {
      _head = new Node;     //new一个节点出来
      _head->_prev = _head; 
      _head->_next = _head; //_prev 和 _next 同时指向了头结点，形成了双向循链表
    }
    //用n个val个构造              
    list(int n, const T& val = T())                
    {                         
      _head = new Node;
      _head->_prev = _head;
      _head->_next = _head;
      for (int i = 0; i < n; i++)
      {
        push_back(val);
      }
    }
    //迭代器区间构造
    template<class IputIterator>
    list(IputIterator first, IputIterator last)
    {
      _head = new Node;
      _head->_prev = _head;
      _head->_next = _head;
      while (first != last)
      {
        push_back(*first);
        ++first;
      }
    }
    //拷贝构造 --- 现代写法 lt2(lt1)
    list(const list<T>& lt)
    {
      _head = new Node;
      _head->_prev = _head;
      _head->_next = _head;
      list<T> tmp(lt.begin(), lt.end());
      std::swap(_head, tmp._head);
    }
    //赋值重载 --- 现代写法 lt2 = lt1
    list<T>& operator=(list<T> lt)
    {
      std::swap(_head, lt._head);
      return *this;
    }
    ~list()
    {
      clear();
      delete _head;
      _head = nullptr;
    }
    void clear()
    {
      iterator it = begin();
      while (it != end())
      {
        erase(it++);
      }
      _head->_prev = _head;
      _head->_next = _head;
    }
    void push_front(const T& x){ insert(begin(), x); }
    void push_back(const T& x) { insert(end(), x);}
    void pop_front() {erase(begin());}
    void pop_back(){erase(--end());}
    //在pos位置插入元素x
    iterator insert(iterator pos, const T& x)
    {
      Node* cur = pos._node;
      Node* prev = cur->_prev;
      Node* newnode = new Node(x);
      prev->_next = newnode;
      newnode->_prev = prev;
      newnode->_next = cur;
      cur->_prev = newnode;
      return iterator(newnode);
    }
    //在pos位置删除元素
    iterator erase(iterator pos)
    {
      assert(pos != end());
      Node* prev = pos._node->_prev;
      Node* next = pos._node->_next;
      delete pos._node;
      prev->_next = next;
      next->_prev = prev;
      return iterator(next);
    }
  private:
    Node* _head;
  };
  void print_list(const list<int>& lt)
  {
    list<int>::const_iterator it = lt.begin();
    while (it != lt.end())
    {
      cout << *it << " ";
      ++it;
    }
    cout << endl;
  }
  void test_list5()
  {
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    list<int>::reverse_iterator rit = lt.rbegin();
    while (rit != lt.rend())
    {
      cout << *rit << " ";
      ++rit;
    }
    cout << endl;
  }
}

以上是对list模拟实现的全部结束，大家可以在.c文件下进行测试。如果存在任何问题，或者有不同的见解，大家可以直接在评论区提出来

【C++】STL——list模拟实现（2）