目录

一、仿函数

仿函数的核心特点：

仿函数的优势

仿函数的用途

二、容器适配器

1.什么是容器适配器？

vector和deque代码性能对比

三、deque的简单介绍

deque的缺陷 

为什么选择deque作为stack和queue的底层默认容器 

---

一、仿函数

仿函数（Functor）：也称为函数对象（Function Object），是一种在 C++ 中通过类或结构体实现的可调用实体。

---

仿函数的核心特点是 重载了 operator() 运算符，使得类的对象可以像普通函数一样被调用。

仿函数是 C++ 中 “以类模拟函数” 的重要机制，这种机制结合了面向对象的封装性和函数的灵活性，在 STL和算法中有着广泛应用。

仿函数的核心特点：

1. 重载 operator()

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

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

int main() {
    Adder add;          // 创建仿函数对象
    int sum = add(3,5); // 像函数一样调用
    // sum = 8
}

仿函数的优势

1.状态保持：仿函数可以像普通类一样拥有成员变量，用于存储状态或参数，这使得它比普通函数更灵活。
2.模板兼容性：仿函数可以作为模板参数传递，提供更大的灵活性
3.内联优化：编译器更容易对仿函数进行内联优化
4.多态性：可通过继承实现更复杂的行为

仿函数的用途

1. STL算法中的比较器和谓词

• 比较器：通过仿函数指定排序规则（如：升序 / 降序）

#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());  // 使用仿函数指定降序
    // 排序结果：4 3 2 1
    return 0;
}

谓词：用于筛选元素

class IsEven 
{
public:
    bool operator()(int x) const 
    {
        return x % 2 == 0;  // 判断是否为偶数
    }
};

vector<int>::iterator it = find_if(nums.begin(), nums.end(), IsEven());

---

2. 自定义算法逻辑

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

template<class Compare>
void BubbleSort(int* a, int n, Compare com) 
{
    // 使用com(a[j], a[j - 1])进行比较，实现通用排序
    if (com(a[j], a[j - 1])) // 根据仿函数的逻辑决定是否交换
    {  
        swap(a[j-1], a[j]);
    }
}

---

3. 替代函数指针

• 相比函数指针，仿函数更安全（类型检查严格）、更灵活（可携带状态），且性能接近函数调用（编译器易优化）

二、容器适配器

1.什么是容器适配器？

容器适配器（Container Adapter）：是 C++ 标准库中的一种特殊容器，它不直接提供完整的数据存储功能，而是通过封装其他底层容器（如：vector、deque、list）并限制其接口，来实现特定的数据结构。

• 这种设计遵循适配器模式，将已有容器的功能转换为用户期望的接口。
• 它们基于现有的序列容器（如：vector、list、deque）提供特定的接口和行为，实现了不同的数据结构抽象。

---

核心特点：

1. 封装底层容器：适配器内部维护一个底层容器对象（如：deque），所有操作都委托给该容器执行
2. 限制接口：适配器仅暴露特定的接口（如：栈的 push/pop/top），隐藏底层容器的其他功能，确保数据结构的语义正确性
3. 可配置底层容器：用户可通过模板参数指定底层容器类型，默认使用 deque（兼顾效率与灵活性）

那么，这里我们就提出一个疑问，这个deque到底是何方神圣，为什么所有人的底层都是由他来封装？真的有那么厉害吗？vector不可以吗？

vector和deque代码性能对比

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;

/*===================== 性能测试：vector与deque的排序效率对比 =====================*/
//测试目的：比较vector和deque在排序操作中的性能差异
//结论：vector排序效率更高，因内存连续，CPU缓存利用率更好

void test_op1()
{
    cout << "===========性能测试：vector与deque的排序效率对比===========" << endl;
    /*----------------第一阶段：设置随机环境----------------*/
    //1.种随机数种子
    srand(unsigned int(time(0)));
    //2.设随机数据量
    const int N = 1'000'000; //测试数据量：100万

    /*----------------第二阶段：定义vector和deque容器----------------*/
    vector<int> vec; //动态数组（连续内存）
    deque<int> deq; //双端队列（非连续内存）
    
    /*----------------第三阶段：赋值vector和deque容器相同的随机数----------------*/

    for (int i = 0; i < N; ++i) 
    {
        auto e = rand() + i; 

        vec.push_back(e);
        deq.push_back(e);
    }

    /*----------------第四阶段：测试vector和deque容器排序时间----------------*/

    //1.测试vector排序时间
    int begin1 = clock(); 
    sort(vec.begin(), vec.end());   //使用STL排序算法（基于快速排序/归并排序）
    int end1 = clock(); 

    //2.测试deque排序时间
    int begin2 = clock();
    sort(deq.begin(), deq.end()); //deque迭代器为双向迭代器，排序效率低于vector
    int end2 = clock();

    /*----------------第五阶段：输出vector和deque容器排序时间----------------*/
    // 输出耗时（单位：毫秒，clock()/CLOCKS_PER_SEC=秒）
    printf("vector排序耗时:%d ms\n", end1 - begin1);
    printf("deque排序耗时:%d ms\n", end2 - begin2);
}



