21. C++STL 7(8000字详解list及其迭代器的模拟实现)

⭐本篇重点：STL中的list及其迭代器的模拟实现和测试
  ⭐本篇代码：c++学习 · 橘子真甜/c++-learning-of-yzc - 码云 - 开源中国 (gitee.com)
  目次
一. list的节点
二. list的迭代器 
2.1 迭代器框架
 2.2 迭代器实现
三. list的实现
3.1 list的构造函数
3.2 insert
3.2 erase 
3.3 begin和end
3.4 push_back和push_front
3.5 pop_back和pop_front
3.6 clear和析构函数
3.7 测试代码1
3.8 拷贝构造函数和赋值运算符重载 
四. test.h 源代码
五. 测试自界说类型和类类型
5.1测试string类
5.2 测试自界说类
六. 下篇重点：stack和queue的使用与模拟实现

---

一. list的节点

        我们知道，list是一个带头的双向循环链表。所以这个节点应该包含以下成员变量。

1.     //表示链表的节点
2.     template<class T>
3.         struct ListNode
4.         {
5.                 ListNode* _next;
6.                 ListNode* _prev;
7.                 T _data;
9.         //构造函数
10.                 ListNode(const T& data = T())
11.                         :_next(nullptr)
12.                         , _prev(nullptr)
13.                         , _data(data)
14.                 {};
15.         };

复制代码

二. list的迭代器 

        我们模拟过string和vector，它两的迭代器都用原生指针就能实现。但是list的迭代器使用原生指针无法实现。好比我们++it，不能简朴的让指针+1就行。
2.1 迭代器框架

        list迭代器结构体如下：

1.         //迭代器，T为节点的data，Ptr表示data的地址，Ref表示data的引用
2.         template<class T, class Ptr, class Ref>
3.         struct ListIterator
4.         {
5.                 typedef ListNode<T> Node;
6.                 typedef ListIterator<T, Ptr, Ref> Self;
7.                 Node* _node;
9.                 //构造函数
10.                 ListIterator(Node* node)
11.                         :_node(node)
12.                 {}
14.                 //前置++
15.                 Self& operator++()
16.                 {}
18.                 //后置++
19.                 Self operator++(int)
20.                 {}
22.                 //前置--
23.                 Self& operator--()
24.                 {}
26.                 //后置--
27.                 Self operator--(int)
28.                 {}
30.                 //解引用，获取这个节点
31.                 Ref operator*()
32.                 {}
34.                 //->，箭头获取的是节点的指针
35.                 Ptr operator->()
36.                 {}
38.                 //判断是否相等
39.                 bool operator==(const Self& self)
40.                 {}
42.                 //判断是否不等
43.                 bool operator!=(const Self& self)
44.                 {}
45.         };

复制代码

 2.2 迭代器实现

operator++
在list中，++只必要让我们的指针指向当前节点的下一个节点即可
前置++

1.                 //前置++
2.                 Self& operator++()
3.                 {       
4.                         //返回++后的结果
5.                         _node = _node->_next;
6.                         return *this;       
7.                 }

复制代码

后置++。后置++留意要用中心变量生存并且不能引用返回！

1.                 //后置++
2.                 Self operator++(int)
3.                 {
4.                         //返回++前的结果，需要保存++前的指针
5.                         //注意这里不可使用引用返回，tmp在栈中。属于局部变量，出函数会销毁！
6.                         Node* tmp = _node;
7.                         _node = _node->_next;
8.                         return tmp;
9.                 }

复制代码

operator* 和 operator->
*返回当前节点的data，->返回当前节点data的地址（即一个指针） 
好比： *it = data         it-> = &data

1.                 //解引用，获取这个节点
2.                 Ref operator*()
3.                 {
4.                         return _node->_data;
5.                 }
7.                 //->，箭头获取的是节点的指针
8.                 Ptr operator->()
9.                 {
10.                         return &_node->_data;
11.                 }

复制代码

根据上面的代码        --和== !=同理可以实现 
迭代器的全部实现代码如下：

