【C++】list容器及其模拟实现

目录

1. list的介绍及使用
1.1 list的介绍
1.2 list的使用
1.2.1 list的构造
1.2.2 list iterator的使用
1.2.3 list capacity
1.2.4 list element access
1.2.5 list modifiers
1.2.6 list的迭代器失效
2. list的模拟实现
2.1 模拟实现list
2.1.1list节点
2.1.2list常见功能接口
2.1.3list迭代器实现
2.1.4list构造与析构函数
2.1.5完整代码
2.2 list的反向迭代器
3. list与vector的对比

---

1. list的介绍及使用

1.1 list的介绍

list的文档介绍

在数据结构当中，我们学习过链表的一系列形式，带头、不带头、双向、单向、循环、不循环等形式，其中带头双向链表由于可以轻易找到头尾节点，某一节点前后节点，具有头结点，因此链表为空不需要做特殊处理等优势，作为链表最完善的形式。C++STL中list底层的结构就是采用带头双向循环链表（对list的明白需要创建在对数据结构有一定基础上，对于链表不了解的读者可以先移步学习链表。）
1.2 list的使用

list中的接口比力多，此处类似之前string、vector，只需要掌握如何正确的使用，然后再去深入研究背后的原理，以达到可扩展的本领。以下为list中一些常见的重要接口。
1.2.1 list的构造

构造函数（ (constructor)）接口说明
listlist (size_type n, const value_type& val =
value_type())构造的list中包罗n个值为val的
元素list() 构造空的list，有一个头结点
list (const list& x)拷贝构造函数list (InputIterator first, InputIterator last)用[first, last)区间中的元素构造
list

2. // list的构造
3. void TestList1()
4. {
5.         list<int> l1;                         // 构造空的l1
6.         list<int> l2(4, 100);                 // l2中放4个值为100的元素
7.         list<int> l3(l2.begin(), l2.end());  // 用l2的[begin(), end()）左闭右开的区间构造l3
8.         list<int> l4(l3);                    // 用l3拷贝构造l4
10.         // 以数组为迭代器区间构造l5
11.         int array[] = { 16,2,77,29 };
12.         list<int> l5(array, array + sizeof(array) / sizeof(int));
14.         // 列表格式初始化C++11
15.         list<int> l6{ 1,2,3,4,5 };
17.         // 用迭代器方式打印l5中的元素
18.         list<int>::iterator it = l5.begin();
19.         while (it != l5.end())
20.         {
21.                 cout << *it << " ";
22.                 ++it;
23.         }
24.         cout << endl;
26.         // C++11范围for的方式遍历
27.         for (auto& e : l5)
28.                 cout << e << " ";
30.         cout << endl;
31. }

复制代码

1.2.2 list iterator的使用

此处，各人可临时将迭代器明白成一个指针，该指针指向list中的某个节点。当然由于链表的节点存储并不是一块连续的空间，因此list的迭代器并不是原生指针，而是通过封装实现的。
函数声明接口说明begin + end返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器rbegin
+rend返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的reverse_iterator,即begin位置

2. // list迭代器的使用
3. // 注意：遍历链表只能用迭代器和范围for
4. void PrintList(const list<int>& l)
5. {
6.         // 注意这里调用的是list的 begin() const，返回list的const_iterator对象
7.         for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it)
8.         {
9.                 cout << *it << " ";
10.                 // *it = 10; 编译不通过
11.         }
13.         cout << endl;
14. }
16. void TestList2()
17. {
18.         int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
19.         list<int> l(array, array + sizeof(array) / sizeof(array[0]));
20.         // 使用正向迭代器正向list中的元素
21.         // list<int>::iterator it = l.begin();   // C++98中语法
22.         auto it = l.begin();                     // C++11之后推荐写法
23.         while (it != l.end())
24.         {
25.                 cout << *it << " ";
26.                 ++it;
27.         }
28.         cout << endl;
30.         // 使用反向迭代器逆向打印list中的元素
31.         // list<int>::reverse_iterator rit = l.rbegin();
32.         auto rit = l.rbegin();
33.         while (rit != l.rend())
34.         {
35.                 cout << *rit << " ";
36.                 ++rit;
37.         }
38.         cout << endl;
39. }

