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

1.list 底层

list为任意位置插入删除的容器，底层为带头双向循环链表

begin() 代表第一个结点，end()代表最后一个结点的下一个

2. list的模拟实现

1. list_node 类设计

template<class T>
  struct list_node
  {
    list_node<T>* _next;
    list_node<T>* _prev;
    T _data;
  };

C++中，Listnode作为类名，而next和prev都是类指针，指针引用成员时使用->，而对象引用成员时使用 .

通过显示实例化，将两个类指针指定类型为T

2. list类如何调用类型

Listnode 代表类型

Listnode 代表类名 + 模板参数才是类型

而_head 以及创建新节点前都需加上类型

3 .push_back(正常实现)

void push_back(const T&x)//尾插
        {
            node* newnode = new node(x);
            node* tail = _head->_prev;
            tail->_next = newnode;
            newnode->_prev = tail;
            newnode->_next = _head;
            _head->_prev = newnode;
        }

当我们想要创建一个节点时，需要调用node的构造函数

typedef list_node node ，node是由 list_node 类提供的

list_node(const T& x=T())//list类的构造函数
      :_next(nullptr)
      , _prev(nullptr)
      , _data(x)
    {
    }

最好在构造函数处提供全缺省，对于内置类型int可以使用0，但对于自定义类型来说就不可以，所以为了满足泛型的要求，使用匿名对象调用默认构造函数

4. 迭代器的实现

若在数组上有一个int类型的指针，解引用是int类型的数据，再++可以加载下一个位置，因为物理空间是连续的

同样若在链表上，解引用类型为 node，再++不能到下一个节点，因为物理空间不连续

所以构造迭代器通过封装节点的指针来进行构造 (后面会讲)

第一个模板参数T

创建一个_list_iterator的类，来实现迭代器功能

template<class T>
    struct _list_iterator
    {
        typedef list_node<T> node;
        typedef _list_iterator<T> self;
        node* _node;
        _list_iterator(node* n)
            :_node(n)
        {
        }
        T& operator*()//解引用 
        {
            return _node->_data;
        }
        _list_iterator<T>& operator++()//返回迭代器
        {
            _node = _node->_next;//指向下一个节点
            return *this;
        }
        bool operator!=(const self&s)
        {
            return _node != s._node;
        }
    };

在list类中，调用迭代器实现begin()和end()功能

typedef _list_iterator<T,T&,T*> iterator，

通过typedef 将_list_node类模板定义为iterator

iterator begin()
    {
      return iterator(_head->_next);//通过匿名对象访问第一个数据
    }
    iterator end()
    {
      return iterator(_head);//通过匿名对象访问最后一个数据的下一个
    }

在list类中实现begin()和end()，内部调用_list_node类的构造函数

const迭代器

假设第一个代表的是T * ，而第二个代表的 T * const，保护迭代器本身不可以被修改，而我们想要保护迭代器指向的内容不可被修改即 const T*

复制_list_iterator类中的内容，并将名字修改为const_list_iterator

只需修改*operator类型为cosnt T& ，说明解引用后的数据返回不能被修改

template<class T>
    struct _list_const_iterator
    {
        typedef list_node<T> node;
        typedef _list_const_iterator<T> self;
        node* _node;
        _list_const_iterator(node* n)
            :_node(n)
        {
        }
        const T& operator*()//解引用 
        {
            return _node->_data;
        }
        self& operator++()//前置++
        {
            _node = _node->_next;//指向下一个节点
            return *this;
        }
        self& operator++(int)//后置++
        {
            self ret = *this;
            _node = _node->_next;
            return ret;
        }
        self& operator--()//前置--
        {
            _node = _node->_prev;
            return *this;
        }
        self& operator--(int)//后置--
        {
            self ret = *this;
            _node = _node->_prev;
            return ret;
        }
        bool operator!=(const self& s)//!=
        {
            return _node != s._node;
        }
        bool operator==(const self& s)//==
        {
            return _node == s._node;
        }
    };

第二个模板参数Ref

迭代器和const迭代器只有 *operator 的返回值不同，只需在模板中添加一个参数即可使用一个迭代器实现迭代器和const 迭代器的功能

第三个模板参数Ptr

对于内置类型int使用解引用找到对应数据，而自定义类型需使用->寻找下一个节点

AA作为自定义类型，想要找到下一个节点需要使用->，在迭代器中重载 - >

it->_a1，实际上是 it->->_a1，

it->返回值为AA* ,再通过这个指针使用->指向_a1

但是为了增强可读性，省略了一个->

it->_a1 实际上为 it.operator->()->._a1

对list封装的理解

在不考虑封装的情况下，两者等价

从物理空间上来看，it与pnode都是指向1的地址

