【C/C++】STL——深度剖析list容器

​👻内容专栏： C/C++编程
🐨本文概括：list的介绍与使用、深度剖析及模拟实现。
🐼本文作者： 阿四啊
🐸发布时间：2023.10.12

一、list的介绍与使用

1.1 list的介绍

cpluplus网站中有关list的介绍👉 list的文档介绍

---

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

1.2 list的使用

list中的接口也比较多，此处的学习也是类似，只需要掌握如何正确的使用，然后再去深入研究底层的原理，已达到可扩展的能力。以下为list要学习的常用接口。

1.2.1 list的构造

以下为list的四种构造方式。我们通常使用迭代器遍历访问list，由于list是一种双向链表，不支持随机访问，所以不能像数组一样使用[]操作符来访问元素。
代码演示：

#include
#include
#include
#include
using namespace std;
//list的使用及测试
void test_list1()
{
	//无参初始化
	list<int> lt1;
	lt1.push_back(1);
	lt1.push_back(2);
	lt1.push_back(3);
	lt1.push_back(4);

	list<int>::iterator it1 = lt1.begin();
	while (it1 != lt1.end())
	{
		cout << *it1 << " ";
		it1++;
	}
	cout << endl;
 
	//n个val初始化
	list<string> lt2(10,"xxx");
	list<string>::iterator it2 = lt2.begin();
	while (it2 != lt2.end())
	{
		cout << *it2 << " ";
		it2++;
	}
	cout << endl;

	//迭代器区间初始化
	int arr[] = { 10, 20, 30, 40 };

	list<int> lt3(arr, arr + sizeof(arr) / sizeof(*arr));
	list<int>::iterator it3 = lt3.begin();
	while (it3 != lt3.end())
	{
		cout << *it3 << " ";
		it3++;
	}
	cout << endl;

	//拷贝构造
	list<int> lt4(lt3);
	list<int>::iterator it4 = lt4.begin();
	while (it4 != lt4.end())
	{
		cout << *it4 << " ";
		it4++;
	}
	cout << endl;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

1.2.2 list iterator的使用

此处，大家可暂时将迭代器理解为一个指针（有关于迭代器我们还会在后面章节讲解到），该指针指向list中的某个节点。

注意⚠️：

1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
2. rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动。

代码演示：

// list迭代器的使用
// 注意：遍历链表只能用迭代器和范围for
void PrintList(const list<int>& l)
{
	// 注意这里调用的是list的 begin() const，返回list的const_iterator对象
	for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it)
	{
		cout << *it << " ";
		// *it = 10; 编译不通过
	}

	cout << endl;
}

