STL-list

请添加图片描述

🚀0.前言

言C++之言，聊C++之识，以C++会友，共向远方。各位博友的各位你们好啊，这里是持续分享C++知识的小赵同学，今天要分享的C++知识是list ，在这一章，小赵将会继续向大家聊聊C++的list知识 。✊

1.List节点的设计

我们前面说list的底层是一个双向链表结构，那么这样的一个结构，我们前面是设计过的，我们只需要加上我们的模版就好了。

1
2
3
4
5
6
7
8
9
10
11
template<class T>
struct list_node {
	list_node(const T& x = T())
		:_data(x)
		, _next(nullptr)
		, _prev(nullptr)
	{}
	list_node<T>* _prev;
	list_node<T>* _next;
	T _data;
};

2.List的迭代器

List的迭代器不是像我们之前的vector是一块连续的空间的，不能直接天然支持++，–这样的操作，还有成员的访问等操作都要我们自己去实现。

2.1迭代器的功能的实现

2.1.1迭代器

list这个类的迭代器的底层设计是类似这样的。

img

这里的实现一定要小心我们之前的迭代器是这样的。

image-20250312001413699

那么其实这个时候我们只要将它收尾相接就是我们现在的这个了。

由于我们是个环，方面我们的访问我们可以把头设置为空,让end指向它

image-20250312002655017然后根据这个逻辑我们就可以设计出来了

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
template<class T >
class list_iterator
{
private:
	typedef list_node<T>  Node;
	typedef list_iterator<T> Self;
public:
    Node* _node;
	list_iterator(Node* node) {
		_node = node;
	}
	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;
	}
	T& operator*()//访问
	{
		return _node->_data;
	}
	T* operator->()
	{
		return& (_node->_data);
	}
	bool operator!=(Self & self)
	{
		return _node != self._node;
	}
	bool operator==(Self & self){
		 return _node == self._node; 
	}
	};

然后这里我在实现的这个地方最不理解的就是为什么->返回的是指针，不是我们data,然后我问了一下deepseek

1.编译器需通过递归调用operator->直到获得原生指针，才能访问成员，返回指针是唯一终止条件。

2.若返回对象而非指针，会导致无限递归或编译错误，因对象无法直接触发成员访问。

==至于编译器底层会这样设计，我找来找去也没找到特别好的话语去总结，最后我想了一下，主要还是为了去兼容C吧，C的->是针对指针去解决的，那意味着->遇到指针才能有真正的作用，所以编译器即使运行你重载也要保持两者的同一种意义，那么我们返回这个指针后，编译器还会再一次->去获得参数。这也就是我们后面说的为什么我们明明只是用了->却是调用两次的原因==

2.1.2const 迭代器

const 迭代器与普通迭代器的差别很少，只有两个地方的差距。

1
2
3
4
5
6
7
8
const T& operator*()//访问
{
	return _node->_data;
}
const T* operator->()`
{
	return &(_node->_data);`
}

迭代器的优化

很显然如果我们只为了两个函数的差别就写了两个类，iterator和const_iterator类，那么太浪费了，也太繁琐了，与我们简洁的stl显得格格不入，那么这个时候，我就不得不佩服前人的智慧了想到了这样妙的方法去解决了这个问题，现在看来我也是叹为观止。

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
template<class T>
class list
{
	
	template<class T, class Ref, class Ptr>
	class list_iterator
	{
	private:
		typedef list_node<T>  Node;
		typedef list_iterator<T> Self;
    public:
		Node* _node;
		list_iterator(Node* node) {
			_node = node;
		}
		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;
		}
		Ref operator*()
		{
			return _node->_data;
		}
	    Ptr operator->()
		{
			return &(_node->_data);
		}
		bool operator!=(Self& self)
		{
			return _node!=self._node;
		}
		bool operator==(Self& self)
		{
			return _node ==self._node;
		}
		
	};
	typedef list_iterator<T, T&, T*> iterator;
	typedef list_iterator<T, const T&, const T*> const_iterator;
public:
};

可以说这样的想法现在看来也是很妙了。

3.List类内的函数的实现

3.1list的构造函数。

list这个类的链表设计是类似这样的。

img

也就是类似一个环状链表。那么我们设计的时候就要首先确定我们的的链表的头的设计，是带头还是不带头呢？小赵这里的实现是带一个头节点，也就是一个空节点，方面我们类的实现。

