【C++】STL标准容器之容器适配器

一、标准容器 2、容器适配器

标准容器 - 容器适配器

怎么理解适配器？

• 容器适配器底层没有自己的数据结构，它是另外一个容器的封装，它的方法全部由底层依赖的容器进行实现的，如下Stack代码，它的底层就是deque，相当于将deque适配成一个Stack
• 没有实现自己的迭代器

template<typename T, typename Container=deque<T>>  
class Stack
{
public:
    void push(const T & val) { con.push_back(val); }//底层的deque的末尾作为栈顶进行入栈出栈
    void pop() { con.pop_back(); }
    T top() const { return con.back(); }  
private:
    Container con;
};

stack适配器源码：

stack queue priority_queue

容器适配器	基本概念	基本 *** 作	底层容器
stack	栈：先进后出	push入栈， pop出栈， top查看栈顶元素， empty判空，size返回元素个数	deque
queue	队列：先进先出，后进后出，头出尾入	push队尾入， pop队头出， front查看队头元素 ，back查看队尾元素， empty判空， size返回队列中元素个数	deque
priority_queue	优先级队列：优先级大的先出队，底层数据结构默认是大根堆	push入队， pop出队， top查看队顶元素， empty判空， size返回元素个数	vector

stack与queue底层容器：deque，为什么不依赖vector呢？

• vector的初始内存使用效率太低了，没有deque好：vector 0-1-2-4-8，deque 4096/sizeof(T)
• 对于queue来说需要支持尾部插入，头部删除，时间复杂度最好都为O(1)，而vector尾插是O(1)，头删却是O(n)，如果queue依赖vector，其出队效率很低
• vector需要大片连续内存，deque只需要分段内存，当存储大量数据时，显然deque对于内存的利用率更好

priority_queue底层容器：vector，为什么依赖vector，不依赖deque？

• 优先级队列底层默认把数据组成一个大根堆结构，而大根堆的构建就需要在一个内存连续的数组上（堆中结点和它左右孩子的关系是通过下标计算的），vector动态数组底层是绝对连续的，而deque是分段连续的，所以用vector

三种容器适配器代码示例：

//stack-------------------------------------------------------------------------------
#include 
#include 
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();  //栈顶出栈
	}
}

//queue-------------------------------------------------------------------------------
#include 
#include 
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;
}

//priority_queue----------------------------------------------------------------------
#include 
#include 
using namespace std;

int main()
{
	priority_queue<int> pque;

	for (int i = 0; i < 20; ++i)
	{
		pque.push(rand() % 100 + 1);
	}

	cout << pque.size() << endl;

	while (!pque.empty())
	{
		cout << pque.top() << " ";
		pque.pop();
	}
	return 0;
}