【C++】list 模仿实现

一、list的介绍

列表是一种顺序容器，它允许在序列中的任何位置实行常量时间插入和删除利用，并允许在两个方向上举行迭代。
它的底层是一个带头双向循环链表，我们直接来看一看整体框架：

1. // List的节点类
2. template<class T>
3. struct ListNode
4. {
5.     ListNode(const T& val = T())
6.         :_val(val)
7.         ,_pPre(nullptr)
8.         ,_pNext(nullptr)
9.     {}
11.     ListNode<T>* _pPre;
13.     ListNode<T>* _pNext;
14.     T _val;
15. };
17. template<class T>
18.         class list
19.         {
20.                 typedef list_node<T> node;
21.         public:
22.         //迭代器
23.                 typedef __list_iterator<T> iterator;
24.         typedef __list_const_iterator<T> const_iterator;
25.         //构造
26.                 list()
27.                 {
28.                         _head = new node(T());
29.                         _head->_next = _head;
30.                         _head->_prev = _head;
31.                 }
32.         private:
33.                 node* _head;
34.         size_t _size;
35.         };

复制代码

二、迭代器

1、list的迭代器失效问题

insert，迭代器不失效。
earse失效。
2、迭代器的功能分类

1、单向迭代器：只能++，不能–。例如单链表，哈希表；
2、双向迭代器：既能++也能–。例如双向链表；
3、随机访问迭代器：能+±-，也能+和-。例如vector和string。
迭代器是内嵌范例（内部类或定义在类里）
3、list迭代器的模仿实现

1、list迭代器的引入
对于vector和string类而言，物理空间是一连的，原生的指针就是迭代器了（不一定哦，只是大概，版本大概差异），解引用就是数据了。但是对于这里的list而言，空间是不一连的，我们知道，迭代器有两个特征：1.解引用 2.++ /–
此时假如解引用是拿不到数据的（空间不一连），更不用说++指向下一个结点了。所以，对于list的迭代器，原生指针已经不符合我们的需求了，我们必要去举行特殊处理：举行类的封装。 我们可以通过类的封装以及运算符重载支持，这样就可以实现像内置范例一样的运算符。
2.平凡迭代器

1. //用类封装迭代器
2. template <class T>
3. struct __list_iterator
4. {
5.     typedef list_node<T> node;
6.     //用节点的指针进行构造
7.     __list_iterator(node* p)
8.         :_pnode(p)
9.     {}
10.     //迭代器运算符的重载
11.     T& operator*()
12.     {
13.         return _pnode->_data;
14.     }
15.     __list_iterator<T>& operator++()//返回值不要写成node* operator++()，因为迭代器++返回迭代器
16.     {
17.         //return _pnode->_next;
18.         _pnode=_pnode->_next;
19.         return *this;//返回的是迭代器
20.     }
21.     bool operator!=(const __list_iterator<T>& it)
22.     {
23.         return _pnode != it._pnode;
24.     }
25. public:
26.     node* _pnode;//封装一个节点的指针
27. };

复制代码

  留意：对于迭代器的拷贝构造和赋值重载我们并不必要自己去手动实现，编译器默认天生的就是浅拷贝，而我们必要的就是浅拷贝，这也说明了，并不是说假如有指针就必要我们去实现深拷贝。别的，迭代器通过结构体指针访问修改链表，所以，对于迭代器我们并不必要构造函数，结点的开释由链表管理。
  3.const迭代器
const迭代器的错误写法：

1. typedef __list_iterator<T> iterator;
2. const list<T>::iterator it=lt.begin();

复制代码

  因为typedef后，const修饰的是迭代器it，只能调用operator*(),调不了operator++()。
  精确写法：想实现const迭代器，，必要再写一个const版本迭代器的类。

