deque简单使用
在C++中，双端队列（Double-Ended Queue, deque）是一种具有动态大小的序列容器，允许在两端快速插入和删除元素。与std::vector相比，std::deque提供了更加灵活的数据结构，特别是在需要频繁在序列的前端进行插入或删除操作时。
双端队列在<deque>头文件中定义，是标准模板库（STL）的一部分。
基本操作
插入和删除：
在前端插入（push_front）和删除（pop_front）元素。
在尾端插入（push_back）和删除（pop_back）元素。
访问元素：
访问首元素（front）和尾元素（back）。
随机访问（通过索引访问，如deque[index]）。
容量：
检查双端队列是否为空（empty）。
获取双端队列中元素的数量（size）。
改变双端队列的大小（resize）。
迭代：
提供迭代器来遍历双端队列中的元素（正向迭代器和反向迭代器）。
#include <iostream>
#include <deque>
int main() {
std::deque<int> myDeque;
// 在尾部插入元素
myDeque.push_back(10);
myDeque.push_back(20);
// 在头部插入元素
myDeque.push_front(5);
myDeque.push_front(2);
std::cout << "Deque elements: ";
for(int elem : myDeque) {
std::cout << elem << " ";
}
std::cout << "\n";
// 访问第一个和最后一个元素
std::cout << "First element: " << myDeque.front() << "\n";
std::cout << "Last element: " << myDeque.back() << "\n";
// 删除头部和尾部元素
myDeque.pop_front();
myDeque.pop_back();
std::cout << "Deque size after pop operations: " << myDeque.size() << "\n";
return 0;
}
deque底层实现探究（部分代码）
__deque_buf_size函数（deque中单个缓冲区(buffer)可以容纳的元素数量）
inline size_t __deque_buf_size(size_t n, size_t sz) {
return n != 0 ? n : (sz < 512 ? size_t(512 / sz) : size_t(1));
}这个函数用于计算deque中单个缓冲区(buffer)可以容纳的元素数量。接受两个参数，n表示用户指定的元素数量，sz表示单个元素的大小。如果n不为0，就直接使用用户指定的数量。如果n为0，则根据元素的大小计算。如果单个元素大小小于512字节，那么一个缓冲区将分配足够的空间来存放至少512字节的元素（即512 / sz个元素），否则只存放一个元素。
__deque_iterator 迭代器
template <class T, class Ref, class Ptr, size_t BufSiz>
struct __deque_iterator {//deque迭代器
typedef __deque_iterator<T, T&, T*, BufSiz> iterator;
typedef __deque_iterator<T, const T&, const T*, BufSiz> const_iterator;
static size_t buffer_size() {
return __deque_buf_size(BufSiz, sizeof(T)); //结点的大小
}
typedef random_access_iterator_tag iterator_category;
typedef T value_type;
typedef Ptr pointer;
typedef Ref reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef T** map_pointer;//结点指针
typedef __deque_iterator self;
T* cur;
T* first;
T* last;
map_pointer node;//结点指针node
__deque_iterator(T* x, map_pointer y)
: cur(x), first(*y), last(*y + buffer_size()), node(y) {}
__deque_iterator() : cur(0), first(0), last(0), node(0) {}
__deque_iterator(const iterator& x)
: cur(x.cur), first(x.first), last(x.last), node(x.node) {}
reference operator*() const {
return *cur;
}
pointer operator->() const {
return &(operator*());
}
difference_type operator-(const self& x) const {
return difference_type(buffer_size()) * (node - x.node - 1) +
(cur - first) + (x.last - x.cur);
}
self& operator++() {
++cur;
if (cur == last) {
set_node(node + 1);
cur = first;
}
return *this;
}
self operator++(int) {
self tmp = *this;
++*this;
return tmp;
}
self& operator--() {
if (cur == first) {
set_node(node - 1);
cur = last;
}
--cur;
return *this;
}
self operator--(int) {
self tmp = *this;
--*this;
return tmp;
}
self& operator+=(difference_type n) {
difference_type offset = n + (cur - first);
if (offset >= 0 && offset < difference_type(buffer_size()))
cur += n;
else {
difference_type node_offset =
offset > 0 ? offset / difference_type(buffer_size())
: -difference_type((-offset - 1) / buffer_size()) - 1;
set_node(node + node_offset);
cur = first + (offset - node_offset * difference_type(buffer_size()));
}
return *this;
}
self operator+(difference_type n) const {
self tmp = *this;
return tmp += n;
}
self& operator-=(difference_type n) {
return *this += -n;
}
self operator-(difference_type n) const {
self tmp = *this;
return tmp -= n;
}
reference operator[](difference_type n) const {
return *(*this + n);
}
bool operator==(const self& x) const {
return cur == x.cur;
}
bool operator!=(const self& x) const {
return !(*this == x);
}
bool operator<(const self& x) const {
return (node == x.node) ? (cur < x.cur) : (node < x.node);
}
void set_node(map_pointer new_node) {
node = new_node;
first = *new_node;
last = first + difference_type(buffer_size());
}
};迭代器模版定义
template <class T, class Ref, class Ptr, size_t BufSiz>
struct __deque_iterator {//deque迭代器定义了一个模板，T是数据类型，Ref是引用类型，Ptr是指针类型，BufSiz是缓冲区大小。
定义了一个结构体__deque_iterator，作为deque的迭代器。
typedef __deque_iterator<T, T&, T*, BufSiz> iterator;
typedef __deque_iterator<T, const T&, const T*, BufSiz> const_iterator;
static size_t buffer_size() {
return __deque_buf_size(BufSiz, sizeof(T)); //结点的大小
}
typedef random_access_iterator_tag iterator_category;
typedef T value_type;
typedef Ptr pointer;
typedef Ref reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef T** map_pointer;//结点指针
typedef __deque_iterator self;typedef __deque_iterator<T, T&, T*, BufSiz>iterator; typedef __deque_iterator<T, const T&, const T*, BufSiz> const_iterator;
定义了迭代器和常量迭代器类型，分别用于修改和访问deque元素。
static size_t buffer_size() { return __deque_buf_size(BufSiz, sizeof(T)); }
定义了一个静态成员函数buffer_size，用来计算每个缓冲区的大小。
typedef random_access_iterator_tag iterator_category; typedef T value_type; typedef Ptr pointer; typedef Ref reference; typedef size_t size_type; typedef ptrdiff_t difference_type; typedef T** map_pointer;
定义了iterator_category为random_access_iterator_tag。这表示__deque_iterator是一个随机访问迭代器，支持像数组一样的快速随机访问。这个类型信息用于算法优化，让算法知道可以对这种迭代器进行随机访问。
定义了value_type为模板参数T，即迭代器指向的元素类型。这告诉我们迭代器遍历的容器中存储的数据类型。
定义了pointer为模板参数Ptr，即指向元素的指针类型。这是迭代器内部用来指向元素的指针类型。
定义了reference为模板参数Ref，即元素的引用类型。这允许迭代器通过解引用操作符返回元素的引用。
定义了size_type为size_t，这是一个无符号整数类型，用来表示大小或者数量。
定义了difference_type为ptrdiff_t，这是一个有符号整数类型，用来表示两个迭代器之间的距离。它能够表示正数也能表示负数，用于计算两个迭代器之间的位置差距。
定义了map_pointer为指向指针的指针，即T**，这里的map_pointer用于指向控制结构中的一块内存，这块内存本身又存储了指向容器中某一块缓冲区的指针。在deque的实现中，这样的结构用于支持动态的缓冲区扩展和收缩，允许deque高效地在前端或后端添加或删除元素。T*表示元素的指针，可以理解为数组，T**表示数组的指针，也就是数组的数组。
typedef __deque_iterator self;
定义了一个类型别名self，表示迭代器自身的类型。
成员变量
T* cur;
T* first;
T* last;
map_pointer node;//结点指针node定义了四个成员变量：cur是当前元素的指针，first是当前缓冲区第一个元素的指针，last是当前缓冲区最后一个元素之后的指针，node是指向当前缓冲区的指针。
构造函数
__deque_iterator(T* x, map_pointer y)
: cur(x), first(*y), last(*y + buffer_size()), node(y) {}
__deque_iterator() : cur(0), first(0), last(0), node(0) {}
__deque_iterator(const iterator& x)
: cur(x.cur), first(x.first), last(x.last), node(x.node) {}__deque_iterator(T* x, map_pointer y) : cur(x), first(*y), last(*y + buffer_size()), node(y) {}
这是一个参数化构造函数，接收两个参数：x和y。x是一个指向元素的指针，y是一个指向指针的指针，即map_pointer，指向deque的一个缓冲区。构造函数使用这些参数初始化迭代器的内部状态：
cur初始化为x，表示当前迭代器指向的元素。
first通过解引用y获得，表示当前缓冲区的第一个元素的位置。
last也是通过解引用y并加上缓冲区大小（通过buffer_size()计算得到）来确定当前缓冲区最后一个元素的下一个位置。
node初始化为y，表示指向当前缓冲区的指针。
__deque_iterator() : cur(0), first(0), last(0), node(0) {}
这是一个无参数构造函数，用于创建一个未指向任何元素的迭代器。所有内部指针，包括cur、first、last和node，都被初始化为nullptr（即0），表示这是一个“空”迭代器。
__deque_iterator(const iterator& x) : cur(x.cur), first(x.first), last(x.last), node(x.node) {}
这是一个拷贝构造函数，用于创建一个新的迭代器，其状态是基于另一个同类型迭代器x的。这个构造函数简单地将x迭代器的内部状态（cur、first、last和node）复制到新创建的迭代器中，使得两个迭代器指向相同的元素和缓冲区。
引用操作符*和成员访问操作符->
reference operator*() const {
return *cur;
}
pointer operator->() const {
return &(operator*());
}这个成员函数重载了解引用操作符*，使得可以通过迭代器直接访问其当前指向的元素。cur是一个指针，指向迭代器当前所指的元素。通过返回*cur，即返回当前元素的引用，允许我们读取或修改该元素。const关键字表示这个操作不会修改迭代器本身的状态。
这个成员函数重载了成员访问操作符->，使得可以通过迭代器访问其当前指向元素的成员。这里，它通过调用operator*()来获取当前元素的引用，然后返回这个元素的地址，从而允许通过->操作符来访问元素的成员。例如，如果迭代器指向的元素是一个结构体或类的实例，那么可以直接使用迭代器加->来访问该元素的成员函数或成员变量。const关键字同样表示这个操作不改变迭代器本身的状态。
迭代器相减操作
difference_type operator-(const self& x) const {
return difference_type(buffer_size()) * (node - x.node - 1) +
(cur - first) + (x.last - x.cur);
}这段代码重载了减法操作符-，用于计算两个__deque_iterator迭代器之间的距离。这个操作符返回两个迭代器之间的元素数量差，其类型为difference_type，通常是ptrdiff_t，一个用于表示指针（或迭代器）间距离的整数类型。
difference_type(buffer_size()) * (node - x.node - 1)：这部分计算了this迭代器和x迭代器之间跨越的完整缓冲区数量乘以每个缓冲区的大小。node - x.node - 1计算了两个迭代器间完整缓冲区的数量（不包括this和x所在的缓冲区）。
(cur - first)：这部分计算了this迭代器在其当前缓冲区中的位置，即this迭代器当前指向的元素与当前缓冲区第一个元素之间的距离。
(x.last - x.cur)：这部分计算了x迭代器在其所在缓冲区到缓冲区末尾的元素数量，实际上是计算x迭代器到其缓冲区结束位置的距离。
迭代器移动
self& operator++() {
++cur;
if (cur == last) {
set_node(node + 1);
cur = first;
}
return *this;
}
self operator++(int) {
self tmp = *this;
++*this;
return tmp;
}
self& operator--() {
if (cur == first) {
set_node(node - 1);
cur = last;
}
--cur;
return *this;
}
self operator--(int) {
self tmp = *this;
--*this;
return tmp;
}这四个成员函数重载了前置和后置的自增（++）和自减（--）操作符，使得__deque_iterator可以向前或向后移动，这是迭代器的基本功能之一，允许遍历deque容器中的元素。
前置自增操作符++
self& operator++() { ++cur; if (cur == last) { set_node(node + 1); cur = first; } return *this; }
++cur;首先将当前元素指针（cur）向前移动一个位置。
if (cur == last)检查cur是否已经到达当前缓冲区的末尾（注意last指向当前缓冲区最后一个元素之后的位置）。
如果是，set_node(node + 1);将迭代器移动到下一个缓冲区，同时cur更新为新缓冲区的第一个元素的位置（first）。
返回*this，即更新后的迭代器本身。
后置自增操作符++(int)
self operator++(int) { self tmp = *this; ++*this; return tmp; }
创建当前迭代器的副本tmp。
使用前置自增++*this;更新当前迭代器。
返回副本tmp，符合后置自增操作的语义，即返回增加前的值。
前置自减操作符--
self& operator--() { if (cur == first) { set_node(node - 1); cur = last; } --cur; return *this; }
if (cur == first)检查cur是否已经是当前缓冲区的第一个元素。
如果是，则set_node(node - 1);将迭代器移动到前一个缓冲区，同时cur更新为该缓冲区的最后一个元素的位置（注意这里cur赋值为last，实际上应该是赋值为last - 1，因为last指向的是缓冲区末尾的下一个位置）。
--cur;然后将当前元素指针向后移动一个位置。
返回*this，即更新后的迭代器本身。
后置自减操作符--(int)
self operator--(int) { self tmp = *this; --*this; return tmp; }
创建当前迭代器的副本tmp。
使用前置自减--*this;更新当前迭代器。
返回副本tmp，符合后置自减操作的语义，即返回减少前的值。
迭代器+=n个位置操作
self& operator+=(difference_type n) {
difference_type offset = n + (cur - first);
if (offset >= 0 && offset < difference_type(buffer_size()))
cur += n;
else {
difference_type node_offset =
offset > 0 ? offset / difference_type(buffer_size())
: -difference_type((-offset - 1) / buffer_size()) - 1;
set_node(node + node_offset);
cur = first + (offset - node_offset * difference_type(buffer_size()));
}
return *this;
}这段代码重载了+=操作符，使得__deque_iterator迭代器可以在当前位置的基础上向前（或向后，如果n为负数）移动n个位置。这是随机访问迭代器的一个重要特性，允许迭代器进行非连续的跳跃式移动。
self& operator+=(difference_type n) {
这行定义了operator+=的函数签名，接收一个difference_type类型的参数n，表示要移动的元素数量，可以是正数也可以是负数。函数返回迭代器自身的引用，允许链式调用。
difference_type offset = n + (cur - first);
计算offset，即从当前缓冲区的开始位置first到目标位置的总偏移量。如果n为正，表示向后移动；如果n为负，表示向前移动。
if (offset >= 0 && offset < difference_type(buffer_size())) cur += n;
如果计算出的offset在当前缓冲区的范围内（即大于等于0且小于缓冲区的大小），直接调整当前元素指针cur即可达到目标位置。
else { difference_type node_offset = offset > 0 ? offset / difference_type(buffer_size()) : -difference_type((-offset - 1) / buffer_size()) - 1;
如果offset超出了当前缓冲区的范围，需要跨越一个或多个缓冲区。node_offset计算需要移动多少个缓冲区，正数表示向后跨越，负数表示向前跨越。
set_node(node + node_offset);
调用set_node函数，根据计算出的node_offset移动到新的缓冲区。
cur = first + (offset - node_offset * difference_type(buffer_size()));
在新的缓冲区中，计算cur的正确位置。offset - node_offset * difference_type(buffer_size())计算在最终缓冲区中的偏移量。
return *this; }
返回迭代器自身的引用，支持链式操作。
迭代器+、-=、-符号重载
self operator+(difference_type n) const {
self tmp = *this;
return tmp += n;
}
self& operator-=(difference_type n) {
return *this += -n;
}
self operator-(difference_type n) const {
self tmp = *this;
return tmp -= n;
}self operator+(difference_type n) const：
创建当前迭代器的一个副本tmp。
使用之前定义的operator+=在tmp上加上n个位置。
返回修改后的副本tmp。这个操作不会改变原始迭代器的状态，因为它是在副本上进行的。
self& operator-=(difference_type n)：
利用已经定义的operator+=实现减法操作，通过向+=传递-n作为参数。
这意味着-=操作实质上是将迭代器向后（或向前，如果n为负数）移动n个位置。
返回当前迭代器的引用，允许链式操作。
self operator-(difference_type n) const：
与加法操作符类似，首先创建当前迭代器的一个副本tmp。
使用operator-=在tmp上减去n个位置。
返回修改后的副本tmp。这个操作也是不会改变原始迭代器的状态，因为它是在副本上进行的。
迭代器[]符号重载
reference operator[](difference_type n) const {
return *(*this + n);
}这段代码重载了下标操作符[]，使得__deque_iterator可以通过下标访问的方式直接访问到相对于当前迭代器位置n个元素的位置处的元素。
*this + n首先使用之前定义的加法操作符+来创建一个新的迭代器，这个新迭代器位于当前迭代器之后（或之前，如果n为负数）n个位置。
*操作符随后被用于这个新的迭代器，通过解引用操作返回位于该位置的元素的引用。
因此，operator[]允许通过类似数组的语法直接访问deque中的元素，即使deque的物理存储可能是非连续的。
迭代器==、!=、<符号重载
bool operator==(const self& x) const {
return cur == x.cur;
}
bool operator!=(const self& x) const {
return !(*this == x);
}
bool operator<(const self& x) const {
return (node == x.node) ? (cur < x.cur) : (node < x.node);
}bool operator==(const self& x) const：
比较两个迭代器是否相等。如果两个迭代器指向deque中相同的元素（即它们的cur成员，也就是当前元素的指针，相同），则认为这两个迭代器相等，返回true；否则返回false。
这里没有比较node，因为如果两个迭代器的cur相同，则它们必定在同一个缓冲区中，即node也相同。
bool operator!=(const self& x) const：
通过调用已经定义的等于操作符==来判断两个迭代器是否不相等。如果*this == x返回false，则表示两个迭代器不指向同一个元素，因此这里返回true表明它们不相等；反之亦然。
这是等于操作符的直接逻辑反转。
bool operator<(const self& x) const：
用于比较两个迭代器的顺序。首先判断两个迭代器是否位于同一个缓冲区（即它们的node相同）；如果是，那么通过比较它们的cur来判断顺序。
如果不在同一个缓冲区，那么通过比较它们的node来判断哪个迭代器指向的元素在deque中的位置更前。
这允许对迭代器进行排序，从而可以在算法中使用迭代器来比较元素位置，如在二分查找或其他需要元素顺序信息的算法中。
set_node函数
void set_node(map_pointer new_node) {
node = new_node;
first = *new_node;
last = first + difference_type(buffer_size());
}这个成员函数set_node是__deque_iterator结构体中的一个辅助函数，用于设置迭代器以指向新的缓冲区。当迭代器需要跨越到另一个缓冲区时，这个函数被调用来更新迭代器的状态，确保它正确地指向新的缓冲区内的元素。
new_node是一个指向新缓冲区的指针的指针（map_pointer类型），也就是deque的控制结构中的一个节点。
更新node成员变量为新缓冲区的指针，node现在指向新的缓冲区。
通过解引用new_node获取新缓冲区的首地址，然后将这个地址赋值给first。first现在指向新缓冲区中的第一个元素。
计算新缓冲区的最后一个元素的下一个位置，并将这个位置的指针赋值给last。这里使用buffer_size()函数来获取缓冲区的大小（即可以存储的元素数量），然后将这个大小加到first上，从而得到last的位置。这里的buffer_size()函数返回的是根据deque的元素类型和可能的用户指定的缓冲区大小参数BufSiz计算出的缓冲区大小。
deque类（部分代码）
成员变量
iterator start;
iterator finish;
map_pointer map;
size_type map_size;iterator start;
start是一个迭代器，指向deque中的第一个缓冲区位置。这个迭代器使得可以从deque的前端开始访问元素。
iterator finish;
finish是一个迭代器，指向deque中最后一个缓冲区位置。这个设计是为了提供一种统一的方式来表示容器的末尾，类似于C++标准库中其他容器的end迭代器。
map_pointer map;
map是一个指向指针数组的指针，这个指针数组中的每个指针都指向deque的一个缓冲区。deque的实现通常涉及多个这样的缓冲区，每个缓冲区存储容器的一部分元素，而map则管理这些缓冲区的指针，从而允许随机访问deque中的任意元素。
size_type map_size;
map_size表示map指针数组的大小，也就是当前deque可以使用的缓冲区数量。这个数值反映了deque的容量在空间布局上的一个方面，即它能够管理多少个缓冲区。
deque的begin、end、rbegin、rend
iterator begin() {
return start;
}
iterator end() {
return finish;
}
const_iterator begin() const {
return start;
}
const_iterator end() const {
return finish;
}
reverse_iterator rbegin() {
return reverse_iterator(finish);
}
reverse_iterator rend() {
return reverse_iterator(start);
}
const_reverse_iterator rbegin() const {
return const_reverse_iterator(finish);
}
const_reverse_iterator rend() const {
return const_reverse_iterator(start);
}deque[]
reference operator[](size_type n) {
return start[difference_type(n)];
}
const_reference operator[](size_type n) const {
return start[difference_type(n)];
}start是第一个缓冲区的位置，对这个缓冲区的cur副本进行+=n个位置操作，而原cur不会改变，计算出来的第n个位置作为返回值。
deque的front、back
reference front() {
return *start;
}
reference back() {
iterator tmp = finish;
--tmp;
return *tmp;
}
const_reference front() const {
return *start;
}
const_reference back() const {
const_iterator tmp = finish;
--tmp;
return *tmp;
}deque的size()、max_size()、empty()
size_type size() const {
return finish - start;;
}
bool empty() const {
return finish == start;
}deque的头插尾插头删尾删
void push_back(const value_type& t) {
if (finish.cur != finish.last - 1) {
construct(finish.cur, t);
++finish.cur;
} else
push_back_aux(t);
}
void push_front(const value_type& t) {
if (start.cur != start.first) {
construct(start.cur - 1, t);
--start.cur;
} else
push_front_aux(t);
}
void pop_back() {
if (finish.cur != finish.first) {
--finish.cur;
destroy(finish.cur);
} else
pop_back_aux();
}
void pop_front() {
if (start.cur != start.last - 1) {
destroy(start.cur);
++start.cur;
} else
pop_front_aux();
}
push_back函数
当尾部当前缓冲区(finish.cur)没有达到其最后一个元素的位置(finish.last - 1)时，直接在尾部当前位置构造新元素t并将finish.cur向后移动一个位置，以指向新的末尾。
如果尾部当前缓冲区已满（finish.cur == finish.last - 1），则调用push_back_aux(t)，一个辅助函数来处理在新的缓冲区中添加元素的情况。
push_front函数
当头部当前缓冲区(start.cur)不在其第一个元素的位置时（即有空间在当前缓冲区的前面插入新元素），在start.cur前一个位置构造新元素t并将start.cur向前移动一个位置。
如果头部当前缓冲区没有空间（start.cur == start.first），则调用push_front_aux(t)，一个辅助函数来处理在新的缓冲区中添加元素的情况。
pop_back函数
当尾部当前缓冲区(finish.cur)不在其第一个元素的位置时（即尾部缓冲区中有至少两个元素可以移除），将finish.cur向前移动一个位置并销毁该位置上的元素。
如果尾部当前缓冲区只有一个元素时（finish.cur == finish.first），则调用pop_back_aux()，一个辅助函数来处理跨缓冲区移除尾部元素的情况。
pop_front函数
当头部当前缓冲区(start.cur)不在其最后一个元素的位置时（即头部缓冲区中有至少两个元素可以移除），销毁start.cur位置上的元素并将start.cur向后移动一个位置。
如果头部当前缓冲区只有一个元素时（start.cur == start.last - 1），则调用pop_front_aux()，一个辅助函数来处理跨缓冲区移除头部元素的情况。
结尾
最后，感谢您阅读我的文章，希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点，请随时在评论区留言。
同时，不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中，我将继续探讨这个话题的不同方面，为您呈现更多深度和见解。
谢谢您的支持，期待与您在下一篇文章中再次相遇！