void test_list2()
{
	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	list<int> l(array, array + sizeof(array) / sizeof(array[0]));
	// 使用正向迭代器正向list中的元素
	// list::iterator it = l.begin();   // C++98中语法
	auto it = l.begin();                     // C++11之后推荐写法
	while (it != l.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	// 使用反向迭代器逆向打印list中的元素
	// list::reverse_iterator rit = l.rbegin();
	auto rit = l.rbegin();
	while (rit != l.rend())
	{
		cout << *rit << " ";
		++rit;
	}
	cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

1.2.3 list capacity

1.2.4 list element access

1.2.5 list modifiers

代码演示：

// list插入和删除
// push_back/pop_back/push_front/pop_front
void test_list3()
{
	int array[] = { 1, 2, 3 };
	list<int> L(array, array + sizeof(array) / sizeof(array[0]));

	// 在list的尾部插入4，头部插入0
	L.push_back(4);
	L.push_front(0);
	PrintList(L);

	// 删除list尾部节点和头部节点
	L.pop_back();
	L.pop_front();
	PrintList(L);
}

// insert /erase 
void test_list4()
{
	int array1[] = { 1, 2, 3 };
	list<int> L(array1, array1 + sizeof(array1) / sizeof(array1[0]));

	// 获取链表中第二个节点
	auto pos = ++L.begin();
	cout << *pos << endl;

	// 在pos前插入值为4的元素
	L.insert(pos, 4);
	PrintList(L);

	// 在pos前插入5个值为5的元素
	L.insert(pos, 5, 5);
	PrintList(L);

	// 在pos前插入[v.begin(), v.end)区间中的元素
	vector<int> v{ 7, 8, 9 };
	L.insert(pos, v.begin(), v.end());
	PrintList(L);

	// 删除pos位置上的元素
	L.erase(pos);
	PrintList(L);

	// 删除list中[begin, end)区间中的元素，即删除list中的所有元素
	L.erase(L.begin(), L.end());
	PrintList(L);
}

// resize/swap/clear
void test_list5()
{
	// 用数组来构造list
	int array1[] = { 1, 2, 3 };
	list<int> l1(array1, array1 + sizeof(array1) / sizeof(array1[0]));
	PrintList(l1);

	// 交换l1和l2中的元素
	list<int> l2;
	l1.swap(l2);
	PrintList(l1);
	PrintList(l2);

	// 将l2中的元素清空
	l2.clear();
	cout << l2.size() << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

1.2.6 operations

对于sort的成员函数大家可能有疑问了，算法库里面不是有sort吗？为什么自己还需要另外实现一个sort呢？
这里我们就需要讲解一下迭代器的分类问题了，iterator 按功能上分为const修饰的正反向迭代器与非const修饰的正反向迭代器，按性质上分为单向迭代器、双向迭代器、随机迭代器。
简单来说，单向迭代器支持++，常见的容器有单链表、哈希表。双向迭代器支持++/--，常见的容器有双向链表、红黑树(map/set)，随机迭代器支持++/--/+/-，常见的容器有vector、string、deque

观察算法库里的sort，按形参说明就需要传入随机迭代器，但是list容器的底层迭代器属于双向迭代器，所以，这里对于list的sort得自己写一个成员函数。

以下简单写一些操作接口，稍微感受一下即可。

代码演示：

void test_list6()
{
	list<int> l1;
	l1.push_back(1);
	l1.push_back(2);
	l1.push_back(3);
	l1.push_back(4);
	l1.push_back(5);

	list<int>::iterator it = l1.begin();
	while (it != l1.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;

	l1.reverse();
	it = l1.begin();

	while (it != l1.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;

	//sort(l1.begin(), l1.end()); error

	l1.sort();

	it = l1.begin();

	while (it != l1.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;

	list<int> l2;

	l2.push_back(1);
	l2.push_back(2);
	l2.push_back(3);
	l2.push_back(5);
	l2.push_back(2);
	l2.push_back(6);
	l2.push_back(7);
	l2.push_back(6);

	for (auto e: l2)
	{
		cout << e << " ";
	}
	cout << endl;

	l2.sort();
	l2.unique();//对于不连续重复元素并不能达到去重效果，需要先进行排序


	for (auto e : l2)
	{
		cout << e << " ";
	}
	cout << endl;

	l2.remove(3); //删除容器中指定的元素
	
	for (auto e : l2)
	{
		cout << e << " ";
	}
	cout << endl;
	
}
void test_list7()
{
	list<int> mylist1, mylist2;
	list<int>::iterator it;

	// set some initial values:
	for (int i = 1; i <= 4; ++i)
		mylist1.push_back(i);      // mylist1: 1 2 3 4

	for (int i = 1; i <= 3; ++i)
		mylist2.push_back(i * 10);   // mylist2: 10 20 30

	it = mylist1.begin();
	++it;                         // points to 2

	cout << "mylist1:";
	for (auto e : mylist1)
	{
		cout << e << " ";
	}
	cout << endl;

	cout << "mylist2:";
	for (auto e : mylist2)
	{
		cout << e << " ";
	}
	cout << endl;

	cout << "----------------------------------------" << endl;

	mylist1.splice(it, mylist2); // mylist1: 1 10 20 30 2 3 4
								  // mylist2 (empty)
								  // "it" still points to 2 (the 5th element)
	cout << "mylist1:";
	for (auto e : mylist1)
	{
		cout << e << " ";
	}
	cout << endl;

	cout << "mylist2:";
	for (auto e : mylist2)
	{
		cout << e << " ";
	}
	cout << endl;

	cout << "----------------------------------------" << endl;


	mylist2.splice(mylist2.begin(), mylist1, it);
													// mylist1: 1 10 20 30 3 4
													// mylist2: 2
													// "it" is now invalid.
	cout << "mylist1:";
	for (auto e : mylist1)
	{
		cout << e << " ";
	}
	cout << endl;

	cout << "mylist2:";
	for (auto e : mylist2)
	{
		cout << e << " ";
	}
	cout << endl;

	cout << "----------------------------------------" << endl;

	mylist2.splice(mylist2.end(), mylist1, mylist1.begin(), mylist1.end());
												//mylist1: 
												//mylist2:2 1 10 20 30 3 4

	cout << "mylist1:";
	for (auto e : mylist1)
	{
		cout << e << " ";
	}
	cout << endl;

	cout << "mylist2:";
	for (auto e : mylist2)
	{
		cout << e << " ";
	}
	cout << endl;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166

1.3 list的迭代器失效

前面说过，此处大家可将迭代器暂时理解成类似于指针(实际迭代器并不一定是原生态指针，在后面模拟实现list我们会了解，其实是进行封装了的iterator)，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

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

二、list的模拟实现

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

2.1 list_node 节点类

首先我们还是命令一个MyList的空间，以表示与库里面的list进行区分。
首先使用struct封装每一个list的节点，因为里面的前驱_prev与后继_next到时候在外面使用时，需要进行外部访问，所以我们将list_node封装为struct，默认的限定符为public.

namespace MyList
{
	//list节点类
	template<class T>
	struct list_node
	{
		T _data;
		list_node<T>* _next;
		list_node<T>* _prev;
	
		list_node(const T& val = T())
			:_data(val)
			, _next(nullptr)
			, _prev(nullptr)
		{}
	};
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2.2 list的框架

因为有过数据结构链表的基础，这里多的细节不给大家详细介绍，list给一个头节点指针_head即可，有的版本也会给定一个_size，用来记录链表的节点个数。
写一个empty_init函数，表示空list的初始化工作，构造函数直接调用它，为什么不直接写到构造函数中，这在后面其他地方也会用到。
对于push_back尾插一个节点元素，我们不再像C语言那样写一个创建节点的函数，而这里我们可以直接new一个Node，节点类会去调用它的构造函数，然后链接到list的最后一个节点，双链表中，头节点的前驱指针_head->_prev指向的就是最后一个节点。另外，每每插入一个节点，_size++一下。

template<class T>
class list
{
	typedef list_node<T> Node;
public:
	void empty_init()
	{
		_head = new Node;
		_head->_next = _head;
		_head->_prev = _head;
		_size = 0;
	}
	list()
	{
		empty_init();
	}
	
	void push_back(const T& val)
	{
		Node* tail = _head->_prev;
		
		Node* newnode = new Node(val);

		newnode->_prev = tail;
		tail->_next = newnode;
		newnode->_next = _head;
		_head->_prev = newnode;
		
		_size++;
	}

	size_t size()
	{
		return _size;
	}

private:
	Node* _head;
	size_t _size;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

2.3 list迭代器

我们思考一下，链表是怎么访问的呢？可以像string、vector一样使用访问操作符[]吗？，答案是，当然不能，因为string、vector在内存空间中数据是连续存储的，而list是利用内存中大量的空间内存碎片，使用指针连接而成，那么此时我们就需要用迭代器来访问了，迭代器该怎么写呢？难道可以像string、vector一样用原生指针表示吗，答案依旧不行，也正是因为list是非连续的内存存储结构，使用原生指针作为迭代器会导致一些错误的内存访问，这会导致程序崩溃或一些未定义行为，因为C语言学过，指针是涉及到算术运算的，因此，对于涉及到指针行为，我们需要进行封装迭代器！

这里大家可以简单查看一些stl库里面的list的头文件，它的封装是如何命名与书写的，文件已经上传到我的资源，点击访问-> 资源下载

库中将迭代器类命名为__list_iterator

我们将__list_iterator作为list迭代器实现的类，以下简称迭代器类，为了在类里面方便使用，我们将节点类list_node typedef 为 Node，迭代器类里面，我们只有一个_node指针成员，构造函数参数当然也为Node*类型。

我们目的是将iterator封装，通过迭代器访问list的每一个元素，那么也就是达到和string、vector一样统一的访问效果，如以下图中表示：

图中的++、*、!=等等就是指针的一些行为。前面我们说过，list属于双向迭代器，有++，也有--操作，接下来我们就需要用到operator操作符重载，在日期类，我们就实现过前置++与后置++，有无一个int参数，构成他们之间的函数重载，前置++返回自增之后的值，后置++返回自增之前的值，提前将*this存储即可，前置--与后置--操作类似，我就不多赘述了。
_node = _node->_next：指针指向下一个节点。
_node = _node->_prev：指针指向前一个节点。
_node->_data:拿到迭代器指向的元素。

template<class T>
struct __list_iterator
{
	typedef list_node<T> Node;
	typedef __list_iterator Self;
	Node* _node;
	__list_iterator(Node* node)
	{
		_node = node;
	}
	
	
	Self& operator++()
	{
		_node = _node->_next;
		return *this;
	}
	
	
	//后置++的重载,需要给定一个参数以区分前置++
	Self operator++(int)
	{
		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;
	}
	
	T& operator*()
	{
		return _node->_data;
	}
	//当前迭代器对象的_node与s迭代器对象的_node进行比较
	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}
	bool operator==(const Self& s)
	{
		return _node == s._node;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

到这，我们可以继续编写list类。
前面说过，我们在使用的时候，注意到了list还是涉及到迭代器失效的问题，特别是erase删除数据之后，迭代器指向的节点无效。在网站标准文档中还是给出了返回一个iterator值，规避方法就是在下一次使用前，必须先给其赋值。

🔗库中insert返回值说明：

🔗库中erase返回值说明：

🔗list中beign与end的指向：

template<class T>
class list
{
	typedef list_node<T> Node;
public:
	typedef __list_iterator<T> iterator;


	void empty_init()
	{
		_head = new Node;
		_head->_next = _head;
		_head->_prev = _head;
		_size = 0;
	}
	list()
	{
		empty_init();
	}

	~list()
	{
		clear();
		delete _head;
		_head = nullptr;
	}

	iterator begin()
	{
		//return iterator(_head->_next);
		return _head->_next;
	}
	iterator end()
	{
		return _head;
	}

	void push_back(const T& val)
	{
		/*Node* tail = _head->_prev;
		
		Node* newnode = new Node(val);

		newnode->_prev = tail;
		tail->_next = newnode;
		newnode->_next = _head;
		_head->_prev = newnode;*/
		insert(end(), val);

	}
	void push_front(const T& val)
	{
		insert(begin(), val);
	}
	void pop_front()
	{
		erase(begin());
	}
	void pop_back()
	{
		erase(end()--);
	}

	
	void clear()
	{
		iterator it = begin();

		while (it != end())
		{
			it = erase(it);
			it++;
		}
	}

	iterator insert(iterator pos, const T& val)
	{
		Node* cur = pos._node;
		
		Node* newnode = new Node(val);

		// cur->prev newnode cur 
		cur->_prev->_next = newnode;
		newnode->_prev = cur->_prev;
		newnode->_next = cur;
		cur->_prev = newnode;

		_size++;

		return iterator(newnode);
	}

	iterator erase(iterator pos)
	{
		Node* cur = pos._node;
		Node* prev = cur->_prev;
		Node* next = cur->_next;

		delete cur;
		_size--;
		
		return iterator(next);
	}

	size_t size()
	{
		return _size;
	}

private:
	Node* _head;
	size_t _size;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113

测试：

void test_list1()
{
	list<int>lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);

	list<int>::iterator it = lt.begin();

	while (it != lt.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;

	lt.insert(lt.begin(), 20);

	it = lt.begin();
	while (it != lt.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

打印结果：

1 2 3 4 5
20 1 2 3 4 5
1
2

在这里我们并不好实现const类型的迭代器，并不是简单的const iterator，原因为何，待会需要结合其他知识说明。

2.4 拷贝构造与赋值重载

list的拷贝构造函数写法有许多种，这里给出简单通俗的方式，先调用empty_init()函数，使用范围for循环，给对象的每一个元素进行push_back即可，注意我们没有写const类型的迭代器，因此这里暂时去掉const，至于const类型的迭代器我们待会讲解。

list的赋值重载函数，我们可以复用写好的拷贝构造，使用现代写法，让编译器代替我们打工😉

//参数使用const修饰编译不通过，因为范围for，底层是利用了const的类型器，而我们没有实现const类型的
//iterator，const对象访问非const对象就会出现权利的放大，编译出错
//list(const list& lt)
list(list<T>& lt)
{
	empty_init();
	for (auto e : lt)
	{
		push_back(e);
	}
}

lt1 = lt2
//list& operator=(const list& lt)
//{
//	//传统写法
//	if (*this != lt)
//	{
//		clear();
//		for (auto e : lt)
//		{
//			push_back(e);
//		}
//	}
//	return *this;
//}


void swap(const list<T>& lt)
{
	std::swap(_head, lt._head);
	std::swap(_size, lt._size);
}
//lt1 = lt2
list<T>& operator=(list<T> lt)
{
	//现代写法
	swap(lt);
	return *this;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

测试：

void test_list2()
{
	list<int>lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);

	list<int>::iterator it = lt.begin();

	while (it != lt.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;

	list<int>lt1(lt);

	list<int>::iterator it1 = lt1.begin();

	while (it1 != lt1.end())
	{
		cout << *it1 << " ";
		it1++;
	}
	cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

打印结果：

1 2 3 4 5
1 2 3 4 5
1
2

2.5 list中存储自定义类型

若在list节点中存储自定义类型，通过直接用*it的方式去访问自定义类型中的数据会报错，究竟为什么呢？
其实和vector一样，编译器并不知道你要以哪种方式去打印，是元素之间添加空格呢还是冒号分隔还是换行呢？并不清楚，你只能自己对于每个自定义类型中的数据进行处理操作。

错误示范：

//像vector一样，对自定义类型本身不支持流插入
//所以在test_list3中使用<<访问会出错
struct A
{
	A(int a = 0,int b = 0)
		:_a(a)
		,_b(b)
	{}

	int _a;
	int _b;
};
void test_list3()
{
	list<A> lt;
	lt.push_back(A(1, 2));
	lt.push_back(A(2, 3));
	lt.push_back(A(3, 4));

	list<A>::iterator it = lt.begin();
	while (it != lt.end())
	{
		// error C2679: 二元“<<”: 没有找到接受“T”类型的右操作数的运算符(或没有可接受的转换)
		//cout << *it << " "; //访问报错
		cout << (*it)._a << " " << (*it)._b << " ";//访问运算符 自定义类型.自定义类型成员
		it++;
	}

	cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

T* operator->()
{
	return &_node->_data;
}
1
2
3
4

让我们回顾一下指针访问内置类型和自定义类型的方式：

所以对于自定义类型，我们就可以在迭代器类中，重载一个operator->函数:

T* operator->()
{
	//->优先级高于&
	return &_node->_data;
}

1
2
3
4
5
6

通过->访问自定义类型成员：
通过迭代器it + -> + 自定义类型成员就可以访问，但是仔细想想，咦？为什么这里不是it->->_a？
其实显式调用的时候应该这么写：it.operator->()->_a，实际是因为这么写可读性不好，编译器做了特殊处理，省略掉了中间的->

void test_list3()
{
	list<A> lt;
	lt.push_back(A(1, 2));
	lt.push_back(A(2, 3));
	lt.push_back(A(3, 4));

	list<A>::iterator it = lt.begin();
	while (it != lt.end())
	{
		cout << it->_a << " " << it->_b  << " ";

	//显式地调用：cout << it.operator->()->_a << " " << it.operator->()->_b << " ";
	//本来应该是it->->_a,但是这样写可读性不好，于是编译器做了特殊处理，省略了一个->

		it++;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

所以，到这里我们更加深刻理解了为什么要封装iterator，对于指针的行为、数据的访问，使得更加灵活的访问，使得vector、list、set等容器的遍历访问具有统一性。

2.6 const类型的迭代器

到这里，迭代器类的封装，我们已经写的差不多了，不过对于刚才的疑惑const类型的迭代器我们该如何写？是直接在迭代器iterator前加个const吗？

例如这样，这样子就是const修饰iterator本身了，表示一旦初始化之后，就不能修改了。我们想要的结果是类似于iterator的const_iterator，他们两个本质是不同的对象，const_iterator表示迭代器指向的内容是常量，不可修改。也就是说我们实现的const_iterator只能读取容器中的元素，不能修改。

const list<int>::iterator it = lt.begin();
1

而我们只有再封装一个const_iterator版本的对象👇:
本质是对通过迭代器拿到的元素不能做修改，所以我们对于operator*和operator->的返回值加上const即可

template<class T>
struct __list_const_iterator
{
	typedef list_node<T> Node;
	typedef __list_const_iterator Self;
	Node* _node;
	__list_const_iterator(Node* node)
	{
		_node = node;
	}


	Self& operator++()
	{
		_node = _node->_next;
		return *this;
	}


	//后置++的重载,需要给定一个参数以区分前置++
	Self operator++(int)
	{
		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;
	}

	//*it = 1;
	const T& operator*()
	{
		return _node->_data;
	}
	
	const T* operator->()
	{
		return &_node->_data;
	}

	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}
	bool operator==(const Self& s)
	{
		return _node == s._node;
	}

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

但是，大家不觉得这里的代码冗余度很高吗？我们只是对细微处作了修改，我们有没有什么办法，简化一下呢？没错，就是改变模板参数列表。
那么怎么改呢？我们看一下库中是如何写的：

库中的模板参数列表，给出了reference引用和pointer指针两个参数，对于const_iteratorconst类型的迭代器，我们只需在模板参数Ref和Ptr添加const修饰即可。

2.7 实现全容器的打印函数(深刻体会泛型编程的意义)

我们实现了const类型的迭代器之后，可以将写一个打印list的函数，

void print_list(const list<int>& lt)
{
	list<int>::const_iterator it = lt.begin();
	while (it != lt.end())
	{
		*it;
		cout << *it << " ";
		it++;
	}
	cout << endl;
}
void test_list4()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	print_list(lt);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

以上结果能够正确打印，但是对于list这种类型的对象，以上函数也用不了，故我们需要实现一个模板函数：
list是一个未实例化的模板，直接通过访问list类模板名 + ：：会报错，因为编译器就无法判断list::iterator是内嵌类型还是静态成员变量，所以我们需要在其前面加一个typename，意思是告诉编译器这是一个类型，等到list实例化后再去类里面读取。

//实例化
template<typename T>
//template
void print_list(const list<T>& lt)
{
	//list未示例化的类模板，编译器不能去它里面去找
	//编译器就无法判断list::iterator是内嵌类型还是静态成员变量
	//前面加一个typename就是告诉编译器，这里是一个类型，等到list实例化后，
	//再去类里面读取
	typename list<T>::const_iterator it = lt.begin();
	while (it != lt.end())
	{
		*it;
		cout << *it << " ";
		it++;
	}
	cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

对此，我们还可以实现一个专门针对任意容器的打印函数。

template<typename Container>
void print_container(const Container& con)
{
	typename Container::const_iterator it = con.begin();
	while (it != con.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11

测试：

void test_list5()
{
	
	list<string> lt;
	lt2.push_back("11111");
	lt2.push_back("11111");
	lt2.push_back("11111");
	lt2.push_back("11111");
	print_list(lt2); 

	vector<string> v;
	v.push_back("22222");
	v.push_back("22222");
	v.push_back("22222");
	v.push_back("22222");
	print_container(v);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

打印结果：

11111 11111 11111 11111
22222 22222 22222 22222
1
2

三、list模拟实现源码

list深度剖析及模拟实现