STL-List

前言

我们将进入到C++STL 的学习。STL在各各C++的头文件中，以源代码的形式出现，不仅要会用，还要了解底层的实现。源码之前，了无秘密。
STL六大组件

Container通过Allocator取得数据储存空间，Algorithm通过Iterator存取Container内容，Functor可以协助Algorithm完成不同的策略变化，Adapter可以修饰或者套接Functor。

序列式容器sequential containers

List

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

List constructor

List modify

模拟实现List

迭代器部分，这个是重点，不再是普通的原生指针，而是对指针的封装。

template<class T, class Ref, class Ptr>
	struct __list_iterator
	{
		typedef ListNode<T> Node;
		//每新增一个模板参数，只需要加到self就行了
		typedef __list_iterator<T, Ref, Ptr> self;

		typedef Ptr pointer; //内嵌类型

		Node* _node;

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

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

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

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

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

		bool operator ==(const self& it)const
		{
			return _node != it._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
62
63

反向迭代器

namespace jt
{
	/*template*/

	//我们使用三个模板参数
	template<class Iterator, class Ref, class Ptr>
	class reverse_iterator
	{
		typedef reverse_iterator<Iterator, Ref, Ptr> self;
		reverse_iterator(Iterator it)
			:_it(it)
		{} 

		//rbegin() == end()  begin() == rend()
		self operator*()const
		{
			Iterator prev = _it;
			return *--prev; //返回前一个值
		}

		//取__list_iterator 中的 typedef Ptr pointer;
		//假如是vercor的话iterator中是没有typedef Ptr pointer;
		//因为vector的iterator没有封装，只是原生指针，就不能用了。
		//STL中用迭代器萃取来实现的。

		//加typename 举个例子 
		//vector v 能过
		//vector v 不能过
		//typename vector v 能过
		//typename Iterator::pointer operator*()const
		//{
		//	Iterator prev = _it;
		//	return *--prev; //返回前一个值
		//}

		Ref& operator++()
		{
			--_it;
			return *this;
		}

		Ptr operator->()
		{
			return &operator*();
		}

		self& operator--()
		{ 
			++_it;
			return *this;
		}

		bool operator==(const self& rit) const
		{
			return _it != rit._it;
		}

	private:
		Iterator _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
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主体

template<class T>
	struct ListNode
	{
		ListNode<T>* _next;
		ListNode<T>* _prev;
		T _data;
		ListNode(const T& data = T())
			:_next(nullptr)
			, _prev(nullptr)
			, _data(data)
		{}
	};
template <class T>
	class list
	{
		typedef ListNode<T> Node;
		
	public:
		typedef __list_iterator<T, T&, T*> iterator;
		typedef __list_iterator<T, const T&, const T*> const_iterator;

		typedef reverse_iterator<T, T&, T*> iterator;
		typedef reverse_iterator<T, const T&, const T*> const_iterator;

		reverse_iterator rbegin()
		{
			return reverse_iterator(end());
		}

		reverse_iterator rend()
		{
			return reverse_iterator(begin());
		}

		iterator begin()
		{
			return iterator(_head->_next);
		}
		iterator end() //哨兵位头结点
		{
			return iterator(_head);
		}

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

	public:
		void push_back(const T& x)
		{
			/*Node* new_node = new Node(x);
			Node* tail = _head->_prev;
			tail->_next = new_node;
			new_node->_prev = tail;
			_head->_prev = new_node;
			new_node->_next = _head;*/
			insert(end(), x);
		}

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

		void pop_back()
		{
			erase(--end()); //调用迭代器的--
		}

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

		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				//iterator del = it++; //后置++保留了第一个哨兵位头结点
				//delete del._node;
				earse(it++);

			}
			/*_head->_next = _head;
			_head->_prev = _head;*/
		}

		//不存在迭代器失效问题
		iterator insert(iterator pos, const T& x)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* new_node = new Node(x);

			prev->_next = new_node;
			new_node->_prev = prev;
			new_node->_next = cur;
			cur->_prev = new_node;
			return iterator(new_node);
		}

		//存在迭代器失效，pos指向的空间给delete了
		iterator earse(iterator pos)
		{
			assert(pos != end());
			Node* prev = pos._node->_prev;
			Node* next = pos._node->_next;
			delete pos._node;
			prev->_next = next;
			next->_prev = prev;
			return iterator(next);
		}

	public:
		list()
		{
			_head = new Node();
			_head->_next = _head;
			_head->_prev = _head; 
		}

	/*	list(const list& l)
		{
			_head = new Node();
			_head->_next = _head;
			_head->_prev = _head;
			for (auto x : l) push_back(x);
		}*/

	/*	list& operator=(const list& l)
		{
			if (this != &l) clear();

			for (auto x : l) push_back(x);
			return *this;
		}
*/
		template<class InputIterator>
		list(InputIterator first, InputIterator last)
		{
			_head = new Node();
			_head->_next = _head;
			_head->_prev = _head;
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

		list(const list<T>& l)
		{
			_head = new Node();
			_head->_next = _head;
			_head->_prev = _head;
			list<T> tmp(l.begin(), l.end());
			std::swap(_head, tmp._head);
		}

		//调用list l (100, 1)
		//会和list(InputIterator first, InputIterator last)冲突
		list(size_t n, const T& val = T())
		{
			_head = new Node();
			_head->_next = _head;
			_head->_prev = _head;
			for (size_t i = 0; i < n; i++)
				push_back(val);
		}

		//重载一个int版本
		list(int n, const T& val = T())
		{
			_head = new Node();
			_head->_next = _head;
			_head->_prev = _head;
			for (size_t i = 0; i < n; i++)
				push_back(val);

		}

		list<T>& operator=(list<T>& l)
		{
			swap(_head, l._head);
			return *this;
		}
		
		~list()
		{	 
			clear();
			delete _head;
			_head = nullptr;
		}
	private:
		Node* _head;

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