容器适配器---queue、stack、priority_queue_容器适配器包括哪些

什么是配接器

配接器（adapters）在STL组件的灵活组合运用功能上，扮演者轴承、转换器的角色。Adapter这个概念，事实上是一种设计模式。在设计模式中对adapter样式的定义如下：将一个class接口转化为另一个class接口，使原本接口不兼容而不能合作的classes，可以一起运作。

使用
1.应用于容器 container adapters ， 比如stack和queue，其实就是一个适配器，他们通过修饰deque的接口而成就出的另一个容器风貌。
2.应用于迭代器iterator adapters
3，应用于仿函数

容器配接器

应用于容器 container adapters ， 比如stack和queue，其实就是一个适配器，他们通过修饰deque的接口而成就出的另一个容器风貌。

常见的容器适配器

比如stack、queue就是基于deque（双端队列）上封装出来的结构

容器适配器–queue

队列（Queue）队列是一种先进先出（FirstInFirstOut，FIFO）的线性表。它只允许在表的一端进行插入，而在另一端进行删除。向队列中插入元素称为入队，从队列中删除元素称为出队。

2）队首（front）允许进行删除的一端称为队首。

2）队尾（rear）允许进行插入的一端称为队尾。

4）队列的长度队列中数据元素的个数表示队列的长度。

5）空队列当队列中没有元素时称为空队列。

6）先进先出表（FIFO）队列的修改是按先进先出的原则进行的，又称为先进先出表（FIFO）

常用接口测试