1
2
3
4
5
6
7
8
9
10
private:
	typedef typedef list_node<T>  Node;
	Node* _head;
public:
	list()
	{
		_head = new Node;
		_head->_next = _head;
		_head->_prev = _head;
	}

那么这样实现的方案，用图表示就是下面这样。

image-20250311235447061

那么这个时候其实我们这个既是我们的头结点也是我们的尾节点，刚好就是我们的一个最开始的环。

image-20250311235840949

当然细心的小伙伴已经发现了我们的list类不止这一个构造函数，还有另外几个，那么这几个我们可以学一下前面的函数套用的方法等实现push_back之后再实现会更好实现。

3.2list的一些简单的函数实现

3.2.1 empty实现

1
2
3
4
bool empty()
{
	return _head->_prev == _head
}

3.2.2size实现size()

这里我们可以再加一个size的参数，方便我们的实现和使用。

1
2
3
4
size_t size()
{
	return _size;
}

3.2.3迭代器的访问

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const_iterator begin()const
{
	return _head->_next;
}
const_iterator end()const
{
	return _head;
}
iterator begin()
{
	return _head->_next;
}
iterator end()
{
	return _head;
}

3.2.4front和back

1
2
3
4
5
6
7
8
T front()
{
	return _head->_next->_data;
}
T back()
{
	return _head->_prev->_data;
}

4.增删

4.1.增

4.1.1push_back

push_back就相当于在尾部差一个加点，也就是下图

image-20250312002822603

1
2
3
4
5
6
7
8
9
10
iterator push_back(const T& val)
{
	Node* newnode = new Node(val);
	Node *tail = _head->_prev;
	newnode->_next = _head;
	newnode->_prev = tail;
	_head->_prev = newnode;
	tail->_next = newnode;
    return newnode;
}

有了push_back我们就可以火速实现一下之前没实现的几个构造函数

构造函数

1
2
3
4
5
6
7
8
list(size_t n, const T& val = T())
{
	_head = new Node;
	_head->_next = _head;
	_head->_prev = _head;
	_size = 0;
	for (int i = 0; i < n; i++)push_back(val);
}

这里我们发现一个问题就是我们前几步和我们之前的构造函数的前几步是一样的，那么我们可以把这部分函数拿出来单独实现一下。

同时实现一下我们的迭代器构造

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
list(size_t n, const T& val = T())
{
	empty_init();
	for (int i = 0; i < n; i++)push_back(val);
}
template<class InputIterator>
list(InputIterator first, InputIterator last)
{
	empty_init();
	while (first !=last)
	{
		push_back(*first);
		first++;
	}
}

拷贝构造函数

1
2
3
4
5
6
7
8
list(const list<T>& x)
{
	empty_init();
	for (const auto& ch : x)
	{
		push_back(ch);
	}
}

4.1.2insert

这里的insert建议和前面的push_back的插入图一起食用效果更好

1
2
3
4
5
6
7
8
9
10
11
12
iterator insert(iterator position, const T& val)
{
	Node* newnode = new Node(val);
	Node* pos = position._node;
	Node* pre = pos->_prev;
	Node* nex = pos->_next;
	pre->_next = newnode;
	newnode->_prev = pre;
	nex->_prev = newnode;
	newnode->_next = new;
    return newnode;
}

同时我们的push_back也可以用这个函数去实现，然后再实现一下push_front;

1
2
3
4
5
6
iterator push_back(const T& val) {
	return insert(begin(),val);
}
iterator pop_front(const T& val) {
	return erase(end(), val);
}

4.2删除

4.2.1pop_back

尾删的结构大致是这样的：

image-20250312010105443

1
2
3
4
5
6
7
8
void pop_back()
{
	Node* pos = _head->_prev;
	Node* tail = pos->_prev;
	tail->_next = _head;
	_head->_prev = tail;
	delete pos;
}

4.2.2erase

在任意位置删除也是和尾删差不多

1
2
3
4
5
6
7
8
9
10
iterator erase(iterator position)
{
	Node* pos = position._node;
	Node* pre = pos->_prev;
	Node* nex = pos->_next;
	pre->_next = nex;
	nex->_prev = pre;
	delete pos;
    return nex;
}

