0
0

【STL】：list的模拟实现

朋友们、伙计们，我们又见面了，本期来给大家解读一下有关list的模拟实现，如果看完之后对你有一定的启发，那么请留下你的三连，祝大家心想事成！

C 语 言 专 栏：C语言：从入门到精通****

数据结构专栏：数据结构****

个 人 主 页 ：stackY、****

C + + 专 栏 ：C++****

Linux 专 栏 ：Linux****

1. 基本构造

list的底层其实是一个带头双向循环的链表，所以在模拟实现之前可以看一下库里面怎么实现的：

  1. namespace ywh
  2. {
  3.     //链表结构
  4.     template<class T>
  5.     struct list_node
  6.     {
  7.         T _data;                 //节点中的数据
  8.         list_node<T>* _prev;    //指向前一个节点的指针
  9.         list_node<T>* _next;    //指向后一个节点的指针
  11.         //构造
  12.         list_node(const T& x = T())
  13.             :_data(x)
  14.             , _prev(nullptr)
  15.             , _next(nullptr)
  16.         {}
  18.     };
  20.     //list结构
  21.     template<class T>
  22.     class list
  23.     {
  24.     public:
  25.         typedef list_node<T> Node;
  26.     public:
  27.         
  28.         //空初始化
  29.         void empty_init()
  30.         {
  31.             _head = new Node;
  32.             _head->_prev = _head;
  33.             _head->_next = _next;
  34.         }
  35.         //构造
  36.         list()
  37.         {
  38.             empty_init();
  39.         }
  41.     private:
  42.         Node* _head;  //链表的头节点
  43.         size_t _size; //节点个数
  44.     };
  45. }

2. 正向迭代器

在使用list的阶段的迭代器使用方法和之前的string、vector一样，但是了解过链表的结构都知道，链表要访问下一个节点就是使用节点中的next指针指向下一个节点，需要访问里面的数据需要找到里面的data，++和解引用并不能访问链表的节点，那么迭代器的使用在底层肯定是封装加运算符重载。

在实现迭代器的时候也需要采用封装和运算符重载，运算符重载需要用到++、--、!=、==、*、->等运算符。迭代器分为const迭代器和非const迭代器，首先先来看看非const迭代器：

2.1 非const迭代器

迭代器的实现一般使用struct来进行封装：

  1. namespace ljm
  2. {
  3.     //链表结构
  4.     template<class T>
  5.     struct list_node
  6.     {
  7.         T _data;                 //节点中的数据
  8.         list_node<T>* _prev;    //指向前一个节点的指针
  9.         list_node<T>* _next;    //指向后一个节点的指针
  11.         //构造
  12.         list_node(const T& x = T())
  13.             :_data(x)
  14.             , _prev(nullptr)
  15.             , _next(nullptr)
  16.         {}
  18.     };
  20.     //非const正向迭代器
  21.     template<class T>
  22.     struct __list_iterator
  23.     {
  24.         typedef list_node<T> Node;
  25.         typedef __list_iterator<T> self;
  26.         Node* _node;
  27.         //迭代器构造
  28.         __list_iterator(Node* node)
  29.             :_node(node)
  30.         {}
  31.         
  32.         //前置
  33.         //operator++
  34.         self& operator++()
  35.         {
  36.             return _node->_next;
  37.         }
  38.         //operator--
  39.         self& operator--()
  40.         {
  41.             return _node->_prev;
  42.         }
  44.         //后置
  45.         self operator++(int)
  46.         {
  47.             self* tmp(_node);
  48.             _node = _node->_next;
  49.             return tmp;
  50.         }
  51.         //operator--
  52.         self operator--(int)
  53.         {
  54.             self* tmp(_node);
  55.             _node = _node->_prev;
  56.             return tmp;
  57.         }
  59.         //operator*
  60.         T& operator*()
  61.         {
  62.             return _node->_data;
  63.         }
  64.         //operator->
  65.         T* operator->()
  66.         {
  67.             return &_node->_data;
  68.         }
  69.         //operator!=
  70.         bool operator!=(const self& s)
  71.         {
  72.             return _node != s._node;
  73.         }
  74.         //operator==
  75.         bool operator==(const self& s)
  76.         {
  77.             return _node == s._node;
  78.         }
  79.     };
  81.     //list结构
  82.     template<class T>
  83.     class list
  84.     {
  85.     public:
  86.         typedef list_node<T> Node;
  87.     public:
  88.         
  89.         //空初始化
  90.         void empty_init()
  91.         {
  92.             _head = new Node;
  93.             _head->_prev = _head;
  94.             _head->_next = _head;
  95.         }
  96.         //构造
  97.         list()
  98.         {
  99.             empty_init();
  100.         }
  101.         ///正向迭代器
  102.         iterator begin()
  103.         {
  104.             return iterator(_head->_next); //使用匿名对象进行构造
  105.         }
  106.         iterator end()
  107.         {
  108.             return iterator(_head);
  109.         }
  111.     private:
  112.         Node* _head;  //链表的头节点
  113.         size_t _size; //节点个数
  114.     };
  115. }

