c++中的list容器讲解

1. list的介绍及使用

1.1 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的构造

1.2.2 list iterator的使用

此处，大家可暂时将迭代器理解成一个指针，该指针指向list中的某个节点。

【注意】:

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

1.2.3 list capacity

1.2.4 list element access

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

1.2.6 list的迭代器失效

前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节
点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代
器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。
list的各个接口代码，演示：

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include

using namespace std;

//list的构造
void constructor()
{
	/*list l1();*/
	list<int> l2(4, 100);
	list<int> l3(l2.begin(), l2.end());
	list<int> l4(l3);
	int array[5] = { 1,2,3,4,5 };
	list<int> l5(array, array+sizeof(array) / sizeof(array[0]));
	list<int> l6{ 9,8,7,6,5,4 };
	
	// 用迭代器方式打印l5中的元素
	list<int>::iterator it = l5.begin();
	for (; it != l5.end(); ++it)
	{
		cout << *it << " ";
	}
	cout << endl;

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


// 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 << " ";
	}
	cout << endl;
	/*std::list mylist;
	for (int i = 1; i <= 5; ++i) mylist.push_back(i);

	std::cout << "mylist backwards:";
	for (std::list::reverse_iterator rit = mylist.rbegin(); rit != mylist.rend(); ++rit)
		std::cout << ' ' << *rit;

	std::cout << '\n';*/

}

void TestList2()
{
	int array[10] = { 1,2,3,4,5,6,7,8,9,10 };
	list<int> ls(array, array + sizeof(array) / sizeof(array[0]));
	for (auto e : ls)
	{
		cout << e << " ";
	}
	cout << endl;
}

void test3()
{
	
	list<int> lt{ 9,8,7,6,5,4 };
	int sz = lt.size();
	list<int>::iterator it = lt.begin();
	for (int i = 0; i < sz; ++i)
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
}

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

	L.push_back(4);
	L.push_front(0);
	Printlist(L);
	L.pop_back();
	L.pop_front();
	Printlist(L);
}

void TestList4()
{
	int array1[] = { 1,2,3 };
	list<int> L(array1, array1 + sizeof(array1) / sizeof(array1[0]));
	auto pos = ++L.begin();
	cout << *pos << endl;

	L.insert(pos, 5, 5);
	Printlist(L);

	vector<int> v{ 7,8,9 };
	L.insert(pos, v.begin(), v.end());
	Printlist(L);

	L.erase(pos);
	Printlist(L);
	L.erase(L.begin(), L.end());
	Printlist(L);
}

void TestList5()
{
	// 用数组来构造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;
}

void Testiterator()
{
	int array[10] = { 1,2,3,4,5,6,7,8,9,10 };
	list<int> l1(array, array + sizeof(array) / sizeof(array[0]));
	auto it = l1.begin();
	while (it != l1.end())
	{
		l1.erase(it);
		++it;
	}
}

// 改正
void TestListIterator()
{
	int array[] = { 1,2,3,4,5,6,7,8 };
	list<int> l(array, array + sizeof(array) / sizeof(array[0]));
	auto it = l.begin();
	while (it != l.end())
	{
		l.erase(it++);//erase后it的所指的被删除位置的迭代器失效，通过it++来解决，
		//因为失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响
	}
}

