【C++】容器适配器全知道

在 C++ 的 STL 中，容器适配器是一种特殊的组件，它基于已有的容器类型，通过封装和重新定义接口，提供了一种新的、具有特定行为的数据结构😏。例如，我们可以将一个顺序容器（如vector、list等）转换为一个具有栈（stack）行为或者队列（queue）行为的容器，这就是容器适配器的神奇之处👏。

三、STL 标准库中堆栈和队列的底层结构

（一）堆栈（`stack`）的底层结构

默认底层容器
在 STL 中，stack适配器默认使用deque作为其底层容器😎。当然，我们也可以根据实际需求选择其他合适的顺序容器，如vector或list，但deque是最常用的选择✨。
为什么选择deque作为默认底层容器
deque（双端队列）具有一些非常适合作为堆栈底层容器的特性🧐。它允许在两端快速插入和删除元素，这与堆栈的后进先出（LIFO）特性非常契合😃。而且，deque在内存管理上相对灵活，能够在一定程度上避免vector在频繁插入和删除元素时可能出现的内存重新分配问题，同时又不像list那样在随机访问元素时性能较差👏。

（二）队列（`queue`）的底层结构

默认底层容器
queue适配器默认也是基于deque来实现的😎。同样，我们也可以根据具体情况选择其他容器，但deque在大多数情况下能够提供较好的性能和功能平衡✨。
deque对于队列操作的优势
对于队列的先进先出（FIFO）操作，deque能够高效地在一端进行元素的插入（入队），在另一端进行元素的删除（出队）😉。其内存管理方式使得队列在处理大量元素的入队和出队操作时，能够保持较好的性能表现，不会因为频繁的内存操作而导致效率下降🧐。

四、`deque`的简单介绍（了解）

（一）`deque`的概念

deque（双端队列）是一种动态数组，它允许在两端快速插入和删除元素，同时也支持随机访问元素😎。与普通的vector相比，deque在内存管理上更加灵活，它可以在两端动态地分配和释放内存，而不是像vector那样在内存不足时需要整体重新分配内存，这使得deque在一些特定场景下具有更好的性能表现✨。

（二）`deque`的基本操作

以下是一些deque的基本操作示例代码，帮助我们更好地理解它的功能😉。首先，包含必要的头文件并使用using namespace std;来简化代码中的命名空间限定。

#include <iostream> #include <deque> using namespace std; int main() { // 创建一个空的deque deque<int> d; // 在尾部插入元素 d.push_back(1); d.push_back(2); d.push_back(3); // 在头部插入元素 d.push_front(0); // 访问deque中的元素 cout << "deque中的元素为: "; for (auto it = d.begin(); it!= d.end(); ++it) { cout << *it << " "; } cout << endl; // 删除头部元素 d.pop_front(); // 删除尾部元素 d.pop_back(); // 再次访问deque中的元素 cout << "删除元素后的deque: "; for (auto it = d.begin(); it!= d.end(); ++it) { cout << *it << " "; } cout << endl; return 0; }

在上述代码中，我们首先创建了一个空的deque，然后分别在头部和尾部插入了一些元素，接着遍历并输出了deque中的所有元素。之后，我们删除了头部和尾部的元素，并再次遍历输出deque，展示了deque在两端进行插入和删除操作的便利性😎。

（三）`deque`的内存管理方式

deque的内存管理方式与vector有所不同🧐。它内部通常由多个连续的内存块组成，每个内存块可以存储一定数量的元素。当在deque的两端插入元素时，如果当前内存块已满，deque会自动分配一个新的内存块，并将新元素插入到合适的位置😉。这种内存管理方式使得deque在频繁插入和删除元素时，不需要像vector那样频繁地重新分配整个内存空间，从而提高了性能👏。然而，由于deque的内存布局相对复杂，其随机访问元素的速度可能略慢于vector，但在大多数情况下，这种性能差异并不明显😎。

五、双队列（`deque`）的原理介绍

（一）`deque`的数据结构设计

deque的数据结构设计旨在实现高效的两端插入和删除操作，同时兼顾一定的随机访问性能😎。它通常由一个中控器（map）和多个缓冲区（buffer）组成✨。中控器用于管理各个缓冲区的地址，每个缓冲区则存储实际的数据元素😉。

（二）元素的存储与访问

当向deque中插入元素时，根据插入位置的不同（头部或尾部），deque会选择合适的缓冲区进行插入操作😏。如果当前缓冲区已满，deque会自动分配新的缓冲区，并更新中控器的信息🧐。在访问元素时，deque通过中控器找到对应的缓冲区，然后在缓冲区内进行偏移计算，以获取指定位置的元素😉。这种设计使得deque在两端操作时具有较高的效率，同时在随机访问时也能保持相对较好的性能，尽管比vector略慢一些，但在很多情况下已经足够满足需求👏。

（三）`deque`的迭代器实现

deque的迭代器是一个相对复杂但功能强大的组件😎。它需要能够遍历deque中的所有元素，无论这些元素分布在哪个缓冲区中✨。迭代器内部维护了当前元素所在缓冲区的指针、在缓冲区中的偏移量以及中控器的相关信息😉。通过这些信息，迭代器可以在遍历过程中准确地在不同缓冲区之间切换，从而实现对整个deque的遍历操作🧐。例如，当迭代器进行自增操作时，它会首先检查当前缓冲区是否还有下一个元素，如果有，则直接移动到下一个元素；如果当前缓冲区已遍历完，则通过中控器找到下一个缓冲区，并将指针指向该缓冲区的起始位置，然后继续遍历😏。

