0
0

模拟实现STL中的list

1.设计list的结点

STL中的list采用的底层数据结构是带头双向循环链表，我们也采用这种方式，因此，结点可以这样来设计。

代码如下：为了满足容器中可以存放各种类型的数据这一需求，我们使用模板元编程的思想，将结点设计为模板类型。

  1.     /* 定义节点 */
  2.     template<class T>       // T表示存储的数据的类型 
  3.     struct ListNode
  4.     {
  5.         ListNode<T>* _prev; // 指向前一个结点
  6.         ListNode<T>* _next; // 指向后一个结点
  7.         T _data;            // 存储数据
  9.         ListNode(const T& x = T()) // 构造函数
  10.             :_next(nullptr)
  11.             , _prev(nullptr)
  12.             , _data(x)
  13.         {}
  14.     };

2.设计list的迭代器

list的底层空间不像string和vector那样是连续的，因此，list的迭代器需要对结点的指针进行封装，来模拟指针的行为。比如：连续空间上的指针进行++操作，直接就能到达后一个数据的位置，但是不连续空间上的指针进行++操作不能到达后一个数据的位置。

同样，我们需要将迭代器设计为模板类型，我们设计三个模板参数，分别是：

  • T：存储的数据的类型。
  • Ref：存储的数据的引用类型，相当于T&。
  • Ptr：存储的数据的指针类型，相当于T*。
  1. template<class T, class Ref, class Ptr>
  2. struct __list_iterator
  3. {
  4.     typedef ListNode<T> Node;
  5.     typedef __list_iterator<T, Ref, Ptr> self;
  6.         
  7.     // 成员变量
  8.     Node* _node; // 对结点的指针进行封装
  9. };

之所以遮掩设计是为了同时满足const对象和非const对象的需求，const对象需要调用const版本的迭代器，非const兑现需要调用非const版本的迭代器。

代码如下：迭代器模仿的是原生指针的行为，因此，我们实现迭代器的时候，至少需要实现以下操作。

  • 前置++和后置++
  • 前置--和后置--
  • 指针的解引用（*）操作
  • 指针的箭头（->）操作
  • 判断 相等 和 不相等 操作
  1. /* 
  2.     * 迭代器
  3.     * T：存储的元素类型
  4.     * Ref：该类型的引用T&
  5.     * Ptr：该类型的指针T*
  6. */
  7. template<class T, class Ref, class Ptr>
  8. struct __list_iterator
  9. {
  10.     typedef ListNode<T> Node;
  11.     typedef __list_iterator<T, Ref, Ptr> self;
  12.         
  13.     /* 成员变量 */
  14.     Node* _node; // 对结点的指针进行封装即可
  16.     /* 成员函数 */
  17.     __list_iterator(Node* x)
  18.         :_node(x)
  19.     {}
  21.     // ++it
  22.     self& operator++()        // 前置++，让当前迭代器指向下一个节点
  23.     {
  24.         _node = _node->_next;
  25.         return *this;         // 返回++以后的值
  26.     }
  28.     // it++
  29.     self operator++(int)      // 后置++，让当前迭代器指向下一个节点
  30.     {
  31.         //__list_iterator<T> tmp(*this);
  32.         self tmp(*this);
  34.         _node = _node->_next;
  36.         return tmp;           // 返回++之前的值
  37.     }
  39.     // --it
  40.     self& operator--()        // 前置--，让当前迭代器指向上一个节点
  41.     {
  42.         _node = _node->_prev;
  43.         return *this;         // 返回--之后的值
  44.     }
  46.     // it--
  47.     self operator--(int)      // 后置--，让当前迭代器指向上一个节点
  48.     {
  49.         self tmp(*this);
  51.         _node = _node->_prev; // 返回--之前的值
  53.         return tmp;
  54.     }
  56.     Ref operator*()           // 返回当前结点的数据域的引用
  57.     {
  58.         return _node->_data;
  59.     }
  61.     Ptr operator->()          // 返回当前结点中数据域的指针
  62.     {
  63.         return &(_node->_data);
  64.     }
  66.     bool operator!=(const self& s) // 判断两个迭代器是否不相等
  67.     {
  68.         return _node != s._node;
  69.     }
  71.     bool operator==(const self& s) // 判断两个迭代器是否相等
  72.     {
  73.         return _node == s._node;
  74.     }
  75. };

