C++ STL 容器适配器 stack、queue、priority_queue 详解与实现

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（优先级队列）本质是堆结构，需要根据元素的优先级来调整堆的顺序。对于自定义类型，编译器无法默认判断元素的大小关系因此必须通过 运算符重载 或 自定义比较器 告诉编译器如何比较元素的优先级。

常见场景：

1. 使用默认比较器（大顶堆）：需求希望自定义类型的对象形成大顶堆（优先级高的元素为'较大'的对象）。实现：重载 < 运算符，定义'当前对象小于另一个对象'的逻辑。
2. 显式指定小顶堆（或自定义比较逻辑）：需求希望自定义类型的对象形成小顶堆（优先级高的元素为'较小'的对象），或使用其他比较规则（如：按属性倒序）。实现：重载 > 运算符，并搭配 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 和算法中有着广泛应用。

仿函数的核心特点：

1. 重载 operator()
2. 可携带状态：仿函数可以像普通类一样拥有成员变量，用于存储状态或参数，这使得它比普通函数更灵活。

使用时：

Add add;
int result = add(3, 5);

通过在类中定义 operator() 运算符，使得该类的对象可以像函数一样被调用：

class Add {
public:
    int operator()(int a, int b) {
        return a + b;
    }
};

2. 仿函数有什么用途？

1. STL 算法中的比较器和谓词
2. 自定义算法逻辑
3. 替代函数指针：相比函数指针，仿函数更安全（类型检查严格）、更灵活（可携带状态），且性能接近函数调用（编译器易优化）

在自定义算法中，通过仿函数将逻辑抽象出来，提高代码复用性。

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. 仿函数与普通函数的区别有哪些？

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++ 中的三种标准容器适配器的对比差别？

为什么 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 的核心特点：

1. 双端操作高效：可以在 O(1) 时间复杂度内从头部（front）或尾部（back）插入/删除元素
2. 随机访问支持：提供随机访问迭代器（operator[] 和 at() 方法），可以像数组一样通过下标直接访问元素
3. 动态扩容：无需预先指定容量，可根据元素数量动态扩展扩容时通常不会像 vector 一样整体复制元素，而是通过增加分段连续的内存块（缓冲区）来扩展

2. deque 的底层结构是什么样的？

物理存储结构

dque 的底层实现通常通过 分块数组（分段连续存储） 实现：由多个固定大小的数组块（buffer）组成，每个块存储部分元素。通过一个中央控制映射表（map）管理，记录每个缓冲区的地址和边界，保证逻辑上的连续性。 总结：这种结构使得 deque 在头部和尾部扩展时只需分配新的缓冲区，无需移动已有元素，适合需要频繁双端操作的场景。

迭代器的设计

dque 的底层并非真正的连续内存空间，而是由多个分段连续的小内存块（缓冲区）拼接而成。从逻辑上看，它类似于一个动态的二维数组，通过巧妙的设计让用户感知到'整体连续'的访问体验，但实际上每个小段内存是连续的，段与段之间通过指针连接。 为了维护这种连续空间和随机访问的假象，deque 的迭代器承担了关键角色。由于其内存结构的特殊性，deque 的迭代器需要处理跨段访问的逻辑，因此设计比 vector 的迭代器更复杂。 具体来说，迭代器需要记录：当前所在的缓冲区、缓冲区中的位置、以及指向下一个/上一个缓冲区的指针，从而在遍历或随机访问时能够正确跳转至目标位置。 简单来说：deque 通过分段连续存储 + 复杂迭代器的组合，实现了双端高效操作与随机访问的平衡，尽管底层物理空间不连续，但逻辑上呈现为一个连续的队列。

3. deque 的优势是什么？

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 作为底层容器，主要原因如下：

1. 操作场景匹配：stack 和 queue 不需要遍历元素（因此标准库中它们不提供迭代器），仅需在固定一端或两端进行操作。如：栈的栈顶、队列的队头和队尾。deque 的双端操作效率为 O(1)，且无需遍历，完美契合这种场景。deque 的主要缺陷是遍历效率低（因迭代器需处理跨缓冲区跳转），但 stack 和 queue 完全不涉及遍历操作，因此能完美避开这一缺陷，充分发挥其双端操作和动态扩容的优势。
2. 性能与内存优势：对于 stack，元素增长时，deque 的扩容无需像 vector 那样整体搬移数据，只需新增分段连续的内存块（缓冲区），效率更高。对于 queue，元素增长时，deque 既能在尾部高效插入（push_back），又能在头部高效删除（pop_front），且分段存储的内存利用率高于 list（无需为每个元素存储指针）。 综上：deque 的特性与 stack、queue 的操作需求高度契合，成为 STL 选择其作为默认底层容器的核心原因。