复制代码

  STL中范围同一都是左闭右开的区间，在list中由于头结点并不存储有效的数据，begin返回的是指向第一个有效数据的迭代器，end()返回最后一个元素的下一个位置，由于是循环链表，最后一个元素的下一个位置指向就是头结点。
  list由于底层的链表存储空间不连续，因此list不在支持下标 +[]的随机访问，同样，比起之前string与vector，list的迭代器也发生了变化，list迭代器不再支持+或-某一常数来改变访问的指向。
  这里我们需要在拓展增补一下迭代器的相干概念

   基于功能上是正向还是反向遍历，迭代器可以分为正向迭代器iterator与反向迭代器reverse_iterator，以及支持const对象的迭代器。
  基于底层结构的不同，实现出来的迭代器又有性质上的不同，可以分为单向、双向、随机迭代器（STL底层还抽象出一个最小单元的输入迭代器，我们使用的只有上诉三个迭代器，这个最小单元可以不考虑），不同迭代器支持的迭代操作不同，单向迭代器只支持单向移动，只能++，双向迭代器如我们本次学习list支持++、--两个方向迭代，而随机迭代器支持通过+、-某一个对象跳跃式移动到某一个位置。STL中所实现的一些组件，由于底层实现存在+、-、++、--等操作，对于有的迭代器是不支持的，如上段代码中sort底层实现式快排加堆排存在+、-等操作，因此传入的迭代器必须是随机迭代器。（不同的迭代器之间其实还存在者继承等复杂关系，本文不在深入探究）
  

   由上图不同迭代器支持的符号，我们可以得出使用范围上随机迭代器>双向迭代器>单向迭代器。以是在日后的使用中，我们需要根据文档查询对应支持的迭代器范例。
  

   【留意】
1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
2. rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动
  1.2.3 list capacity

函数声明接口说明empty检测list是否为空，是返回true，否则返回falsesize返回list中有效节点的个数 1.2.4 list element access

函数声明接口说明front返回list的第一个节点中值的引用back返回list的最后一个节点中值的引用 1.2.5 list modifiers

函数声明接口说明push_front在list首元素前插入值为val的元素pop_front删除list中第一个元素push_back在list尾部插入值为val的元素pop_back删除list中最后一个元素insert在list position 位置中插入值为val的元素erase删除list position位置的元素swap互换两个list中的元素clear清空list中的有效元素

2. // list插入和删除
3. // push_back/pop_back/push_front/pop_front
4. void TestList3()
5. {
6.         int array[] = { 1, 2, 3 };
7.         list<int> L(array, array + sizeof(array) / sizeof(array[0]));
9.         // 在list的尾部插入4，头部插入0
10.         L.push_back(4);
11.         L.push_front(0);
12.         PrintList(L);
14.         // 删除list尾部节点和头部节点
15.         L.pop_back();
16.         L.pop_front();
17.         PrintList(L);
18. }
20. // insert /erase
21. void TestList4()
22. {
23.         int array1[] = { 1, 2, 3 };
24.         list<int> L(array1, array1 + sizeof(array1) / sizeof(array1[0]));
26.         // 获取链表中第二个节点
27.         auto pos = ++L.begin();
28.         cout << *pos << endl;
30.         // 在pos前插入值为4的元素
31.         L.insert(pos, 4);
32.         PrintList(L);
34.         // 在pos前插入5个值为5的元素
35.         L.insert(pos, 5, 5);
36.         PrintList(L);
38.         // 在pos前插入[v.begin(), v.end)区间中的元素
39.         vector<int> v{ 7, 8, 9 };
40.         L.insert(pos, v.begin(), v.end());
41.         PrintList(L);
43.         // 删除pos位置上的元素
44.         L.erase(pos);
45.         PrintList(L);
47.         // 删除list中[begin, end)区间中的元素，即删除list中的所有元素
48.         L.erase(L.begin(), L.end());
49.         PrintList(L);
50. }
52. // resize/swap/clear
53. void TestList5()
54. {
55.         // 用数组来构造list
56.         int array1[] = { 1, 2, 3 };
57.         list<int> l1(array1, array1 + sizeof(array1) / sizeof(array1[0]));
58.         PrintList(l1);
60.         // 交换l1和l2中的元素
61.         list<int> l2;
62.         l1.swap(l2);
63.         PrintList(l1);
64.         PrintList(l2);
66.         // 将l2中的元素清空
67.         l2.clear();
68.         cout << l2.size() << endl;
69. }