1. //用类封装const迭代器
2. template <class T>
3. struct __list_const_iterator
4. {
5.     typedef list_node<T> node;
6.     //用节点的指针进行构造
7.     __list_const_iterator(node* p)
8.         :_pnode(p)
9.     {}
10.     //迭代器运算符的重载
11.     const T& operator*()const
12.     {
13.         return _pnode->_data;
14.     }
15.     __list_const_iterator<T>& operator++()//返回值不要写成node*，因为迭代器++肯定返回迭代器
16.     {
17.         //return _pnode->_next;//返回类型错误的
18.         _pnode = _pnode->_next;
19.         return *this;//返回的是迭代器
20.     }
21.     __list_const_iterator<T>& operator--()
22.     {
23.         _pnode = _pnode->_prev;
24.         return *this;
25.     }
26.     bool operator!=(const __list_const_iterator<T>& it)const
27.     {
28.         return _pnode != it._pnode;
29.     }
30. public:
31.     node* _pnode;//封装一个节点的指针
32. };
34. typedef __list_const_iterator<T> const_iterator;

复制代码

  假如是这样子去实现的话，我们就会发现，这两个迭代器的实现并没有多大的区别，唯一的区别就在于operator*的差异。const迭代器和平凡迭代器的唯一区别就是平凡迭代器返回T&，可读可写，const迭代器返回const T&,可读不可写，上面的代码存在很大的问题：代码冗余，所以我们应该去解决这个问题：我们可以参考源码的实现：类模板参数解决这个问题，这也是迭代器的强大之处

1. //用类封装普通/const迭代器
2. template <class T,class Ref>
3. struct __list_iterator
4. {
5.     typedef list_node<T> node;
6.     typedef __list_iterator<T,Ref> Self;
7.     //用节点的指针进行构造
8.     __list_iterator(node* p)
9.         :_pnode(p)
10.     {}
11.     //迭代器运算符的重载
12.     Ref operator*()
13.     {
14.         return _pnode->_data;
15.     }
16.     Self& operator++()//返回值不要写成node*，因为迭代器++肯定返回迭代器啊，你返回节点指针类型不对
17.     {
18.         //return _pnode->_next;//返回类型错误的
19.         _pnode=_pnode->_next;
20.         return *this;//返回的是迭代器
21.     }
22.     Self& operator--()
23.     {
24.         _pnode = _pnode->_prev;
25.         return *this;
26.     }
27.     bool operator!=(const Self& it)
28.     {
29.         return _pnode != it._pnode;
30.     }
31. public:
32.     node* _pnode;//封装一个节点的指针
33. };
35. typedef __list_iterator<T, T&> iterator;
36. typedef __list_iterator<T, const T&> const_iterator;

复制代码

4、迭代器operator->的重载
迭代器的用法就是模仿指针的活动，假如现在有一个指向结构的指针，那么就必要用到->来解引用。

1. //*的重载：返回节点的数据
2. Ref operator*()
3. {
4.     return _pnode->_data;
5. }
6. //->的重载：返回数据的指针
7. T* operator->()
8. {
9.     return &_pnode->_data;
10. }

复制代码

但是operator->利用T*做返回值范例，这样无论是平凡迭代器和const迭代器都能修改，所以operator->的返回值范例应该改为泛型：

1. template <class T, class Ref,class Ptr>
2. Ptr operator->()
3. {
4.     return &_pnode->_data;
5. }
6. typedef __list_iterator<T, T&, T*> iterator;
7. typedef __list_iterator<T, const T&, const T*> const_iterator;

复制代码

5、迭代器价值
1、封装底层实现，不袒露底层实现的细节；
2、多种容器提供同一的访问方式，降低利用本钱；
C语言没有运算符重载和引用等语法，是实现不了迭代器的。
三、增删查改

1、insert和erase

insert：在pos位置上一个插入，返回插入位置的迭代器，对于list的insert迭代器不会失效，vector失效是因为扩容导致pos位置造成野指针问题。

1.                 iterator insert(iterator pos,const T& x)
2.                 {
3.                         node* newnode = new node(x);
4.                         node* cur = pos._pnode;
5.                         node* prev = cur->_prev;
7.                         newnode->_prev = prev;
8.                         prev->_next = newnode;
9.                         newnode->_next = cur;
10.                         cur->_prev = newnode;
12.                         ++_size;
13.                         return iterator(newnode);
14.                 }

