本文共 2414 字，大约阅读时间需要 8 分钟。
deque 概述
deque，也叫双端队列，是一种支持高效插入和删除容器双端元素的数据结构。与向量类似，deque 允许随机访问元素，并且内部通过连续的分段版本实现，给使用者创造了连续的使用感受。其独特之处在于，它不仅支持尾部操作（如向量），还支持头部操作，因此名为双端队列。
deque 的主要特点是支持双端插入和删除操作，且其底层结构为分段连续的数组，虽然内部逻辑复杂，但使用者可以像使用向量一样方便地进行操作。
deque 的常用功能
构造函数
deque()：创建空 deque。
deque(int nSize)：创建包含 nSize 个元素的 deque。
deque(int nSize, const T& t)：创建包含 nSize 个元素且值均为 t 的 deque。
deque(const deque&)：复制构造函数。
增加函数
void push_front(const T& x)：在 deque 的头部添加一个元素 x。
void push_back(const T& x)：在 deque 的尾部添加一个元素 x。
iterator insert(iterator it, const T& x)：在 it 前的位置插入一个元素 x。
void insert(iterator it, int n, const T& x)：在 it 前的位置插入 n 个元素 x。
void insert(iterator it, const_iterator first, const_iterator last)：在 it 前的位置插入 first 到 last 之间的元素。
删除函数
iterator erase(iterator it)：删除 deque 中的某个元素。
iterator erase(iterator first, iterator last)：删除 deque 中 first 到 last 之间的元素。
void pop_front()：删除头部元素。
void pop_back()：删除尾部元素。
void clear()：清空 deque。
遍历函数
reference at(int pos)：返回 pos位置元素的引用。
reference front()：返回首元素的引用。
reference back()：返回尾元素的引用。
iterator begin()：返回向量头指针。
iterator end()：返回指向末尾元素后一个位置的指针。
reverse_iterator rbegin()：反向迭代器，指向最后一个元素。
reverse_iterator rend()：反向迭代器，指向第一个元素前一个元素。
判断函数
bool empty() const：判断 deque 是否为空。容量和大小函数
int size() const：返回元素个数。
int max_size() const：返回最大允许元素数量。
其他函数
void swap(deque&)：交换两个 deque。
void assign(int n, const T& x)：将元素的值设为 x。
deque 源码剖析
deque 内部是分段连续的，其使用者显示为连续。以下是 deque 的源码概述：
templateclass deque {public: typedef T value_type; enum { _S_Bits = ImplementationDefined }; iterator begin() { return start; } iterator end() { return finish; } size_type size() const { return finish - start; } // 其他函数};
控制中心
deque 的控制中心（map）类型设为 T**，每个指针指向一个 buffer。控制中心用于管理 deque 的线性性质。
deque 迭代器
deque 的迭代器通过模拟空间的连续性实现了线性响应：
templatestruct __deque_iterator { // 迭代器属性 iterator Category = random_access_iterator_tag; T value_type; ptr pointer; Ref reference; size_t size_type; T** map_pointer; // 以及其他成员};
插入方法
deque 的 insert 方法根据插入位置选择前迁移或后迁移策略：
iterator insert(iterator position, const value_type& x) { if (position.cur == start.cur) { push_front(x); return start; } else if (position.cur == finish.cur) { push_back(x); iterator tmp = finish; --tmp; return tmp; } else { return insert_aux(position, x); }} 这是一篇关于 deque 数据结构详细介绍，涵盖其概述、使用方法、源码剖析以及具体的实现细节。deque 被广泛应用于需要高效双端操作的场景，如系统编程和实时应用中，其性能和灵活性使其成为开发者的理想选择。
转载地址：http://scjnz.baihongyu.com/