deque容器 双端队列 (deque容器的特点)
本文目录导航：
deque容器（双端队列）
双端队列(deque)是一种允许在两端进行插入和删除操作的数据结构。
与通常只允许在尾部进行操作的队列不同，deque可以对头部和尾部进行操作，更像双端数组。
相较于vector，deque内部通过维护缓冲区和中控器来管理数据。
中控器负责存储每段缓冲区的地址，使得操作就像是在连续的内存空间中进行，但实际上数据可能不连续存放。
这使得deque的访问速度稍慢于vector，因为一旦访问完一段缓冲区，需要通过地址切换到下一个缓冲区。
deque的迭代器支持随机访问，这意味着可以使用迭代器直接访问容器中的任意位置。
构造函数方面，可以通过多种方式创建deque容器，包括初始化列表、复制现有容器等。
在进行赋值操作时，deque能够接收其他容器、数组或迭代器等作为源，实现数据的复制。
deque的大小操作与vector不同，它不提供capacity()函数，因为deque的内部容量没有硬性限制，可以动态增加新的缓冲区。
这意味着deque可以无限制地扩展，只要中控器的地址足够管理。
插入和删除操作在deque中非常灵活，可以指定具体位置进行操作，但要求操作的参数必须是迭代器。
deque的数据存取与vector、string等容器的使用方法相同，可以通过下标或迭代器进行访问、修改。
对于支持随机访问的deque，可以利用sort算法直接对其进行排序，无需额外转换。
C++后台开发面试：STL六大组件
容器类是容纳、包含一组元素或元素集合的对象，包含七种基本容器：向量（vector）、双端队列（deque）、列表（list）、集合（set）、多重集合（multiset）、映射（map）和多重映射（multimap）。
列表（list）是一种双向链表，它支持在任何位置插入、删除元素。
向量（vector）是一种动态数组，提供随机访问和插入操作。
双端队列（deque）在两端插入和删除元素，提供高效操作。
关联式容器使用红黑树作为底层数据结构，支持快速查找、插入和删除操作。
红黑树具有五大特性：节点颜色为红色或黑色、根节点为黑色、每个叶子节点（NIL节点）为黑色、每个红色节点的两个子节点均为黑色、从任一节点到其每个叶子节点的所有简单路径上包含相同数目的黑色节点。
迭代器（Iterator）允许我们遍历容器中的元素，只支持顺序容器和关联容器。
算法（Algorithm）处理容器内元素，如搜索、排序、修改等，与迭代器配合，实现通用性。
适配器（Adapter）将不同接口的容器转换成统一的迭代器接口。
函数对象（Function object）实现仿函数行为，用于算法的自定义逻辑。
分配器（Allocator）负责内存配置与管理。
STL默认使用两级分配器实现内存管理，当申请内存大小大于128字节时，使用malloc/free分配，小于128字节时，从预先分配的内存池中获取内存，减少内存碎片。
内存池策略优化内存分配效率，减少内存碎片生成，适用于小对象快速分配。
以上内容整理自相关博客和公开课，提供C++后台开发面试中关于STL六大组件的基础知识与应用。
如何最简单、通俗地理解c++的deque容器?
deque，即双端队列，是一种特殊的容器，采用多段地址连续的存储空间实现，便于高效地在两端插入和删除元素。
deque的迭代器为random access类型，其内部实现包含四部分：cur、ptr、base、node。
迭代器进行增减操作时，会自动跳转到下一个或上一个node，操作效率高。
内部数据结构封装在_Deque_impl_data中，它采用map形式存储数据，并且通过继承的方式避免引入内存消耗。
_Deque_base类中有一个_Deque_impl成员，用于管理node和map的内存分配与释放。
其中，_M_allocate_node和_M_deallocate_node用于分配和释放单个node的内存，_M_create_nodes和_M_destroy_nodes用于申请或释放多个node的内存，而_M_allocate_map和_M_deallocate_map用于管理map的内存分配。
std::deque类主要关注几个关键成员函数：push_back/front、pop_back/front、insert。
push_back和push_front分别用于在末尾或开头插入元素，操作时会考虑预留空间情况，如需扩展内存，则调用相应的函数实现。
pop_back和pop_front则相对简单，主要负责释放元素占用的node内存，而不涉及map的收缩。
insert函数支持在任意位置插入元素，处理逻辑较为复杂，包括插入单个元素、多个相同值、区间元素等不同情况。
对于插入单个元素或多个相同值，函数会移动元素腾出空间，然后插入新元素；对于插入迭代器指向的区间元素，需要区分迭代器类型，调用相应的处理函数。
总体而言，deque通过巧妙的数据结构设计和高效的内存管理策略，实现了对元素的高效操作。
phper