复制代码

list中另有一些操作，需要用到时各人可参阅list的文档说明。
1.2.6 list的迭代器失效

   前面说过，此处各人可将迭代器临时明白成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中举行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器（该迭代器变为野指针），其他迭代器不会受到影响。

1. void TestListIterator1()
2. {
3.         int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
4.         list<int> l(array, array + sizeof(array) / sizeof(array[0]));
5.         auto it = l.begin();
6.         while (it != l.end())
7.         {
8.                 // erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给
9.                 其赋值
10.                         l.erase(it);
11.                 ++it;
12.         }
13. }
14. // 改正
15. void TestListIterator()
16. {
17.         int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
18.         list<int> l(array, array + sizeof(array) / sizeof(array[0]));
19.         auto it = l.begin();
20.         while (it != l.end())
21.         {
22.                 l.erase(it++); // it = l.erase(it);erase会返回当前删除节点的下一节点
23.         }
24. }

复制代码

2. list的模拟实现

2.1 模拟实现list

要模拟实现list，必须要熟悉list的底层结构以及其接口的含义，通过上面的学习，这些内容已基本
掌握，现在我们来模拟实现list。
2.1.1list节点

1. //链表的节点，由于存储的数据不定，我们这里实现成模板       
2. template<class T>
3.         struct list_node
4.         {
5.                 T _data;
6.                 list_node<T>* _next;
7.                 list_node<T>* _prev;
9.                 list_node(const T& data = T())
10.                         :_data(data)
11.                         ,_next(nullptr)
12.                         ,_prev(nullptr)
13.                 {}
14.         };

复制代码

2.1.2list常见功能接口

1.                 void clear()
2.                 {
3.                         auto it = begin();//挨个释放list中节点资源
4.                         while (it != end())
5.                         {
6.                                 it = erase(it);//复用删除功能
7.                         }
8.                 }
10.                 void swap(list<T>& lt)
11.                 {
12.                         std::swap(_head, lt._head);
13.                         std::swap(_size, lt._size);
14.                 }
16.                 void push_back(const T& x)
17.                 {
18.                         /*Node* newnode = new Node(x);
19.                         Node* tail = _head->_prev;
21.                         tail->_next = newnode;
22.                         newnode->_prev = tail;
23.                         newnode->_next = _head;
24.                         _head->_prev = newnode;
26.                         ++_size;*/
28.                         insert(end(), x);//尾插直接复用插入代码
29.                 }
31.                 void push_front(const T& x)
32.                 {
33.                         insert(begin(), x);//头插直接复用插入代码
34.                 }
36.                 iterator insert(iterator pos, const T& x)
37.                 {
38.             //插入一个新节点
39.                         Node* cur = pos._node;//当前位置节点
40.                         Node* prev = cur->_prev;//前驱节点
41.                         Node* newnode = new Node(x);
43.                         // prev newnode cur
44.                         newnode->_next = cur;//新节点next指向当前位置节点
45.                         cur->_prev = newnode;//当前节点前驱指针指向新节点
46.                         newnode->_prev = prev;//新前驱节点的前驱指针指向前驱节点
47.                         prev->_next = newnode;//前驱节点next指向新节点
49.                         ++_size;//更新list中节点个数
51.                         return newnode;//返回新节点指针，返回值在根据指针构造出对应迭代器
52.                 }
54.                 void pop_back()
55.                 {
56.                         erase(--end());//尾删直接复用对应删除代码
57.                 }
59.                 void pop_front()
60.                 {
61.                         erase(begin());//前删直接复用对应删除代码
62.                 }
64.                 iterator erase(iterator pos)
65.                 {
66.                         assert(pos != end());//不能删除头结点
68.                         Node* prev = pos._node->_prev;//将删除节点前驱跟后驱节点的指向相连
69.                         Node* next = pos._node->_next;
71.                         prev->_next = next;
72.                         next->_prev = prev;
73.                         delete pos._node;//释放删除节点的资源
75.                         --_size;
77.                         return next;//返回删除节点后驱节点指针，返回值在根据指针构造出对应迭代器
78.                         //这一步返回操作可以更新外部指向删除节点的迭代器的值
79.                         //防止迭代器失效的问题
80.                 }
82.                 size_t size() const
83.                 {
84.                         return _size;
85.                 }
87.                 bool empty() const
88.                 {
89.                         return _size == 0;
90.                 }               
92.    

