【C++】list的模拟实现及其应用

文章目录

• list的相关介绍
• list的使用
• • • list构造
    • list iterator的使用
    • list capacity
    • list element access
    • list modifiers
    • list迭代器失效
• sort问题
• list模拟实现的完整代码
• list与vector的对比

list的相关介绍

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

list的使用

list构造

构造函数的基本使用

#include<iostream>
#include<list>
using namespace std;

int main()
{
	list<int> lt1;
	list<int> lt2(5, 100);
	list<int> lt3(lt2.begin(), lt2.end());
	list<int> lt4(lt2);
	for (auto ch : lt2)
	{
		cout << ch << " ";
	}
	cout << endl;
	for (auto ch : lt3)
	{
		cout << ch << " ";
	}
	cout << endl;
	for (auto ch : lt4)
	{
		cout << ch << " ";
	}
	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

构造函数的模拟实现
简单介绍一下下面的代码，empty_init是创造个头节点（哨兵位），因为每个构造函数都要注意头结点的问题，所以为了方便写个函数。

void empty_init()
{
	_head = new node;
	_head->_next = _head;
	_head->_prev = _head;
}

list()//默认构造
{
	empty_init();
}
//传区间构造
template <class Iterator>
list(Iterator first, Iterator last)
{
	empty_init();

	while (first != last)
	{
		push_back(*first);
		++first;
	}
}

// lt2(lt1)
/*list(const list<T>& lt)
{
	empty_init();
	for (auto e : lt)
	{
		push_back(e);
	}
}*/
//现代的构造函数写法
void swap(list<T>& tmp)
{
	std::swap(_head, tmp._head);
}
//这里传引用并不会出现问题，因为下面的区间构造是值拷贝
list(const list<T>& lt)
{
	empty_init();
	list<T> tmp(lt.begin(), lt.end());
	swap(tmp);
}
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

list iterator的使用

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

迭代器的相关使用

int main()
{
	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>::reverse_iterator rit = lt.rbegin();
	while (rit != lt.rend())
	{
		cout << *rit << " ";
		rit++;
	}
	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

list迭代器的模拟实现
这里是将迭代器做了个封装，因为list的每个节点的地址并不一定是是连续的（大概率是不连续的）所以对list++,–等操作实现不了。对它进行封装就能实现了。
【注意】

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

//typedef __list_iterator<T, T&, T*> iterator;
//typedef __list_iterator<T, const T&, const T*> const_iterator;
//模板有三个参数，看着很麻烦，但是对代码简洁方便起了很大作用。
//T是list的储存类型，Ref是控制节点的值是否能修改，Ptr控制返回的地址是否能修改
template<class T, class Ref, class Ptr>
struct __list_iterator
{
	typedef list_node<T> node;
	typedef __list_iterator<T, Ref, Ptr> iterator;
	node* _node;//成员变量
	//构造函数将节点初始化
	__list_iterator(node* n)
		:_node(n)
	{
	}
	Ref operator*()
	{
		return _node->_date;
	}
	//->最后返回的是date的地址
	Ptr operator->()
	{
		return &_node->_date;
	}
	//前置加加
	iterator& operator++()
	{
		_node = _node->_next;
		return *this;
	}
	iterator operator++(int)//后置加加标志
	{
		iterator tmp(*this);
		_node = _node->_next;
		return tmp;
	}
	//前置减减
	iterator& operator--()
	{
		_node = _node->_prev;
		return *this;
	}
	iterator operator--(int)//后置减减标志
	{
		iterator tmp(*this);
		_node = _node->_prev;
		return tmp;
	}
	bool operator!=(const iterator& s)
	{
		return _node != s._node;
	}
	bool operator==(const iterator& 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

下面是对操作符重载->，进行的应用

struct custom
{
	int a;
	int b;
	custom(int _a = 0, int _b = 0)
		:a(_a)
		, b(_b)
	{}
};
void print_list(const list<custom>& lt)
{
	list<custom>::const_iterator it = lt.begin();
	while (it != lt.end())
	{
		//也可以写成（*it）.a 
		//这里本应该是it->->a,为了增强可读性，变成了一个。

		cout << it->a << ":" << it->b << endl;
		//本体是it.operator->()->a
		//it.operator->()是等于custom*
		//it.operator++(0)是一个意思
		++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

list capacity

int main()
{
	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> lt1;
	cout << lt.size()<<endl;
	cout << lt1.size() << endl;
	cout << lt.empty() << endl;
	cout << lt1.empty() << endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

list element access

int main()
{
	std::list<int> mylist;
	mylist.push_back(77);
	mylist.push_back(22);
	// now front equals 77, and back 22
	mylist.front() -= mylist.back();
	std::cout << "mylist.front() is now " << mylist.front() << '\n';
	return 0;
}
1
2
3
4
5
6
7
8
9
10

list modifiers

int main()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(1);
	lt.push_back(1);
	lt.push_back(1);
	lt.push_front(10);
	lt.push_back(100);
	for (auto ch : lt)
	{
		cout << ch << " ";
	}
	cout << endl;
	lt.pop_back();
	lt.pop_front();
	for (auto ch : lt)
	{
		cout << ch << " ";
	}
	cout << endl;
	lt.insert(++lt.begin(),100);
	lt.erase(--lt.end());
	for (auto ch : lt)
	{
		cout << ch << " ";
	}
	cout << endl;
	list<int> lt1(3, 100);
	lt.swap(lt1);
	for (auto ch : lt)
	{
		cout << ch << " ";
	}
	cout << endl;
	lt.clear();
	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

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
24

sort问题

这里问题就是std中已经有了sort，为什么list中又写了一个sort。
理论而言，模板语法上可以传任意类型参数，但是内部使用迭代器对迭代器有要求
list的迭代器是双向迭代器，而std中的迭代器是随机迭代器，
在随机迭代器当中使用的是快排，源码中使用了减法，这是双向迭代器没有的，
所以也就导致list当中有自己的sort。

在这里举个例子，下面是双向迭代器，可以使用，双向迭代器或者随机迭代器，这里随机迭代器是一个特殊的双向迭代器，
如果它是个随即迭代器就只能使用随机迭代器。
单向迭代器，就是三种迭代器都可以使用。

但是list中的sort并不常用，原因是它的效率不高，想要追求效率高，就把list到中的数据拷贝到vector当中，排完序在拷贝回来。这样的效率会有很大的提升。

    for (auto e : lt1)
	{
		v.push_back(e);
	}
	sort(v.begin(), v.end());
	size_t i = 0;
	for (auto& e : lt1)
	{
		e = v[i++];
	}
1
2
3
4
5
6
7
8
9
10

list模拟实现的完整代码

#pragma once
#include<iostream>
using namespace std;
namespace zzm
{
	template<class T>
	struct list_node
	{
		list_node* _prev;
		list_node* _next;
		T _date;
		list_node(const T& x = T())
			:_prev(nullptr)
			, _next(nullptr)
			, _date(x)
		{
		}
	};

	template<class T, class Ref,class Ptr>
	struct __list_iterator
	{
		typedef list_node<T> node;
		typedef __list_iterator<T, Ref,Ptr> iterator;
		node* _node;
		__list_iterator(node* n)
			:_node(n)
		{
		}
		Ref operator*()
		{
			return _node->_date;
		}
		Ptr operator->()
		{
			return &_node->_date;
		}
		iterator& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		iterator operator++(int)//后置加加标志
		{
			iterator tmp(*this);
			_node = _node->_next;
			return tmp;
		}
		iterator& operator--()
		{
			_node = _node->_prev;
			return *this;
		}
		iterator operator--(int)//后置减减标志
		{
			iterator tmp(*this);
			_node = _node->_prev;
			return tmp;
		}
		bool operator!=(const iterator& s)
		{
			return _node != s._node;
		}
		bool operator==(const iterator& s)
		{
			return _node == s._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;
		//typedef const iterator const>iterator;
		//是行不通的，T*const  ×
		//应该是const T*       √
		/*list()
		{
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;
		}*/
		iterator begin()
		{
			//iterator it(_head->_next);
			//return it;
			return iterator(_head->_next);
			//匿名构造，生命周期只有这一行
		}
		iterator end()
		{
			return iterator(_head);
		}
		const_iterator begin() const
		{
			//iterator it(_head->_next);
			//return it;
			return const_iterator(_head->_next);
			//匿名构造，生命周期只有这一行
		}
		const_iterator end() const
		{
			return const_iterator(_head);
		}
		void empty_init()
		{
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;
		}

		list()
		{
			empty_init();
		}

		template <class Iterator>
		list(Iterator first, Iterator last)
		{
			empty_init();

			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

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

		list(const list<T>& lt)
		{
			empty_init();

			list<T> tmp(lt.begin(), lt.end());
			swap(tmp);
		}

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

		void push_back(const T& a)
		{
			/*node* tail = _head->_prev;
			node* new_node = new node(a);
			_head->_prev = new_node;
			tail->_next = new_node;
			new_node->_next = _head;
			new_node->_prev = tail;*/
			insert(end(),a);
		}
		void push_front(const T& a)
		{
			insert(begin(), a);
		}
		void insert(iterator pos,const T&x)
		{
			node* cur = pos._node;
			node* drev = cur->_prev;
			node* new_node = new node(x);
			new_node->_next = cur;
			new_node->_prev = drev;
			drev->_next = new_node;
			cur->_prev = new_node;
		}
		void erase(iterator pos)
		{
			node* next = pos._node->_next;
			node* prev = pos._node->_prev;
			next->_prev = prev;
			prev->_next = next;
			delete pos._node;
		}
		void pop_back()
		{
			erase(--end());
		}

		void pop_front()
		{
			erase(begin());
		}
		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}

		//头节点是不清的
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				//it = erase(it);
				erase(it++);
				//删除的是临时拷贝
			}
		}
	private:
		node* _head;
	};
	void print_list(const list<int>& lt)
	{
		list<int>::const_iterator it = lt.begin();
		while (it != lt.end())
		{
			//(*it) *= 2;

			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

list与vector的对比