【C++进阶之路】list的基本使用和模拟实现_c++ list调试时

初步认识

 在正式讲解之前,我们先简单的认识一下list

①定义

template < class T, class Alloc = allocator<T> > class list;
1

同样这里有两个模板参数，第一个是实例化的类型，第二个是空间配置器。

②底层原理

库里的list是采用带头双向循环链表进行实现的。

• forward_list是单链表

• 带哨兵位的头结点，是为了给end()迭代器留位置。

③迭代器的分类

1.输入迭代器
2.输出迭代器
3.单向迭代器——forward_list,unorder_xxx
4.双向迭代器——list/map/set
5.随机访问迭代器——vector/string/deque

之间的关系：

• 从左到右是被包含的关系。

一、基本使用

1.插入结点元素

	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);
	lt.push_back(6);

	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
	
	list<int>::iterator it = lt.begin();
	for (size_t i = 0; i < 5; i++)
	{
		it++;
	}
	//在第五个位置的前面插入10
	//第五个位置——是下标为5，也就是第六个元素。
	lt.insert(it,10);


	for (auto e : lt)
	{
		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

• 说明：因为list不支持随机访问，因此没有+，+=，[] 运算符重载，但支持++，- -。

• 这里的迭代器，在插入之后，并没有失效，因为结点的插入是单个申请，单个释放的。不存在 扩容的现象。

2.删除结点元素

void test_list()
{
	list<int> lt;
	lt.push_back(2);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(90);
	lt.push_back(6);
	lt.push_back(7);


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

	//删除所有的偶数结点
	list<int>::iterator it = lt.begin();
	while (it != lt.end())
	{
		if (*it % 2 == 0)
		{
			it = lt.erase(it);
		}
		else
		{
			it++;
		}
	}

	for (auto e : lt)
	{
		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

• erase在释放之后，迭代器是肯定失效的，因为其所指向的空间都失效了。因此库里采用返回值进行更新迭代器。

3.合并两个有序链表

• 前提必须是有序的。

void test_list()
{
	list<int> lt;
	lt.push_back(2);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);
	lt.push_back(6);
	lt.push_back(7);


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

	list<int> lt1;
	lt1.push_back(1);
	lt1.push_back(3);
	lt1.push_back(5);
	lt1.push_back(7);
	lt1.push_back(9);

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

	//将lt1合并到lt上
	lt.merge(lt1);
	for (auto e : lt)
	{
		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

4.将一条链表的某一部分转移到另一条链表

接口：

void splice (iterator position, list& x);
//将x链表转移到另一条链表的pos位置之前
void splice (iterator position, list& x, iterator i);
//将x链表的某个位置的结点移到另一条链表的pos之前
void splice (iterator position, list& x, iterator first, iterator last);
//将x链表的[first,last)的区间移到另一条链表的pos位置之前。
1
2
3
4
5
6
7

注意：迭代器/迭代器区间不能重合！

list<int> lt;
	lt.push_back(2);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);
	lt.push_back(6);
	lt.push_back(7);


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

	list<int> lt1;
	lt1.push_back(1);
	lt1.push_back(3);
	lt1.push_back(5);
	lt1.push_back(7);
	lt1.push_back(9);

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

	//将lt1转移到到lt的前面
	lt.splice(lt.begin(),lt1);
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

	//将lt的后半部分转移到lt1上
	list<int>::iterator it = lt.begin();
	for (size_t i = 0; i < 5; i++)
	{
		it++;
	}
	lt1.splice(lt1.begin(), lt ,it, lt.end());

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

	//将lt1的第一个结点移到lt的最前面
	lt.splice(lt.begin(), lt1, lt1.begin());

	for (auto e : lt)
	{
		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

5.对链表排序并去重

• unique去重的前提是有序。

	list<int> lt;
	lt.push_back(2);
	lt.push_back(1);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(2);
	lt.push_back(6);
	lt.push_back(4);
	
	lt.sort();
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

	lt.unique();

	for (auto e : lt)
	{
		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

6.vector与list排序的比较

void test_list2()
{
	list<int> lt;
	vector<int> v;
	//设置随机数起点
	srand((unsigned)time(nullptr));
	size_t datas_num = 1000000;
	for (size_t i = 0; i < datas_num; i++)
	{
		int n = rand();
		lt.push_back(n);
		v.push_back(n);
	}
	int begin1 = clock();
	sort(v.begin(), v.end());
	int end1 = clock();
	cout <<"vector:" << (end1 - begin1) << endl;

	int begin2 = clock();
	lt.sort();
	int end2 = clock();
	cout <<"list:" << (end2 - begin2) << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

• 结果：list的排序有点挫，不过如果数据量比较小，可以使用list提供的排序，数据量比较大的话，那就将list的数据拷贝到vector，进行排序，再拷贝回去。
• 注意：在debug下进行测试可能会得到不一样的结果，因为vector是使用递归的快排进行实现的，如果debug下添加的调试信息会使栈帧的开销较大，从而影响时间的效率。而list的底层原理是归并，虽然也是递归，但调试信息添加的可能较少，因此会较快。而realease版本是发型版本是做了优化的，性能更好。

二、模拟实现

①要点说明

• 1.为了不与库里面的list冲突，我们需要命名空间对自己实现的类进行封装
• 2.这里我们实现的框架是按照带头双向循环链表的数据结构进行实现的。
• 3.为了理解，下面的接口是分开讲解的，最后我会给出源码。

②基本框架

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

	T _val;
	list_node* _next;
	list_node* _prev;
};

template<class T>
class list
{
	typedef list_node<T> Node;
public:
	
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

③迭代器

• 这是list的最关键的部分！

我们先来谈谈是如何实现的，迭代器必然是指向一个结点的指针，但是能完成++操作，以及解引用操作，那该怎么办呢？答案其实很简单——用类进行封装，通过运算符重载实现相应的功能。

简单的迭代器框架：

template<class T>
struct list_iterator
{
	typedef list_iterator<T> iterator;	
	Node* _node;
};
1
2
3
4
5
6

构造函数

list_iterator(Node* val = nullptr)
	:_node(val)
{}
list_iterator(const iterator& lt)
	:_node(lt._node)
{}
1
2
3
4
5
6

• 析构我们使用默认生成的即可，可千万不要写析构释放迭代器指向的空间，因为迭代器指向的空间属于list。应由list进行管理。

剩下的操作是，类里面进行重载++，-- ,*。

++

//前置
iterator& operator ++() 
{
	_node = _node->_next;
	return *this;
}
//后置
iterator operator ++(int)
{
	list_iterator tmp(_node);
	_node = _node->_next;
	return tmp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

- -

//前置
iterator& operator --()
{
	_node = _node->_prev;
	return *this;
}
//后置
iterator operator --(int)
{
	list_iterator tmp(_node);
	_node = _node->_prev;
	return tmp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

*

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

这样迭代器的基本功能就实现了，但是const的迭代器该如何实现呢？

是这样么？

typedef const list_iterator<T> const_iterator;
1

这样迭代器的成员变量不可被修改，即不可以++或者- -，不符合要求，我们想要的只是返回的值不可被修改。

一般都会再拷贝一份进行，将拷贝的迭代器改改，但是我们还可以设置第二个模板参数，这样外面可以这样定义。

template<class T，class Ref> struct list_iterator;
//里面的运算符重载——*
Ref operator *()
{
	return _node->_val;
}

//list里面可以这样定义

typedef list_iterator<T,const T&> const_iterator;
typedef list_iterator<T,T&> iterator;
1
2
3
4
5
6
7
8
9
10
11

• 这样问题就解决了。

->

还有第二个问题，如果迭代器指向的是自定义类型，比如：

struct A
{
	A(int x = 0)
		:_a1(x)
	{}
	int _a1;
};
1
2
3
4
5
6
7

如果想要访问其成员，直接解引用是不行的。

我们可以这样：

iterator it = lt.begin();
(*it)._a1;
1
2

访问其元素。

我们还可以重载-> 进行访问:

T* operator ->()
{
	return &(_node->_val);
}
iterator it = lt.begin();
it->_a1;
1
2
3
4
5
6

这样其实省略了一个箭头，这省略的一个箭头其实是为了美观，编译器在处理时，会自动加上的。

如果是const对象呢？其实处理方式一样的，再加一个模板参数。

更新后的模板，和迭代器:

template<class T,class Ref,class Ptr> struct list_iterator;
Ptr operator ->()
{
	return &(_node->_val);
}
typedef list_iterator<T,const T&,const T*> const_iterator;
typedef list_iterator<T,T&,T*> iterator;
1
2
3
4
5
6
7

那完整版的迭代器即为:

template<class T,class Ref,class Ptr>
//第一个参数：为了确定Node的类型；
//第二个是为了实现*解引用的const与非const返回值
//第三个是为实现Node成员为结构体对象的指针的访问对象。
struct list_iterator
{
	typedef list_node<T> Node;
	typedef list_iterator<T, Ref, Ptr> self;
	typedef list_iterator<T, T&, T*> iterator;


	list_iterator(Node* val = nullptr)
		:_node(val)
	{}
	list_iterator(const iterator& lt)
		:_node(lt._node)
	{}


	//重载++
	self& operator ++() 
	{
		_node = _node->_next;
		return *this;
	}
	//后置++，为了区别需要重载一下，这里的参数实际上没啥用
	self operator ++(int)
	{
		list_iterator tmp(_node);
		_node = _node->_next;
		return tmp;
	}
	self& operator --()
	{
		_node = _node->_prev;
		return *this;
	}
	self operator --(int)
	{
		list_iterator tmp(_node);
		_node = _node->_prev;
		return tmp;
	}
	bool operator != (const self& it) const
	{
		return _node != it._node;
	}
	bool operator == (const self& it) const//const和非const都能用
	{
		return _node == it._node;
	}		
	Ptr operator ->()
	{
		return &(_node->_val);
	}
	Ref operator *()
	{
		return _node->_val;
	}
	Node* _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
61

list里的迭代器

iterator begin() 
{
	return _head->_next; 
	//隐式类型转换
}
const_iterator begin()const
{
	return _head->_next;
	
}
iterator end()
{
	return _head;
}
const_iterator end()const
{
	return _head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

④insert

//在pos之前插入
void insert(iterator pos, const T& val)
{
	Node* newnode = new Node(val);
	Node* cur = pos._node;
	Node* prev = cur->_prev;

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

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


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

⑤erase

Node* erase(iterator pos)
{
	assert(pos != end());
	//这个检查是不很严格的，如果删除一个未知的结点，这个是检查不到的!
	Node* cur = pos._node;
	Node* prev = cur->_prev;
	Node* next = cur->_next;

	prev->_next = next;
	next->_prev = prev;

	delete cur;

	_size--;
	return next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

⑥push_back

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

	//newnode->_next = _head;
	//newnode->_prev = tail;

	//_head->_prev = newnode;
	//tail->_next = newnode;
	insert(end(), val);
}
1
2
3
4
5
6
7
8
9
10
11
12

⑦push_front

void push_front(const T& val)
{
	insert(begin(), val);
}
1
2
3
4

⑧pop_front

void pop_front()
{
	erase(begin());
}
1
2
3
4

⑨pop_back()

void pop_back()
{
	erase(--end());
}
1
2
3
4

⑩构造函数

//默认构造函数
list()
{
	_head = new Node;
	_head->_next = _head;
	_head->_prev = _head;
	_size = 0;
}

//拷贝构造
list(const list<T>& lt)
{
	_head = new Node;
	_head->_next = _head;
	_head->_prev = _head;
	_size = 0;

	for (auto e : lt)
	{
		push_back(e);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

⑪clear

void clear()
{
	iterator it = begin();
	while (it != end())
	{
		it = erase(it);
	}
}
1
2
3
4
5
6
7
8

⑫析构函数

~list()
{
	clear();
	delete _head;
}
1
2
3
4
5

⑬赋值重载

void swap(list &tmp)
{
	std::swap(_head, tmp._head);
	std::swap(_size, tmp._size);
}
list& operator = (list tmp)
{
	swap(tmp);
	return *this;
}
1
2
3
4
5
6
7
8
9
10

剩余的接口，过于简单，这里就不再列出了，有兴趣请看源码。

源码

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

		T _val;
		list_node* _next;
		list_node* _prev;
	};



	template<class T,class Ref,class Ptr>
	struct list_iterator
	{
		typedef list_node<T> Node;
		typedef list_iterator<T, Ref, Ptr> self;
		typedef list_iterator<T, T&, T*> iterator;
		//这个看着确实有点奇怪，写这个为了实现const_iterator转换为
		//非const_itertaor，从而达到类型转换的效果。


		list_iterator(Node* val = nullptr)
			:_node(val)
		{}
		list_iterator(const iterator& lt)
			:_node(lt._node)
		{}


		//重载++
		self& operator ++() 
		{
			_node = _node->_next;
			return *this;
		}
		//后置++，为了区别需要重载一下，这里的参数实际上没啥用
		self operator ++(int)
		{
			list_iterator tmp(_node);
			_node = _node->_next;
			return tmp;
		}
		self& operator --()
		{
			_node = _node->_prev;
			return *this;
		}
		self operator --(int)
		{
			list_iterator tmp(_node);
			_node = _node->_prev;
			return tmp;
		}
		bool operator != (const self& it) const
		{
			return _node != it._node;
		}
		bool operator == (const self& it) const//const和非const都能用
		{
			return _node == it._node;
		}		
		Ptr operator ->()
		{
			return &(_node->_val);
		}
		//加上迭代器为it则调用此函数在底层上实际被翻译为
		//(it.operator->())->结构体成员，忽略了一个->，看起来更加的美观。


		Ref operator *()
		{
			return _node->_val;
		}
		Node* _node;
	};
	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()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
			_size = 0;
		}
		list(const list<T>& lt)
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
			_size = 0;

			for (auto e : lt)
			{
				push_back(e);
			}
		}
		~list()
		{
			clear();
			delete _head;
		}
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
			//cout << _size << endl;
		}
		iterator begin() 
		{
			//return _head->_next;
			//隐式类型转换为list_itertor
			
			return _head->_next; 
		}
		const_iterator begin()const
		{
			//return _head->_next;
			//隐式类型转换为list_itertor

			return _head->_next;
		}
		iterator end()
		{
			return _head;
			//返回的是_head的拷贝，因此返回对象具有常属性
			
			//隐式类型转换为list_itertor
			//return itrator(_head->next); 
			//匿名对象
		}
		const_iterator end()const
		{
			return _head;
			//返回的是_head的拷贝，因此返回对象具有常属性

			//隐式类型转换为list_itertor
			//return itrator(_head->next); 
			//匿名对象
		}
		void push_back(const T& val)
		{
			//Node* tail = _head->_prev;
			//Node* newnode = new Node(val);

			//newnode->_next = _head;
			//newnode->_prev = tail;

			//_head->_prev = newnode;
			//tail->_next = newnode;
			insert(end(), val);
		}
		//在pos之前插入
		void insert(iterator pos, const T& val)
		{
			Node* newnode = new Node(val);
			Node* cur = pos._node;
			Node* prev = cur->_prev;

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

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


			_size++;
		}
		Node* erase(iterator pos)
		{
			assert(pos != end());
			//这个检查是不很严格的，如果删除一个未知的结点这个是会报错的!
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;

			prev->_next = next;
			next->_prev = prev;

			delete cur;

			_size--;
			return next;
		}
		void pop_back()
		{
			erase(--end());
		}
		void pop_front()
		{
			erase(begin());
		}
		void push_front(const T& val)
		{
			insert(begin(), val);
		}
		size_t size()
		{
			return _size;
		}
		bool empty()
		{
			return _size == 0;
		}
		void swap(list &tmp)
		{
			std::swap(_head, tmp._head);
			std::swap(_size, tmp._size);
		}
		list& operator = (list tmp)
		{
			swap(tmp);
			return *this;
		}

	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
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235

总结

 今天的分享就到这里了，如果觉得文章不错，点个赞鼓励一下吧！我们下篇文章再见！