pnode作为一个原生指针，解引用指针就会拿到这个地址，找到这个地址指向空间的内容

++pnode，找到下一个节点的地址，但是下一个节点不一定是要的节点

*it 识别成为自定义类型就会调用函数

5. insert

void insert(iterator pos,const T&x)//在pos位置前插入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;
        }

6.push_back与 push_front(复用)

两者都可以通过复用 insert的方式实现

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 push_front(const T&x)//头插
        {
            insert(begin(), x);
        }

7. erase

void erase(iterator pos)//删除pos位置
        {
            //头节点不可以删除
            assert(pos != end());
            node* cur = pos._node;
            node* prev = cur->_prev;
            node* next = cur->_next;
            prev->_next = next;
            next->_prev = prev;
            delete cur;
        }

由于头节点不可以删除，所以使用assert断言的方式

8. pop_back与pop_front (复用)

                void pop_back()//尾删
        {
            erase(--end());
        }
        void pop_front()//头删
        {
            erase(begin());
        }

9. clear 清空数据

void clear()//清空数据
            //但是要注意不要把head清掉
        {
            iterator it = begin();
            while (it != end())
            {
                it=erase(it);//为了防止迭代器失效设置返回值
                 //返回值为当前节点的下一个
            }
        }

迭代器失效是指迭代器所指向的节点失效即节点被删除了

erase函数执行后，it所指向的节点被删除，因此it无效，在下一次使用it时，必须先给it赋值

为了防止迭代器失效所以使erase设置返回值，返回值为当前节点的下一个

10. 迭代器区间构造

void empty_init()
    {
      _head = new node;
      _head->_next = _head;
      _head->_prev = _head;
    }
template <class Iterator>
    list(Iterator first, Iterator last)
    {
      empty_init();
      while (first != last)
      {
        push_back(*first);
        ++first;
      }
    }

想要尾插的前提时，需要有头节点的存在，所以设置一个函数对头节点初始化

12. 拷贝构造

传统写法

void empty_init()
    {
      _head = new node;
      _head->_next = _head;
      _head->_prev = _head;
    }
list(const list<T>& It)//拷贝构造  传统写法
        {
            empty_init();//初始化头节点
            for (auto e : It)
            {
                push_back(e);
            }
        }

现代写法

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);
        }

通过调用std中的swap来达到交换的目的

13. 赋值

void swap(list<T>& tmp)
    {
      std::swap(_head, tmp._head);
    }
list<T>& operator=(list<T> It)
        {
            swap(It);
            return *this;
        }

参数不可以使用 list &，虽然可以达到赋值的目的，但是It的值也会发生改变

3.完整代码