2.2 const迭代器

迭代器中涉及到修改的就是*和->，const迭代器的作用是指向的内容不能修改，本身不能修改，所以需要重新进行封装：

  1. namespace ljm
  2. {
  3.     //链表结构
  4.     template<class T>
  5.     struct list_node
  6.     {
  7.         T _data;                 //节点中的数据
  8.         list_node<T>* _prev;    //指向前一个节点的指针
  9.         list_node<T>* _next;    //指向后一个节点的指针
  11.         //构造
  12.         list_node(const T& x = T())
  13.             :_data(x)
  14.             , _prev(nullptr)
  15.             , _next(nullptr)
  16.         {}
  18.     };
  20.     //非const正向迭代器
  21.     //...
  23.     //const正向迭代器
  24.     template<class T>
  25.     struct __list_const_iterator
  26.     {
  27.         typedef list_node<T> Node;
  28.         typedef __list_const_iterator<T> self;
  29.         Node* _node;
  30.         //迭代器构造
  31.         __list_const_iterator(Node* node)
  32.             :_node(node)
  33.         {}
  35.         //前置
  36.         //operator++
  37.         self& operator++()
  38.         {
  39.             _node = _node->_next;
  40.             return *this;
  41.         }
  42.         //operator--
  43.         self& operator--()
  44.         {
  45.             _node = _node->_prev;
  46.             return *this;
  47.         }
  49.         //后置
  50.         self operator++(int)
  51.         {
  52.             self* tmp(_node);
  53.             _node = _node->_next;
  54.             return tmp;
  55.         }
  56.         //operator--
  57.         self operator--(int)
  58.         {
  59.             self* tmp(_node);
  60.             _node = _node->_prev;
  61.             return tmp;
  62.         }
  64.         //operator*
  65.         const T& operator*()
  66.         {
  67.             return _node->_data;
  68.         }
  69.         //operator->
  70.         const T* operator->()
  71.         {
  72.             return &_node->_data;
  73.         }
  74.         //operator!=
  75.         bool operator!=(const self& s)
  76.         {
  77.             return _node != s._node;
  78.         }
  79.         //operator==
  80.         bool operator==(const self& s)
  81.         {
  82.             return _node == s._node;
  83.         }
  84.     };
  86.     //list结构
  87.     template<class T>
  88.     class list
  89.     {
  90.     public:
  91.         typedef list_node<T> Node;
  92.         typedef __list_iterator<T> iterator;
  93.         typedef __list_const_iterator<T> const_iterator;
  94.     public:
  95.         基本构造///
  96.         //空初始化
  97.         void empty_init()
  98.         {
  99.             _head = new Node;
  100.             _head->_prev = _head;
  101.             _head->_next = _head;
  102.         }
  103.         //构造
  104.         list()
  105.         {
  106.             empty_init();
  107.         }
  108.         ///正向迭代器
  109.         iterator begin()
  110.         {
  111.             return iterator(_head->_next); //使用匿名对象进行构造
  112.         }
  113.         iterator end()
  114.         {
  115.             return iterator(_head);
  116.         }
  117.         const_iterator begin() const
  118.         {
  119.             return const_iterator(_head->_next);
  120.         }
  121.         const_iterator end() const
  122.         {
  123.             return const_iterator(_head);
  124.         }
  126.     private:
  127.         Node* _head;  //链表的头节点
  128.         size_t _size; //节点个数
  129.     };
  130. }

2.3 正向迭代器的改进优化

上面的这两种写法不难看出有很多代码都是重复出现的，使得代码非常冗余，那么怎么将这些冗余的代码进行合并呢？

我们可以看一下库里面如何实现：