1.         //迭代器，T为节点的data，Ptr表示data的地址，Ref表示data的引用        template<class T, class Ptr, class Ref>        struct ListIterator        {                typedef ListNode<T> Node;                typedef ListIterator<T, Ptr, Ref> Self;                Node* _node;                //构造函数                ListIterator(Node* node)                        :_node(node)                {}                //前置++
2.                 Self& operator++()
3.                 {       
4.                         //返回++后的结果
5.                         _node = _node->_next;
6.                         return *this;       
7.                 }                //后置++
8.                 Self operator++(int)
9.                 {
10.                         //返回++前的结果，需要保存++前的指针
11.                         //注意这里不可使用引用返回，tmp在栈中。属于局部变量，出函数会销毁！
12.                         Node* tmp = _node;
13.                         _node = _node->_next;
14.                         return tmp;
15.                 }                //前置--                Self& operator--()                {                        _node = _node->_prev;                        return *this;                }                //后置--                Self operator--(int)                {                        Node* tmp = _node;                        _node = _node->_prev;                        return tmp;                }                //解引用，获取这个节点
16.                 Ref operator*()
17.                 {
18.                         return _node->_data;
19.                 }
21.                 //->，箭头获取的是节点的指针
22.                 Ptr operator->()
23.                 {
24.                         return &_node->_data;
25.                 }                //判断是否相等                bool operator==(const Self& it)                {                        return it._node == _node;                }                //判断是否不等                bool operator!=(const Self& it)                {                        return it._node != _node;                }        };

复制代码

三. list的实现

list的框架如下。位于 test.h中

1.         template<class T>
2.         class list
3.         {
4.                 typedef ListNode<T> Node;        //typedef list的节点
5.         public:
6.                 //list 的迭代器
7.                 typedef ListIterator<T, T*, T&> iterator;
8.                 typedef ListIterator<T, const T*, const T&> const_iterator;
11.         private:
12.                 Node* _head;        //list的头节点
13.         };

复制代码

3.1 list的构造函数

         list是带头双向循环链表。只要在堆中开辟一个头节点，然后让它的next和prev都指向自己即可。留意头节点的data不存储任何值。

1.                 //构造函数
2.                 list()
3.                         :_head(new Node)
4.                 {
5.                         _head->_next = _head;
6.                         _head->_prev = _head;
7.                 }

复制代码

3.2 insert

        和vector一样，我们先界说出insert和erase。然后push_back和pop_back去复用insert和erase的代码可以提高代码的复用。
        思考一下list的insert中的pos是什么？        list没有下标，只能用迭代器表示pos
插入代码的逻辑图如下

我们只要让prev链接号newnode，再让newnode链接好cur即可 （留意提前生存好cur）
代码如下：

1.                 //insert。在pos位置插入data
2.                 void insert(const iterator& pos, const T& data)
3.                 {
4.                         Node* newnode = new Node(data);
5.                         Node* cur = pos._node;
6.                         Node* pre = cur->_prev;
8.                         //1.链接pre和newnode
9.                         pre->_next = newnode;
10.                         newnode->_prev = pre;
12.                         //2.链接newnode和cur
13.                         newnode->_next = cur;
14.                         cur->_prev = newnode;
15.                 }

复制代码

即便只有一个头节点上面代码也没问题。逻辑图如下 

3.2 erase 

        erase比较简朴。找到pos的前后节点pre和next，链接pre和next，然后删除cur即可
留意：返回的节点应该是next节点（即删除cur后，next处于pos的位置）
代码如下：

1.         //erase，删除pos位置的节点
2.                 iterator erase(const iterator& pos)
3.                 {
4.                         Node* cur = pos._node;
5.                         Node* pre = cur->_prev;
6.                         Node* next = cur->_next;
8.                         pre->_next = next;
9.                         next->_prev = pre;
11.                         delete cur;
12.                         return next;        //删除cur后，pos就处于next了
13.                 }

复制代码

3.3 begin和end

        begin返回第一个节点（头节点的next）的迭代器，end末了一个节点后一个的迭代器（就是头节点）
代码如下：

1.                 iterator begin()
2.                 {
3.                         return _head->_next;
4.                 }
6.                 iterator end()
7.                 {
8.                         return _head;
9.                 }
11.                 const_iterator begin()const
12.                 {
13.                         return const_iterator(_head->_next);
14.                 }
16.                 const_iterator end()const
17.                 {
18.                         return const_iterator(_head);
19.                 }

复制代码

3.4 push_back和push_front

        有了insert这两个函数就简朴了。push_back直接在end()这个迭代器调用insert，push_front直接在begin()调用insert。
代码如下：

1.                 //尾插
2.                 void push_back(const T& data)
3.                 {
4.                         insert(end(), data);
5.                 }
7.                 //头插
8.                 void push_front(const T& data)
9.                 {
10.                         insert(begin(), data);
11.                 }

复制代码

3.5 pop_back和pop_front

同理。调用erase即可。不外留意尾删是删除末了一个节点不是头节点！

1.                 //头删
2.                 void pop_front()
3.                 {
4.                         erase(begin());
5.                 }
7.                 //尾删
8.                 void pop_back()
9.                 {
10.                         //erase(end());                        //不是删除头节点，而是头节点的前一个节点（尾节点）
11.                         erase(_head->_prev);
12.                 }

复制代码

3.6 clear和析构函数

        使用迭代器遍历链表，一个一个删除节点即可。clear不会删除头节点

