【C++】list的模拟实现（下）-阿里云开发者社区

4. list的构造函数

在文章的最开始，我们为了让自己的list类能够跑起来，简易的实现了一个list的构造函数，现在我们对这个构造进行一个修改

我们在后面会经常用到空初始化，参照库里面的实现，我们也实现一个empty_initialize

void empty_initialize()
{
    _head = new node(T());
    _head->_next = _head;
    _head->_prev = _head;
}

接下来就要正式实现构造函数了

默认构造，默认构造的功能和我们刚刚实现的empty_initialize的功能刚好一模一样，所以直接复用即可。
指定值与长度的构造，首先复用empty_initialize，然后再尾插新元素即可，这里的尾插也可以复用push_back。
迭代器区间构造，同样的复用empty_initialize，然后遍历迭代器区间，尾插新元素。
对于拷贝构造，复用empty_initialize构造一个空链表，然后遍历参数中的链表，拿到每个元素依次尾插到空链表中（也可以使用现代写法：使用参数中链表的迭代器构造一个对象，然后使用swap交换临时对象和this指针指向的对象）

list()//默认构造
{
    empty_initialize();
}
list(size_t n, const T& val = T())//指定值与长度的构造
{
    empty_initialize();
    for (size_t i = 0; i < n; ++i)
    {
        push_back(val);
    }
}
template<class InputIterator>
list(InputIterator first, InputIterator last)//迭代器区间构造
{
    empty_initialize();
    while (first != last)
    {
        push_back(*first);
        ++first;
    }
}
list(const list<T>& lt)//拷贝构造的经典写法
{
    empty_initialize();
    for (const auto& e : lt)
    {
        push_back(e);
    }
}
void swap(list<T>& lt)//拷贝构造的现代写法
{
    std::swap(_head, lt._head);
}
list(const list<T>& lt)
{
    empty_initialize();
    list<T> tmp(lt.begin(), lt.end());
    swap(tmp);
}

5. 析构函数和赋值重载

关于默认的成员函数，现在还剩下析构函数和复制重载

1.赋值重载

和之前的vector一样，赋值重载也有经典写法和现代写法两种实现方式。

1. 经典写法

首先做一个判断，防止自己给自己赋值，这情况在经典写法下是致命的。然后清空this指向的list对象，然后遍历右操作数对象，然后尾插到this指向的对象。

list<T>& operator=(list<T>& lt)//经典写法
{
    if (this != *lt)//防止自己给自己赋值
    {
        clear();
        for (auto& e : lt)
        {
            push_back(e);
        }
    }
}

2. 现代写法

同样的通过传参的过程中，利用传值传参的方式调用拷贝构造，构造出一个形参lt，然后使用swap交换this指针和lt。

list<T>& operator=(list<T> lt)//现代写法
{
    swap(lt);
    return *this;
}

2.析构函数和clear

1. 析构函数

对于list，析构函数要做的事情就是释放list中的每个节点的空间，然后释放头节点的空间，这个功能让我们想到了clear函数，它的功能是释放除了头节点之外的所有节点，所以我们可以考虑在析构函数中复用clear函数，然后释放头节点的空间即可。

2. clear

对于clear删除节点，我们直接调用erase删除即可，可以删除任意位置节点，由于list结构的原因，任意位置的节点删除效率相同，所以可以任意删除，直到list为空为止。

bool empty()//这里顺手实现一下empty函数，当list中头尾节点都是自己的时候，就说明list已经空了。当_head的next或prev中的任意一个指向_head本身即可判定list已经空了。
{
    return _head->_next == _head;
}
void clear()
{
    while (!empty())
    {
        erase(--end());
    }
}
~list()
{
    clear();
    delete _head;
    _head = nullptr;
}

6.size

对于list的结构，按照我们之前实现过的情况，如果我们想知道list的元素个数，我们只能通过遍历计数得到，那么size的时间复杂度就是O(n)了，这样复杂度太高了，所以这里准备在list的成员变量中再增加一个size，表示元素个数。

class list
{
public:
    size_t size()
    {
        return _size;
    }
private:
    node* _head;
    size_t _size;
}

增加这个成员变量之后，我们整个结构中可能要大改了，要增加size的初始化和操作

这个时候，我们复用的优点就显现出来了，由于所有的构造我们都复用了empty_initialize，所有的插入都复用了insert，删除都复用了erase，所以只需要更改empty_initialize，insert，erase中的实现即可，这就是代码复用的有点：提高了代码后期的可维护性

7. 数据操作

1.inset

首先，我们首先insert，这个是整个list中需要实现插入操作都要复用的函数，所以非常重要。

首先new出来一个存放执行值的节点，然后将这个节点连接到list的指定位置上，insert操作就完成啦。当然insert之后，迭代器就失效了，所以我们要返回指向newnode节点的迭代器。别忘了++_size

iterator insert(iterator pos, const T& val = T())
{
    node* newnode = new node(val);
    //   prev   newnode   cur
    node* prev = pos._pnode->_prev;
    node* cur = pos._pnode;
    prev->_next = newnode;
    newnode->_prev = prev;
    newnode->_next = cur;
    cur->_prev = newnode;
    ++_size;
    return iterator(newnode);
}

2.push_front和push_back

这两个接口都是可以复用insert的，只是传入插入的位置不同，我们直接指定插入位置即可

由于insert是在pos位置之前插入，所以这里注意一下，end返回的是最后一个元素的下一个位置，所以push_back穿的位置为end即可。

void push_back(const T& val = T())
{
    insert(end(), val);
}
void push_front(const T& val = Y())
{
    insert(begin(), val);
}

3.erase

找到pos位置的前后两个节点，然后将两个节点连接起来，最后释放pos指向的节点即可。注意别忘了–_size