int main()
{
	constructor();
	cout << endl;
	list<int> l1{ 1,2,3,45 };
	Printlist(l1);
	cout << endl;
	TestList2();
	cout << endl;
	test3();
	cout << endl;
	TestList3();
	cout << endl;
	TestList4();
	cout << endl;
	TestList5();
	cout << endl;
	//Testiterator();
	//cout << endl;
	TestListIterator();
	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
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

2. list的模拟实现

2.1 模拟实现list

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

#pragma once
#include
#include

using namespace std;

namespace hcm
{
	template<class T>
	struct ListNode
	{
		ListNode(const T& val = T())
			:_prev(nullptr)
			, _next(nullptr)
			, _val(val)
		{}

		ListNode<T>* _prev;
		ListNode<T>* _next;
		T _val;
	};

	template<class T,class Ref,class Ptr>
	class ListIterator
	{
		typedef ListNode<T> Node;
		typedef ListIterator<T, Ref, Ptr> Self;
	public:
		typedef Ref Ref;
		typedef Ptr Ptr;
	public:
		//
		// 构造
		ListIterator(Node* node = nullptr)
			:_node(node)
		{}
		// 具有指针类似行为
		Ref operator*()
		{
			return _node->_val;
		}
		Ptr operator->()
		{
			return &(operator*());
		}
		// 迭代器支持移动
		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;
		}
		// 迭代器支持比较
		bool operator!=(const Self& l) const
		{
			return _node != l._node;
		}
		bool operator == (const Self& l) const
		{
			return _node == l._node;
		}

		Node* _node;
	};
	template<class Iterator>
	class ReverseListIterator
	{
// 注意：此处typename的作用是明确告诉编译器，Ref是Iterator类中的一个类型，
// 而不是静态成员变量
// 否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员变量
// 因为静态成员变量也是按照 类名::静态成员变量名 的方式访问的
	public:
		typedef typename Iterator::Ref Ref;
		typedef typename Iterator::Ptr Ptr;
		typedef ReverseListIterator<Iterator> Self;
	public:
		ReverseListIterator(Iterator it)
			:_it(it)
		{}
		// 具有指针类似行为
		Ref operator*()
		{
			Iterator temp(_it);
			--temp;
			return *temp;
		}
		Ptr operator->()
		{
			return &(operator*());
		}
		// 迭代器支持移动
		Self& operator++()
		{
			--_it;
			return *this;
		}
		Self& operator++(int)
		{
			Self temp(*this);
			--_it;
			return temp;
		}
		Self& operator--()
		{
			++_it;
			return *this;
		}
		Self& operator--(int)
		{
			Self temp(*this);
			++_it;
			return temp;
		}
		// 迭代器支持比较
		bool operator!=(const Self& l)const
		{
			return _it != l._it;
		}
		bool operator ==(const Self& l) const
		{
			return _it == l._it;
		}

		Iterator _it;
	};

	template<class T>
	class list
	{
		typedef ListNode<T> Node;

	public:
		// 正向迭代器
		typedef ListIterator<T, T&, T*> iterator;
		typedef ListIterator<T, const T&, const T&> const_iterator;

		// 反向迭代器
		typedef ReverseListIterator<iterator> reverse_iterator;
		typedef ReverseListIterator<const_iterator> const_reverse_iterator;
	public:
		///
		// List的构造
		list()
		{
			CreateHead();
		}

		list(int n, const T& value = T())
		{
			CreateHead();
			for (int i = 0; i < n; ++i)
				push_back(value);
		}

		template <class Iterator>
		list(Iterator first, Iterator last)
		{
			CreateHead();
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

		list(const list<T>& l)
		{
			CreateHead();

			// 用l中的元素构造临时的temp,然后与当前对象交换
			list<T> temp(l.begin(), l.end());
			this->swap(temp);
		}

		list<T>& operator=(list<T> l)
		{
			this->swap(l);
			return *this;
		}

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

		///
		// List的迭代器
		iterator begin()
		{
			return iterator(_head->_next);
		}

		iterator end()
		{
			return iterator(_head);
		}

		const_iterator begin()const
		{
			return const_iterator(_head->_next);
		}

		const_iterator end()const
		{
			return const_iterator(_head);
		}

		reverse_iterator rbegin()
		{
			return reverse_iterator(end());
		}

		reverse_iterator rend()
		{
			return reverse_iterator(begin());
		}

		const_reverse_iterator rbegin()const
		{
			return const_reverse_iterator(end());
		}

		const_reverse_iterator rend()const
		{
			return const_reverse_iterator(begin());
		}

		///
		// List的容量相关
		size_t size()const
		{
			Node* cur = _head->_next;
			size_t count = 0;
			while (cur != _head)
			{
				count++;
				cur = cur->_next;
			}

			return count;
		}

		bool empty()const
		{
			return _head->_next == _head;
		}

		void resize(size_t newsize, const T& data = T())
		{
			size_t oldsize = size();
			if (newsize <= oldsize)
			{
				// 有效元素个数减少到newsize
				while (newsize < oldsize)
				{
					pop_back();
					oldsize--;
				}
			}
			else
			{
				while (oldsize < newsize)
				{
					push_back(data);
					oldsize++;
				}
			}
		}
		
		// List的元素访问操作
		// 注意：List不支持operator[]
		T& front()
		{
			return _head->_next->_val;
		}

		const T& front()const
		{
			return _head->_next->_val;
		}

		T& back()
		{
			return _head->_prev->_val;
		}

		const T& back()const
		{
			return _head->_prev->_val;
		}

		
		// List的插入和删除
		void push_back(const T& val)
		{
			insert(end(), val);
		}

		void pop_back()
		{
			erase(--end());
		}

		void push_front(const T& val)
		{
			insert(begin(), val);
		}

		void pop_front()
		{
			erase(begin());
		}

		// 在pos位置前插入值为val的节点
		iterator insert(iterator pos, const T& val)
		{
			Node* pNewNode = new Node(val);
			Node* pCur = pos._node;
			// 先将新节点插入
			pNewNode->_prev = pCur->_prev;
			pNewNode->_next = pCur;
			pNewNode->_prev->_next = pNewNode;
			pCur->_prev = pNewNode;
			return iterator(pNewNode);
		}

		// 删除pos位置的节点，返回该节点的下一个位置
		iterator erase(iterator pos)
		{
			// 找到待删除的节点
			Node* pDel = pos._node;
			Node* pRet = pDel->_next;

			// 将该节点从链表中拆下来并删除
			pDel->_prev->_next = pDel->_next;
			pDel->_next->_prev = pDel->_prev;
			delete pDel;

			return iterator(pRet);
		}

		void clear()
		{
			Node* cur = _head->_next;

			// 采用头删除删除
			while (cur != _head)
			{
				_head->_next = cur->_next;
				delete cur;
				cur = _head->_next;
			}

			_head->_next = _head->_prev = _head;
		}

		void swap(hcm::list<T>& l)
		{
			std::swap(_head, l._head);
		}

	private:
		void CreateHead()
		{
			_head = new Node;
			_head->_prev = _head;
			_head->_next = _head;
		}
	private:
		Node* _head;
	};

}

template<class T>
void PrintList(const hcm::list<T>& l)
{
	auto it = l.begin();
	while (it != l.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
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
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403

list.cpp

#include"list.h"

// 测试List的构造
void TestList1()
{
	hcm::list<int> l1;
	hcm::list<int> l2(10, 5);
	PrintList(l2);
	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	hcm::list<int> l3(array, array + sizeof(array) / sizeof(array[0]));
	PrintList(l3);
	hcm::list<int> l4(l3);
	PrintList(l4);

	l1 = l4;
	PrintList(l1);

}
// PushBack()/PopBack()/PushFront()/PopFront()
void TestBiteList2()
{
	hcm::list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(10);
	PrintList(lt);
	lt.pop_back();
	PrintList(lt);
	lt.push_front(0);
	PrintList(lt);
	lt.pop_front();
	PrintList(lt);

}

// 测试insert和erase
void TestBiteList3()
{
	int array[] = { 1, 2, 3, 4, 5 };
	hcm::list<int> l(array, array + sizeof(array) / sizeof(array[0]));

	auto pos = l.begin();
	l.insert(l.begin(), 0);
	PrintList(l);

	++pos;
	l.insert(pos, 2);
	PrintList(l);

	l.erase(l.begin());
	l.erase(pos);
	PrintList(l);

	// pos指向的节点已经被删除，pos迭代器失效
	cout << *pos << endl;

	auto it = l.begin();
	while (it != l.end())
	{
		it = l.erase(it);
	}
	cout << l.size() << endl;
}

// 测试反向迭代器
void TestBiteList4()
{
	int array[] = { 1, 2, 3, 4, 5 };
	hcm::list<int> l(array, array + sizeof(array) / sizeof(array[0]));

	auto rit = l.rbegin();
	while (rit != l.rend())
	{
		cout << *rit << " ";
		++rit;
	}
	cout << endl;

	const hcm::list<int> cl(l);
	auto crit = l.rbegin();
	while (crit != l.rend())
	{
		cout << *crit << " ";
		++crit;
	}
	cout << endl;
}

int main()
{
	TestList1();
	TestBiteList2();
	TestBiteList3();
	TestBiteList4();

	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
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

运行结果如下：

3. list与vector的对比

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