标准接口介绍
一、栈：stack
1. 栈的基本操作
std::stack::top
// stack::top
#include<iostream>
#include<stack>
int main(){
std::stack<int> mystack;
mystack.push(10);
mystack.push(20);
mystack.top()-=5;
std::cout << "现在栈顶的元素是：" << mystack.top() << '\n';
return 0;
}
std::stack::push
// stack::push/pop
#include<iostream>
#include<stack>
int main(){
std::stack<int> mystack;
for(int i = 0; i < 5;++i){
mystack.push(i);
}
std::cout << "从栈中弹出元素..." << std::endl;
while(!mystack.empty()){
std::cout << mystack.top() << ' ';
mystack.pop();
}
std::cout << '\n';
return 0;
}
std::stack::pop
2. 查询栈的状态
std::stack::size
// stack::size
#include<iostream>
#include<stack>
int main(){
std::stack<int> myints;
std::cout << "初始状态下的 size: " << myints.size() << '\n';
for(int i = 0; i < 5; i++){
myints.push(i);
}
std::cout << "入栈元素后的 size: " << myints.size() << '\n';
myints.pop();
std::cout << "出栈元素后的 size: " << myints.size() << '\n';
return 0;
}
std::stack::empty
// stack::empty
#include<iostream>
#include<stack>
int main(){
std::stack<int> mystack;
int sum(0);
for(int i=1;i<=10;i++) mystack.push(i);
while(!mystack.empty()){
sum += mystack.top();
mystack.pop();
}
std::cout << "total: " << sum << '\n';
return 0;
}
二、队列：queue
1. 队列基本操作
std::queue::front
// queue::front
#include<iostream>
#include<queue>
int main(){
std::queue<int> myqueue;
myqueue.push(77);
myqueue.push(16);
myqueue.front()-= myqueue.back();
std::cout << "现在的队头元素是：" << myqueue.front() << '\n';
return 0;
}
std::queue::back
// queue::back
#include<iostream>
#include<queue>
int main(){
std::queue<int> myqueue;
myqueue.push(12);
myqueue.push(75);
myqueue.back()-= myqueue.front();
std::cout << "现在的队尾元素是：" << myqueue.back() << '\n';
return 0;
}
std::queue::push
// queue::push/pop
#include<iostream>
#include<queue>
int main(){
std::queue<int> myqueue;
int myint;
std::cout << "请输入一些整数（输入 0 以结束）：\n";
do{
std::cin >> myint;
myqueue.push(myint);
}while(myint);
std::cout << "myqueue 队列中的内容是： ";
while(!myqueue.empty()){
std::cout << ' '<< myqueue.front();
myqueue.pop();
}
std::cout << '\n';
return 0;
}
std::queue::pop
2. 查询队列状态
std::queue::size
// queue::size
#include<iostream>
#include<queue>
int main(){
std::queue<int> myints;
std::cout << "初始状态下的 size: " << myints.size() << '\n';
for(int i = 0; i < 5; i++){
myints.push(i);
}
std::cout << "入队元素后的 size: " << myints.size() << '\n';
myints.pop();
std::cout << "出队元素后的 size: " << myints.size() << '\n';
return 0;
}
std::queue::empty
// queue::empty
#include<iostream>
#include<queue>
int main(){
std::queue<int> myqueue;
int sum(0);
for(int i = 1; i <=10; i++){
myqueue.push(i);
}
while(!myqueue.empty()){
sum += myqueue.front();
myqueue.pop();
}
std::cout << "队列中的元素之和是：" << sum << '\n';
return 0;
}
三、优先队列：priority_queue
1. 优先队列的基本操作
std::priority_queue::top
// priority_queue::top
#include<iostream>
#include<queue>
int main(){
std::priority_queue<int> mypq;
mypq.push(10);
mypq.push(20);
mypq.push(15);
std::cout << "现在优先队列中的队头的元素是：" << mypq.top() << '\n';
return 0;
}
std::priority_queue::push
// priority_queue::push/pop
#include<iostream>
#include<queue>
int main(){
std::priority_queue<int> mypq;
mypq.push(30);
mypq.push(100);
mypq.push(25);
mypq.push(40);
std::cout << "从优先队列中出队元素..." << std::endl;
while(!mypq.empty()){
std::cout << mypq.top() << " ";
mypq.pop();
}
std::cout << '\n';
return 0;
}
std::priority_queue::pop
2. 查询优先队列的状态
std::priority_queue::size
// priority_queue::size
#include<iostream>
#include<queue>
int main(){
std::priority_queue<int> myints;
std::cout << "初始状态下的 size: " << myints.size() << '\n';
for(int i = 0; i < 5; i++){
myints.push(i);
}
std::cout << "入队元素后的 size: " << myints.size() << '\n';
myints.pop();
std::cout << "出队元素后的 size: " << myints.size() << '\n';
return 0;
}
std::priority_queue::empty
// priority_queue::empty
#include<iostream>
#include<queue>
int main(){
std::priority_queue<int> mypq;
int sum(0);
for(int i = 1; i <=10; i++){
mypq.push(i);
}
while(!mypq.empty()){
sum += mypq.top();
mypq.pop();
}
std::cout << "队列中的元素之和是:" << sum << '\n';
return 0;
}
优先队列怎么显示定义为'小顶堆'？
1. 元素类型是'内置类型'
在 C++ 中，若要显式将 priority_queue 定义为小顶堆（元素值越小，优先级越高），需通过模板参数指定底层容器和比较器。具体点说就是显式指定使用默认的 vector 底层容器和使用标准库 <functional> 提供的 greater<T> 比较器。
注：上面博主没有写错哦，就是要显示指定上面的两种的东西，可能你会有疑问底层容器使用的就是默认的 vector 啦，我还显示指定个蛋啊！
哈哈 O(∩_∩)O，这是因为 priority_queue 的模板参数列表要求：当你指定第三个参数（比较器）时，必须同时指定第二个参数（底层容器）。若不指定比较器：可省略所有模板参数，默认使用 vector 和 less。若指定比较器：必须显式指定底层容器，否则会导致编译错误。
总结：如果你想让优先队列定义为'小顶堆'，可以使用下面的定义方法：std::priority_queue<T, std::vector<T>, std::greater<T>> 或 std::priority_queue<T, std::deque<T>, std::greater<T>>
代码案例：使用优先队列定义'小顶堆'（存储内置类型）
#include<iostream>
#include<vector>
#include<queue>
#include<functional>
using namespace std;
int main(){
/*------------------测试 1：优先队列创建的'大顶堆'------------------*/
cout << "---------测试 1：优先队列创建的'大顶堆'---------" << endl;
/*-------------第一步：创建'大顶堆'的一个优先队列-------------*/
//1.先创建一个 vector 容器（目的：为优先队列进行赋值）
vector<int> v{3,2,7,6,0,4,1,9,8,5};
//2.使用默认的方式创建一个优先队列（不指定：'底层容器'+'比较器'）
priority_queue<int> q1;
//3.为优先队列进行赋值
for(auto& it : v)
q1.push(it);
/*-------------第二步：输出优先队列的队头元素验证'大顶堆'-------------*/
cout << "优先的队列的队头元素是：" << q1.top() << endl;
/* 注意事项： * 默认情况下，priority_queue 使用 vector 作为底层容器，less<int> 作为比较器 * 这会构建一个'大顶堆'（即：堆顶元素为最大值） * 创建大顶堆：优先级最高的元素是最大值 *
/*------------------测试 2：优先队列创建的'小顶堆'------------------*/
cout << "---------测试 1：优先队列创建的'小顶堆'---------" << endl;
/*-------------第一步：创建'小顶堆'的一个优先队列-------------*/
/*---------方式一：逐个插入方式初始化---------*/
priority_queue<int, vector<int>, greater<int>> q2;
for(auto& it : v){
q2.push(it);
}
/*-------------第二步：输出优先队列的队头元素验证'小顶堆'-------------*/
cout << "优先的队列的队头元素是：" << q2.top() << endl;
/* 注意事项： * 通过显式指定模板参数： * 元素类型：int * 底层容器：vector<int> * 比较器：greater<int>（表示'较小的元素优先级更高'） * 这会构建一个'小顶堆'（即：堆顶元素为最小值） * 创建大顶堆：优先级最高的元素是最小值 *
return 0;
}
2. 元素类型是'自定义类型'
在 priority_queue 中存储 自定义类型 的数据时，用户需要在自定义类型中重载 < 或 > 运算符，以明确元素的优先级规则。
核心逻辑：priority_queue（优先级队列）本质是堆结构，需要根据元素的优先级来调整堆的顺序。对于自定义类型，编译器无法默认判断元素的大小关系因此必须通过 运算符重载 或 自定义比较器 告诉编译器如何比较元素的优先级。
常见场景：
- 使用默认比较器（大顶堆）：需求希望自定义类型的对象形成大顶堆（优先级高的元素为'较大'的对象）。实现：重载
<运算符，定义'当前对象小于另一个对象'的逻辑。 - 显式指定小顶堆（或自定义比较逻辑）：需求希望自定义类型的对象形成小顶堆（优先级高的元素为'较小'的对象），或使用其他比较规则（如：按属性倒序）。实现：重载
>运算符，并搭配std::greater<自定义类型>比较器。
代码案例：使用优先队列定义'小顶堆'（存储内置类型）
#include<iostream>
#include<vector>
#include<queue>
#include<functional>
using namespace std;
/*-------------------------定义日期类-------------------------*/
class Date{
public:
/*-------------第一部分：定义友元函数-------------*/
//1.实现：'<<运算符重载函数'
friend ostream& operator<<(ostream& out, const Date& d){
out << d._year << "-" << d._month << "-" << d._day;
return out;
}
/*-------------第二部分：定义成员函数-------------*/
//1.实现：'全缺省构造函数'
Date(int year = 1900, int month = 1, int day = 1):_year(year),_month(month),_day(day){}
//2.实现：'<运算符重载函数'
bool operator<(const Date& d) const{
return (_year < d._year) || (_year == d._year && _month < d._month) || (_year == d._year && _month == d._month && _day < d._day);
}
//3.实现：'>运算符重载函数'
bool operator>(const Date& d) const{
return (_year > d._year) || (_year == d._year && _month > d._month) || (_year == d._year && _month == d._month && _day > d._day);
}
private:
int _year;
int _month;
int _day;
};
/*-------------------------测试 priority_queue 对自定义类型的使用-------------------------*/
int main(){
/*------------------第一部分：大顶堆示例------------------*/
//1.使用默认的方式定义优先队列 ---> 大顶堆
priority_queue<Date> q1;
//2.为优先队列赋值 ---> 插入三个日期，按 operator< 排序后，最大的日期在堆顶
q1.push(Date(2025,5,29));
q1.push(Date(2025,5,28));
q1.push(Date(2025,5,30));
//3.输出优先队列的队头的元素 ---> 输出堆顶元素（最大日期）
cout << q1.top() << endl;
/*------------------第二部分：小顶堆示例------------------*/
//2.显示指定'底层容器 + 比较器'定义优先队列 ---> 小顶堆
priority_queue<Date, vector<Date>, greater<Date>> q2;
//3.为优先队列赋值 ---> 插入相同的三个日期，按 operator> 排序后，最小的日期在堆顶
q2.push(Date(2025,5,29));
q2.push(Date(2025,5,28));
q2.push(Date(2025,5,30));
//3.输出优先队列的队头的元素 ---> 输出堆顶元素（最小日期）
cout << q2.top() << endl;
return 0;
}
模拟实现展示
头文件：Stack.h
#pragma once
#include<deque>
namespace mySpace {
template<class T, class Container = std::deque<T>>
class stack {
private:
Container _con;
public:
void push(const T& x) { _con.push_back(x); }
void pop() { _con.pop_back(); }
const T& top() const { return _con.back(); }
size_t size() const { return _con.size(); }
bool empty() const { return _con.empty(); }
};
}
头文件：Queue.h
#pragma once
#include<deque>
namespace mySpace {
template<class T, class Container = std::deque<T>>
class queue {
private:
Container _con;
public:
void push(const T& x) { _con.push_back(x); }
void pop() { _con.pop_front(); }
const T& front() const { return _con.front(); }
const T& back() const { return _con.back(); }
size_t size() const { return _con.size(); }
bool empty() const { return _con.empty(); }
};
}
头文件：PriorityQueue.h
#pragma once
#include<vector>
template<class T>
class Less {
public:
bool operator()(const T& x, const T& y) { return x < y; }
};
template<class T>
class Greater {
public:
bool operator()(const T& x, const T& y) { return x > y; }
};
namespace mySpace {
template<class T, class Container = std::vector<T>, class Compare = Less<T>>
class priority_queue {
private:
Container _con;
void AdjustUp(int child) {
Compare com;
int parent = (child - 1) / 2;
while(child > 0) {
if(com(_con[parent], _con[child])) break;
std::swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
}
void AdjustDown(int parent) {
Compare com;
int minchild = parent * 2 + 1;
while(minchild < _con.size()) {
if(minchild + 1 < _con.size() && com(_con[minchild + 1], _con[minchild])) minchild++;
if(com(_con[parent], _con[minchild])) break;
std::swap(_con[minchild], _con[parent]);
parent = minchild;
minchild = parent * 2 + 1;
}
}
public:
void push(const T& x) {
_con.push_back(x);
AdjustUp(_con.size() - 1);
}
void pop() {
if(empty()) return;
std::swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
AdjustDown(0);
}
const T& top() { return _con[0]; }
size_t size() const { return _con.size(); }
bool empty() const { return _con.empty(); }
};
}
测试文件：Test.cpp
#include<iostream>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
#include"Stack.h"
#include"Queue.h"
#include"PriorityQueue.h"
using namespace std;
void test01(){
cout << "------------测试栈的功能------------" << endl;
mySpace::stack<int, list<int>> stk;
stk.push(1); stk.push(2); stk.push(3); stk.push(4);
cout << "入栈之后，此时栈顶的元素是：" << stk.top() << endl;
stk.pop();
cout << "出栈之后，此时栈顶的元素是：" << stk.top() << endl;
cout << "------------测试队列的功能------------" << endl;
mySpace::queue<int> que;
que.push(1); que.push(2); que.push(3); que.push(4);
cout << "入队之后，此时队头的元素是：" << que.front() << endl;
cout << "入队之后，此时队尾的元素是：" << que.back() << endl;
que.pop();
cout << "出队之后，此时队头的元素是：" << que.front() << endl;
cout << "出队之后，此时队尾的元素是：" << que.back() << endl;
}
void test02(){
cout << "------------测试优先队列（堆）的功能------------" << endl;
mySpace::priority_queue<int, vector<int>, Greater<int>> pqu;
pqu.push(4); pqu.push(1); pqu.push(5); pqu.push(7); pqu.push(9);
while(!pqu.empty()){
cout << pqu.top() << " ";
pqu.pop();
}
cout << endl;
}
int main(){
test01();
test02();
return 0;
}
代码片段剖析
片段一：AdjustUp 和 AdjustDown 方法的参数为什么进行了简化？
在自定义的 priority_queue 类模板中，AdjustUp 和 AdjustDown 方法的参数之所以从原始的数组指针和长度简化为 child 或 parent 下标，是因为：类模板内部已经封装了底层容器（如：vector），无需再通过外部传入数据数组和长度。
原始参数设计的问题：这种设计需要用户手动传入数组和长度，耦合性高且不通用。当 priority_queue 封装了底层容器（如：vector）后，这些数据应属于类的内部状态，无需外部暴露。
修改后参数简化的原因：封装底层容器，类模板中定义了成员变量 Container _con，用于存储堆元素。AdjustUp 和 AdjustDown 直接通过 _con 访问元素，无需外部传入数组指针。自动获取容器长度，通过 _con.size() 获取当前元素个数，替代旧版本的 n 参数，避免手动传递长度可能导致的越界问题。依赖类模板参数，比较逻辑通过类模板参数 Compare 实现（仿函数 com），而非硬编码比较规则，提升了代码的灵活性（可适配大堆/小堆）。
片段二：Swap(&a[child], &a[parent]) 的传参为什么发生了改变？
在代码中使用 std::swap(_con[child], _con[parent]) 替换原始的 Swap(&a[child], &a[parent])，主要是因为：底层容器的封装方式改变 和 C++ 标准库的易用性。
原始代码的问题：a 是外部传入的数组指针，需要通过 &a[child] 获取元素地址，再传递给自定义的 Swap 函数进行交换。这种方式依赖原始数组的内存布局，且 Swap 函数可能需要手动实现，耦合性高且不通用。
修改后使用 std::swap 的原因：自定义的 priority_queue 类模板中，元素存储在成员变量 _con（底层容器，如：vector<T>）中。_con[child] 和 _con[parent] 直接通过容器的 operator[] 接口访问元素，无需通过指针操作原始内存。
核心问题深究
一、仿函数
1. 什么是仿函数？
仿函数（Functor）：也称为函数对象（Function Object），是一种在 C++ 中通过类或结构体实现的可调用实体。仿函数的核心特点是 重载了 operator() 运算符，使得类的对象可以像普通函数一样被调用。仿函数是 C++ 中 '以类模拟函数' 的重要机制，这种机制结合了面向对象的封装性和函数的灵活性，在 STL 和算法中有着广泛应用。
仿函数的核心特点：
- 重载 operator()
- 可携带状态：仿函数可以像普通类一样拥有成员变量，用于存储
状态或参数，这使得它比普通函数更灵活。
使用时：
Add add;
int result = add(3, 5);
通过在类中定义 operator() 运算符，使得该类的对象可以像函数一样被调用：
class Add {
public:
int operator()(int a, int b) {
return a + b;
}
};
2. 仿函数有什么用途？
- STL 算法中的比较器和谓词
- 自定义算法逻辑
- 替代函数指针：相比函数指针，仿函数更安全（类型检查严格）、更灵活（可携带状态），且性能接近函数调用（编译器易优化）
在自定义算法中，通过仿函数将逻辑抽象出来，提高代码复用性。
template<class Compare>
void BubbleSort(int* a, int n, Compare com){
if(com(a[j], a[j - 1])){
swap(a[j-1], a[j]);
}
}
谓词：用于筛选元素（如：find_if、remove_if）
class IsEven {
public:
bool operator()(int x) const {
return x % 2 == 0;
}
};
比较器：通过仿函数指定排序规则（如：升序/降序）
#include<algorithm>
#include<vector>
using namespace std;
class Greater {
public:
bool operator()(int a, int b) const {
return a > b;
}
};
int main(){
vector<int> nums = {3, 1, 4, 2};
sort(nums.begin(), nums.end(), Greater());
return 0;
}
3. 仿函数与普通函数的区别有哪些？
| 特性 | 普通函数 | 仿函数 |
|---|---|---|
| 调用方式 | 直接调用 | 通过对象调用 |
| 状态存储 | 无法存储状态 | 可通过成员变量存储状态 |
| 类型安全 | 弱 | 强 |
| 可复用性 | 低 | 高 |
| 重载 | 通过不同参数列表 | 通过多个 operator() 实现 |
| 性能 | 取决于编译器 | 容易 |
4. 怎么让冒泡排序既可以升序又可以降序排序？
假如我们想要对一批数据使用冒泡排序同时实现升序和降序排序，该怎么做呢？可能有些小伙伴会说：这很简单的啦，把原来的冒泡排序代码复制一份，修改其中的比较逻辑就行啦！
哈哈，小伙伴的回答简单粗暴没毛病，但是呢会导致重复代码冗余，违背了 DRY（Don't Repeat Yourself）原则。
为解决这个问题，我们可以引入 仿函数（Functor） 来实现比较逻辑的抽象，避免硬编码比较规则，从而提升代码的灵活性和可维护性。
代码案例：使用仿函数使冒泡排序同时实现升序和降序排序
#include<iostream>
using namespace std;
template<class T>
class Less {
public:
bool operator()(const T& x, const T& y) const {
return x < y;
}
};
template<class T>
class Greater {
public:
bool operator()(const T& x, const T& y) const {
return x > y;
}
};
template<class Compare>
void BubbleSort(int* a, int n, Compare com){
for(int i = 1; i <= n - 1; i++){
for(int j = 1; j <= n - i; j++){
if(com(a[j], a[j - 1])){
swap(a[j - 1], a[j]);
}
}
}
}
int main(){
Less<int> lessFunc;
Greater<int> greaterFunc;
int a[] = {9, 1, 2, 8, 5, 7, 4, 6, 3};
int n = sizeof(a)/sizeof(a[0]);
BubbleSort(a, n, lessFunc);
BubbleSort(a, n, greaterFunc);
return 0;
}
二、容器适配器
1. 什么是容器适配器？
容器适配器（Container Adapter）：是 C++ 标准库中的一种特殊容器，它不直接提供完整的数据存储功能，而是通过封装其他底层容器（如：vector、deque、list）并限制其接口，来实现特定的数据结构。这种设计遵循适配器模式，将已有容器的功能转换为用户期望的接口。
核心特点：
- 封装底层容器：适配器内部维护一个底层容器对象（如：
deque），所有操作都委托给该容器执行 - 限制接口：适配器仅暴露特定的接口（如：栈的
push/pop/top），隐藏底层容器的其他功能，确保数据结构的语义正确性 - 可配置底层容器：用户可通过模板参数指定底层容器类型，默认使用
deque（兼顾效率与灵活性）
2. C++ 中的三种标准容器适配器的对比差别？
| 适配器 | 默认底层容器 | 可选底层容器 | 数据结构 | 主要操作 | 典型用途 |
|---|---|---|---|---|---|
| stack | deque | vector, list | 栈 (LIFO) | push, pop, top | 函数调用栈，撤销操作 |
| queue | deque | list | 队列 (FIFO) | push, pop, front, back | 任务调度，消息队列 |
| priority_queue | vector | deque | 优先队列 | push, pop, top | 任务优先级调度，Dijkstra 算法 |
为什么 queue 的底层容器不可以是：vector？
适配器 queue：底层容器既可以是标准容器类模板（如：deque、list 等），也能是其他专门设计的容器类。但这类底层容器至少需支持以下操作：front、back、pop_front、push_back、size、empty。
在 C++ 标准库中，deque 和 list 这两种标准容器类满足上述全部要求，而容器 vector 却不满足上面的要求。因此，默认情况下，若创建 queue 时未手动指定底层容器，STL 会自动使用 deque 作为其底层容器。也可以显示指定使用 list 作为底层容器。但是不能使用 vector 作为底层容器。
为什么 priority_queue 的底层容器不可以是：list？
适配器 priority_queue：底层容器既可以是标准容器类模板（如：vector、deque 等），也可以是其他专门设计的容器类。但该容器至少需支持以下操作：支持随机访问迭代器，以便内部能通过迭代器操作维持堆结构；需实现 front()、push_back()、pop_back()、size()、empty()。
在 C++ 标准库中，vector 和 deque 这两种标准容器类满足上述全部要求，而容器 list 却不满足上面的要求。因此，默认情况下，若创建 priority_queue 时未手动指定底层容器，STL 会自动使用 vector 作为其底层容器。也可以显示指定使用 deque 作为底层容器。但是不能使用 list 作为底层容器。
为什么 priority_queue 的默认的底层容器是：vector？
既然 vector 和 deque 都可以作为 priority_queue 的底层容器，那为什么默认选择 vector 而不是 deque 呢？这主要与 priority_queue 的核心操作特性和两种容器的性能差异有关。 priority_queue 的核心操作（如：push、pop）依赖 随机访问迭代器 和 下标操作 来调整堆结构。 vector 的优势：支持连续内存存储和随机访问迭代器，通过下标 operator[] 访问元素的时间复杂度为 O(1)。 dque 的劣势：虽然也支持随机访问迭代器，但内部采用分段连续存储（缓冲区链表），迭代器的底层实现更复杂，下标访问的性能略低于 vector。
3. 使用容器适配器需要注意那些事情？
使用容器适配器时我们需要注意以下两点的内容：
- 迭代器限制：适配器不提供迭代器（例如：begin()、end()），因为其设计目的是限制访问方式（如：栈只能访问栈顶）
- 底层容器选择：根据操作频率选择容器（例如：stack 频繁 push/pop 时选 deque，需随机访问选 vector）
三、序列容器：deque（双端队列）
1. 什么是 deque？
deque（双端队列）：是 C++ 标准模板库（STL）中的一种序列式容器，全称是 double-ended queue。它允许在容器的头部和尾部高效地执行元素的插入、删除和访问操作，同时支持随机访问（通过下标访问元素）。
总结：它结合了 vector 和 list 的部分优点。
dque 的核心特点：
- 双端操作高效：可以在 O(1) 时间复杂度内从头部（front）或尾部（back）插入/删除元素
- 随机访问支持：提供随机访问迭代器（operator[] 和 at() 方法），可以像数组一样通过下标直接访问元素
- 动态扩容：无需预先指定容量，可根据元素数量动态扩展扩容时通常不会像 vector 一样整体复制元素，而是通过增加分段连续的内存块（缓冲区）来扩展
2. deque 的底层结构是什么样的？
物理存储结构
dque 的底层实现通常通过 分块数组（分段连续存储） 实现：由多个固定大小的数组块（buffer）组成，每个块存储部分元素。通过一个中央控制映射表（map）管理，记录每个缓冲区的地址和边界，保证逻辑上的连续性。 总结：这种结构使得 deque 在头部和尾部扩展时只需分配新的缓冲区，无需移动已有元素，适合需要频繁双端操作的场景。
迭代器的设计
dque 的底层并非真正的连续内存空间，而是由多个分段连续的小内存块（缓冲区）拼接而成。从逻辑上看，它类似于一个动态的二维数组，通过巧妙的设计让用户感知到'整体连续'的访问体验，但实际上每个小段内存是连续的，段与段之间通过指针连接。 为了维护这种连续空间和随机访问的假象，deque 的迭代器承担了关键角色。由于其内存结构的特殊性，deque 的迭代器需要处理跨段访问的逻辑，因此设计比 vector 的迭代器更复杂。 具体来说，迭代器需要记录：当前所在的缓冲区、缓冲区中的位置、以及指向下一个/上一个缓冲区的指针，从而在遍历或随机访问时能够正确跳转至目标位置。 简单来说：deque 通过分段连续存储 + 复杂迭代器的组合，实现了双端高效操作与随机访问的平衡，尽管底层物理空间不连续，但逻辑上呈现为一个连续的队列。
3. deque 的优势是什么？
| 特性 | vector | deque |
|---|---|---|
| 内存连续性 | 连续存储 | 分段连续存储（非连续） |
| 随机访问性能 | 高（缓存利用率好） | 稍低（跨缓冲区时需指针跳转） |
| 头部操作效率 | O(n)（需移动所有元素） | O(1) |
| 扩容策略 | 按需翻倍（整体复制） | 新增缓冲区（局部扩展） |
| 适用场景 | 随机访问多、尾部操作多 | 双端操作多、长度频繁变化 |
dque 的优势在于：
- 与 vector 相比：头部操作高效：在头部插入或删除元素时，无需像 vector 那样搬移后续所有元素，时间复杂度为 O(1)，效率显著更高。扩容代价低：扩容时，无需像 vector 那样整体复制大量元素，只需新增或释放分段连续的小内存块（缓冲区），避免了大规模数据移动，尤其适合频繁动态扩展的场景。
- 与 list 相比：deque 的底层采用分段连续空间（而非链表结构），空间利用率更高，且无需为每个元素存储额外的指针字段。
4. deque 的致命缺陷是什么？
dque 存在一个致命缺陷：不适合频繁遍历。由于其底层是分段连续的内存块，遍历时迭代器需要频繁检测是否到达当前缓冲区的边界，并跳转至下一段缓冲区，这会导致额外的性能开销，遍历效率低于 vector 和 list。 在需要线性遍历的场景中，deque 的这一特性可能成为瓶颈，因此实际开发中，当需要线性数据结构时，开发者通常优先选择 vector（适合随机访问和尾部操作）或 list（适合双向遍历和中间插入/删除），而 deque 的应用场景相对较少，目前，deque 的典型应用是作为 STL 中 stack（栈）和 queue（队列）的底层数据结构，充分利用其双端操作高效的特性，同时规避了频繁遍历的需求。
5. 为什么 STL 选择 deque 作为 stack 和 queue 的底层默认容器？
stack（栈）：是一种后进先出（LIFO）的线性数据结构。因此只要具备 push_back() 和 pop_back() 操作的线性容器，都可以作为其底层容器。例如：vector 和 list。 queue（队列）：是一种先进先出（FIFO）的线性数据结构。只需支持 push_back() 和 pop_front() 操作的容器即可作为底层容器。例如：list。 但在 STL 中，stack 和 queue 默认选择 deque 作为底层容器，主要原因如下：
- 操作场景匹配：stack 和 queue 不需要遍历元素（因此标准库中它们不提供迭代器），仅需在固定一端或两端进行操作。如：栈的栈顶、队列的队头和队尾。deque 的双端操作效率为 O(1)，且无需遍历，完美契合这种场景。deque 的主要缺陷是遍历效率低（因迭代器需处理跨缓冲区跳转），但 stack 和 queue 完全不涉及遍历操作，因此能完美避开这一缺陷，充分发挥其双端操作和动态扩容的优势。
- 性能与内存优势：对于 stack，元素增长时，deque 的扩容无需像 vector 那样整体搬移数据，只需新增分段连续的内存块（缓冲区），效率更高。对于 queue，元素增长时，deque 既能在尾部高效插入（push_back），又能在头部高效删除（pop_front），且分段存储的内存利用率高于 list（无需为每个元素存储指针）。 综上：deque 的特性与 stack、queue 的操作需求高度契合，成为 STL 选择其作为默认底层容器的核心原因。