【STL】list的底层原理及其实现

list的介绍

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2. list的底层是用双向链表实现的（线性），每个元素都存在相互独立的节点中，每个节点都有一个指针分别指向前一个节点和后一个节点。
3. 因为底层结构是链表，list的插入和删除操作是非常高效的，这与vector容器相反。但是由于链表的结构特点，list的各个节点之间的物理地址是不连续的，也就导致了任意访问某个节点的效率较低。
4. list的空间消耗会比vector大（存储相同个数的元素），因为每个节点还需要给前后指针开空间。

list的整体结构设计

list可以分为三部分：一个是list类本身，一个是节点类，一个是迭代器类。

list类的成员变量一般只有头节点（哨兵），除了负责初始化以外还负责声明和定义插入删除功能。
ListNode节点类封装了list的元素以及前后节点的指针，还负责new出节点时的初始化。
Iterator迭代器类封装了指向节点的指针ListNode*,还负责重载++、–、！=等运算符。为什么要在迭代器内部重载呢？

跟vector不同的是，由于list迭代器指向的是一个节点，且节点间物理地址不连续，向前移动或者向后移动都不能用指针直接去加减。

list的节点类

 // List的节点类
 template<class T>
 struct ListNode
 {
     ListNode(const T& val = T());
     ListNode<T>* _pPre;
     ListNode<T>* _pNext;
     T _val;
 };
1
2
3
4
5
6
7
8
9

list的迭代器类

template<class T, class Ref, class Ptr>
class ListIterator
{
    typedef ListNode<T>* PNode;
    typedef ListIterator<T, Ref, Ptr> Self;
public:
    ListIterator(PNode pNode = nullptr);
    ListIterator(const Self& l);
    T& operator*();
    T* operator->();
    Self& operator++();
    Self operator++(int);
    Self& operator--();
    Self& operator--(int);
    bool operator!=(const Self& l);
    bool operator==(const Self& l);
private:
    PNode _pNode;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

list类

template<class T>
class list
{
    typedef ListNode<T> Node;
    typedef Node* PNode;
public:
    typedef ListIterator<T, T&, T*> iterator;
    typedef ListIterator<T, const T&, const T&> const_iterator;
public:
    ///
    // List的构造
    list();
    list(int n, const T& value = T());
    template <class Iterator>
    list(Iterator first, Iterator last);
    list(const list<T>& l);
    list<T>& operator=(const list<T> l);
    ~list();

    ///
    // List Iterator
    iterator begin();
    iterator end();
    const_iterator begin();
    const_iterator end();
    ///
    // List Capacity
    size_t size()const;
    bool empty()const;

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

list的构造

list有四个构造函数：无参构造、拷贝构造、连续赋值构造、迭代器构造。

//构造的list中包含n个值为val的元素
list (size_type n, const value_type& val = value_type())
//构造空的list，初始化哨兵节点
list() 
//拷贝构造
list (const list& x)
//用[first, last)区间中的元素构造list
list (InputIterator first, InputIterator last) 
1
2
3
4
5
6
7
8

代码模拟实现：