iterator erase(iterator pos)
{
    assert(pos != end());
    node* prev = pos._pnode->_prev;
    node* next = pos._pnode->_next;
    //prev    cur    next
    prev->_next = next;
    next->_prev = prev;
    delete pos._pnode;
    --_size;
    return iterator(next);
}

4.pop_back和pop_front

这里复用erase即可

void pop_back()
{
    erase(--end());
}
void pop_front()
{
    erase(begin());
}

5.resize

resize的实现原则和vector类似。但是对于list只有两种情况

当n小于size时，尾删节点直到size==n
当n大于size时，尾插节点直到size==n

void resize(size_t n, const T& val = T())
{
    while (n < size())
    {
        pop_back();
    }
    while (n > size())
    {
        push_back(val);
    }
}

6.整体代码

最后，附上整体的代码

#pragma once
#include <utility>
namespace my
{
  template<class T>
  struct __list_node//这是一个list的节点类模板
  {
    __list_node* _prev;
    __list_node* _next;
    T _data;
    __list_node(const T& data = T())//__list_node的默认构造函数
      :_data(data)
      , _prev(nullptr)
      , _next(nullptr)
    {}
  };
  template<class T, class Ref, class Ptr>
  struct __list_iterator
  {
    typedef __list_node<T> node;//重命名节点类
    typedef __list_iterator<T, Ref, Ptr> Self;
    node* _pnode;//迭代器的成员变量就是结点指针
    __list_iterator(node* p)//迭代器的构造函数
      :_pnode(p)
    {}
    Ptr operator->()
    {
      return &operator*();
    }
    Ref operator*()//重载*，作用是返回指向的节点的元素值
    {
      return _pnode->_data;
    }
    Self& operator++()//重载++，作用是将迭代器自增1
    {
      _pnode = _pnode->_next;
      return *this;
    }
    Self operator++(int)
    {
      Self tmp(*this);
      _pnode = _pnode->_next;
      return tmp;
    }
    Self& operator--()
    {
      _pnode = _pnode->_prev;
      return *this;
    }
    Self operator--(int)
    {
      Self tmp(*this);
      _pnode = _pnode->_prev;
      return tmp;
    }
    bool operator!=(const Self& it)
    {
      return _pnode != it._pnode;
    }
    bool operator==(const Self& it)
    {
      return _pnode == it._pnode;
    }
  };
  template<class T>
  class list//这是一个list类，其中的成员变量只有一个头节点。
  {
    typedef __list_node<T> node;
  public:
    typedef __list_iterator<T, T&, T*> iterator;//普通迭代器
    typedef __list_iterator<T, const T&, const T*> const_iterator;//const迭代器
    //typedef __list_const_iterator<T> const_iterator;//const迭代器
    iterator begin()
    {
      return _head->_next;
    }
    iterator end()
    {
      return _head;
    }
    const_iterator begin() const
    {
      return _head->_next;
    }
    const_iterator end() const
    {
      return _head;
    }
    void empty_initialize()
    {
      _head = new node(T());
      _head->_next = _head;
      _head->_prev = _head;
      _size = 0;
    }
    list()
    {
      empty_initialize();
    }
    list(size_t n, const T& val = T())
    {
      empty_initialize();
      for (size_t i = 0; i < n; ++i)
      {
        push_back(val);
      }
    }
    template<class InputIterator>
    list(InputIterator first, InputIterator last)
    {
      empty_initialize();
      while (first != last)
      {
        push_back(*first);
        ++first;
      }
    }
    //list(const list<T>& lt)//经典写法
    //{
    //    empty_initialize();
    //    for (const auto& e : lt)
    //    {
    //        push_back(e);
    //    }
    //}
    void swap(list<T>& lt)
    {
      std::swap(_head, lt._head);
    }
    list(const list<T>& lt)//现代写法
    {
      empty_initialize();
      list<T> tmp(lt.begin(), lt.end());
      swap(tmp);
    }
    list<T>& operator=(list<T>& lt)//经典写法
    {
      if (this != *lt)//防止自己给自己赋值
      {
        clear();
        for (auto& e : lt)
        {
          push_back(e);
        }
      }
    }
    //list<T>& operator=(list<T> lt)//现代写法
    //{
    //  swap(lt);
    //  return *this;
    //}
    bool empty()
    {
      return _head->_next == _head;
    }
    void clear()
    {
      while (!empty())
      {
        erase(--end());
      }
    }
    ~list()
    {
      clear();
      delete _head;
      _head = nullptr;
    }
    void push_back(const T& val = T())
    {
      insert(end(), val);
    }
    void push_front(const T& val = Y())
    {
      insert(begin(), val);
    }
    iterator insert(iterator pos, const T& val = T())
    {
      node* newnode = new node(val);
      //   prev   newnode   cur
      node* prev = pos._pnode->_prev;
      node* cur = pos._pnode;
      prev->_next = newnode;
      newnode->_prev = prev;
      newnode->_next = cur;
      cur->_prev = newnode;
      ++_size;
      return iterator(newnode);
    }
    size_t size()
    {
      return _size;
    }
    iterator erase(iterator pos)
    {
      assert(pos != end());
      node* prev = pos._pnode->_prev;
      node* next = pos._pnode->_next;
      //prev    cur    next
      prev->_next = next;
      next->_prev = prev;
      delete pos._pnode;
      --_size;
      return iterator(next);
    }
    void pop_back()
    {
      erase(--end());
    }
    void pop_front()
    {
      erase(begin());
    }
    void resize(size_t n, const T& val = T())
    {
      while (n < size())
      {
        pop_back();
      }
      while (n > size())
      {
        push_back(val);
      }
    }
  private:
    node* _head;
    size_t _size;
  };
}

【C++】list的模拟实现（下）