采用泛型编程，使用模板，将这一转化的工作交给编译器，而我们只需传递const参数和非const参数即可：

  1. namespace ywh
  2. {
  3.     //链表结构
  4.     template<class T>
  5.     struct list_node
  6.     {
  7.         T _data;                 //节点中的数据
  8.         list_node<T>* _prev;    //指向前一个节点的指针
  9.         list_node<T>* _next;    //指向后一个节点的指针
  11.         //构造
  12.         list_node(const T& x = T())
  13.             :_data(x)
  14.             , _prev(nullptr)
  15.             , _next(nullptr)
  16.         {}
  18.     };
  20.     //非const正向迭代器
  21.     //   类型模板参数   传递引用      传递指针
  22.     template<class T, class Ref, class Ptr>
  23.     struct __list_iterator
  24.     {
  25.         typedef list_node<T> Node;
  26.         typedef __list_iterator<T, Ref, Ptr> self;
  27.         Node* _node;
  28.         //迭代器构造
  29.         __list_iterator(Node* node)
  30.             :_node(node)
  31.         {}
  32.         
  33.         //前置
  34.         //operator++
  35.         self& operator++()
  36.         {
  37.             _node = _node->_next;
  38.             return *this;
  39.         }
  40.         //operator--
  41.         self& operator--()
  42.         {
  43.             _node = _node->_prev;
  44.             return *this;
  45.         }
  47.         //后置
  48.         self operator++(int)
  49.         {
  50.             self* tmp(_node);
  51.             _node = _node->_next;
  52.             return tmp;
  53.         }
  54.         //operator--
  55.         self operator--(int)
  56.         {
  57.             self* tmp(_node);
  58.             _node = _node->_prev;
  59.             return tmp;
  60.         }
  62.         //operator*
  63.         Ref operator*()
  64.         {
  65.             return _node->_data;
  66.         }
  67.         //operator->
  68.         Ptr operator->()
  69.         {
  70.             return &_node->_data;
  71.         }
  72.         //operator!=
  73.         bool operator!=(const self& s)
  74.         {
  75.             return _node != s._node;
  76.         }
  77.         //operator==
  78.         bool operator==(const self& s)
  79.         {
  80.             return _node == s._node;
  81.         }
  82.     };
  84.     //list结构
  85.     template<class T>
  86.     class list
  87.     {
  88.     public:
  89.         typedef list_node<T> Node;
  90.         typedef __list_iterator<T, T&, T*> iterator;   //非const迭代器
  91.         typedef __list_iterator<T, const T&, const T*> const_iterator;  //const迭代器
  92.     public:
  93.         基本构造///
  94.         //空初始化
  95.         void empty_init()
  96.         {
  97.             _head = new Node;
  98.             _head->_prev = _head;
  99.             _head->_next = _head;
  100.         }
  101.         //构造
  102.         list()
  103.         {
  104.             empty_init();
  105.         }
  106.         ///正向迭代器
  107.         iterator begin()
  108.         {
  109.             return iterator(_head->_next); //使用匿名对象进行构造
  110.         }
  111.         iterator end()
  112.         {
  113.             return iterator(_head);
  114.         }
  115.         const_iterator begin() const
  116.         {
  117.             return const_iterator(_head->_next);
  118.         }
  119.         const_iterator end() const
  120.         {
  121.             return const_iterator(_head);
  122.         }
  124.     private:
  125.         Node* _head;  //链表的头节点
  126.         size_t _size; //节点个数
  127.     };
  128. }

3. 修改相关接口

3.1 insert、erase

在pos位置进行插入删除比较简单，需要进行链接新节点，改变节点中指针的指向即可，库里面对于插入和删除都带有返回值，那么我们在实现的时候也加上返回值：

  1. ///修改相关接口
  2.         //在pos位置插入节点
  3.         iterator insert(iterator pos, const T& x)
  4.         {
  5.             //创建新新节点
  6.             Node* newnode = new Node(x);
  7.             //链接节点
  8.             Node* cur = pos._node;
  9.             Node* prev = cur->_prev;
  10.             prev->_next = newnode;
  11.             newnode->_prev = prev;
  12.             newnode->_next = cur;
  13.             cur->_prev = newnode;
  14.             //更新节点个数
  15.             ++_size;
  16.             //返回新节点的位置
  17.             return iterator(newnode);
  18.         }
  19.         //删掉pos位置的节点
  20.         iterator erase(iterator pos)
  21.         {
  22.             //保存相对位置
  23.             Node* cur = pos._node;
  24.             Node* prev = cur->_prev;
  25.             Node* next = cur->_next;
  26.             //链接节点
  27.             delete cur;
  28.             prev->_next = next;
  29.             next->_prev = prev;
  30.             //更新节点个数
  31.             --_size;
  32.             //返回pos的下一个位置
  33.             return iterator(next);
  34.         }