复制代码

2.1.3list迭代器实现

由于list的底层是链表，存储空间并不连续，因此，我们需要利用模板举行封装。首先需要说明的是，由于const_iterator指向的对象不能修改，因此如果我们通过重载的函数返回引用或者指针，那么针对const_iterator跟iterator,我们就需要写两份非常相似的代码，非常冗余，对此库内里增长Ref与Ptr两个模板参数用来控制返回值中的引用与指针，传入的参数是const对像，函数返回的引用与指针就是const修饰的，如果是平凡对象，就是平凡的指针和引用，我们就不再需要写两份非常相似的代码了。
因为list的迭代器，我们无法通过原生指针实现，为了能过还原对应的指针操作，我们需要在迭代器类中有一个成员变量是节点指针，同时由于迭代器的相干操作经常使用，我们这里使用struct定义类。

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;//通过模板参数控制iterator与const_iterator
6.                                                 //Ptr指针，Ref引用
7.                                                //不同返回值
8.                 Node* _node;
10.                 list_iterator(Node* node)
11.                         :_node(node)
12.                 {}
14.                 Ref operator*()//模拟解引用指针，我们需要将迭代器指向节点的数据返回
15.                 {
16.                         return _node->_data;
17.                 }
19.                 Ptr operator->()//模拟访问节点内部指针，我们需要将迭代器指向节点的内部成员指针返回
20.                 {
21.                         return &_node->_data;
22.                 }
24.                 Self& operator++()//模拟迭代器++,向后移动
25.                 {
26.                         _node = _node->_next;//迭代器内部的节点指针后移
27.                         return *this;//返回新节点的引用，在根据引用，构造一个新迭代器返回
28.                 }
30.                 Self& operator--()
31.                 {
32.                         _node = _node->_prev;
33.                         return *this;
34.                 }
36.                 Self operator++(int)
37.                 {
38.                         Self tmp(*this);
39.                         _node = _node->_next;
41.                         return tmp;
42.                 }
44.                 Self& operator--(int)
45.                 {
46.                         Self tmp(*this);
47.                         _node = _node->_prev;
49.                         return tmp;
50.                 }
51.                
52.                 bool operator!=(const Self& s) const
53.                 {
54.                         return _node != s._node;
55.                 }
57.                 bool operator==(const Self& s) const
58.                 {
59.                         return _node == s._node;
60.                 }
61.         };
64.         /*template<class T>//如果不通过函模板参数控制，我们就需要因为const_iterator多写一份非常相
65.                        //似的代码
66.         struct list_const_iterator
67.         {
68.                 typedef list_node<T> Node;
69.                 typedef list_const_iterator<T> Self;
70.                 Node* _node;
72.                 list_const_iterator(Node* node)
73.                         :_node(node)
74.                 {}
76.                 const T& operator*()
77.                 {
78.                         return _node->_data;
79.                 }
81.                 const T* operator->()
82.                 {
83.                         return &_node->_data;
84.                 }
86.                 Self& operator++()
87.                 {
88.                         _node = _node->_next;
89.                         return *this;
90.                 }
92.                 Self& operator--()
93.                 {
94.                         _node = _node->_prev;
95.                         return *this;
96.                 }
98.                 Self operator++(int)
99.                 {
100.                         Self tmp(*this);
101.                         _node = _node->_next;
103.                         return tmp;
104.                 }
106.                 Self& operator--(int)
107.                 {
108.                         Self tmp(*this);
109.                         _node = _node->_prev;
111.                         return tmp;
112.                 }
114.                 bool operator!=(const Self& s) const
115.                 {
116.                         return _node != s._node;
117.                 }
119.                 bool operator==(const Self& s) const
120.                 {
121.                         return _node == s._node;
122.                 }
123.         };*/