1.                 //clear清空链表
2.                 void clear()
3.                 {
4.                         iterator it = begin();
5.                         while (it != end())
6.                         {
7.                                 erase(it++);        //后置++，it走到下一个节点后。返回前一个节点去删除即可
8.                         }
9.                 }

复制代码

        析构函数。调用clear然后删除头节点即可。

1.                 ~list()
2.                 {
3.                         clear();
4.                         delete _head;
5.                         _head = nullptr;
6.                 }

复制代码

3.7 测试代码1

        到此为止，整个链表基本实现了。我们来测试一下
测试代码 test.cpp

1. #define _CRT_SECURE_NO_WARNINGS 1
2. #include <iostream>
3. #include "test.h"
4. using namespace std;
6. void test1()
7. {
8.         YZC::list<int> l1;
10.         for (int i = 0; i < 5; i++)                // 0 1 2 3 4
11.                 l1.push_back(i);
12.        
13.         for (int i = 10; i < 15; i++)        // 14 13 12 11 10 0 1 2 3 4
14.                 l1.push_front(i);       
16.         l1.pop_back();        // 14 13 12 11 10 0 1 2 3
17.         l1.pop_front();        // 13 12 11 10 0 1 2 3
19.         YZC::list<int>::iterator it = l1.begin();
20.         while (it != l1.end())
21.         {
22.                 cout << *it << " ";
23.                 ++it;
24.         }
25.         cout << endl;
26. }
28. int main()
29. {
30.         test1();
31.         return 0;
32. }

复制代码

 运行结果如下

3.8 拷贝构造函数和赋值运算符重载 

        拷贝构造。遍历构造即可

1.                 //拷贝构造
2.                 list(const list<T>& l)
3.                         :_head(new Node)
4.                 {
5.                         //1.初始化头节点
6.                         _head->_next = _head;
7.                         _head->_prev = _head;
9.                         //2.遍历l，尾插节点即可
10.                         for (auto const& e : l)
11.                         {
12.                                 push_back(e);
13.                         }
14.                 }

复制代码

        赋值运算符重载。使用暂时变量出函数销毁的特性 

1.                 //operator=
2.                 list& operator=(list<T> l)
3.                 {
4.                         swap(_head, l._head);
5.                         return *this;
6.                 }

复制代码

四. test.h 源代码