3.list类的设计总览

我们的list类设计如下：

  • 成员变量只有一个头结点的指针。
  • 成员函数涉及迭代器的相关操作，四个特殊的成员函数，插入和删除操作。
  1. template<class T> // T表示存储的数据的类型
  2. class list
  3. {
  4. private:
  5.     typedef ListNode<T> Node; // 对结点类型重命名
  6.     Node* _head;              // 定义一个头结点
  7. public:
  8.     /* 迭代器的声明 */
  9.     typedef __list_iterator<T, T&, T*> iterator;                   // 普通版本的迭代器
  10.     typedef __list_iterator<T, const T&, const T*> const_iterator; // const版本的迭代器
  12.     /* 迭代器的相关操作 */
  13.     iterator begin();             // 返回第一个元素的迭代器
  14.     iterator end();               // 返回最后一个元素的后一个位置的迭代器
  15.     const_iterator begin() const; // 提供给const对象的begin
  16.     const_iterator end() const;   // 提供给const对象的end
  18.     /* 四个特殊的成员函数 */
  19.     list();                                // 无参的默认构造函数
  20.     ~list();                               // 析构函数
  21.     list(const list<T>& lt);               // 拷贝构造
  22.     list<T>& operator=(const list<T>& lt); // 赋值运算符重载函数
  24.     /* 插入操作 */
  25.     iterator insert(iterator pos, const T& x); // 在指定位置之前插入指定元素
  26.     void push_back(const T& x);                 // 尾插
  27.     void push_front(const T& x);               // 头插
  29.     /* 删除操作 */
  30.     iterator erase(iterator pos); // 删除指定位置的元素           
  31.     void pop_back();              // 尾删
  32.     void pop_front();              // 头删
  33. };

4.list类的迭代器操作

begin()系列接口用于获取第一个元素的迭代器，也就是头结点后面那个元素的迭代器。

end()系列接口用于获取最后一个元素后面那个元素的迭代器，也就是头结点的迭代器。

为了满足const对象和非const对象的不同需求，我们提供const版本和非const版本。

  1. /* 迭代器的声明 */
  2. typedef __list_iterator<T, T&, T*> iterator;                   // 普通版本的迭代器
  3. typedef __list_iterator<T, const T&, const T*> const_iterator; // const版本的迭代器
  5. iterator begin()         // 返回第一个元素的迭代器
  6. {
  7.     return _head->_next; // 利用单参数的构造函数进行隐式的类型转换
  8. }
  10. iterator end()    // 返回最后一个元素的后一个位置的迭代器
  11. {
  12.     return _head; // 利用单参数的构造函数进行隐式的类型转换
  13. }
  15. const_iterator begin() const // 提供给const对象的begin
  16. {
  17.     return _head->_next;
  18. }
  20. const_iterator end() const   // 提供给const对象的end
  21. {
  22.     return _head;
  23. }

5.list类的四个特殊的默认成员函数

无参的默认构造函数

  • 只需要构造出一个起哨兵作用的头结点即可

  1. // 无参的默认构造函数
  2. list()   
  3.     : _head(new Node)
  4.     , _head->_next(_head)
  5.     , _head->_prev(_head);
  6. {}

拷贝构造函数

  • list的拷贝构造函数可以复用尾插实现。（尾插在后面会讲解，先用起来）
  1. // 拷贝构造
  2. list(const list<T>& lt)
  3.     : _head(new Node)
  4.     , _head->_next(_head)
  5.     , _head->_prev(_head);
  6. {
  7.     for (const auto& e : lt)
  8.     {
  9.         push_back(e); // 复用尾插实现
  10.     }
  11. }

赋值运算符重载函数

