【容器适配器的认识与模拟】

前言

---

一、引入

朋友们大家好，今天我们来探究一下stl中的适配器，作为stl六大组件之一，适配器的重要性显而易见。
适配，就是可以和其他工具一起配合着使用，并且只要满足适配条件就都可以使用。
我们生活中又有哪些物品可以称为适配器？
例如：排插、手机充电器等

以三孔插座为例：只要你的插头是三叉的，不管你是电脑还是电冰箱或者是电视机，都可以使用同一个插孔进行充电，但是如果你不是三孔插头就另说。

生活中的适配器比比皆是，stl中的适配器也是这么个意思，表示我们可以为适配器传入不同的容器模板，那么，
stl中都有哪些是适配器？
– stack、queue、priority_queue
下面我们一一介绍。

二、容器适配器

（一）stack

上方为stack的定义，模板参数一表示存储数据的类型，模板参数二表示所传容器的类型。

deque

deque：双端队列，底层为数组与链表的结合体，deque的数据存储并非连续的一段空间。
由于deque的底层实现比较复杂， – 如下图，我们一般不单独使用，只作为stack与queue的默认模板参数使用，所以我们只需要看第二张逻辑图就足够。

物理图：

逻辑图：

我们不需要去深究deque的底层实现，可以简单理解为一个指针数组，每个指针指向堆区的一个小数组。

---

stack模拟实现

栈和队列的操作由于受到限制，只能在一段插入和删除数据，不能进行下标访问，不能遍历、查找等，因此实现起来十分简单。

using namespace std;
#include<vector>
#include<list>
#include<iostream>
#include<algorithm>
#include<deque>

namespace kz
{
	template<class T, class container = vector<T>> // 我们这里换一换，使用vector作为默认容器
	class stack 
	{
		typedef stack<T, container> self;

	public:
		stack() = default;

		stack(const self& s)
		{
			container tmp = s._arr; // 利用vector自己的拷贝构造
			_arr = tmp;
		}

		self& operator=(const self s) // 利用深拷贝
		{
			swap(s._arr);
		}

		void push(const T& val) { _arr.push_back(val); }

		void pop() { _arr.pop_back(); }

		T& top() { return _arr.back(); }

		const T& top() const { return _arr.back(); }

		size_t size() const { return _arr.size(); }

		size_t capacity() const { return _arr.capacity(); }

		bool empty() const { return _arr.empty(); }

		void swap(self& s) { std::swap(_arr, s._arr); }

	private:
		container _arr;
	};
}
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

示例：

	void Test_stack()
	{
		stack<int>s1;
		s1.push(1);
		s1.push(2);
		s1.push(3);
		s1.push(4);
		

		stack<int>s2;
		s2.push(10);
		s2.push(20);
		s2.push(30);
		cout << s1.size() << endl;
		cout << s2.size() << endl;
		cout << endl;
		
		s1.swap(s2);
		cout << s1.size() << endl;
		cout << s2.size() << endl;
		while (!s1.empty())
		{
			cout << s1.top() << endl;
			s1.pop();
		}
		cout << endl;

		while (!s2.empty())
		{
			cout << s2.top() << endl;
			s2.pop();
		}
	}

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

运行实例：

---

（二）queue

queue模拟实现

namespace kz
{
	template<class T, class Con = deque<T>>
	class queue
	{
	public:

		void push(const T& x) { _arr.push_back(x); }

		void pop() { _arr.pop_front(); }

		T& back() { return _arr.back(); }

		const T& back()const { return _arr.back(); }

		T& front() { return _arr.front(); }

		const T& front()const { return _arr.front(); }

		size_t size()const { return _arr.size(); }

		bool empty()const { return _arr.empty(); }

	private:

		Con _arr;

	};
}

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

