一、怎么理解适配器？

1）适配器底层没有自己的数据结构，它是另外一个容器的封装，它的方法全部由底层依赖的容器进行实现的；
2）没有实现自己的迭代器；

二、常见的容器适配

容器适配器有三种常见的类型：栈（stack）、队列（queue）和优先队列

1.栈

先进后出，后进先出

push入栈  pop出栈  top查看栈顶元素  empty判断栈空  size返回元素个数

#include<iostream>
#include<stack>
using namespace std;
int main()
{
	stack<int> s1;
	for (int i = 0; i < 20; ++i)
	{
		s1.push(rand() % 100 + 1);
	}
	cout << s1.size() << endl;
	while (!s1.empty())
	{
		cout << s1.top() << " ";
		s1.pop();
	}
	return 0;
}

2.队列

先进先出，队尾入，队头出

push入队  pop出队  front查看队头元素  back查看队尾元素  empty判断队空  size返回元素个数

#include<iostream>
#include<queue>
using namespace std;
int main()
{
	queue<int> que;
	for (int i = 0; i < 20; ++i)
	{
		que.push(rand() % 100 + 1);
	}
	cout << que.size() << endl;
	while (!que.empty())
	{
		cout << que.front() << " ";
		que.pop();
	}
	return 0;
}

3.优先级队列

优先队列是一种特殊的队列，其中的元素按照一定的优先级进行排序，因此具有较高优先级的元素会被优先处理。

push入队  pop出队  top查看队顶元素  empty判断队空  size返回元素个数
ps：top返回优先级队列中最大(最小元素)；pop删除优先级队列中最大(最小)元素，即堆顶元素

#include<iostream>
#include<queue>
using namespace std;
int main()
{
	priority_queue<int> que;
	for (int i = 0; i < 20; ++i)
	{
		que.push(rand() % 100 + 1);
	}
	cout << que.size() << endl;
	while (!que.empty())
	{
		cout << que.top() << " ";
       //输出96 92 82 79 70 68 65 63 62 59 46 43 42 37 35 28 28 25 6 1
       //先查看最大元素
		que.pop();
	}
	return 0;
}

4.区别

stack和queue依赖于deque，为什么不依赖于vector？？？

• vector的初始内存使用效率太低了，没有deque好：queue<int> stcak<int> => vector 0-1-2-4-8，但deque 4096/sizeof(int) = 1024（即一次性开辟的第二维的内存空间）；
• 对于queue来说，需要支持尾部插入。头部删除的复杂度都是O(1)，但vector的头部删除是O(n)，效率很低，不满足要求；
• vector需要大片的连续内存，deque只需要分段的内存，当存储大量数据时，明显deque对于内存的利用率更好。

---

priority_queue依赖于vector，为什么依赖于vector？？？

底层默认把数据组成一个大根堆结构，在一个内存连续的数组上构建一个大根堆或小根堆，而deque的内存不是连续的。