void test()
{
	//测试构造
	queue<int>vv1;
	cout << "有效元素的个数为  ";
	cout << vv1.size() << endl;
	vv1.push(1);
	vv1.push(2);
	vv1.push(3);
	vv1.push(4);
	vv1.push(5);
	cout << "执行入队完成后" << endl;
	cout << "有效元素的个数为  ";
	cout << vv1.size() << endl;
	cout << "队头元素为" << vv1.front() << endl;
	cout << "队尾元素为" << vv1.back() << endl;
	//出队操作
	vv1.pop();
	cout << "执行一次出队操作后" << endl;
	cout << "队头元素为" << vv1.front() << endl;
	cout << "队尾元素为" << vv1.back() << endl;
	cout << "有效元素的个数为  ";
	cout << vv1.size() << endl;
	if (vv1.empty())
	{
		cout << "空" << endl;
	}
	else
	{
		cout << "非空" << 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

模拟实现queue

namespace bite
{
	template<class T, class Container = std::deque<T>>
	class queue
	{
	public:
		queue()
		{}

		void push(const T& data)
		{
			c.push_back(data);
		}

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

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

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

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

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

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

		bool empty()const
		{
			return c.empty();
		}
	private:
		Container c;
	};
}
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

容器适配器–stack

定义：一种“特殊”的线性数据结构，其只能在一端进行操作。可以操作的一端称为栈顶，另一端称为栈底。
特性：last in first out 先进后出

常用接口测试

构造

//测试构造
void test_constructor()
{
	deque<int>mycp1(2, 100);
	vector<int>mycp2(3, 100);
	//无参构造
	stack<int>vv1;
	//拷贝构造，再不提供显式的声明时，只能构造deque对象。
	stack<int>vv2(mycp1);
	//显式给出存储类型
	stack<int, vector<int>>vv3(mycp2);
	cout << vv1.size() << endl;
	cout << vv2.size() << endl;
	cout << vv3.size() << endl;
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

size()方法、top()方法 size()方法 pop()方法 push(）方法

void test()
{
	stack<int>vv1;
	if (vv1.empty())
	{
		cout << "栈空" << endl;
	}
	else
	{
		cout << "栈非空" << endl;
	}
	vv1.push(10);
	vv1.push(20);
	vv1.push(30);
	vv1.push(40);
	cout << "vv1此时的有效元素个数为" << vv1.size() << endl;
	cout << "vv1的栈顶元素为" << vv1.top() << endl;
	vv1.pop();
	cout << "执行出栈操作后" << endl;
	cout << "vv1此时的有效元素个数为" << vv1.size() << endl;
	cout << "vv1的栈顶元素为" << vv1.top() << endl;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

模拟实现stack

namespace mystack
{
	
	// Container: 栈底层存储元素的容器的类型，
	
	template<class T, class Container = std::deque<T>>
	class stack
	{
	public:
		stack()
			: c()
		{}

		void push(const T& data)
		{
			c.push_back(data);
		}

		void pop()
		{
			if (c.empty())
				return;

			c.pop_back();
		}

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

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

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

		bool empty()const
		{
			return c.empty();
		}
	private:
		Container c;
	};
}
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

priority_queue 优先级队列

常用方法测试

//构造

void test_constructor()
{
	//无参构造
	priority_queue<int>vv1;
	cout << vv1.size() << endl;
	//迭代器构造
	int arr[] = { 2,4,4,9,1,0 };
	priority_queue<int>vv2(arr,arr+6);
	cout << vv2.size() << endl;
}
1
2
3
4
5
6
7
8
9
10

void test_push_top()
{
	priority_queue<int>vv1;
	vv1.push(1);
	vv1.push(5);
	vv1.push(2);
	vv1.push(9);
	vv1.push(4);
	cout << "有效元素个数为" << vv1.size() << endl;
	cout << "堆顶元素为" << vv1.top() << endl;
	vv1.pop();
	cout << "有效元素个数为" << vv1.size() << endl;
	cout << "堆顶元素为" << vv1.top() << endl;
	if (vv1.empty())
	{
		cout << "优先级队列为空" << endl;
	}
	else
	{
		cout << "优先级队列非空" << endl;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

模拟实现

namespace my
{
	template<class T, class container = std::vector<T>, class compare = std::less<T>>
	//template<class T, class Container = std::vector<T>, class Compare = std::less<T>>
	class priority_queue
	{
	public:
		priority_queue()
		{}

		template<class Iterator>
		priority_queue(Iterator first, Iterator last)
			: c(first, last)
		{
			int root = ((c.size() - 1 - 1) >> 1);
			for (; root >= 0; root--)
				AdjustDown(root);
		}
		void push(const T& t1)
		{
			c.push_back(t1);
			AdjustUp();
		}
		void pop()
		{
			if (empty())
			{
				return;
			}
			std::swap(c.front(), c.back());
			c.pop_back();
			AdjustDown(0);
		}
		const T& top()const
		{
			return c.front();
		}

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

		bool empty()const
		{
			return c.empty();
		}
	private:
		void AdjustDown(int root)
		{
			int child = root * 2 + 1;
			int size = c.size();
			while (child < size)
			{
				if (child + 1 < size && com(c[child], c[child + 1]))
				{
					child += 1;
				}
				if(com(c[root],c[child]))
				{
					std::swap(c[root], c[child]);
					root = child;
					child = 2 * root + 1;
				}
				else
				{
					return;
				}
			}
		}
		void AdjustUp()
		{
			int child = c.size() - 1;
			int parent = ((child - 1) >> 1);

			while (child)
			{
				if (com(c[parent], c[child]))
				{
					std::swap(c[parent], c[child]);
					child = parent;
					parent = ((child - 1) >> 1);
				}
				else
				{
					return;
				}
			}
		}
	

	private:
		container c;
		compare com;
	};
}
#include<iostream>
using namespace std;
void TestMyPriorityQueue()
{
	int array[] = { 5,6,3,0,9,2,8,1,7,4 };
	my::priority_queue<int, vector<int>, less<int>> q(array, array + sizeof(array) / sizeof(array[0]));
	cout << q.top() << endl;

	q.pop();
	cout << q.top() << endl;
	cout << q.size() << 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
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

简单介绍deque双端队列

概念

deque(双端队列)：是一种双开口的 “连续” 空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高
deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组
双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，落在了deque的迭代器身上

双端队列元素的访问-简单介绍

双端队列的优势与缺陷

与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必vector高的。与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。但是，deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构

为什么选用deque作为stack和queu底层实现

1. stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
2. 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高。