c++之List容器的模拟实现

注：终极代码以汇总的为准
1.前言

在之前的数据布局中，我们曾模拟实现过链表的数据布局，但是非常贫苦，全篇都袒露了链表的底层布局-----指针，但是从利用的角度，利用者并不关心你用的底层布局是啥，而且编写者也不肯意将所有的底层布局暴袒露来，为此，在此文章中，我们将充分发挥c++的上风，将指针包装一下，变为迭代器
2.根本框架的实现

根本布局包罗链表的创建，包罗链表结点的创建，结点的初始化，以及对底层布局----指针的封装,还有一些根本操作，例如++，==，！=，还有解引用操作等。
我们将造链表的文件放在List.h文件中，等下在test.cpp文件中进行测试。
如下代码是根本的布局代码：（具体功能没实现）

1. #include <assert.h>
2. namespace rens
3. {
4.         template<class T>
5.         struct list_node              //定义结点结构
6.         {
7.                 list_node* <T> _next;
8.                 list_node* <T> _prev;
9.                 T _data;
11.                 list_node(const T& x=T())
12.                         :_next(nullptr)
13.                         ,_prev(nullptr)
14.                         ,_data(x)
15.                 {}
16.         };
17. }
18. template <class T>
19. struct list_iterator
20. {
21.         typedef list_node<T> Node;
22.         Node* _node;
23.         list_iterator(Node* node)
24.                 :_node(node)
25.         {}
27.         T& operator*()                  //模拟指针的解引用
28.         {
29.                 return _node->_data;        //返回的是数据，类型为T
30.         }
32.         T* operator->()                 //解引用的->,这个较为特殊
33.         {
34.                 return &_node->_data;
35.         }
37.         list_iterator<T>& operator++()
38.         {
39.                 _node = _node->_next;
40.                 return *this;              //++操作返回的是下一个结点
41.         }
43.         bool operator!=(const list_iterator<T>& it)
44.         {
45.                 return this->_node != it._node;
46.         }
48.         bool operator==(const list_node<T>& it)
49.         {
50.                 return this->_node == it._node;
51.         }
52. };
56. template <class T>
57. class list
58. {
59.         typedef list_node<T> Node;
60. public:
61.         typedef list_iterator<T> iterator;
62. private:
63.         Node* _head;
64.         size_t _size;
65. };

复制代码

 但是，上述代码假如要是想遍历const对象是，由于我们的迭代器不是const迭代器，不能满足我们的需求，为此我们还要将上述代码cv一份，并改为const迭代器。
const迭代器代码如下：

1. template <class T>
2. struct const_list_iterator
3. {
4.         typedef list_node<T> Node;
5.         Node* _node;
6.         const_list_iterator(Node* node)
7.                 :_node(node)
8.         {}
10.         const T& operator*()                  //模拟指针的解引用
11.         {
12.                 return _node->_data;        //返回的是数据，类型为T
13.         }
15.         const T* operator->()                 //解引用的->,这个较为特殊
16.         {
17.                 return &_node->_data;
18.         }
20.         const_list_iterator<T>& operator++()
21.         {
22.                 _node = _node->_next;
23.                 return *this;              //++操作返回的是下一个结点
24.         }
26.         bool operator!=(const const_list_iterator<T>& it)
27.         {
28.                 return this->_node != it._node;
29.         }
31.         bool operator==(const const_list_iterator<T>& it)
32.         {
33.                 return this->_node == it._node;
34.         }
35. };

复制代码

但是，通过对比（对比图如下），我们发现这两段代码重复度太大了，仅仅是返回类型的区别，如许写未免太浪费，所以我们将其改造一下！

 

改造想法：既然我们的类型就是有无const的区别，那我们不妨利用模板，对其进行改造，添加一个Ref,即reference,引用&以及Ptr,即pointer,指针
为了方便改造，我们将原来的list_iterator<T>给typedef一下，省的总改！
 改造代码：

1. template <class T, class Ref, class Ptr>
2. struct list_iterator
3. {
4.         typedef list_node<T> Node;
5.         typedef list_iterator<T, Ref, Ptr> self;
7.         Node* _node;
8.         list_iterator(Node* node)
9.                 :_node(node)
10.         {}
12.         Ref operator*()                  //模拟指针的解引用
13.         {
14.                 return _node->_data;        //返回的是数据，类型为T
15.         }
17.         Ptr operator->()                 //解引用的->,这个较为特殊
18.         {
19.                 return &_node->_data;
20.         }
22.         self& operator++()           //前置++,返回的是引用， this指向的对象不销毁。
23.         {
24.                 _node = _node->_next;
25.                 return *this;              //++操作返回的是下一个对象
26.         }
28.         self operator++(int)          //后置++,返回的是一个临时对象，tmp出函数就销毁了
29.         {
30.                 self tmp(*this);
31.                 _node = _node->_next;
32.                 return tmp;
33.         }
34.         self& operator--()
35.         {
36.                 _node = _node->_prev;
37.                 return *this;
38.         }
40.         self operator--(int)
41.         {
42.                 self tmp(*this);
43.                 _node = _node->_prev;
44.                 return tmp;
45.         }
47.         bool operator!=(const self& it)
48.         {
49.                 return this->_node != it._node;
50.         }
52.         bool operator==(const self& it)
53.         {
54.                 return this->_node == it._node;
55.         }
56. };