#include<iostream>
#include<list>
#include<assert.h>
using namespace std;
namespace yzq
{
  template<class T>
  struct list_node
  {
    list_node<T>* _next;
    list_node<T>* _prev;
    T _data;
    list_node(const T& x=T())//构造函数
      :_next(nullptr)
      , _prev(nullptr)
      , _data(x)
    {
    }
  };
  //迭代器
  template<class T,class Ref,class Ptr>
  struct _list_iterator
  {
    typedef list_node<T> node;
    typedef _list_iterator<T,Ref,Ptr> self;
    node* _node;
    _list_iterator(node* n)
      :_node(n)
    {
    }
    Ref operator*()//解引用 
    {
      return _node->_data;
    }
    Ptr operator->()//->
    {
      return &_node->_data;
    }
    self& operator++()//前置++
    {
      _node = _node->_next;//指向下一个节点
      return *this;
    }
    self& operator++(int)//后置++
    {
      self ret = *this;
      _node = _node->_next;
      return ret;
    }
    self& operator--()//前置--
    {
      _node = _node->_prev;
      return *this;
    }
    self& operator--(int)//后置--
    {
      self ret = *this;
      _node = _node->_prev;
      return ret;
    }
    bool operator!=(const self&s)//!=
    {
      return _node != s._node;
    }
    bool operator==(const self& s)//==
    {
      return _node == s._node;
    }
  };
  //const迭代器
  //template<class T>
  //struct _list_const_iterator
  //{
  //  typedef list_node<T> node;
  //  typedef _list_const_iterator<T> self;
  //  node* _node;
  //  _list_const_iterator(node* n)
  //    :_node(n)
  //  {
  //  }
  //  const T& operator*()//解引用 
  //  {
  //    return _node->_data;
  //  }
  //  self& operator++()//前置++
  //  {
  //    _node = _node->_next;//指向下一个节点
  //    return *this;
  //  }
  //  self& operator++(int)//后置++
  //  {
  //    self ret = *this;
  //    _node = _node->_next;
  //    return ret;
  //  }
  //  self& operator--()//前置--
  //  {
  //    _node = _node->_prev;
  //    return *this;
  //  }
  //  self& operator--(int)//后置--
  //  {
  //    self ret = *this;
  //    _node = _node->_prev;
  //    return ret;
  //  }
  //  bool operator!=(const self& s)//!=
  //  {
  //    return _node != s._node;
  //  }
  //  bool operator==(const self& s)//==
  //  {
  //    return _node == s._node;
  //  }
  //};
  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;//const迭代器
    //typedef _list_const_iterator<T> const_iterator;
    void empty_init()
    {
      _head = new node;
      _head->_next = _head;
      _head->_prev = _head;
    }
    list()//构造函数
    {
      empty_init();
    }
    template <class Iterator>
    list(Iterator first, Iterator last)
    {
      empty_init();
      while (first != last)
      {
        push_back(*first);
        ++first;
      }
    }
    //list(const list<T>& It)//拷贝构造
    //{
    //  empty_init();//初始化头节点
    //  for (auto e : It)
    //  {
    //    push_back(e);
    //  }
    //}
    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<T>& operator=(list<T> It)//赋值
    {
      swap(It);
      return *this;
    }
    ~list()//析构函数
    {
      //将头节点也要释放掉
      clear();
      delete _head;
      _head = nullptr;
    }
    void clear()//清空数据
      //但是要注意不要把head清掉
    {
      iterator it = begin();
      while (it != end())
      {
        it=erase(it);//为了防止迭代器失效设置返回值
         //返回值为当前节点的下一个
      }
    }
    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 push_front(const T&x)//头插
    {
      insert(begin(), x);
    }
    void insert(iterator pos,const T&x)//在pos位置前插入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;
    }
    iterator erase(iterator pos)//删除pos位置
    {
      //头节点不可以删除
      assert(pos != end());
      node* cur = pos._node;
      node* prev = cur->_prev;
      node* next = cur->_next;
      prev->_next = next;
      next->_prev = prev;
      delete cur;
      return iterator(next);
    }
    void pop_back()//尾删
    {
      erase(--end());
    }
    void pop_front()//头删
    {
      erase(begin());
    }
    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);
    }
  private:
    node* _head;
  };
  /*void test(const list<int>&e)
  {
    list<int>::const_iterator it = e.begin();
      while (it != e.end())
      {
          cout << *it << " ";
        ++it;
      }
      cout << endl;
  }
  void test2()
  {
    const list<int> v;
    test(v);
  }*/
  //void test1()
  //{
  //  list<int> v;
  //  v.push_back(1);
  //  v.push_back(2);
  //  v.push_back(3);
  //  v.push_back(4);
  //  list<int>::iterator it= v.begin();
  //  while (it != v.end())
  //  {
  //    cout << *it << " ";
  //    ++it;
  //  }
  //  cout << endl;
  //}
  /*struct AA
  {
    int _a1;
    int _a2;
    AA(int a1=0,int a2=0)
      :_a1(a1)
      ,_a2(a2)
    {
    }
  };*/
  /*void test3()
  {
    list<AA>v;
    v.push_back(AA(1, 1));
    v.push_back(AA(2, 2));
    v.push_back(AA(3, 3));
    list<AA>::iterator it = v.begin();
    while (it != v.end())
    {
      cout << it->_a1 << " :"<<it->_a2<<" ";
      cout << endl;
      it++;
    }
  }*/
  //void test4()
  //{
  //  list<int> v;
  //  v.push_back(1);
  //  v.push_back(2);
  //  v.push_back(3);
  //  v.push_back(4);// 1 2 3 4
  //  for (auto e : v)
  //  {
  //    cout << e << " ";
  //  }
  //  cout << endl;
  //  v.clear();
  //  v.push_back(4);//  4
  //  for (auto e : v)
  //  {
  //    cout << e << " ";
  //  }
  //}
  //void test4()
  //{
  //  list<int> v;
  //  v.push_back(1);
  //  v.push_back(2);
  //  v.push_back(3);
  //  v.push_back(4);// 1 2 3 4
  //  for (auto e : v)
  //  {
  //    cout << e << " ";
  //  }
  //  cout << endl;
  //  list<int> v2(v);
  //  for (auto e : v2)// 1 2 3 4
  //  {
  //    cout << e << " ";
  //  }
  //}
  void test4()
  {
    list<int> v;
    v.push_back(1);
    v.push_back(2);//v1 = 1 2
    list<int> v2;
    v2.push_back(5);
    v2.push_back(6);//v2=5 6
      v2 = v;
    for (auto e : v2)// v2=1 2 
    {
      cout << e << " ";
    }
    cout << endl;
    for (auto e : v)// v1=1 2
    {
      cout << e << " ";
    }
  }
} 
int main()
{
  yzq::test4();
  return 0;
}

【C++】list的模拟实现