复制代码

erase:这里的带头（哨兵位）头结点不可删除，返回值是删除位置的下一个，对于list的erase迭代器是失效的

1.                 iterator erase(iterator pos)
2.                 {
3.                         assert(pos != end());
4.                         node* prev = pos._pnode->_prev;
5.                         node* next = pos._pnode->_next;
7.                         prev->_next = next;
8.                         next->_prev = prev;
9.                         delete pos._pnode;
10.                         --_size;
11.                         return iterator(next);
12.                 }

复制代码

2、push_back和push_front

1.         void push_back(const T& x)
2.                 {
3.                         /*node* newnode = new node(x);
4.                         node* tail = _head->_prev;
6.                         newnode->_prev = tail;
7.                         tial->_next = newnode;
8.                         newnode->_next = _head;
9.                         _head->_prev = newnode;*/
10.                         insert(end(), x);
11.                 }
13.                 void push_front(const T& x)
14.                 {
15.                         insert(begin(), x);
16.                 }

复制代码

3、pop_back和pop_front

尾删和头删，复用erase即可

1.                 void pop_front()
2.                 {
3.                         erase(begin());
4.                 }
6.                 void pop_back()
7.                 {
8.                         erase(--end());
9.                 }

复制代码

四、list的构造函数

1、构造

默认构造：

1. list()
2. {
3.     _head = new node(T());
4.         _head->_next = _head;
5.         _head->_prev = _head;
6.         _size = 0;
7. }

复制代码

我们可以用empty_initialize()来封装初始化，方便复用，不用每次都写：

1. void empty_initialize()
2. {
3.     _head = new node(T());
4.     _head->_next = _head;
5.         _head->_prev = _head;
6.         _size = 0;
7. }

复制代码

迭代器区间构造：

1.             //迭代器区间构造
2.                 template <class InputIterator>
3.                 list(InputIterator first, InputIterator last)
4.                 {
5.                         empty_initialize();
6.                         while (first != last)
7.                         {
8.                                 push_back(*first);
9.                                 ++first;
10.                         }
11.                 }

复制代码

拷贝构造：
传统写法

1.                 list(const list<T>& lt)
2.                 {
3.                         empty_initialize();
4.                         for (const auto& e : lt)
5.                         {
6.                                 push_back(e);
7.                         }
8.                 }

复制代码

用范围for举行尾插，但是要留意要加上&，范围for是*it赋值给给e，又是一个拷贝，e是T范例对象，依次取得容器中的数据，T假如是string范例，不断拷贝，push_back之后又烧毁。
现代写法

1.                 void swap(list<T>& lt)
2.                 {
3.                         std::swap(_head, lt._head);
4.                         std::swap(_size, lt._size);
5.                 }               
6.                 list(const list<T>& lt)
7.                 {
8.                         empty_initialize();
9.                         list<T> tmp(lt.begin(), lt.end());
10.                         swap(tmp);
11.                 }

复制代码

2、赋值重载

传统写法

1.                 list<T>& operator=(list<T>& lt)
2.                 {
3.                         if (this != &lt)
4.                         {
5.                                 clear();
6.                                 for (const auto& e : lt)
7.                                 {
8.                                         push_back(e);
9.                                 }
10.                         }
11.                         return *this;
12.                 }

复制代码

现代写法

1.                 list<T>& operator=(list<T> lt)
2.                 {
3.                         swap(lt);
4.                         return *this;
5.                 }

复制代码

3、析构

对于list，有单独的clear()接口，list的析构可以直接复用clear()，同时还必要我们去开释掉头结点：

1.                 ~list()
2.                 {
3.                         clear();
4.             delete _head;
5.                         _head = nullptr;
6.                 }
8.                 void clear()
9.                 {
10.                         iterator it = begin();
11.                         while (it != end())
12.                         {
13.                                 it = erase(it);
14.                         }
15.                 }

复制代码

类名和范例的区别