复制代码

 别的功能的实现：

1.         template <class T>
2.         class list
3.         {
4.                 typedef list_node<T> Node;
5.         public:
6.                 //typedef list_iterator<T> iterator;
8.                 typedef list_iterator<T, T&, T*> iterator;
9.                 typedef list_iterator<T, const T&, const T*> const_iterator;
11.                 iterator begin()
12.                 {
13.                         iterator it(_head->_next);      //我们的链表是双向循环链表，_head可以理解为哨兵结点
14.                         return it;
15.                 }
17.                 iterator end()
18.                 {
19.                         return iterator(_head);
20.                 }
22.                 const_iterator begin()const        //加上const关键字表示该函数不会修改类的任何成员变量，即它是一个常量成员函数
23.                 {
24.                         return const_iterator(_head->_next);
25.                 }
27.                 const_iterator end()const
28.                 {
29.                         return const_iterator(_head);
30.                 }
32.                 void empty_init()
33.                 {
34.                         _head = new Node;
35.                         _head->_next = _head;
36.                         _head->_prev = _head;
37.                         _size = 0;
38.                 }
40.                 list()
41.                 {
42.                         empty_init();
43.                 }
44.                 list(std::initializer_list<T> lt)
45.                 {
46.                         empty_init();
47.                         for (auto& e : lt)
48.                         {
49.                                 push_back(e);
50.                         }
51.                 }
53.                 //lt2(lt1)
54.                 list(const list<T>& lt)
55.                 {
56.                         empty_init();
57.                         for (auto& e : lt)
58.                         {
59.                                 push_back(e);
60.                         }
61.                 }
62.                 //lt1=lt3
63.                 list<T>& operator=(list<T> lt)
64.                 {
65.                         swap(lt);
66.                         return *this;
67.                 }
68.                 void swap(list<T>& lt)
69.                 {
70.                         std::swap(_head, lt._head);
71.                         std::swap(_size, lt._size);
72.                 }
73.                 ~list()
74.                 {
75.                         clear();
76.                         delete _head;
77.                         _head = nullptr;
78.                 }
79.                 void clear()
80.                 {
81.                         iterator it = begin();
82.                         while (it != end())
83.                         {
84.                                 it = erase(it);
85.                         }
86.                 }
87.                 size_t size()const
88.                 {
89.                         return _size;
90.                 }
91.                 void push_back(const T& x)
92.                 {
93.                         insert(end(), x);
94.                 }
95.                 void push_front(const T& x)
96.                 {
97.                         insert(begin(), x);
98.                 }
99.                 void pop_front()
100.                 {
101.                         erase(begin());
102.                 }
103.                 void pop_back()
104.                 {
105.                         erase(--end());
106.                 }
107.                 void insert(iterator pos, const T& x)
108.                 {
109.                         Node* cur = pos._node;
110.                         Node* prev = cur->_prev;
111.                         Node* newnode = new Node(x);
112.                         prev->_next = newnode;
113.                         newnode->_prev = prev;
114.                         newnode->_next = cur;
115.                         cur->_prev = newnode;
116.                         ++_size;
117.                 }
118.                 iterator erase(iterator pos)
119.                 {
120.                         assert(pos != end());
121.                         Node* cur = pos._node;
122.                         Node* nextnode = cur->_next;
123.                         Node* prevnode = cur->_prev;
124.                         prevnode->_next = nextnode;
125.                         nextnode->_prev = prevnode;
126.                         delete cur;
127.                         --_size;
128.                         return iterator(nextnode);
129.                 }
130.         private:
131.                 Node* _head;
132.                 size_t _size;
133.         };
134. }

复制代码

3.代码的汇总及实现

这是List.h文件 