复制代码

2.1.4list构造与析构函数

与之前string和vector实现不同，空list中构造出来是有一个头结点，头节点的前驱和后驱指针都指向自己。因此，我们这里要单独实现一个空初始化函数。

1.         void empty_init()
2.                 {
3.                         _head = new Node;
4.                         _head->_next = _head;
5.                         _head->_prev = _head;
6.                         _size = 0;
7.                 }
9.                 list()
10.                 {
11.                         empty_init();
12.                 }
14.                 list(initializer_list<T> il)
15.                 {
16.                         empty_init();
17.                         for (auto& e : il)
18.                         {
19.                                 push_back(e);
20.                         }
21.                 }
23.                 // lt2(lt1)
24.                 list(const list<T>& lt)
25.                 {
26.                         empty_init();
28.                         for (auto& e : lt)
29.                         {
30.                                 push_back(e);
31.                         }
32.                 }
34.                 // lt1 = lt3 现代写法的赋值重载
35.                 list<T>& operator=(list<T> lt)
36.                 {
37.                         swap(lt);
38.                         return *this;
39.                 }
41.                 ~list()
42.                 {
43.                         clear();
44.                         delete _head;
45.                         _head = nullptr;
46.                 }

复制代码

2.1.5完整代码

1. #pragma once
2. #include<assert.h>
4. namespace zlr
5. {
6.         template<class T>
7.         struct list_node//链表的节点
8.         {
9.                 T _data;
10.                 list_node<T>* _next;
11.                 list_node<T>* _prev;
13.                 list_node(const T& data = T())
14.                         :_data(data)
15.                         ,_next(nullptr)
16.                         ,_prev(nullptr)
17.                 {}
18.         };
20.         template<class T, class Ref, class Ptr>
21.         struct list_iterator
22.         {
23.                 typedef list_node<T> Node;
24.                 typedef list_iterator<T, Ref, Ptr> Self;//通过模板参数控制iterator与const_iterator
25.                                                 //不同返回值
26.                 Node* _node;
28.                 list_iterator(Node* node)
29.                         :_node(node)
30.                 {}
32.                 Ref operator*()
33.                 {
34.                         return _node->_data;
35.                 }
37.                 Ptr operator->()
38.                 {
39.                         return &_node->_data;
40.                 }
42.                 Self& operator++()
43.                 {
44.                         _node = _node->_next;
45.                         return *this;
46.                 }
48.                 Self& operator--()
49.                 {
50.                         _node = _node->_prev;
51.                         return *this;
52.                 }
54.                 Self operator++(int)
55.                 {
56.                         Self tmp(*this);
57.                         _node = _node->_next;
59.                         return tmp;
60.                 }
62.                 Self& operator--(int)
63.                 {
64.                         Self tmp(*this);
65.                         _node = _node->_prev;
67.                         return tmp;
68.                 }
69.                
70.                 bool operator!=(const Self& s) const
71.                 {
72.                         return _node != s._node;
73.                 }
75.                 bool operator==(const Self& s) const
76.                 {
77.                         return _node == s._node;
78.                 }
79.         };
82.         /*template<class T>//如果不通过函模板参数控制，我们就需要因为const_iterator多写一份非常相
83.                        //似的代码
84.         struct list_const_iterator
85.         {
86.                 typedef list_node<T> Node;
87.                 typedef list_const_iterator<T> Self;
88.                 Node* _node;
90.                 list_const_iterator(Node* node)
91.                         :_node(node)
92.                 {}
94.                 const T& operator*()
95.                 {
96.                         return _node->_data;
97.                 }
99.                 const T* operator->()
100.                 {
101.                         return &_node->_data;
102.                 }
104.                 Self& operator++()
105.                 {
106.                         _node = _node->_next;
107.                         return *this;
108.                 }
110.                 Self& operator--()
111.                 {
112.                         _node = _node->_prev;
113.                         return *this;
114.                 }
116.                 Self operator++(int)
117.                 {
118.                         Self tmp(*this);
119.                         _node = _node->_next;
121.                         return tmp;
122.                 }
124.                 Self& operator--(int)
125.                 {
126.                         Self tmp(*this);
127.                         _node = _node->_prev;
129.                         return tmp;
130.                 }
132.                 bool operator!=(const Self& s) const
133.                 {
134.                         return _node != s._node;
135.                 }
137.                 bool operator==(const Self& s) const
138.                 {
139.                         return _node == s._node;
140.                 }
141.         };*/
143.         template<class T>
144.         class list
145.         {
146.                 typedef list_node<T> Node;
147.         public:
148.                 /*typedef list_iterator<T> iterator;
149.                 typedef list_const_iterator<T> const_iterator;*/
151.                 typedef list_iterator<T, T&, T*> iterator;//将类型重新封装，便于使用，统一风格
152.                 typedef list_iterator<T, const T&, const T*> const_iterator;
154.                 iterator begin()
155.                 {
157.                 /*        iterator it(_head->_next);
158.                         return it;*/
160.                         //return iterator(_head->_next);
161.                         return _head->_next;
162.                 }
164.                 iterator end()
165.                 {
166.                         return _head;
167.                 }
169.                 const_iterator begin() const
170.                 {
171.                         return _head->_next;
172.                 }
174.                 const_iterator end() const
175.                 {
176.                         return _head;
177.                 }
179.                 void empty_init()
180.                 {
181.                         _head = new Node;
182.                         _head->_next = _head;
183.                         _head->_prev = _head;
184.                         _size = 0;
185.                 }
187.                 list()
188.                 {
189.                         empty_init();
190.                 }
192.                 list(initializer_list<T> il)
193.                 {
194.                         empty_init();
195.                         for (auto& e : il)
196.                         {
197.                                 push_back(e);
198.                         }
199.                 }
201.                 // lt2(lt1)
202.                 list(const list<T>& lt)
203.                 {
204.                         empty_init();
206.                         for (auto& e : lt)
207.                         {
208.                                 push_back(e);
209.                         }
210.                 }
212.                 // lt1 = lt3
213.                 list<T>& operator=(list<T> lt)
214.                 {
215.                         swap(lt);
216.                         return *this;
217.                 }
219.                 ~list()
220.                 {
221.                         clear();
222.                         delete _head;
223.                         _head = nullptr;
224.                 }
226.                 void clear()
227.                 {
228.                         auto it = begin();
229.                         while (it != end())
230.                         {
231.                                 it = erase(it);
232.                         }
233.                 }
235.                 void swap(list<T>& lt)
236.                 {
237.                         std::swap(_head, lt._head);
238.                         std::swap(_size, lt._size);
239.                 }
241.                 void push_back(const T& x)
242.                 {
243.                         /*Node* newnode = new Node(x);
244.                         Node* tail = _head->_prev;
246.                         tail->_next = newnode;
247.                         newnode->_prev = tail;
248.                         newnode->_next = _head;
249.                         _head->_prev = newnode;
251.                         ++_size;*/
253.                         insert(end(), x);//直接复用代码
254.                 }
256.                 void push_front(const T& x)
257.                 {
258.                         insert(begin(), x);
259.                 }
261.                 iterator insert(iterator pos, const T& x)
262.                 {
263.                         Node* cur = pos._node;
264.                         Node* prev = cur->_prev;
265.                         Node* newnode = new Node(x);
267.                         // prev newnode cur
268.                         newnode->_next = cur;
269.                         cur->_prev = newnode;
270.                         newnode->_prev = prev;
271.                         prev->_next = newnode;
273.                         ++_size;
275.                         return newnode;
276.                 }
278.                 void pop_back()
279.                 {
280.                         erase(--end());
281.                 }
283.                 void pop_front()
284.                 {
285.                         erase(begin());
286.                 }
288.                 iterator erase(iterator pos)
289.                 {
290.                         assert(pos != end());
292.                         Node* prev = pos._node->_prev;
293.                         Node* next = pos._node->_next;
295.                         prev->_next = next;
296.                         next->_prev = prev;
297.                         delete pos._node;
299.                         --_size;
301.                         return next;
302.                 }
304.                 size_t size() const
305.                 {
306.                         return _size;
307.                 }
309.                 bool empty() const
310.                 {
311.                         return _size == 0;
312.                 }
314.         private:
315.                 Node* _head;
316.                 size_t _size;
317.         };
319.         struct AA
320.         {
321.                 int _a1 = 1;
322.                 int _a2 = 1;
323.         };
325.         // 按需实例化
326.         // T* const ptr1
327.         // const T* ptr2
328.         template<class Container>
329.         void print_container(const Container& con)
330.         {
331.                 // const iterator -> 迭代器本身不能修改
332.                 // const_iterator -> 指向内容不能修改
333.                 typename Container::const_iterator it = con.begin();
334.                 //auto it = con.begin();
335.                 while (it != con.end())
336.                 {
337.                         //*it += 10;
339.                         cout << *it << " ";
340.                         ++it;
341.                 }
342.                 cout << endl;
344.                 for (auto e : con)
345.                 {
346.                         cout << e << " ";
347.                 }
348.                 cout << endl;
349.         }
351.         void test_list1()
352.         {
353.                 list<int> lt;
354.                 lt.push_back(1);
355.                 lt.push_back(2);
356.                 lt.push_back(3);
357.                 lt.push_back(4);
359.                 list<int>::iterator it = lt.begin();
360.                 while (it != lt.end())
361.                 {
362.                         *it += 10;
364.                         cout << *it << " ";
365.                         ++it;
366.                 }
367.                 cout << endl;
369.                 for (auto e : lt)
370.                 {
371.                         cout << e << " ";
372.                 }
373.                 cout << endl;
374.                 print_container(lt);
376.                 list<AA> lta;
377.                 lta.push_back(AA());
378.                 lta.push_back(AA());
379.                 lta.push_back(AA());
380.                 lta.push_back(AA());
381.                 list<AA>::iterator ita = lta.begin();
382.                 while (ita != lta.end())
383.                 {
384.                         //cout << (*ita)._a1 << ":" << (*ita)._a2 << endl;
385.                         // 特殊处理，本来应该是两个->才合理，为了可读性，省略了一个->
386.                         cout << ita->_a1 << ":" << ita->_a2 << endl;
387.                         cout << ita.operator->()->_a1 << ":" << ita.operator->()->_a2 << endl;
389.                         ++ita;
390.                 }
391.                 cout << endl;
392.         }
394.         void test_list2()
395.         {
396.                 list<int> lt;
397.                 lt.push_back(1);
398.                 lt.push_back(2);
399.                 lt.push_back(3);
400.                 lt.push_back(4);
402.                 // insert以后迭代器不失效
403.                 list<int>::iterator it = lt.begin();
404.                 lt.insert(it, 10);
405.                 *it += 100;
407.                 print_container(lt);
409.                 // erase以后迭代器失效
410.                 // 删除所有的偶数
411.                 it = lt.begin();
412.                 while (it != lt.end())
413.                 {
414.                         if (*it % 2 == 0)
415.                         {
416.                                 it = lt.erase(it);
417.                         }
418.                         else
419.                         {
420.                                 ++it;
421.                         }
422.                 }
424.                 print_container(lt);
425.         }
427.         void test_list3()
428.         {
429.                 list<int> lt1;
430.                 lt1.push_back(1);
431.                 lt1.push_back(2);
432.                 lt1.push_back(3);
433.                 lt1.push_back(4);
435.                 list<int> lt2(lt1);
437.                 print_container(lt1);
438.                 print_container(lt2);
440.                 list<int> lt3;
441.                 lt3.push_back(10);
442.                 lt3.push_back(20);
443.                 lt3.push_back(30);
444.                 lt3.push_back(40);
446.                 lt1 = lt3;
447.                 print_container(lt1);
448.                 print_container(lt3);
449.         }
451.         void func(const list<int>& lt)
452.         {
453.                 print_container(lt);
454.         }
456.         void test_list4()
457.         {
458.                 // 直接构造
459.                 list<int> lt0({ 1,2,3,4,5,6 });
460.                 // 隐式类型转换
461.                 list<int> lt1 = { 1,2,3,4,5,6,7,8 };
462.                 const list<int>& lt3 = { 1,2,3,4,5,6,7,8 };
464.                 func(lt0);
465.                 func({ 1,2,3,4,5,6 });
467.                 print_container(lt1);
468.                
469.                 //auto il = { 10, 20, 30 };
470.         /*        initializer_list<int> il = { 10, 20, 30 };
471.                 cout << typeid(il).name() << endl;
472.                 cout << sizeof(il) << endl;*/
473.         }
474. }