/*===================== 性能优化测试：deque排序的优化方案 =====================*/
//测试目的：验证将deque数据拷贝到vector后排序是否更高效
//结论：拷贝后排序+拷贝回deque的总耗时 低于 直接排序deque

void test_op2()
{
    cout << "===========性能优化测试：deque排序的优化方案===========" << endl;
    /*----------------第一阶段：设置随机环境----------------*/
    srand(unsigned int(time(0)));
    const int N = 1000000;

    /*----------------第二阶段：定义两个deque容器----------------*/
    deque<int> deq1; //原始deque
    deque<int> deq2; //用于测试优化方案的deque

    /*----------------第三阶段：赋值两个deque容器相同的随机数----------------*/
    for (int i = 0; i < N; ++i) 
    {
        auto e = rand() + i;

        deq1.push_back(e);
        deq2.push_back(e);
    }

    /*----------------第四阶段：测试两个deque容器排序时间----------------*/
    
    //1.测试直接排序deque的耗时
    int begin1 = clock();
    sort(deq1.begin(), deq1.end()); //直接排序deque（双向迭代器，非连续内存）
    int end1 = clock();

    //2.测试优化方案：拷贝到vector排序后再拷贝回deque
    int begin2 = clock();

    vector<int> v(deq2.begin(), deq2.end()); // 拷贝deque数据到vector（连续内存）
    sort(v.begin(), v.end());                // 高效排序vector
    deq2.assign(v.begin(), v.end());         // 拷贝回deque

    int end2 = clock();

    /*----------------第五阶段：输出两个deque容器的排序时间----------------*/
    printf("deque直接排序耗时:%d ms\n", end1 - begin1);
    printf("deque拷贝到vector排序后拷贝回耗时:%d ms\n", end2 - begin2);
}

int main()
{
    test_op1();
    test_op2(); 

    return 0;
}

deque从运行结果来看，的确有其一定优势，那么我们来看看deque到底是什么。

三、deque的简单介绍

deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)。

---

与vector比较，头插效率高，不需要搬移元素。

与list比较，空间利用率比较高。

但是deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，其底层结构如下图所示：

deque的底层结构

双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，落在了deque的迭代器身上。

为了维护这种连续空间和随机访问的假象，deque 的迭代器承担了关键角色。

由于其内存结构的特殊性，deque 的迭代器需要处理跨段访问的逻辑，因此设计比 vector 的迭代器更复杂。具体来说，迭代器需要记录：

• 当前所在的缓冲区
• 缓冲区中的位置
• 以及指向下一个 / 上一个缓冲区的指针

从而在遍历或随机访问时能够正确跳转至目标位置。

deque迭代器的设计

那deque是如何借助其迭代器维护其假想连续的结构呢？

如图deque通过迭代器内部维护当前块指针和边界信息，在移动时自动处理跨块跳转，使分块存储的多个连续内存区间表现出逻辑上的连续性。

// 前置++操作符示例
_Deque_iterator& operator++() {
    ++_M_cur;                // 先移动到下一个元素
    if (_M_cur == _M_last) { // 到达当前块末尾
        set_node(_M_node + 1); // 切换到下一个块
        _M_cur = _M_first;    // 从新块开始
    }
    return *this;
}

当迭代器跨越块边界时，会进行以下操作：

1. 通过_M_node找到下一个块的指针
2. 更新_M_first和_M_last到新块的边界
3. 将_M_cur指向新块的第一个元素

deque的缺陷 

与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必vector高的。
与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。

---

但是，deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。

为什么选择deque作为stack和queue的底层默认容器 

stack是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的线性结构，都可以作为stack的底层容器，比如vector和list都可以；

queue是先进先出的特殊线性数据结构，只要具有push_back和pop_front操作的线性结构，都可以作为queue的底层容器，比如list。

---

但是STL中对stack和queue默认选择deque作为其底层容器，主要是因为：
1. stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
2. 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高。结合了deque的优点，而完美的避开了其缺陷。