平凡类：类名等于范例
类模板：类名不等价于范例，例如list类模板类名是list,范例list等。
所以我们平常写函数形参和返回值时，总会带上形参和返回值的范例：

1. // 赋值运算符重载
2. list<T>& operator=(list<T> lt)
3. {
4.     swap(lt);
5.     return *this;
6. }

复制代码

五、list和vector的对比

1.vector

vector的优点（结构牛逼）：
1、支持下标的随机访问；
2、尾插尾删服从高（当然扩容的那一次尾插会较慢）；
3、CPU高速缓存掷中高（数据从缓存加载至CPU中，会加载一连的一段数据，vector因为结构一连，高速缓存掷中高）。
vector的缺点：
1、非尾插尾删服从低；
2、扩容有消耗，并存在一定的空间浪费。
vector迭代器失效问题：
insert/erase均失效。（假如string的insert和erase形参是迭代器，那么也会失效，但是大部分接口是下标传参，不考虑失效问题，只有几个接口是迭代器传参，必要留意迭代器失效问题）
2、list

list的优点：
1、按需申请开释，无需扩容；
2、恣意位置插入删除时间O(1)；（这里说的是插入删除，不要加上查找的时间）
list的缺点：
1、不支持下标的随机访问；
2、CPU高速缓存掷中率低；
3、每一个节点除了存储数据外，还必要额外存储两个指针。
vectorlist底 层 结 构动态顺序表，一段一连空间带头结点的双向循环链表随 机 访 问支持随机访问，访问某个元素服从O(1)不支持随机访问，访问某个元素服从O(N)插 入 和 删 除恣意位置插入和删除服从低，必要搬移元素，时间复杂度为O(N)，插入时有大概必要增容，增容：开辟新空间，拷贝元素，开释旧空间，导致服从更低恣意位置插入和删除服从高，不必要搬移元素，时间复杂度为O(1)空 间 利 用 率底层为一连空间，不轻易造成内存碎片，空间利用率高，缓存利用率高底层节点动态开辟，末节点轻易造成内存碎片，空间利用率低，缓存利用率低迭 代 器原生态指针对原生态指针(节点指针)举行封装迭 代 器 失 效在插入元素时，要给所有的迭代器重新赋值，因为插入元素有大概会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器必要重新赋值否则会失效插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响使 用 场 景必要高效存储，支持随机访问，不关心插入删除服从大量插入和删除利用，不关心随机访问 六、模仿实现list整体代码