1. #pragma oncenamespace YZC{        //表示链表的节点        template<class T>        struct ListNode        {                ListNode* _next;                ListNode* _prev;                T _data;                ListNode(const T& data = T())                        :_next(nullptr)                        , _prev(nullptr)                        , _data(data)                {};        };        //迭代器，T为节点的data，Ptr表示data的地址，Ref表示data的引用        template<class T, class Ptr, class Ref>        struct ListIterator        {                typedef ListNode<T> Node;                typedef ListIterator<T, Ptr, Ref> Self;                Node* _node;                //构造函数                ListIterator(Node* node)                        :_node(node)                {}                //前置++
2.                 Self& operator++()
3.                 {       
4.                         //返回++后的结果
5.                         _node = _node->_next;
6.                         return *this;       
7.                 }                //后置++
8.                 Self operator++(int)
9.                 {
10.                         //返回++前的结果，需要保存++前的指针
11.                         //注意这里不可使用引用返回，tmp在栈中。属于局部变量，出函数会销毁！
12.                         Node* tmp = _node;
13.                         _node = _node->_next;
14.                         return tmp;
15.                 }                //前置--                Self& operator--()                {                        _node = _node->_prev;                        return *this;                }                //后置--                Self operator--(int)                {                        Node* tmp = _node;                        _node = _node->_prev;                        return tmp;                }                //解引用，获取这个节点
16.                 Ref operator*()
17.                 {
18.                         return _node->_data;
19.                 }
21.                 //->，箭头获取的是节点的指针
22.                 Ptr operator->()
23.                 {
24.                         return &_node->_data;
25.                 }                //判断是否相等                bool operator==(const Self& it)                {                        return it._node == _node;                }                //判断是否不等                bool operator!=(const Self& it)                {                        return it._node != _node;                }        };        template<class T>        class list        {                typedef ListNode<T> Node;        //typedef list的节点        public:                //list 的迭代器                typedef ListIterator<T, T*, T&> iterator;                typedef ListIterator<T, const T*, const T&> const_iterator;                //构造函数
26.                 list()
27.                         :_head(new Node)
28.                 {
29.                         _head->_next = _head;
30.                         _head->_prev = _head;
31.                 }                //拷贝构造
32.                 list(const list<T>& l)
33.                         :_head(new Node)
34.                 {
35.                         //1.初始化头节点
36.                         _head->_next = _head;
37.                         _head->_prev = _head;
39.                         //2.遍历l，尾插节点即可
40.                         for (auto const& e : l)
41.                         {
42.                                 push_back(e);
43.                         }
44.                 }                //operator=
45.                 list& operator=(list<T> l)
46.                 {
47.                         swap(_head, l._head);
48.                         return *this;
49.                 }                                //析构函数                ~list()
50.                 {
51.                         clear();
52.                         delete _head;
53.                         _head = nullptr;
54.                 }                //clear清空链表
55.                 void clear()
56.                 {
57.                         iterator it = begin();
58.                         while (it != end())
59.                         {
60.                                 erase(it++);        //后置++，it走到下一个节点后。返回前一个节点去删除即可
61.                         }
62.                 }                //insert。在pos位置插入data
63.                 void insert(const iterator& pos, const T& data)
64.                 {
65.                         Node* newnode = new Node(data);
66.                         Node* cur = pos._node;
67.                         Node* pre = cur->_prev;
69.                         //1.链接pre和newnode
70.                         pre->_next = newnode;
71.                         newnode->_prev = pre;
73.                         //2.链接newnode和cur
74.                         newnode->_next = cur;
75.                         cur->_prev = newnode;
76.                 }                //erase，删除pos位置的节点                iterator erase(const iterator& pos)                {                        Node* cur = pos._node;                        Node* pre = cur->_prev;                        Node* next = cur->_next;                        pre->_next = next;                        next->_prev = pre;                        delete cur;                        return next;        //删除cur后，pos就处于next了                }                //尾插
77.                 void push_back(const T& data)
78.                 {
79.                         insert(end(), data);
80.                 }
82.                 //头插
83.                 void push_front(const T& data)
84.                 {
85.                         insert(begin(), data);
86.                 }                 //头删
87.                 void pop_front()
88.                 {
89.                         erase(begin());
90.                 }
92.                 //尾删
93.                 void pop_back()
94.                 {
95.                         //erase(end());                        //不是删除头节点，而是头节点的前一个节点（尾节点）
96.                         erase(_head->_prev);
97.                 }                iterator begin()
98.                 {
99.                         return _head->_next;
100.                 }
102.                 iterator end()
103.                 {
104.                         return _head;
105.                 }
107.                 const_iterator begin()const
108.                 {
109.                         return const_iterator(_head->_next);
110.                 }
112.                 const_iterator end()const
113.                 {
114.                         return const_iterator(_head);
115.                 }        private:                Node* _head;        //list的头节点        };}

复制代码

五. 测试自界说类型和类类型

5.1测试string类

测试代码和结果如下：

1. #define _CRT_SECURE_NO_WARNINGS 1
2. #include <iostream>
3. #include <string>
4. #include "test.h"
5. using namespace std;
7. void test1()
8. {
9.         YZC::list<string> l1;
10.         string s1 = "hello world!";
11.         string s2 = "YZC";
12.         string s3 = "yzc";
13.         string s4 = "list模拟实现";
15.         l1.push_back(s1);
16.         l1.push_back(s2);
17.         l1.push_back(s3);
18.         l1.push_back(s4);
19.         for (const auto& str : l1)
20.                 cout << str << " ";
21.         cout << endl;
23.         //拷贝构造
24.         YZC::list<string> l2(l1);
25.         for (const auto& str : l2)
26.                 cout << str << " ";
27. }
29. int main()
30. {
31.         test1();
32.         return 0;
33. }

复制代码

5.2 测试自界说类

 

1. #define _CRT_SECURE_NO_WARNINGS 1
2. #include <iostream>
3. #include "test.h"
4. using namespace std;
6. struct Date
7. {
8.         int _year = 0;
9.         int _month = 1;
10.         int _day = 1;
11. };
13. void test1()
14. {
15.         YZC::list<Date> l1;
16.         Date d1;
17.         Date d2;
18.         l1.push_back(d1);
19.         l1.push_back(d2);
21.         //1 测试迭代器的解引用
22.         auto it = l1.begin();
23.         while (it != l1.end())
24.         {
25.                 cout << (*it)._year << "/" << (*it)._month << "/" << (*it)._day << endl;
26.                 ++it;
27.         }
28.         cout << endl;
30.         //测试赋值运算符和->
31.         YZC::list<Date>l2 = l1;
32.         auto it1 = l2.begin();
33.         while (it1 != l2.end())
34.         {
35.                 cout << it->_year << "/" << it->_month << "/" << it->_day << endl;
36.                 ++it1;
37.         }
38. }
40. int main()
41. {
42.         test1();
43.         return 0;
44. }

复制代码

测试结果如下：

六. 下篇重点：stack和queue的使用与模拟实现


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。