C++list类(个人笔记)

---

1.熟悉list接口以及使用

list的C++官方文档

1.1list的构造

代码演示:

//list的构造
void TestList1()
{
	list<int> l1;//构造空的l1
	list<int> l2(4, 100);//l2中放4个值为100的元素
	list<int> l3(l2.begin(), l2.end());//用l2的[begin(),end())左闭右开区间构造l3
	list<int> l4(l3);//用l3拷贝构造l4

	//以数组为迭代器区间构造l5
	int array[] = { 16,2,77,29 };
	list<int> l5(array, array + sizeof(array) / sizeof(int));

	//列表格式初始化C++11
	list<int> l6{ 1,2,3,4,5 };

	//用迭代器方式打印l5中的元素
	list<int>::iterator it = l5.begin();
	while (it != l5.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	//C++11范围for的方式遍历
	for (auto& e : l5)
	{
		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

1.2list iterator的使用

注意：

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


	//使用反向迭代器逆向打印list中的元素
	//list<int>::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.3list capacity

1.4list element access

1.5list modifiers

代码演示：

//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]));

	//在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 TestList4()
{
	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 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;
}
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

1.6list的迭代器失效

迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为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
24

2.list的模拟实现

template<class T>
struct list_node
{
	list_node(const T& x = T())
		:_date(x)
		,_next(nullptr)
		,_prev(nullptr)
	{}
public:
	T _date;
	list_node<T>* _next;
	list_node<T>* _prev;
};

//T T& T*
//T const T& const T*
template<class T ,class Ref,class Ptr>
struct __list_iterator
{
	typedef list_node<T> Node;
	typedef __list_iterator<T, Ref, Ptr> self;
	Node* _node;

	__list_iterator(Node* node)
		:_node(node)
	{}

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

	self& operator--()
	{
		_node = _node->_prev;
		return *this;
	}

	self operator++(int)
	{
		self tmp(*this);
		_node = _node->_next;;
		return tmp;
	}

	self operator--(int)
	{
		self tmp(*this);
		_node = _node->_prev;
		return tmp;
	}

	Ref operator* ()
	{
		return _node->_date;
	}

	Ptr operator->()
	{
		return &(_node->_date);
	}

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

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

public:
};

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;

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

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

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

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

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

	list()
	{
		empty_init();
	}

	void swap(list<T>& lt)
	{
		std::swap(_head, lt._head);
		std::swap(_size, lt._size);
	}
	//lt2(lt1)
	list(const list<T>& lt)
	{
		empty_init();
		for (auto e : lt)
		{
			push_back(e);
		}
	}

	//lt2=lt1
	list<T>& operator=(list<T> lt)
	{
		swap(lt);
		return *this;
	}

	~list()
	{
		clear();

		delete _head;
		_head = nullptr;
		_size = 0;
	}

	void clear()
	{
		iterator it = begin();
		while (it != end())
		{
			it = erase(it);
		}
	}

	void push_back(const T& x)
	{
		insert(end(), x);
	}

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

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

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

	iterator insert(iterator pos, const T& x)
	{
		Node* cur = pos._node;
		Node* newnode = new Node(x);
		Node* prev = cur->_prev;

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

		++_size;
		return iterator(newnode);
	}

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

		delete cur;
		next->_prev = prev;
		prev->_next = next;
		--_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
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