空白诗007

这个屌丝很懒，什么也没留下！

热门标签

【十八】【C++】deque双端队列简单使用和deque底层实现探究（部分代码）_c++ 双端队列dqueue

作者：空白诗007 | 2024-08-13 13:50:32

踩

c++ 双端队列dqueue

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()，一个辅助函数来处理跨缓冲区移除头部元素的情况。

结尾

最后，感谢您阅读我的文章，希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点，请随时在评论区留言。

同时，不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中，我将继续探讨这个话题的不同方面，为您呈现更多深度和见解。

谢谢您的支持，期待与您在下一篇文章中再次相遇！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/空白诗007/article/detail/975221

【十八】【C++】deque双端队列简单使用和deque底层实现探究（部分代码）_c++ 双端队列dqueue

deque简单使用

deque底层实现探究（部分代码）

__deque_buf_size函数（deque中单个缓冲区(buffer)可以容纳的元素数量）

__deque_iterator 迭代器

迭代器模版定义

成员变量

构造函数

引用操作符*和成员访问操作符->

迭代器相减操作

迭代器移动

迭代器+=n个位置操作

迭代器+、-=、-符号重载

迭代器[]符号重载

迭代器==、!=、<符号重载

set_node函数

deque类（部分代码）

成员变量

deque的begin、end、rbegin、rend

deque[]

deque的front、back

deque的size()、max_size()、empty()

deque的头插尾插头删尾删

结尾

`__deque_buf_size`函数（deque中单个缓冲区(buffer)可以容纳的元素数量）

`__deque_iterator` 迭代器

引用操作符`*`和成员访问操作符`->`