复制代码

2.2 list的反向迭代器

通过前面例子知道，反向迭代器的++就是正向迭代器的--，反向迭代器的--就是正向迭代器的++，
因此反向迭代器的实现可以借助正向迭代器，即：反向迭代器内部可以包罗一个正向迭代器，对
正向迭代器的接口举行包装即可。

1. template<class Iterator>
2. class ReverseListIterator
3. {
4.         // 注意：此处typename的作用是明确告诉编译器，Ref是Iterator类中的类型，而不是静态
5.         成员变量
6.                 // 否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员变量
7.                 // 因为静态成员变量也是按照 类名::静态成员变量名 的方式访问的
8. public:
9.         typedef typename Iterator::Ref Ref;
10.         typedef typename Iterator::Ptr Ptr;
11.         typedef ReverseListIterator<Iterator> Self;
12. public:
13.         //
14.         // 构造
15.         ReverseListIterator(Iterator it) : _it(it) {}
16.         //
17.         // 具有指针类似行为
18.         Ref operator*() {
19.                 Iterator temp(_it);
20.                 --temp;
21.                 return *temp;
22.         }
23.         Ptr operator->() { return &(operator*()); }
24.         //
25.         // 迭代器支持移动
26.         Self& operator++() {
27.                 --_it;
28.                 return *this;
29.         }
30.         Self operator++(int) {
31.                 Self temp(*this);
32.                 --_it;
33.                 return temp;
34.         }
35.         Self& operator--() {
36.                 ++_it;
37.                 return *this;
38.         }
39.         Self operator--(int)
40.         {
41.                 Self temp(*this);
42.                 ++_it;
43.                 return temp;
44.         }
45.         //
46. // 迭代器支持比较
47. bool operator!=(const Self& l)const { return _it != l._it; }
48. bool operator==(const Self& l)const { return _it != l._it; }
49. Iterator _it;
50. };

复制代码

3. list与vector的对比

vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及
应用场景不同，其重要不同如下：（vector与list的重要区别还是基于底层顺序表与链表的区别，对区别感兴趣的读者可以移步看笔者【初阶数据结构】顺序表与链表的比力（附题）这篇文章）
vectorlist底
层
结
构动态顺序表，一段连续空间带头结点的双向循环链表随
机
访
问支持随机访问，访问某个元素效率O(1)不支持随机访问，访问某个元素效率O(N)插
入
和
删
除任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N)，插入时有大概需要增容，增容：开辟新空间，拷贝元素，开释旧空间，导致效率更低任意位置插入和删除效率高，不需要搬移元素，时间复杂度为O(1)空
间
利
用
率底层为连续空间，不轻易造成内存碎片，空间利用率高，缓存利用率高底层节点动态开辟，小节点轻易造成内存碎片，空间利用率低，缓存利用率低迭
代
器原生态指针对原生态指针(节点指针)举行封装迭
代
器
失
效在插入元素时，要给全部的迭代器重新赋值，因为插入元素有大概会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响使
用
场
景需要高效存储，支持随机访问，不关心插入删除效率大量插入和删除操作，不关心随机访问

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