传统写法：释放赋值list的所有结点，然后复用尾插接口将被赋值list的所有结点尾插进来。

  1. // 传统写法的赋值运算符重载函数
  2. list<T>& operator=(const list<T>& lt)
  3. {
  4.     if (this != &lt)
  5.     {
  6.         // 释放之前的所有结点
  7.         iterator it = begin();
  8.         while (it != end())
  9.         {
  10.             it = erase(it);
  11.         }
  13.         // 复用push_back尾插所有结点
  14.         for (const auto& e : lt)
  15.         {
  16.             push_back(e);
  17.         }
  18.     }
  20.     return *this;
  21. }

现代写法：

  • 现代写法依赖于交换函数，所以我们先实现交换两个list的函数，交换两个list只需要交换list中的 _head 指针即可。
  • 在现代写法中，我们以传值传参的方式传递参数，此时的参数就相当于被赋值对象的一份临时拷贝，也就是复用拷贝构造函数，然后将当前对象与这个临时拷贝的对象进行交换。并且这个临时对象析构的时候，自动调用析构函数，析构的是赋值对象之前的值，避免了手动释放结点。
  1. void swap(list<T>& tmp)
  2. {
  3.     std::swap(_head, tmp._head);
  4. }
  5.         
  6. // 现代写法的赋值运算符重载函数
  7. list<T>& operator=(const list<T> lt)
  8. {
  9.     swap(lt);
  10.     return *this;
  11. }

析构函数

list类涉及到资源的管理，析构函数需要显示给出，在析构的时候，需要逐个释放结点。

  1. // 析构函数
  2. ~list()
  3. {
  4.     // 逐个释放节点
  5.     iterator it = begin();
  6.     while (it != end())
  7.     {
  8.         it = erase(it);
  9.     }
  10.     
  11.     // 释放哨兵位的头结点
  12.     delete _head;
  13.     _head = nullptr;
  14. }

6.list类的插入操作

在指定位置之前插入：

  1. // 在指定位置之前插入指定元素
  3. iterator insert(iterator pos, const T& x)
  4. {
  5.     // prev newnode cur
  6.     Node* cur = pos._node;
  7.     Node* prev = cur->_prev;
  8.     Node* newnode = new Node(x);
  10.     // 连接prev和newnode
  11.     prev->_next = newnode;
  12.     newnode->_prev = prev;
  14.     // 连接newnode和cur
  15.     newnode->_next = cur;
  16.     cur->_prev = newnode;
  18.     return newnode;
  19. }

尾插：在最后一个结点之后插入

  1. // 尾插
  2. void push_back(const T& x)
  3. {
  4.     // head -> …… -> tail -> newnode ->head
  5.     Node* newnode = new Node(x);
  6.     Node* tail = _head->_prev;
  8.     // 连接tail和newnode
  9.     tail->_next = newnode;
  10.     newnode->_prev = tail;
  12.     // 连接newnode和head
  13.     newnode->_next = _head;
  14.     _head->_prev = newnode;
  15. }
  17. // 复用insert实现尾插
  18. void push_back(const T& x)
  19. {
  20.     insert(end(), x);
  21. }

头插：复用insert在begin()之前插入。

  1. // 头插
  2. void push_front(const T& x)
  3. {
  4.     insert(begin(), x);
  5. }

7.list类的删除操作

删除指定位置的元素：

  1. // 删除指定位置的元素
  2. iterator erase(iterator pos)
  3. {
  4.     assert(pos != end());
  6.     // prev cur next
  7.     Node* cur = pos._node;
  8.     Node* prev = cur->_prev;
  9.     Node* next = cur->_next;
  11.     // 断开要删除结点和前后结点的连接
  12.     prev->_next = next;
  13.     next->_prev = prev;
  15.     // 释放要删除的结点
  16.     delete cur;
  18.     // 返回指向被删除结点的后一个结点的迭代器
  19.     return next;
  20. }

复用erase实现尾删和头删：

  • 尾删：end()的上一个位置就是尾结点。
  • 头删：begin()就是第一个结点的位置。
  1. // 尾删
  2. void pop_back()
  3. {
  4.     erase(--end());
  5. }
  7. // 头删
  8. void pop_front()
  9. {
  10.     erase(begin());
  11. }