在进行insert之后可以看到迭代器是不会失效的，但是在erase之后pos位置会被释放，因此erase之后迭代器会失效，在使用前先更新迭代器。

3.2 尾插、头插、尾删、头删、清理

当实现了insert和erase之后，实现这些接口直接复用即可：

  1.         //尾插
  2.         void push_back(const T& x)
  3.         {
  4.             insert(end(), x);
  5.         }
  6.         //头插
  7.         void push_front(const T& x)
  8.         {
  9.             insert(begin(), x);
  10.         }
  11.         //尾删
  12.         void pop_back()
  13.         {
  14.             erase(--end());
  15.         }
  16.         //头删
  17.         void pop_front()
  18.         {
  19.             erase(begin());
  20.         }
  21.         //清理
  22.         void clear()
  23.         {
  24.             iterator it = begin();
  25.             while (it != end())
  26.             {
  27.                 it = erase(it);
  28.             }
  29.         }

4. 拷贝构造、赋值重载、析构

在这里我们都是采用现代写法：

拷贝构造直接使用迭代器依次遍历进行尾插。

  1. //拷贝构造
  2.         list(const list<T>& lt)
  3.         {
  4.             //先创建空节点
  5.             empty_init();
  6.             //依次尾插即可
  7.             for (auto e : lt)
  8.             {
  9.                 push_back(e);
  10.             }
  11.         }
  12.         //operator=
  13.         void swap(list<T>& lt)
  14.         {
  15.             std::swap(_head, lt._head);
  16.             std::swap(_size, lt._size);
  17.         }
  18.         list<T>& operator=(list<T> lt)
  19.         {
  20.             swap(lt);
  21.             return *this;
  22.         }
  23.         //析构
  24.         ~list()
  25.         {
  26.             clear();
  27.             delete _head;
  28.             _head = nullptr;
  29.             _size = 0;
  30.         }

5. 完整代码

