STL——list使用和模拟

list介绍

在STL中list底层使用的是双向带头循环链表，这是一个很完善的结构，可以做到在O（1）时间内完成任意位置的插入和删除。
唯一的缺点就是不支持随机访问，如果要访问list中的第三个元素，只能通过遍历比如迭代器或者范围for来遍历到第三个元素。
所以list不支持算法库里面的sort（因为算法库中的sort底层是快速排序，快速排序为了防止最坏的情况也就是已排序好的数据，在这种情况下的效率就是O（N^2)因此引入了三数取中，但是如果不支持随机访问，三数取中就不可以使用了）
要想对sort进行排序只能使用list自带的sort来进行排序，但是list也很少排序，如果是需要排序的数据一般是用顺序表来存储。

这是list的双向带头循环链表的一个逻辑结构图

物理结构就没有这些箭头，除了数据位另外两个位置保存的都是其他位置的指针。

常见的迭代器类型
单向----》只能++，例如：forword_list和unorder_map
双向----》可++和–，例如：list
随机访问----》可以++/–/+/-/+=/-=等任意方式访问，有vector和string
在文档中根据迭代器名称可以判断出，当前函数支持什么类型的迭代器，这几个迭代器从上到下满足继承关系，上面的一定是下面的，也就是说，上面的迭代器可以调用的函数下面的迭代器一定也可以，但是下面可以调用的函数上面的不一定能调用。

list的使用

构造函数（constructor）

C++这里提供了四种构造函数
1.不传参数构造空链表（也就是只有一个头结点）alloc是空间配置器，也就是内存池
2.使用n个val来构造链表
3.使用了一个迭代器区间来构造（左闭右开），使用的是模板参数，也就是可以是其他容器的迭代器来构造链表
4.拷贝构造

#include
#include
#include

using namespace std;