六、`deque`的缺陷

（一）内存碎片化问题

由于deque在内存管理上的灵活性，它可能会导致内存碎片化问题😔。当不断地在两端插入和删除元素时，deque会频繁地分配和释放内存块，这些小块的内存可能会散布在内存中，形成碎片化😉。在一些对内存连续性要求较高的场景下，内存碎片化可能会影响程序的性能，因为操作系统在分配连续内存块时可能会遇到困难🧐。

（二）随机访问性能相对较低

尽管deque支持随机访问元素，但与vector相比，其随机访问性能相对较低😟。这是因为deque的元素可能分布在多个不连续的缓冲区中，在进行随机访问时，需要通过中控器计算元素所在的缓冲区，然后在缓冲区内进行偏移计算，这比vector直接通过指针偏移访问元素的方式要复杂一些，从而导致了一定的性能开销😉。

（三）迭代器失效问题

deque的迭代器在某些操作后容易失效😟。例如，当在deque的中间插入或删除元素时，可能会导致部分迭代器失效，因为这些操作可能会改变缓冲区的布局和元素的存储位置😉。这就要求在使用deque的迭代器时，需要格外小心，避免在迭代器失效后继续使用，否则可能会导致程序出现未定义行为🧐。

七、`deque`为什么选择作为堆栈和队列的底层默认容器

（一）两端操作的高效性

堆栈和队列的主要操作分别是在一端进行插入和删除（堆栈在顶部，队列在一端插入，另一端删除），deque在两端的插入和删除操作效率很高，非常符合堆栈和队列的操作特性😉。对于堆栈的后进先出（LIFO）操作，deque可以快速地在顶部进行元素的压入和弹出；对于队列的先进先出（FIFO）操作，deque也能够高效地在一端入队，另一端出队，从而提供了良好的性能表现👏。

（二）内存管理的优势

deque的内存管理方式在一定程度上平衡了内存分配和性能之间的关系🧐。与vector相比，它在频繁插入和删除元素时不需要频繁地重新分配整个内存空间，避免了大规模内存复制带来的性能开销；与list相比，它在随机访问元素时虽然性能略低，但仍然具有一定的优势，并且在内存使用上相对更加紧凑😉。这种内存管理特性使得deque在作为堆栈和队列的底层容器时，能够在各种常见的操作场景下表现良好，适用于大多数情况✨。

（三）通用性和灵活性

deque具有较高的通用性和灵活性，它可以适应不同规模和操作频率的堆栈和队列需求😎。无论是处理少量元素还是大量元素，deque都能够提供相对稳定的性能表现。而且，在一些特殊情况下，如果需要对底层容器的行为进行微调，deque也提供了一定的可定制性，例如可以手动控制缓冲区的大小等，这使得它在不同的应用场景中都具有一定的优势👏。

八、STL 标准库中对于堆栈和队列的模拟实现😉

（一）堆栈的模拟实现

下面是一个简单的堆栈模拟实现代码，帮助我们理解堆栈的基本原理和操作😎。同样，先包含必要的头文件并使用using namespace std;。

#include <iostream> #include <vector> using namespace std; // 模拟堆栈类 class MyStack { private: vector<int> data; public: // 入栈操作 void push(int value) { data.push_back(value); } // 出栈操作 void pop() { if (!empty()) { data.pop_back(); } else { cerr << "堆栈为空，无法出栈！" << endl; } } // 获取栈顶元素 int top() const { if (!empty()) { return data.back(); } else { cerr << "堆栈为空，无法获取栈顶元素！" << endl; return -1; } } // 判断堆栈是否为空 bool empty() const { return data.empty(); } }; int main() { MyStack stack; stack.push(1); stack.push(2); stack.push(3); cout << "栈顶元素: " << stack.top() << endl; stack.pop(); cout << "栈顶元素: " << stack.top() << endl; return 0; }

（二）队列的模拟实现

以下是一个简单的队列模拟实现代码😎。

#include <iostream> #include <list> using namespace std; // 模拟队列类 class MyQueue { private: list<int> data; public: // 入队操作 void push(int value) { data.push_back(value); } // 出队操作 void pop() { if (!empty()) { data.pop_front(); } else { cerr << "队列为空，无法出队！" << endl; } } // 获取队首元素 int front() const { if (!empty()) { return data.front(); } else { cerr << "队列为空，无法获取队首元素！" << endl; return -1; } } // 判断队列是否为空 bool empty() const { return data.empty(); } }; int main() { MyQueue queue; queue.push(1); queue.push(2); queue.push(3); cout << "队首元素: " << queue.front() << endl; queue.pop(); cout << "队首元素: " << queue.front() << endl; return 0; }

九、总结

容器适配器在 C++ 编程中是非常重要的概念，理解它们的原理、底层结构以及模拟实现方式，有助于我们更好地运用 STL 中的堆栈和队列等数据结构，提高程序的效率和质量😃。希望通过本文的介绍，你对容器适配器有了更全面的认识和理解✨。如果在学习过程中有任何疑问或建议，欢迎随时交流分享哦😉！