1. #include <assert.h>#include <initializer_list>#include<iostream>#include<algorithm>namespace rens{        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* node)                        :_node(node)                {}                Ref operator*()                  //模拟指针的解引用                {                        return _node->_data;        //返回的是数据，类型为T                }                Ptr operator->()                 //解引用的->,这个较为特殊                {                        return &_node->_data;                }                self& operator++()           //前置++,返回的是引用， this指向的对象不烧毁。                {                        _node = _node->_next;                        return *this;              //++操作返回的是下一个对象                }                self operator++(int)          //后置++,返回的是一个临时对象，tmp出函数就烧毁了                {                        self tmp(*this);                        _node = _node->_next;                        return tmp;                }                self& operator--()                {                        _node = _node->_prev;                        return *this;                }                self operator--(int)                {                        self tmp(*this);                        _node = _node->_prev;                        return tmp;                }                bool operator!=(const self& it)                {                        return this->_node != it._node;                }                bool operator==(const self& it)                {                        return this->_node == it._node;                }        };        //template <class T>        //struct list_iterator        //{        //        typedef list_node<T> Node;        //        Node* _node;        //        list_iterator(Node* node)        //                :_node(node)        //        {}        //        //        T& operator*()                  //模拟指针的解引用        //        {        //                return _node->_data;        //返回的是数据，类型为T        //        }        //        //        T* operator->()                 //解引用的->,这个较为特殊        //        {        //                return &_node->_data;        //        }        //        //        list_iterator<T>& operator++()        //        {        //                _node = _node->_next;        //                return *this;              //++操作返回的是下一个结点        //        }        //        //        bool operator!=(const list_iterator<T>& it)        //        {        //                return this->_node != it._node;        //        }        //        //        bool operator==(const list_node<T>& it)        //        {        //                return this->_node == it._node;        //        }        //};        //template <class T>        //struct const_list_iterator        //{        //        typedef list_node<T> Node;        //        Node* _node;        //        const_list_iterator(Node* node)        //                :_node(node)        //        {}        //        //        const T& operator*()                  //模拟指针的解引用        //        {        //                return _node->_data;        //返回的是数据，类型为T        //        }        //        //        const T* operator->()                 //解引用的->,这个较为特殊        //        {        //                return &_node->_data;        //        }        //        //        const_list_iterator<T>& operator++()        //        {        //                _node = _node->_next;        //                return *this;              //++操作返回的是下一个结点        //        }        //        //        bool operator!=(const const_list_iterator<T>& it)        //        {        //                return this->_node != it._node;        //        }        //        //        bool operator==(const const_list_iterator<T>& it)        //        {        //                return this->_node == it._node;        //        }        //};        template <class T>
2.         class list
3.         {
4.                 typedef list_node<T> Node;
5.         public:
6.                 //typedef list_iterator<T> iterator;
8.                 typedef list_iterator<T, T&, T*> iterator;
9.                 typedef list_iterator<T, const T&, const T*> const_iterator;
11.                 iterator begin()
12.                 {
13.                         iterator it(_head->_next);      //我们的链表是双向循环链表，_head可以理解为哨兵结点
14.                         return it;
15.                 }
17.                 iterator end()
18.                 {
19.                         return iterator(_head);
20.                 }
22.                 const_iterator begin()const        //加上const关键字表示该函数不会修改类的任何成员变量，即它是一个常量成员函数
23.                 {
24.                         return const_iterator(_head->_next);
25.                 }
27.                 const_iterator end()const
28.                 {
29.                         return const_iterator(_head);
30.                 }
32.                 void empty_init()
33.                 {
34.                         _head = new Node;
35.                         _head->_next = _head;
36.                         _head->_prev = _head;
37.                         _size = 0;
38.                 }
40.                 list()
41.                 {
42.                         empty_init();
43.                 }
44.                 list(std::initializer_list<T> lt)
45.                 {
46.                         empty_init();
47.                         for (auto& e : lt)
48.                         {
49.                                 push_back(e);
50.                         }
51.                 }
53.                 //lt2(lt1)
54.                 list(const list<T>& lt)
55.                 {
56.                         empty_init();
57.                         for (auto& e : lt)
58.                         {
59.                                 push_back(e);
60.                         }
61.                 }
62.                 //lt1=lt3
63.                 list<T>& operator=(list<T> lt)
64.                 {
65.                         swap(lt);
66.                         return *this;
67.                 }
68.                 void swap(list<T>& lt)
69.                 {
70.                         std::swap(_head, lt._head);
71.                         std::swap(_size, lt._size);
72.                 }
73.                 ~list()
74.                 {
75.                         clear();
76.                         delete _head;
77.                         _head = nullptr;
78.                 }
79.                 void clear()
80.                 {
81.                         iterator it = begin();
82.                         while (it != end())
83.                         {
84.                                 it = erase(it);
85.                         }
86.                 }
87.                 size_t size()const
88.                 {
89.                         return _size;
90.                 }
91.                 void push_back(const T& x)
92.                 {
93.                         insert(end(), x);
94.                 }
95.                 void push_front(const T& x)
96.                 {
97.                         insert(begin(), x);
98.                 }
99.                 void pop_front()
100.                 {
101.                         erase(begin());
102.                 }
103.                 void pop_back()
104.                 {
105.                         erase(--end());
106.                 }
107.                 void insert(iterator pos, const T& x)
108.                 {
109.                         Node* cur = pos._node;
110.                         Node* prev = cur->_prev;
111.                         Node* newnode = new Node(x);
112.                         prev->_next = newnode;
113.                         newnode->_prev = prev;
114.                         newnode->_next = cur;
115.                         cur->_prev = newnode;
116.                         ++_size;
117.                 }
118.                 iterator erase(iterator pos)
119.                 {
120.                         assert(pos != end());
121.                         Node* cur = pos._node;
122.                         Node* nextnode = cur->_next;
123.                         Node* prevnode = cur->_prev;
124.                         prevnode->_next = nextnode;
125.                         nextnode->_prev = prevnode;
126.                         delete cur;
127.                         --_size;
128.                         return iterator(nextnode);
129.                 }
130.         private:
131.                 Node* _head;
132.                 size_t _size;
133.         };
134. }