		void Empty_Init() {
			head = new Node;
			head->_pre = head;
			head->_next = head;
			head->_val = -1;
			sz = 0;
		}
		//构造
		list()
		{
			Empty_Init();
		}
		list(size_t n, const T& value = T())
		{
			Empty_Init();
			for (size_t i = 0; i < n; i++) {
				push_back(value);
			}
			sz = n;
		}
		//拷贝构造
		list(const list<T>& lt) {
			Empty_Init();
			for (auto& it : lt) {
				push_back(it);
			}
		}
		//迭代器构造
		template <class IIterator>
		list(IIterator first, IIterator last) {
			Empty_Init();
			while (first != last) {
				push_back(*first);
				first++;
			}
		}
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

list节点类的实现

节点类的成员变量就是前后指针以及节点的元素值。此外还需注意构造节点时的初始化工作。

template<class T>
class ListNode {
public:
	ListNode(const T& val = T())
		:_val(val)
		, _pre(nullptr)
		, _next(nullptr)
	{

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

list 迭代器Iterator的使用以及实现

Iterator的使用

在上面iterator类的声明中我们可以看到，不同的容器其迭代器的实现方式是不一样的。在string和vector中的iterator本质是一个指针。但是list的迭代器是一个像指针的类。

//返回第一个元素或最后一个的迭代器
begin()
end()

//rbegin返回第一个元素的reverse_iterator,即end位置，rend返回最后一个元素下一个位置的
//reverse_iterator,即begin位置
rbegin()
rend()
1
2
3
4
5
6
7
8

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

Iterator的底层实现

先实现一个正向的迭代器类。因为涉及到存在const修饰迭代器指向的节点，所以在设计迭代器的时候需要同时设计出const版本（const是修饰节点，不是迭代器本身）。这里我们可以使用模板，模板里面有三个类型：节点数据类型、引用类型、指针类型。

值得注意的是，由于我们需要在迭代器类里访问节点Node类型的成员变量，所以可以将Iterator设为Node类的友元类，或者开放Node类的权限。

迭代器的构造函数的实现：

ListIterator(Node* node)
	:_node(node)
{}
1
2
3

我这里设计的比较简单，只实现了单参的构造函数，可以支持基本的隐式类型转换。

重载*:

Ref operator* () {
	return _node->_val;
}
1
2
3

重载迭代器的移动操作符++、--:

Self& operator++() {
	_node = _node->_next;
	return *this;
}
Self& operator++(int) {//后置++
	Self temp(*this);
	_node = _node->_next;
	return temp;
}

Self& operator--() {
	_node = _node->_pre;
	return *this;
}

Self& operator--(int) {//后置--
	Self temp(_node);
	_node = _node->_pre;
	return temp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

重载->：

Ptr operator ->() {
	return &_node->_val;
}
1
2
3

由于我们想把迭代器当指针使用，重载->是必要的，那么为什么是返回节点元素的地址呢？其实当我们在使用迭代器->时，编译器会自动优化成->->。比如我们的节点元素类型是一个类，我们有时需要访问节点元素类中的成员变量，此时希望通过迭代器->能直接访问到。
观察以下代码：

其中t是一个结构体类型，当我们用list存这样的节点并试图遍历节点中的a1的值时，(*it)得到的是t类型，如果我们想要输出t中的a1，就必须写成（*it）.a1。
我们希望迭代器能像指针一样，it->a1这样就能直接访问a1的元素，于是我们重载一个->,这个->的作用其实等价于it->->a1也就是it.operator->()->a1。这是编译器帮我们优化了。

反向迭代器

方向迭代器和普通的迭代器功能基本一致，只不过由于起始位置是在哨兵位，解引用时需要先往前面移动一个节点再返回其节点元素值

Ref operator* () {
	Self temp(_node);
	temp++;
	return temp._node->_val;
}
1
2
3
4
5

此外移动的方向也和普通迭代器相反，是向节点的前一个节点方向移动。

	Self& operator--() {
		_node = _node->_next;
		return *this;
	}
	Self& operator--(int) {//后置--
		Self temp(*this);
		_node = _node->_next;
		return temp;
	}

	Self& operator++() {
		_node = _node->_pre;
		return *this;
	}

	Self& operator++(int) {//后置++
		Self temp(_node);
		_node = _node->_pre;
		return temp;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

其它功能和普通迭代器几乎一致。

list与vector的比较

list和vector各种代表着的是链表和数组。它们之间的具体区别其实在前面已经讲过了。
链表的优缺点
顺序表的优缺点
迭代器的区别：

vector的迭代器是原生态指针，list的迭代器是对原生态指针(节点指针)进行封装。
vector在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效。
而list插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响

实现list类

#define _CRT_SECURE_NO_WARNINGS 1
#include<assert.h>
#include<iostream>

namespace bite {

	//节点
	template<class T>
	class ListNode {
	public:
		ListNode(const T& val = T())
			:_val(val)
			, _pre(nullptr)
			, _next(nullptr)
		{

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


	//反向迭代器
	template<class T, class Ref, class Ptr>
	class ReserveListIterator {
	public:
		typedef ListNode<T> Node;
		typedef ReserveListIterator<T, Ref, Ptr> Self;

		ReserveListIterator(Node* node)
			:_node(node)
		{}
		//重载
		Ref operator* () {
			Self temp(_node);
			temp++;
			return temp._node->_val;
		}

		Self& operator--() {
			_node = _node->_next;
			return *this;
		}
		Self& operator--(int) {//后置--
			Self temp(*this);
			_node = _node->_next;
			return temp;
		}

		Self& operator++() {
			_node = _node->_pre;
			return *this;
		}

		Self& operator++(int) {//后置++
			Self temp(_node);
			_node = _node->_pre;
			return temp;
		}

		bool operator!=(const Self& p) {
			return _node != p._node;
		}
		//T*/const T*
		Ptr operator ->() {
			return &_node->_val;
		}
		bool operator==(const Self& p) {
			return _node == p._node;
		}
		Node* _node;
	};


	//迭代器
	template<class T, class Ref, class Ptr>//T表示节点数据类型，Ref表示T&、Ptr表示T*类型
	class ListIterator {
	public:
		typedef ListNode<T> Node;
		typedef ListIterator<T, Ref, Ptr> Self;

		ListIterator(Node* node)
			:_node(node)
		{}
		//重载
		Ref operator* () {
			return _node->_val;
		}

		Self& operator++() {
			_node = _node->_next;
			return *this;
		}
		Self& operator++(int) {//后置++
			Self temp(*this);
			_node = _node->_next;
			return temp;
		}

		Self& operator--() {
			_node = _node->_pre;
			return *this;
		}

		Self& operator--(int) {//后置--
			Self temp(_node);
			_node = _node->_pre;
			return temp;
		}

		bool operator!=(const Self& p) {
			return _node != p._node;
		}
		//T*/const T*
		Ptr operator ->() {
			return &_node->_val;
		}
		bool operator==(const Self& p) {
			return _node == p._node;
		}
		Node* _node;
	};

	template<class T>
	class list {
	public:
		//节点
		typedef ListNode<T> Node;
		typedef Node* pNode;

		//迭代器
		typedef ListIterator<T, T&, T*> Iterator;
		typedef ListIterator<T, const T&, const T*> const_Iterator;
		typedef ReserveListIterator<T, T&, T*> Reserve_Iterator;
		typedef ReserveListIterator<T, const T&, const T*> const_Reserve_Iterator;
		

	public:

		void Empty_Init() {
			head = new Node;
			head->_pre = head;
			head->_next = head;
			head->_val = -1;
			sz = 0;
		}

		//构造
		list()
		{
			Empty_Init();
		}

		list(size_t n, const T& value = T())
		{
			Empty_Init();
			for (size_t i = 0; i < n; i++) {
				push_back(value);
			}
			sz = n;
		}

		//拷贝构造
		list(const list<T>& lt) {
			Empty_Init();
			for (auto& it : lt) {
				push_back(it);
			}
		}

		//迭代器构造
		template <class IIterator>
		list(IIterator first, IIterator last) {
			Empty_Init();
			while (first != last) {
				push_back(*first);
				first++;
			}
		}

		//析构
		~list() {
			Iterator it = begin();
			while (it != end()) {
				it = erase(it);
			}
			delete head;
			sz = 0;
		}

		void swap(list<T> lt) {
			std::swap(lt.head, head);
			std::swap(sz, lt.sz);
		}


		//普通迭代器
		Iterator begin() {
			return head->_next;
		}
		Iterator end() {
			return head;
		}
		//const迭代器
		const_Iterator begin() const {
			return head->_next;
		}
		const_Iterator end() const {
			return head;
		}
		//反向迭代器
		 Reserve_Iterator  rbegin() {
			 return head;
		 }
		 Reserve_Iterator  rend() {
			 return head->_next;
		 }

		 const_Reserve_Iterator rbegin() const {
			 return head;
		 }
		 const_Reserve_Iterator rend() const {
			 return head->_next;
		 }

		//插入
		void insert(Iterator pos, const T& val) {
			Node* newnode = new Node(val);
			Node* cur = pos._node;

			newnode->_pre = cur->_pre;
			newnode->_next = cur;
			cur->_pre->_next = newnode;
			cur->_pre = newnode;
			sz++;
		}
		//删除
		Iterator erase(Iterator pos) {
			assert(sz > 0);
			Node* cur = pos._node;
			Node* t = cur->_next;
			cur->_pre->_next = cur->_next;
			cur->_next->_pre = cur->_pre;
			delete cur;
			sz--;
			return t;
		}
		//尾插
		void push_back(const T& val) {
			insert(end(), val);
			//size++;
		}


		//操作符重载
		list<T>& operator = (list<T> lt) {
			swap(lt);
			return *this;
		}


		// List Capacity
		size_t size()const {
			return sz;
		}
		bool empty()const {
			return sz == 0;
		}

	private:
		pNode head;
		size_t sz;
	};
}
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