有了删除函数我们也可以快速的实现析构函数了,顺便实现一下我们的clear函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
clear()
{
    iterator it = begin();
	while (it != end())
	{
		it = erase(it);
	}
}
~list()
{
	clear();	
    delete _head;
	_head=nullptr
}

这里也是一样套用erase实现我们的pop_back和pop_front

1
2
3
4
5
6
iterator pop_back(){
	return erase(--end());
}
iterator pop_front(){
	return erase(begin());
}

5.赋值函数

最后还有一个赋值函数收个尾，也是很简单用我们上节课的办法。

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

6.完整代码

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
namespace zcg {
	template<class T>
	struct list_node {
		list_node<T>* _prev;
		list_node<T>* _next;
		T _data;
	};
	template<class T>
	class list
	{
	private:
		typedef typedef list_node<T>  Node;
		Node* _head;
		template<class T, class Ref, class Ptr>
		class list_iterator
		{
			typedef list_node<T>  Node;
			typedef list_iterator<T> Self;
		public:
			Node* _node;
			list_iterator(Node* node) {
				_node = node;
			}
			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;
			}
			Ref operator*()
			{
				return _node->_data;
			}
		    Ptr operator->()
			{
				return &(_node->_data);
			}
			bool operator!=(Self& self)
			{
				return _node!=self._node;
			}
			bool operator==(Self& self)
			{
				return _node ==self._node;
			}
	};
		typedef list_iterator<T, T&, T*> iterator;
		typedef list_iterator<T, const T&, const T*> const_iterator;
	private:
		typedef typedef list_node<T>  Node;
		Node* _head;
		size_t _size;
	public:
		void empty_init()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
			_size = 0;
		}
		list()
		{
			empty_init();
		}
		list(size_t n, const T& val = T())
		{
			empty_init();
			for (int i = 0; i < n; i++)push_back(val);
		}
		template<class InputIterator>
		list(InputIterator first, InputIterator last)
		{
			empty_init();
			while (first !=last)
			{
				push_back(*first);
				first++;
			}
		}
		list(const list<T>& x)
		{
			empty_init();
			for (const auto& ch : x)
			{
				push_back(ch);
			}
		}
		void Swap(list<T> x)
		{
			std::swap(_head, x._head);
			std::swap(_size,x._size);
		}
		list<T>& operator=(const list<T>& x)
		{
			Swap(x);
			return *this;
		}
		bool empty()
		{
			return _head->_prev == _head
		}
		size_t size()
		{
			return _size;
		}
		T front()
		{
			return _head->_next->_data;
		}
		T back()
		{
			return _head->_prev->_data;
		}
		const_iterator begin()const
		{
			return _head->_next;
		}
		const_iterator end()const
		{
			return _head;
		}
		iterator begin()
		{
			return _head->_next;
		}
		iterator end()
		{
			return _head;
		}
		//void push_back(const T& val)
		//{
		//	Node* newnode = new Node(val);
		//	Node *tail = _head->_prev;
		//	newnode->_next = _head;
		//	newnode->_prev = tail;
		//	_head->_prev = newnode;
		//	tail->_next = newnode;
		//}
		iterator insert(iterator position, const T& val)
		{
			Node* newnode = new Node(val);
			Node* pos = position._node;
			Node* pre = pos->_prev;
			Node* nex = pos->_next;
			pre->_next = newnode;
			newnode->_prev = pre;
			nex->_prev = newnode;
			newnode->_next = new;
			return newnode;
		}
		iterator push_back(const T& val) {
			return insert(begin(),val);
		}
		iterator pop_front(const T& val) {
			return erase(end(), val);
		}
		/*iterator pop_back()
		{
			Node* pos = _head->_prev;
			Node* tail = pos->_prev;
			tail->_next = _head;
			_head->_prev = tail;
			delete pos;
			return nex;
		}*/
		
		iterator erase(iterator position)
		{
			Node* pos = position._node;
			Node* pre = pos->_prev;
			Node* nex = pos->_next;
			pre->_next = nex;
			nex->_prev = pre;
			delete pos;
			return nex;
		}
		void pop_back(){
			erase(--end());
		}
		void pop_front(){
			erase(begin());
		}
		clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}
		~list()
		{
			clear();
			delete _head;
			_head=nullptr
		}
	};

}
#C++STL:深度剖析List，手撕List代码
STL-list
https://zcg555.github.io/2025/03/13/STL-list/
Author
John Doe
Posted on
March 13, 2025
Licensed under