8.list.hpp源代码

  1. #include <assert.h>
  3. namespace xy
  4. {
  5.     /* 定义节点 */
  6.     template<class T>       // T表示存储的数据的类型 
  7.     struct ListNode
  8.     {
  9.         ListNode<T>* _prev; // 指向前一个结点
  10.         ListNode<T>* _next; // 指向后一个结点
  11.         T _data;            // 存储数据
  13.         ListNode(const T& x = T()) // 构造函数
  14.             :_next(nullptr)
  15.             , _prev(nullptr)
  16.             , _data(x)
  17.         {}
  18.     };
  20.     /* 
  21.         * 迭代器
  22.         * T：存储的元素类型
  23.         * Ref：该类型的引用T&
  24.         * Ptr：该类型的指针T*
  25.     */
  26.     template<class T, class Ref, class Ptr>
  27.     struct __list_iterator
  28.     {
  29.         typedef ListNode<T> Node;
  30.         typedef __list_iterator<T, Ref, Ptr> self;
  31.         
  32.         /* 成员变量 */
  33.         Node* _node; // 对结点的指针进行封装即可
  35.         /* 成员函数 */
  36.         __list_iterator(Node* x)
  37.             :_node(x)
  38.         {}
  40.         // ++it
  41.         self& operator++()        // 前置++，让当前迭代器指向下一个节点
  42.         {
  43.             _node = _node->_next;
  44.             return *this;         // 返回++以后的值
  45.         }
  47.         // it++
  48.         self operator++(int)      // 后置++，让当前迭代器指向下一个节点
  49.         {
  50.             //__list_iterator<T> tmp(*this);
  51.             self tmp(*this);
  53.             _node = _node->_next;
  55.             return tmp;           // 返回++之前的值
  56.         }
  58.         // --it
  59.         self& operator--()        // 前置--，让当前迭代器指向上一个节点
  60.         {
  61.             _node = _node->_prev;
  62.             return *this;         // 返回--之后的值
  63.         }
  65.         // it--
  66.         self operator--(int)      // 后置--，让当前迭代器指向上一个节点
  67.         {
  68.             self tmp(*this);
  70.             _node = _node->_prev; // 返回--之前的值
  72.             return tmp;
  73.         }
  75.         Ref operator*()           // 返回当前结点的数据域的引用
  76.         {
  77.             return _node->_data;
  78.         }
  80.         Ptr operator->()          // 返回当前结点中数据域的指针
  81.         {
  82.             return &(_node->_data);
  83.         }
  85.         bool operator!=(const self& s) // 判断两个迭代器是否不相等
  86.         {
  87.             return _node != s._node;
  88.         }
  90.         bool operator==(const self& s) // 判断两个迭代器是否相等
  91.         {
  92.             return _node == s._node;
  93.         }
  94.     };
  96.     template<class T> // T表示存储的数据的类型
  97.     class list
  98.     {
  99.     private:
  100.         typedef ListNode<T> Node; // 对结点类型重命名
  101.         Node* _head;              // 定义一个头结点
  102.     public:
  103.         /* 迭代器的声明 */
  104.         typedef __list_iterator<T, T&, T*> iterator;                   // 普通版本的迭代器
  105.         typedef __list_iterator<T, const T&, const T*> const_iterator; // const版本的迭代器
  107.         iterator begin()         // 返回第一个元素的迭代器
  108.         {
  109.             return _head->_next; // 利用单参数的构造函数进行隐式的类型转换
  110.         }
  112.         iterator end()    // 返回最后一个元素的后一个位置的迭代器
  113.         {
  114.             return _head; // 利用单参数的构造函数进行隐式的类型转换
  115.         }
  117.         const_iterator begin() const // 提供给const对象的begin
  118.         {
  119.             return _head->_next;
  120.         }
  122.         const_iterator end() const   // 提供给const对象的end
  123.         {
  124.             return _head;
  125.         }
  127.         /* 四个特殊的成员函数 */
  129.         // 无参的默认构造函数
  130.         list()   
  131.             : _head(new Node)
  132.             , _head->_next(_head)
  133.             , _head->_prev(_head);
  134.         {}
  136.         // 拷贝构造
  137.         list(const list<T>& lt)
  138.             : _head(new Node)
  139.             , _head->_next(_head)
  140.             , _head->_prev(_head);
  141.         {
  142.             for (const auto& e : lt)
  143.             {
  144.                 push_back(e);
  145.             }
  146.         }
  148.         // 传统写法的赋值运算符重载函数
  149.         list<T>& operator=(const list<T>& lt)
  150.         {
  151.             if (this != &lt)
  152.             {
  153.                 // 释放之前的所有结点
  154.                 iterator it = begin();
  155.                 while (it != end())
  156.                 {
  157.                     it = erase(it);
  158.                 }
  160.                 // 复用push_back尾插所有结点
  161.                 for (const auto& e : lt)
  162.                 {
  163.                     push_back(e);
  164.                 }
  165.             }
  167.             return *this;
  168.         }
  170.         void swap(list<T>& tmp)
  171.         {
  172.             std::swap(_head, tmp._head);
  173.         }
  174.         
  175.         // 现代写法的赋值运算符重载函数
  176.         list<T>& operator=(const list<T> lt)
  177.         {
  178.             swap(lt);
  179.             return *this;
  180.         }
  182.         // 析构函数
  183.         ~list()
  184.         {
  185.             iterator it = begin();
  186.             while (it != end())
  187.             {
  188.                 it = erase(it);
  189.             }
  191.             delete _head;
  192.             _head = nullptr;
  193.         }
  195.         /* 插入操作 */
  197.         // 在指定位置之前插入指定元素
  198.         iterator insert(iterator pos, const T& x)
  199.         {
  200.             // prev newnode cur
  201.             Node* cur = pos._node;
  202.             Node* prev = cur->_prev;
  203.             Node* newnode = new Node(x);
  205.             // 连接prev和newnode
  206.             prev->_next = newnode;
  207.             newnode->_prev = prev;
  209.             // 连接newnode和cur
  210.             newnode->_next = cur;
  211.             cur->_prev = newnode;
  213.             return newnode;
  214.         }
  216.         // 尾插
  217.         void push_back(const T& x)
  218.         {
  219.             // head -> …… -> tail -> newnode ->head
  220.             Node* newnode = new Node(x);
  221.             Node* tail = _head->_prev;
  223.             // 连接tail和newnode
  224.             tail->_next = newnode;
  225.             newnode->_prev = tail;
  227.             // 连接newnode和head
  228.             newnode->_next = _head;
  229.             _head->_prev = newnode;
  230.         }
  232.         //void push_back(const T& x)
  233.         //{
  234.         //    insert(end(), x);
  235.         //}
  237.         // 头插
  238.         void push_front(const T& x)
  239.         {
  240.             insert(begin(), x);
  241.         }
  243.         /* 删除操作 */
  245.         // 删除指定位置的元素
  246.         iterator erase(iterator pos)
  247.         {
  248.             assert(pos != end());
  250.             // prev cur next
  251.             Node* cur = pos._node;
  252.             Node* prev = cur->_prev;
  253.             Node* next = cur->_next;
  255.             // 断开要删除结点和前后结点的连接
  256.             prev->_next = next;
  257.             next->_prev = prev;
  259.             // 释放要删除的结点
  260.             delete cur;
  262.             // 返回指向被删除结点的后一个结点的迭代器
  263.             return next;
  264.         }
  266.         // 尾删
  267.         void pop_back()
  268.         {
  269.             erase(--end());
  270.         }
  272.         // 头删
  273.         void pop_front()
  274.         {
  275.             erase(begin());
  276.         }
  277.     };
  278. }
标签： c++ 开发语言
本文转载自: https://blog.csdn.net/D5486789_/article/details/143833799
版权归原作者 手捧向日葵的花语 所有， 如有侵权，请联系我们删除。
登录后发布评论

“模拟实现STL中的list”的评论:

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

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

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

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

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

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

Kafka学习笔记

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