复制代码

这是test.cpp文件

1. #include"list.h"
3. using namespace std;
5. void test1()
6. {
7.         rens::list<int> lt1;
8.         lt1.push_back(1);
9.         lt1.push_back(2);
10.         lt1.push_back(3);
11.         lt1.push_back(4);
13.         rens::list<int>::iterator it1 = lt1.begin();
14.         while (it1 != lt1.end())
15.         {
16.                 *it1 += 1;
17.                 cout << *it1 << " ";
18.                 ++it1;
19.         }
20.         cout << endl;
21. }
22. void print(const rens::list<int>& lt)
23. {
24.         // const迭代器本身可以修改，指向内容不能修改
25.         rens::list<int>::const_iterator it = lt.begin();
26.         while (it != lt.end())
27.         {
28.                 cout << *it << " ";
29.                 ++it;
30.         }
31.         cout << endl;
32. }
33. struct A
34. {
35.         A(int a1=1,int a2=1)
36.                 :_a1(a1)
37.                 ,_a2(a2)
38.         {}
39.         int _a1;
40.         int _a2;
41. };
42. void test2()
43. {
44.         rens::list<A> lt2;
45.         lt2.push_back({ 1,1 });
46.         lt2.push_back({ 2,2 });
47.         lt2.push_back({ 3,3 });
48.         lt2.push_back({ 4,4 });
49.         rens::list<A>::iterator it = lt2.begin();
50.         while (it != lt2.end())
51.         {
52.                 cout << it->_a1 << "," << it->_a2 << endl;
53.                 ++it;
54.         }
55.         cout << endl;
56.         rens::list<int> lt1;
57.         lt1.push_back(1);
58.         lt1.push_back(2);
59.         lt1.push_back(3);
60.         print(lt1);
61. }
62. void test3()
63. {
64.         rens::list<int> lt1;
65.         lt1.push_back(1);
66.         lt1.push_back(2);
67.         lt1.push_back(3);
68.         lt1.push_back(4);
70.         for (auto e : lt1)
71.         {
72.                 cout << e << " ";
73.         }
74.         cout << endl;
75.         lt1.push_front(5);
76.         lt1.push_front(6);
78.         for (auto e : lt1)
79.         {
80.                 cout << e << " ";
81.         }
82.         cout << endl;
84.         lt1.pop_back();
85.         lt1.pop_back();
86.         lt1.pop_front();
87.         lt1.pop_front();
89.         for (auto e : lt1)
90.         {
91.                 cout << e << " ";
92.         }
93.         cout << endl;
95.         lt1.pop_back();
96.         lt1.pop_back();
97.         for (auto e : lt1)
98.         {
99.                 cout << e << " ";
100.         }
101.         cout << endl;
102. }
103. void test4()
104. {
105.         rens::list<int> lt1;
106.         lt1.push_back(1);
107.         lt1.push_back(2);
108.         lt1.push_back(3);
109.         lt1.push_back(4);
111.         for (auto e : lt1)
112.         {
113.                 cout << e << " ";
114.         }
115.         cout << endl;
117.         rens::list<int> lt2(lt1);
118.         lt1.clear();
119.         for (auto e : lt1)
120.         {
121.                 cout << e << " ";
122.         }
123.         cout << endl;
124.         for (auto e : lt2)
125.         {
126.                 cout << e << " ";
127.         }
128.         cout << endl;
129.         rens::list<int> lt3 = { 10,20,30,40 };
130.         lt1 = lt3;
131.         for (auto e : lt1)
132.         {
133.                 cout << e << " ";
134.         }
135.         cout << endl;
136. }
137. int main()
138. {
139.     //test1();
140.         //test2();
141.         //test3();
142.         test4();
143.         return 0;
144. }

复制代码

 


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