1. namespace fx
2. {
3.     // List的节点类
4.     template<class T>
5.     struct ListNode
6.     {
7.         ListNode(const T& val = T())
8.             :_val(val)
9.             ,_pPre(nullptr)
10.             ,_pNext(nullptr)
11.         {}
13.         ListNode<T>* _pPre;
15.         ListNode<T>* _pNext;
16.         T _val;
17.     };
20.     //List的迭代器类
21.     template<class T, class Ref, class Ptr>
22.     class ListIterator
23.     {
24.         typedef ListNode<T>* PNode;
25.         typedef ListIterator<T, Ref, Ptr> Self;
26.     public:
27.         ListIterator(PNode pNode = nullptr)
28.             :_pNode(pNode)
29.         {}
31.         ListIterator(const Self& l)
32.         {
33.             _pNode = l._pNode;
34.         }
36.         Ref operator*()
37.         {
38.             return _pNode->_val
39.         }
41.         Ptr operator->()
42.         {
44.         }
46.         Self& operator++()
47.         {
48.             return _pNode->_pNext;
49.         }
51.         Self operator++(int)
52.         {
53.             Self tmp(*this);
54.             _pNode = _pNode->_pNext;
55.             return tmp;
56.         }
57.         Self& operator--()
58.         {
59.             return _pNode->_pPre;
60.         }
61.         Self& operator--(int)
62.         {
63.             Self tmp(*this);
64.             _pNode = _pNode->_pPre;
65.             return tmp;
66.         }
67.         bool operator!=(const Self& l)
68.         {
69.             return _pNode != l._pNode;
70.         }
71.         bool operator==(const Self& l)
72.         {
73.             return _pNode == l._pNode;
74.         }
75.     private:
76.         PNode _pNode;
77.     };
80.     //list类
81.     template<class T>
82.     class list
83.     {
84.         typedef ListNode<T> Node;
85.         typedef Node* PNode;
86.     public:
87.         typedef ListIterator<T, T&, T*> iterator;
88.         typedef ListIterator<T, const T&, const T*> const_iterator;
89.     public:
90.         ///
91.         // List的构造
92.         void CreateHead()
93.         {
94.             Node* _pHead = new Node;
95.             _pHead->_pNext = _pHead;
96.             _pHead->_pPre = _pHead;
97.             _size = 0;
98.         }
99.         list()
100.         {
101.             CreateHead();
102.         }
104.         list(int n, const T& value = T())
105.         {
106.             CreateHead();
107.             for (int i = 0; i < n; ++i)
108.             {
109.                 push_back(value);
110.             }
111.                
112.         }
114.         template <class Iterator>
115.         list(Iterator first, Iterator last)
116.         {
117.             CreateHead();
118.             wihle(first != last)
119.             {
120.                 push_back(*first);
121.                 ++first;
122.             }
123.         }
125.         list(const list<T>& l)
126.         {
127.             CreateHead();
128.             for (auto& e : lt)
129.             {
130.                 push_back(e);
131.             }
132.         }
134.         list<T>& operator=(const list<T> l)
135.         {
136.             swap(l);
137.             return *this;
138.         }
140.         ~list()
141.         {
142.             clear();
143.             delete _head;
144.             _head = nullptr;
145.         }
148.         ///
149.         // List Iterator
150.         iterator begin()
151.         {
152.             return _pHead->_pNext;
153.         }
154.         iterator end()
155.         {
156.             return _pHead;
157.         }
158.         const_iterator begin()
159.         {
160.             return _head->_next;
161.         }
162.         
163.         const_iterator end()
164.         {
165.             return _pHead;
166.         }
169.         ///
170.         // List Capacity
171.         size_t size()const
172.         {
173.             return _size;
174.         }
175.         bool empty()const
176.         {
177.             return _size == 0;
178.         }
181.         
182.         // List Access
183.         T& front()
184.         {
185.             return *begin();
186.         }
187.         const T& front()const
188.         {
189.             return *begin();
190.         }
191.         T& back()
192.         {
193.             return _head->_prev->_val;
194.         }
195.         const T& back()const
196.         {
197.             return _head->_prev->_val;
198.         }
201.         
202.         // List Modify
203.         void push_back(const T& val)
204.         {
205.             insert(end(), val);
206.         }
208.         void pop_back()
209.         {
210.             erase(--end());
211.         }
212.         void push_front(const T& val)
213.         {
214.             insert(begin(), val);
215.         }
216.         void pop_front()
217.         {
218.             erase(begin());
219.         }
220.         // 在pos位置前插入值为val的节点
221.         iterator insert(iterator pos, const T& val)
222.         {
223.             Node* newnode = new Node;
224.             Node* cur = pos._node;
225.             Node* prev = cur->_prev;
227.             newnode->_next = cur;
228.             cur->_prev = newnode;
229.             newnode->_prev = prev;
230.             prev->_next = newnode;
232.             ++_size;
234.         }
235.         // 删除pos位置的节点，返回该节点的下一个位置
236.         iterator erase(iterator pos)
237.         {
238.             assert(pos != end());
240.             Node* prev = pos._node->_prev;
241.             Node* next = pos._node->_next;
243.             prev->_next = next;
244.             next->_prev = prev;
245.             delete pos._node;
247.             --_size;
248.         }
250.         void clear()
251.         {
252.             auto it = begin();
253.             while (it != end())
254.             {
255.                 it = erase(it);
256.             }
257.         }
258.         void swap(list<T>& l)
259.         {
260.             std::swap(_head, lt._head);
261.             std::swap(_size, lt._size);
262.         }
263.     private:
264.         PNode _pHead;
265.         size_t _size;
266.     };
267. };

复制代码

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