---

前言

今天我们学的是C++的STL容器中的list，是一个双向的带头的链表，在任意位置的插入和删除的时间复杂度为O(1)，今天我们首先结合C++中list文档了解关于list容器的函数接口来实现链表的增删查改等内容，到文章最后我们自己也来模拟实现list容器。

---

正文开始

一、list的介绍及使用

1.1 list的介绍

list的文档介绍

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

1.2 list的使用

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

1.2.1 list的构造

// constructing lists
#include 
#include 
int main()
{
	std::list<int> l1; // 构造空的l1
	std::list<int> l2(4, 100); // l2中放4个值为100的元素
	std::list<int> l3(l2.begin(), l2.end()); // 用l2的[begin(), end()）左闭右开的区间构造l3
		std::list<int> l4(l3); // 用l3拷贝构造l4
		// 以数组为迭代器区间构造l5
	int array[] = { 16,2,77,29 };
	std::list<int> l5(array, array + sizeof(array) / sizeof(int));
	// 用迭代器方式打印l5中的元素
	for (std::list<int>::iterator it = l5.begin(); it != l5.end(); it++)
		std::cout << *it << " ";
	std::cout << endl;

	// C++11范围for的方式遍历
	for (auto& e : l5)
		std::cout << e << " ";

	std::cout << endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

其他list的对象也可以按照这个方法打印

1.2.2 list iterator的使用

【注意】

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

1.2.3 list capacity

1.2.4 list element access

1.2.5 list modifiers

#include 
using namespace std;
void PrintList(list<int>& l) {
	for (auto& e : l)
		cout << e << " ";
	cout << endl;
}
//=====================================================================================
// push_back/pop_back/push_front/pop_front
void TestList1()
{
	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 TestList2()
{
	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 TestList3()
{
	// 用数组来构造list
	int array1[] = { 1, 2, 3 };
	list<int> l1(array1, array1 + sizeof(array1) / sizeof(array1[0]));
	PrintList(l1);
	list<int> l2;
	// 交换l1和l2中的元素
	l1.swap(l2);
	PrintList(l1);
	PrintList(l2);
	// 将l2中的元素清空
	l2.clear();
	cout << l2.size() << endl;
}
int main()
{
	TestList1();
	//TestList2();
	//TestList3();
	return 0;
}
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

list中还有一些操作，需要用到时大家可参阅list的文档说明

1.2.6 list的迭代器失效

前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节
点被删除了。因为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);
		++it;
	}
}
// 改正
void TestListIterator()
{
	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())
	{
		l.erase(it++); // it = l.erase(it);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

二、list的模拟实现

2.1 模拟实现list

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

namespace rose
{
	template<class T>
	struct _list_node
	{
		T _val;
		_list_node<T>* _prev;
		_list_node<T>* _next;
		
		_list_node(const T& val=T())
			:_val(val)
			,_prev(nullptr)
			, _next(nullptr)
		{}
	};
	//原生指针(节点指针),已经无法完成迭代器的功能
	//list::iterator  ->Node*

	//通过两个模板参数控制
	template<class T,class Ref,class Ptr>
	struct _list_iterator //_list_iterator去封装Node*，重载这个类的operator*，++等运算符，去模拟像指针一样的访问行为
	{
		//节点的指针原生行为不满足迭代器定义
		//这里迭代器通过类去封装节点的指针，重载运算符来控制
		typedef _list_node<T> node;
		typedef _list_iterator<T, Ref, Ptr> self;
		node* _pnode;

		_list_iterator(node* pnode)
			:_pnode(pnode)
		{}
		//拷贝构造，operator=，析构我们不写，编译器默认生成就可以用
		Ref operator*()
		{
			return _pnode->_val;
		}
		//这里本来应该是两个->，第一个是it->去调用重载的operator->返回T*的指针，第一个箭头去T*的指针去，访问对象中的成员
		//但是两个箭头，程序的可读性很差，所以编译器做了特殊的识别处理，为了可读性，省略了一个箭头
		Ptr operator->()
		{
			return &(_pnode->_val);
		}
		bool operator!=(const self& s)const
		{
			return _pnode != s._pnode;
		}
		bool operator==(const self& s)const
		{
			return _pnode == s._pnode;
		}
		//it++ -> it.operator(&it);
		self& operator++()
		{
			_pnode = _pnode->_next;
			return *this;
		}
		self& operator--()
		{
			_pnode = _pnode->_prev;
			return *this;
		}
		//it++ -> it.operator(&it,0);
		self operator++(int)
		{
			self tmp(*this);
			_pnode = _pnode->_next;
			return tmp;
		}
		self operator--(int)
		{
			self tmp(*this);
			_pnode = _pnode->_prev;
			return tmp;
		}
	};
	//有了这样的方式，不关心容器底层结构到底是数组，链表，树形结构等等，封装隐藏了底层的细节
	//让我们可以用简单统一的方式去访问修改容器，这个也就是迭代器真正的价值

	template<class T>
	class list
	{
		typedef _list_node<T> node;		
	public:
		typedef _list_iterator<T,T&,T*> iterator;
		typedef _list_iterator<T,const T&,const T*> const_iterator;
		//只能读不能写，如何控制_list_iterator中如何控制写呢？
		//typedef _list_const_iterator const_iterator;

		iterator begin()
		{
			return iterator(_head->_next);
		}
		const_iterator begin()const
		{
			return const_iterator(_head->_next);
		}
		iterator end()
		{
			return iterator(_head);
		}
		const_iterator end()const
		{
			return const_iterator(_head);
		}
		list()
		{
			//_head = new node(T());
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;
		}
		list(const list<T>& lt)
		{
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;
			for (const auto& e : lt)
			{
				push_back(e);
			}
		}
		//list& operator=(const list& lt)
		//{
		//	if (this != <)
		//	{
		//		clear();
		//		for (const auto& e : lt)
		//		{
		//			push_back(e);
		//		}
		//	}
		//	return *this;
		//}

		list<T>& operator=(list<T> lt)
		{	
			swap(_head, lt._head);
			return *this;
		}
		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}
		void clear()
		{	
			iterator it = begin();
			while (it != end())
			{
				//it=erase(it);
				erase(it++);
			}
		}


		void push_back(const T& x)
		{
			//node* newnode=new node(x);
			//node* tail = _head->_prev;
			//tail->_next = newnode;
			head    tail    newnode
			//newnode->_prev = tail;
			//newnode->_next = _head;
			//_head->_prev = newnode;
			insert(end(), x);
		}
		void push_front(const T& x)
		{
			insert(begin(), x);
		}
		void pop_front()
		{
			erase(begin());
		}
		void pop_back()
		{
			assert(_head->next != _head);
			/*node* tail = _head->_prev;
			node* prev = tail->_prev;
			prev->_next = _head;
			_head->_prev = prev;
			delete tail;*/
			erase(--end());
		}
		void insert(iterator pos,const T& x)
		{
			node* cur = pos._pnode;
			node* prev = cur->_prev;
			node* newnode = new node(x);
			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;
		}
		iterator erase(iterator pos)
		{
			assert(pos._pnode);
			assert(pos!=end());

			node* cur = pos._pnode;
			node* prev = cur->_prev;
			prev->_next = cur->_next;
			cur->_next->_prev = prev;
			delete cur;
			return (iterator)prev->_next;
		}
		bool empty()
		{
			return begin() == end();
		}
		size_t size()
		{
			size_t sz = 0;
			iterator it = begin();
			while (it != end())
			{
				sz++;
				it++;
			}
			return sz;
		}
	private:
		node* _head;	
	};
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
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225

2.2对模拟的rose::list进行测试

void PrintList(const list<int>& lt)
	{
		list<int>::const_iterator it = lt.begin();
		while (it != lt.end())
		{
			cout << *it << " ";
			it++;
		}
		cout << endl;
	}
	class Date {

	public:
		

		int _year = 0;
		int _month = 1;
		int _day = 1;
	};


	void test_list1()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		list<int>::iterator it = lt.begin();
		while (it != lt.end())
		{
			cout << *it << " ";
			it++;
		}
		cout << endl;
		PrintList(lt);
	}
	void test_list2()
	{
		list<Date> lt;
		lt.push_back(Date());
		lt.push_back(Date());
		lt.push_back(Date());
		lt.push_back(Date());
		list<Date>::iterator it = lt.begin();
		while (it!=lt.end())
		{
			cout << it->_year << " " << it->_month << " " << it->_day << " " << endl;;
			it++;
		}
	}
	void test_list3()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		lt.clear();
	}
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

三、list与vector的对比

vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不
同，其主要不同如下：

---

总结

例如：以上就是今天要讲的内容，本文仅仅简单介绍了list的使用和模拟实现，最后我们还将list和vector两个重要的容器进行了对比。文章主要的一部分迭代器失效需要大家多多注意一些细节就好了，今天就到这里啦！