template<class T>
void Print(T& tmp)
{
	typename T::iterator it = tmp.begin();
	while (it != tmp.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
}
int main()
{
	list<int> l1;
	list<int> l2(10, 6);
	string s("hello kisskernel");
	list<char> l3(s.begin(), s.end());
	
	Print(l1);
	Print(l2);
	Print(l3);
	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

这段代码就是list构造函数的使用，这里还实现了一个可以打印任意类型容器的模板打印函数，这里要注意，第10行，访问模板内的内嵌类型的使用，前面如果不加typename就会报错，因为模板在没有实例化之前是不能取模板的内嵌类型的，这时候编译器根本就不认识T，也不知道T是什么类型这时候取内嵌的iterator就会报错。所以前面加上了typename就是告诉编译器这个参数是个模板类型，等实例化之后再去里面取内嵌类型。

迭代器

list的迭代器和其他容器一样的不多赘述。
要注意虽然迭代器的使用类似指针的操作，在前面的vector和string中迭代器也确实就是指针，但是在这里的list迭代器如果单单是指针的话，不能满足list这里的迭代器要求，比如it++如果时原生指针就时地址++，并不能跳到下一个节点这是错误的。
所以list的迭代器时封装了节点的指针，然后通过重载运算符来完成迭代器的操作，包括后面的map和set也是类似的。
迭代器的使用都是通用的，所有容器都是一样的。

算法中的函数模板理论上都是通用的，传什么迭代器都是可以的，但是因为算法中可能用到了不同的迭代器操作，有一些迭代器可能不支持这些操作，比如sort需随机访问，listiu是不支持的。

注意：因为迭代器的操作都是左闭右开的，所以begin的位置就是第一个节点的位置，end的位置是最后一个节点的下一个位置，也就是头结点（哨兵位）的位置。
结构如下：

这里的begin是正向迭代器的开始，++向着逆时针移动。
rbegin是反向迭代器的开始，++向着顺时针方向移动
反向迭代器：关于反向迭代器，这里为了让end和rbegin保持一致，所以他们都是指向头结点的，但是rbegin解引用拿到的是最后一个节点4，这是因为反向迭代器的实现重载*的时候是返回的前一个位置的值。所以rend解引用拿到的就是头结点（这里会报错哦，这也证明了拿到的确实就是头节点）。

list capacity

1.判断链表是否为空（用迭代器begin和end判断是不是相等的就可以了，相等就是空）
2.返回链表的元素个数（可以遍历链表来计数，也可在成员中加一个_size来记录，插入就++，删除就–）

list modify（修改）

修改函数只需要了解框选出来的即可。
1.头插
2.头删
3.尾插
4.尾删
5.随机插入（在pos位置之前插入）

返回值是新插入的元素的第一个位置（如果只插入一个元素，就返回这个插入的元素的位置）。
6.删除

返回的迭代器是最后一个被删除的位置的下一个位置的迭代器。如果已将容器最后一个元素删除那么返回的就是end()；
7.交换
8.清空链表

其他接口函数

assign就是将对象赋值成一块区间的值，第一个就是将容器内的数据清空然后将这个迭代器区间内的数据插入进去，第二个就是清空然后插入n个val

splice的意思就是拼接结合的意思。将一个容器的元素结合到另一个容器中。
1.将x容器内的元素全部接合到调用容器的position位置的前面开始。
2.将迭代器i位置的x容器内的元素接合到pos位置之前。
3.将x容器的迭代器区间左闭右开的[ first，last）的这个区间接合到pos位置之前。

list迭代器失效问题

因为list底层是双向带头循环链表，所以使用迭代器插入一个节点并不会导致迭代器失效，因为插入的节点不会导致其他节点的物理地址的变换。使用erase删除一个节点同样也不会导致其他迭代器失效，只会导致删除的这个节点失效。

list模拟实现

首先我们需要了解list的这个容器总共有几部分组成，首先是list的主题，其实就是一个指针，指向了双向带头循环链表的头节点。然后就是需要节点，可以将节点封装成一个类，然后最重要的就是迭代器了。vector和string的迭代器都可以使用原生指针来实现，因为他们的存储空间是连续的，++ 或者-- 后就能找到附近的元素，但是list的存储空间是不连续的。

所以list的原生指针行为不能满足list对于迭代器的定义，我们就需要通过类来封装原生指针，重载操作符来实现迭代器功能。这里一共需要三个类，list，_list_node , _list_iterator。
正因为使用类封装迭代器重载了运算符，所以我们在使用的时候可以不需要关注容器底层到底是数组，链表或者是树形结构，我们都可以使用简单统一的方法来访问修改容器，这其实就是迭代器的意义。

基础框架(节点类）

	//封装节点类
	template<class T>
	struct _list_node
	{
		typedef _list_node<T> node;
		
		_list_node(const T& val = T())
			:_val(val)
			,_next(nullptr)
			,_prev(nullptr)
		{}

		T _val;
		_list_node* _next;
		_list_node* _prev;
	};

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

基础框架（迭代器类）

//封装迭代器类
	template<class T,class Ref, class Ptr>
	struct _list_iterator
	{
		typedef _list_node<T> node;
		typedef _list_iterator<T,Ref,Ptr> self;

		_list_iterator(node* pnode)
			:_pnode(pnode)
		{}

		Ref operator*()
		{
			return _pnode->_val;
		}

		Ptr operator->()
		{
			return &_pnode->_val;
		}
		//前置++
		self& operator++()
		{
			_pnode = _pnode->_next;
			return *this;
		}
		//后置++
		//临时对象不能返回引用
		self operator++(int)
		{
			self tmp(*this);
			_pnode = _pnode->_next;
			return tmp;
		}

		//前置--
		self& operator--()
		{
			_pnode = _pnode->_prev;
			return *this;
		}

		//后置--
		self operator--(int)
		{
			self tmp(*this);
			_pnode = _pnode->_prev;
			return tmp;
		}

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

		self& operator+(int x)
		{
			while (x--)
				_pnode = _pnode->_next;
			return *this;
		}

		self& operator-(int x)
		{
			while (x--)
				_pnode = _pnode->_prev;
			return *this;
		}

		node* _pnode;
	};
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

基础框架（链表主体类）

	//list主体类
	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;
        //.................
    private:
		node* _head;
	};
1
2
3
4
5
6
7
8
9
10
11
12
13

这里的迭代器类可以看到使用了三个模板参数，其实主要是为了适配const对象而加上了两个对象。因为如果是const对象，调用operator*（）的时候返回的必须是const T&，使得这个对象只能读不能写。如果像前面那样直接写成函数重载，这里就会有问题了，因为迭代器并不是const类型的所以只有返回值类型不相同的两个函数是不能构成函数重载的。

这里我们还有方法；那就是再写一个const_iterator类，但是这个类除了除了operator*（）和operator->这两个函数的返回值不同以外，其他的函数都是相同的，所以代码会有很多的冗余。

这时就可以使用模板来搞定，将这两个函数的返回值都写成模板参数，const和非const只需要在模板实例化的时候控制就可以了，实际上还是生成了两个类，但是这是编译器替我们写的，并不需要我们自己动手。

链表主体函数

		//迭代器
		typedef _list_iterator<T, T&, T*> iterator;
		typedef _list_iterator<T, const T&, const T*> const_iterator;

		iterator begin()
		{
			return iterator(_head->_next);
		}

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

		iterator end()
		{
			return iterator(_head);
		}

		const_iterator end() const
		{
			return const_iterator(_head);
		}
		//
		//构造函数
		list()
		{
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;
		}

		list(size_t n, const T& val = T())
		{
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;
			while (n--)
			{
				push_back(val);
			}
		}

		list(int n, const T& val = T())
		{
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;
			while (n--)
			{
				push_back(val);
			}
		}

		template<class iterator>
		list(iterator first, iterator last)
		{
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}
		//拷贝构造
		list(const list<T>& x)
		{
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;

			list tmp(x.begin(), x.end());
			swap(tmp);
		}
		//析构
		~list()
		{
			node* cur = _head->_next;
			while (cur != _head)
			{
				node* next = cur->_next;
				delete cur;
				cur = next;
			}

			delete _head;
			_head = nullptr;
		}
		
		//自定义类型交换
		void swap(list<T>& x)
		{
			::swap(_head, x._head);
		}

		void push_back(const T& x)
		{
			node* newnode = new node(x);
			node* tail = _head->_prev;

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

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

		iterator insert(iterator pos, const T& x)
		{
			node* newnode = new node(x);
			node* cur = pos._pnode;
			node* prev = (pos._pnode)->_prev;

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

			return pos;
		}

		iterator erase(iterator pos)
		{
			node* cur = pos._pnode;
			node* next = cur->_next;
			node* prev = cur->_prev;

			prev->_next = next;
			next->_prev = prev;
			
			delete cur;
			return next;
		}

		iterator pop_front()
		{
			return erase(_head->_next);
		}
		iterator pop_back()
		{
			return erase(_head->_prev);
		}

		void clear()
		{
			node* cur = _head->_next;
			while (cur != _head)
			{
				node* next = cur->_next;
				delete cur;
				cur = next;
			}
			_head->_next = _head;
			_head->_prev = _head;
		}
		//
		size_t size() const
		{
			size_t count = 0;
			node* cur = _head->_next;
			while (cur != _head)
			{
				count++;
				cur = cur->_next;
			}
			return count;
		}
		
		bool empty() const
		{
			return _head->_next == _head;
		}
		//
		T& front()
		{
			return _head->_next->_val;
		}

		T& back()
		{
			return _head->_prev->_val;
		}
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

下面着重说一下迭代器重载的operator->的作用。

比如这里有一个类date

class date
{
public:
	date(int year = 0, int month = 1, int day = 1)
		:_year(year)
		,_month(month)
		,_day(day)
	{}

	int _year;
	int _month;
	int _day;
};
1
2
3
4
5
6
7
8
9
10
11
12
13

如果我们的list里面存放的是date类对象，我们要输出的时候就会遇到问题，想要只输出year，只能先解引用然后再使用点来访问date里面的数据。

void test5()
{
	xzj::list<date> ld;
	ld.push_back({ 1900,2,28 });
	ld.push_back({ 1901,3,29 });
	ld.push_back({ 1902,4,20 });
	ld.push_back({ 1903,5,20 });

	xzj::list<date>::iterator it = ld.begin();
	while (it != ld.end())
	{
		cout << (*it)._year << endl;
		++it;
	}
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

但是这样访问呢多少有点别扭，以前使用指针访问结构体里面的数据都是使用->那么在这里我们也可以使用->只需要重载->操作符即可

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

有了上面的重载我们就可以直接使用->来访问date对象内的数据了

void test5()
{
	xzj::list<date> ld;
	ld.push_back({ 1900,2,28 });
	ld.push_back({ 1901,3,29 });
	ld.push_back({ 1902,4,20 });
	ld.push_back({ 1903,5,20 });

	xzj::list<date>::iterator it = ld.begin();
	while (it != ld.end())
	{
		cout << it->_year << endl;
		++it;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

但是这里it->实际调用方式是：it . operator->()，这个函数返回了date*这个类型的地址，但是仅有一个地址是不可以的，我们是不是还需要一个->才能访问数据呢？所以一共需要两个->
理论上来讲是这样的，但是这里编译器做了优化，所以这里只需要一个箭头就可以访问了。