** 头文件：List.h**

  1. #pragma once
  3. namespace ywh
  4. {
  5.     //链表结构
  6.     template<class T>
  7.     struct list_node
  8.     {
  9.         T _data;                 //节点中的数据
  10.         list_node<T>* _prev;    //指向前一个节点的指针
  11.         list_node<T>* _next;    //指向后一个节点的指针
  13.         //构造
  14.         list_node(const T& x = T())
  15.             :_data(x)
  16.             , _prev(nullptr)
  17.             , _next(nullptr)
  18.         {}
  20.     };
  22.     //非const正向迭代器
  23.     //   类型模板参数   传递引用      传递指针
  24.     template<class T, class Ref, class Ptr>
  25.     struct __list_iterator
  26.     {
  27.         typedef list_node<T> Node;
  28.         typedef __list_iterator<T, Ref, Ptr> self;
  29.         Node* _node;
  30.         //迭代器构造
  31.         __list_iterator(Node* node)
  32.             :_node(node)
  33.         {}
  34.         
  35.         //前置
  36.         //operator++
  37.         self& operator++()
  38.         {
  39.             _node = _node->_next;
  40.             return *this;
  41.         }
  42.         //operator--
  43.         self& operator--()
  44.         {
  45.             _node = _node->_prev;
  46.             return *this;
  47.         }
  49.         //后置
  50.         self operator++(int)
  51.         {
  52.             self* tmp(_node);
  53.             _node = _node->_next;
  54.             return tmp;
  55.         }
  56.         //operator--
  57.         self operator--(int)
  58.         {
  59.             self* tmp(_node);
  60.             _node = _node->_prev;
  61.             return tmp;
  62.         }
  64.         //operator*
  65.         Ref operator*()
  66.         {
  67.             return _node->_data;
  68.         }
  69.         //operator->
  70.         Ptr operator->()
  71.         {
  72.             return &_node->_data;
  73.         }
  74.         //operator!=
  75.         bool operator!=(const self& s)
  76.         {
  77.             return _node != s._node;
  78.         }
  79.         //operator==
  80.         bool operator==(const self& s)
  81.         {
  82.             return _node == s._node;
  83.         }
  84.     };
  86.     //list结构
  87.     template<class T>
  88.     class list
  89.     {
  90.     public:
  91.         typedef list_node<T> Node;
  92.         typedef __list_iterator<T, T&, T*> iterator;   //非const迭代器
  93.         typedef __list_iterator<T, const T&, const T*> const_iterator;  //const迭代器
  94.     public:
  95.         基本构造///
  96.         //空初始化
  97.         void empty_init()
  98.         {
  99.             _head = new Node;
  100.             _head->_prev = _head;
  101.             _head->_next = _head;
  102.         }
  103.         //构造
  104.         list()
  105.         {
  106.             empty_init();
  107.         }
  108.         //拷贝构造
  109.         list(const list<T>& lt)
  110.         {
  111.             //先创建空节点
  112.             empty_init();
  113.             //依次尾插即可
  114.             for (auto e : lt)
  115.             {
  116.                 push_back(e);
  117.             }
  118.         }
  119.         //operator=
  120.         void swap(list<T>& lt)
  121.         {
  122.             std::swap(_head, lt._head);
  123.             std::swap(_size, lt._size);
  124.         }
  125.         list<T>& operator=(list<T> lt)
  126.         {
  127.             swap(lt);
  128.             return *this;
  129.         }
  130.         //析构
  131.         ~list()
  132.         {
  133.             clear();
  134.             delete _head;
  135.             _head = nullptr;
  136.             _size = 0;
  137.         }
  138.         ///正向迭代器
  139.         iterator begin()
  140.         {
  141.             return iterator(_head->_next); //使用匿名对象进行构造
  142.         }
  143.         iterator end()
  144.         {
  145.             return iterator(_head);
  146.         }
  147.         const_iterator begin() const
  148.         {
  149.             return const_iterator(_head->_next);
  150.         }
  151.         const_iterator end() const
  152.         {
  153.             return const_iterator(_head);
  154.         }
  155.         ///修改相关接口
  156.         //在pos位置插入节点
  157.         iterator insert(iterator pos, const T& x)
  158.         {
  159.             //创建新新节点
  160.             Node* newnode = new Node(x);
  161.             //链接节点
  162.             Node* cur = pos._node;
  163.             Node* prev = cur->_prev;
  164.             prev->_next = newnode;
  165.             newnode->_prev = prev;
  166.             newnode->_next = cur;
  167.             cur->_prev = newnode;
  168.             //更新节点个数
  169.             ++_size;
  170.             //返回新节点的位置
  171.             return iterator(newnode);
  172.         }
  173.         //删掉pos位置的节点
  174.         iterator erase(iterator pos)
  175.         {
  176.             //保存相对位置
  177.             Node* cur = pos._node;
  178.             Node* prev = cur->_prev;
  179.             Node* next = cur->_next;
  180.             //链接节点
  181.             delete cur;
  182.             prev->_next = next;
  183.             next->_prev = prev;
  184.             //更新节点个数
  185.             --_size;
  186.             //返回pos的下一个位置
  187.             return iterator(next);
  188.         }
  189.         //尾插
  190.         void push_back(const T& x)
  191.         {
  192.             insert(end(), x);
  193.         }
  194.         //头插
  195.         void push_front(const T& x)
  196.         {
  197.             insert(begin(), x);
  198.         }
  199.         //尾删
  200.         void pop_back()
  201.         {
  202.             erase(--end());
  203.         }
  204.         //头删
  205.         void pop_front()
  206.         {
  207.             erase(begin());
  208.         }
  209.         //清理
  210.         void clear()
  211.         {
  212.             iterator it = begin();
  213.             while (it != end())
  214.             {
  215.                 it = erase(it);
  216.             }
  217.         }
  218.         //节点个数
  219.         size_t size()
  220.         {
  221.             return _size;
  222.         }
  223.     private:
  224.         Node* _head;  //链表的头节点
  225.         size_t _size; //节点个数
  226.     };
  227. }

朋友们、伙计们，美好的时光总是短暂的，我们本期的的分享就到此结束，欲知后事如何，请听下回分解~，最后看完别忘了留下你们弥足珍贵的三连喔，感谢大家的支持！

标签： c++ 开发语言 STL
本文转载自: https://blog.csdn.net/Yikefore/article/details/134090437
版权归原作者 stackY、 所有， 如有侵权，请联系我们删除。
登录后发布评论

“【STL】：list的模拟实现”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

网络安全法-网络运行安全

使用selenium/drissionpage时如何阻止chrome自动跳转http到https

docker desktop 里部署的Open WebUI 管理员密码忘记了的处理方法

在ubuntu20.04中搭建onsite比赛运行环境

利用开源的低代码表单设计器FcDesigner高效管理和渲染复杂表单结构

Kafka学习笔记

【前端】浏览器输入url到页面呈现发生了什么？