C++ STL | 容器适配器-洪萨配资

C++ STL 中的容器适配器（Container Adapters）

容器适配器是基于现有的 STL 容器（序列容器或关联容器）通过限制接口、改变语义来实现特定数据结构的一种“适配”方式。

它们本身不是独立的容器，而是对已有容器的封装，提供了受限的、更专一的接口。

C++ STL 中目前存在的三种主要容器适配器（C++11～C++20）

容器适配器	底层默认容器	主要接口特点	典型用途	是否支持比较运算符	是否可自定义底层容器
`stack`	`deque`	只允许栈顶操作（push/pop/top）	后进先出（LIFO）	是（C++20起）	是
`queue`	`deque`	队首出、队尾进（push/pop/front/back）	先进先出（FIFO）	是（C++20起）	是
`priority_queue`	`vector`+ 大顶堆	只能访问/弹出队首（最大/最小元素）	优先级队列（默认最大堆）	否	是

一、详细对比表（包含常用操作的时间复杂度）

容器适配器|底层默认容器|压入元素|弹出元素|访问顶/首元素|判空/大小|遍历方式|随机访问---------------|----------------|--------------|--------------|---------------|-----------|------------------|-----------stack<T>|deque|push()O(1)|pop()O(1)|top()O(1)|empty()/size()|不支持遍历|不支持 queue<T>|deque|push()O(1)|pop()O(1)|front()O(1)|empty()/size()|不支持遍历|不支持 priority_queue|vector+heap|push()O(log n)|pop()O(log n)|top()O(1)|empty()/size()|不支持遍历|不支持

二、最常用写法与自定义底层容器示例

#include<iostream>#include<stack>#include<queue>#include<vector>#include<deque>#include<list>// 1. 普通使用std::stack<int>s;// 默认用 dequestd::queue<int>q;// 默认用 dequestd::priority_queue<int>pq;// 默认 vector + 大顶堆// 2. 常用小技巧 - 最小堆（最常用写法）std::priority_queue<int,std::vector<int>,std::greater<int>>minHeap;// 3. 完全自定义底层容器std::stack<int,std::vector<int>>stack_vec;// 用 vector 做栈（不推荐，效率较低）std::stack<int,std::deque<int>>stack_deque;// 最常用组合（默认）std::stack<int,std::list<int>>stack_list;// 可以，但不常见std::queue<int,std::list<int>>queue_list;// 合法，但效率通常不如 deque// 4. priority_queue 最常见的几种写法usingpii=std::pair<int,int>;// 最大堆（默认）std::priority_queue<int>max_pq;// 最小堆（最常用写法）std::priority_queue<int,std::vector<int>,std::greater<>>min_pq;// 自定义比较器 - 按 pair 第一元素从小到大，相同则第二元素从大到小autocmp=[](constpii&a,constpii&b){if(a.first!=b.first)returna.first>b.first;// 小顶堆returna.second<b.second;// 第二关键字大顶};std::priority_queue<pii,std::vector<pii>,decltype(cmp)>pq_custom(cmp);

三、容器适配器重要特性总结（面试/笔试高频）

都没有clear()、erase()、insert()等普通容器接口
都没有迭代器！（不能遍历）
都没有begin()/end()/rbegin()等
priority_queue是唯一默认不保证先进先出的
priority_queue不提供pop()返回值的接口（与 Java 不同）
stack和queue在 C++20 之后支持了operator==、operator<=>（需底层容器也支持）
改变底层容器不会改变时间复杂度（除了 priority_queue 的底层必须是随机访问容器）

四、常见面试/笔试陷阱题速览

// 下面哪些是合法的？（多选）A.std::stack<int>::iterator it;// × 没有迭代器B.std::priority_queue<int>pq;pq.clear();// × 没有 clear()C.std::queue<int>q;q.push(1);q.pop();// √D.std::priority_queue<int>pq;pq.emplace(42);// √（C++11）E.std::stack<int,std::vector<int>>s;s.top()=10;// × top()返回const引用（const T&）F.autopq=std::priority_queue<int>{1,2,3};// × 没有这种初始化方式G.std::priority_queue<int>pq{1,3,2};// × 同上