示例：

	void Test_queue()
	{
		queue<int>q1;
		q1.push(10);
		q1.push(20);
		q1.push(30);
		q1.push(50);

		queue<int>q2(q1);

		while (!q1.empty())
		{
			cout << q1.front() << ' ';
			q1.pop();
		}
		cout << endl << endl;

		while (!q2.empty())
		{
			cout << q2.front() << ' ';
			q2.pop();
		}
		cout << endl << 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

运行实例：

---

为什么栈和队列要使用deque

vector的尾插尾删效率高，无需挪动数据，但是头插头删效率低下；
list的头插头删、尾插尾删效率都很高，但是，数据存储不是连续的，所以访问数据的效率低下；
由于双端队列的数据存储是从中间开始的，头插头删、尾插尾删效率都很高，并且读取数据时效率也可以接受，
整合了vector与list的优点，但是在实际应用中没有vector与list那么极致，或者说：短板拉长了，长板变短了。
但是在栈和队列这样只需要进行头插头删，尾插尾删，不需要进行遍历的限制下使用deque不失为一种好的选择。

---

（三）priority_queue

相比于stack与queue，priority_queue 的底层要复杂许多，前两个参数相同，但优先级队列最后多了一个比较仿函数，而这个仿函数是选最值。
优先级队列的底层是堆，因此我们一般使用vector作为默认容器，而且一般不会改变它，
默认比较仿函数是less，按照我们平时的思路排出的应该是升序，但是这里默认堆顶是最大值，这是第一个需要注意的地方；
第二个需要注意的就是后两个参数的位置，我们一般不会改变vector容器，但是比较函数则不一定，当数据元素为自定义类型时就必须自定义比较仿函数，但是在改变比较仿函数时我们还必须先传第二个参数，因此当我们需要改变比较仿函数时需要传三个参数，这个确实有些多此一举，但是标准已经确定就不会再更改，因此我们以后使用也需要注意。

priority_queue模拟实现

#pragma once
#include<iostream>
using namespace std;
#include<vector>

namespace kz
{
	template<class T>
	struct less
	{
		bool operator()(const T& e1, const T& e2) const// 小于
		{
			return e1 < e2;
		}
	};

	template<class T>
	struct greater
	{
		bool operator()(const T& e1, const T& e2) const // 大于
		{
			return e1 > e2;
		}
	};

	template<class T, class container = vector<T>, class compare  = less<T>> // 适配器
	class priority_queue
	{
	public:
		priority_queue() = default; // 使用默认构造

		template<class iteratortype> // 迭代器区间构造
		priority_queue(iteratortype begin, iteratortype end)
			:_a(begin, end)
		{
			MakeHeap();
		}

		void push(const T& val)
		{
			_a.push_back(val);
			//  向上调整 
			AdjustUp(_a.size() - 1);
		}

		const T& top() // 堆中的数据不允许修改，防止破坏堆的结构
		{
			return _a.front();
		}

		void pop()
		{
			SwapTop(0, _a.size() - 1);
			_a.pop_back();
		}

		size_t size()
		{
			return _a.size();
		}

		bool empty()
		{
			return _a.empty();
		}

	private:
		void SwapTop(size_t begin, size_t end)
		{
			swap(_a[begin], _a[end]);
			AdjustDown(0, _a.size() - 1);
		}
		// 初始化 -- 建堆
		void MakeHeap()
		{
			for (int i = (_a.size() - 2) / 2; i >= 0; --i) // 此处如果使用size_t 要注意控制结束条件，避免无限循环
				AdjustDown(i, _a.size());
		}
		//		向上调整
		void AdjustUp(size_t child) // 配合标准库实现：小堆降序
		{
			size_t parent = (child - 1) / 2;
			while (child > 0)
			{
				if (cmp(_a[parent], _a[child]))
				{
					swap(_a[child], _a[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else // 孩子不大于父亲就退出
				{
					break;
				}
			}
		}
		// 向下调整
		void AdjustDown(size_t parent, size_t capacity)
		{
			size_t child = parent * 2 + 1;
			while (child < capacity)
			{
				// 右孩子存在且 大
				if (child + 1 < capacity && cmp(_a[child], _a[child + 1]))
					++child;
				// 孩子比双亲大
				if (cmp(_a[parent], _a[child]))
				{
					swap(_a[child], _a[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else// 否则调整结束
				{
					break;
				}
			}
		}

	private:
		container _a;
		compare cmp;
	};

}
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

示例：

	void TestPriorityQueue_1()
	{
		priority_queue<int>q;
		for (int i = 0; i < 6; ++i) q.push(i);
		while(!q.empty())
		{
			cout << q.top() << " ";
			q.pop();
		}
		cout << endl << endl;

	}

	void TestPriorityQueue_2()
	{
		srand((unsigned)time(nullptr));
		vector<int>v;
		for (int i = 0; i < 10; ++i) v.push_back(rand()%100);
		priority_queue<int, vector<int>, greater<int>>q(v.begin(), v.end());
		while (!q.empty())
		{
			cout << q.top() << " ";
			q.pop();
		}
		cout << endl << endl;

	}

	struct Person
	{
		int _a;
		int _b;

		bool operator<(const Person& p)const // 告诉对方我的比较规则
		{
			return _a < p._a;
		}
	};

	void TestPriorityQueue_3()
	{
		srand((unsigned)time(nullptr));
		vector<Person>v;
		for (int i = 0; i < 10; ++i) v.push_back({ rand() % 100 , i});
		priority_queue<Person>q(v.begin(), v.end());

		while (!q.empty())
		{
			cout << q.top()._a << " " << q.top()._b << endl;
			q.pop();
		}
		cout << endl << 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

运行实例：

---

总结

适配器就是在容器的外面再嵌套一层容器，通过对普通容器的限制，达到我们想要的结果。
stl中的容器适配器一共有三个stack、queue以及priority_queue，它们的操作很少，并且接口十分类似，今天我们已经见识了它们的函数接口以及接口的实现，如果你可以自行写出它们的模拟实现，那你对于容器适配器的理解就会迈入很高的层次。
希望对有需要的朋友带来帮助。