STL容器：deque核心总结

deque属于顺序容器的一种，是一个双端队列，它允许在容器的两端进行快速插入和删除元素的操作。

deque虽然支持像vector一样样的按索引访问，但其随机访问效率不如vector。

std::deque适用于需要在首尾两端频繁进行插入和删除的场景。

deque的底层实现

deque的元素不连续存储，而是由多个固定大小的连续内存块组成，并通过一个主控map来管理。

_M_map是一个指针数组，其中每个元素（node）指向一块内存块。内存块才是deque 的储存空间主体。

deque：

map：记录每个内存块的地址。
map_size：内存块的个数。
start迭代器：记录着map数组中首个内存块的信息。
finish迭代器：记录着map数组中最后一个内存块的信息。

template<typename _Tp> class _Deque_base {
    typedef _Deque_iterator<_Tp> iterator;
protected:
    _Tp** _M_map;
    size_t _M_map_size;
    iterator _M_start;
    iterator _M_finish;
};

迭代器：

cur：指向当前迭代器所代表的元素。
first：指向当前数据块的起始位置。
last：指向当前数据块的末尾位置。
node：指向map数组中存储的指向当前数据块的位置。

template<class _Tp> struct _Deque_iterator {
    typedef _Tp** _Map_pointer;

    _Tp* _M_cur;
    _Tp* _M_first;
    _Tp* _M_last;
    _Map_pointer _M_node;
};

初始状态

初始时，_M_map成员为nullptr , _M_map_size为0。

插入元素

以尾部插入为例：

首先，deque 检查 _M_finish._M_cur 是否等于 _M_finish._M_last。如果相等，说明当前数据块已满。
如果数据块未满：新元素直接添加到 _M_finish._M_cur 指向的位置，然后将 _M_finish._M_cur 向后移动一位。
如果数据块已满：
- deque 需要移动到下一个数据块。它通过 _M_finish._M_node 指针向后移动一位，找到 _M_map 中下一个可用的指针。
- 如果 _M_map 中有空闲块，就直接使用。如果没有，deque 会分配一个新块。
- 然后，将新元素插入到新块的开头，并更新 _M_finish 迭代器的 _M_node 和 _M_cur 指针。

当_M_map满了后，会对其扩容。

头部插入与尾部插入类似，但操作的是_M_start，并且头部插入是从后往前插入。

删除元素

以尾部删除为例：

首先，将 _M_finish._M_cur 指针向前移动一位，使其指向最后一个元素。
如果 _M_finish._M_cur 现在等于 _M_finish._M_first，这意味着当前数据块中的元素已被全部删除。
在这种情况下，deque 会释放这个数据块，并将 _M_finish 迭代器的 _M_node 指针向前移动，指向 _M_map 中的前一个数据块。

随机访问

对于dq[i]：

计算 _M_start 迭代器的块内偏移

start_offset_in_block = _M_start._M_cur - _M_start._M_first
计算i相对deque开头的总偏移量

total_offset = i + start_offset_in_block
计算数据块索引

block_index = total_offset / map_size
定位数据块的指针

target_map_node = _M_start._M_node + block_index
计算块内偏移

offset_in_block = total_offset % block_size
定位元素的指针

target_element_ptr = *target_map_node + offset_in_block

deque的size

deque对象大小是固定的。

std::deque<int> dq;
std::cout << sizeof(dq) << std::endl; // 输出80

deque的构造函数

deque的构造函数和vector类似：

deque<int> v1;                                  // 无元素
deque<int> v2 {1, 2, 3, 4, 5};                  // 列表初始化
deque<int> v3(4);                               // 4个元素，初始值为0
deque<int> v4(5, 3);                            // 5个元素，初始值为3
deque<int> v5(v4);                              // 使用另外一个vector拷贝构造
deque<int> v6(std::move(v5));                   // 使用另外一个vector移动构造
deque<int> v7(arr1, arr1+5);                    // 使用指针初始化
deque<int> v8(v4.begin(), v4.end());            // 使用迭代器初始化[左闭,右开）

deque的成员函数

访问

成员函数	函数说明
`at(size_type n)`	带有边界检查，返回对索引 `n` 处元素的引用。如果索引越界，则抛出 `std::out_of_range` 异常。
`operator[](size_type n)`	返回对索引 `n` 处元素的引用。不执行边界检查，速度更快。
`front()`	返回对第一个元素的引用。
`back()`	返回对最后一个元素的引用。

修改

成员函数	说明
`assign(size_type count, const T& value)`	将 `deque` 的内容替换为 `count` 个值为 `value` 的元素。
`push_front(const T& value)`	在 `deque` 的开头添加一个新元素 `value`。
`push_back(const T& value)`	在 `deque` 的末尾添加一个新元素 `value`。
`pop_front()`	移除 `deque` 的第一个元素。
`pop_back()`	移除 `deque` 的最后一个元素。
`insert(iterator position, const T& value)`	在 `position` 前插入一个值为 `value` 的新元素。
`erase(const_iterator position)`	移除 `position` 处的元素。
`emplace_front(Args&&... args)`	在 `deque` 开头通过就地构造插入新元素。
`emplace_back(Args&&... args)`	在 `deque` 末尾通过就地构造插入新元素。
`emplace(const_iterator position, Args&&... args)`	在 `position` 处通过就地构造插入新元素。
`clear()`	移除所有元素，使 `deque` 变为空。
`resize(size_type count)`	改变 `deque` 的大小为 `count`。
`swap(deque& other)`	与另一个 `deque` 交换内容。

容量

成员函数	说明
`empty()`	如果 `deque` 中没有元素，则返回 `true`。
`size()`	返回 `deque` 中元素的数量。
`max_size()`	返回 `deque` 可以容纳的最大元素数量。和系统或库实现相关。
`shrink_to_fit()`	减少容量以适应其大小。可能会释放未使用的内存。非强制，能否达成依赖于实现。

迭代器

成员函数	说明
`begin()`	返回指向 `deque` 第一个元素的迭代器。
`end()`	返回指向 `deque` 最后一个元素之后位置的迭代器。
`rbegin()`	返回指向 `deque` 最后一个元素的反向迭代器。
`rend()`	返回指向 `deque` 第一个元素之前位置的反向迭代器。
`cbegin()`	返回指向 `deque` 第一个元素的 `const` 迭代器。
`cend()`	返回指向 `deque` 最后一个元素之后位置的 `const` 迭代器。
`crbegin()`	返回指向 `deque` 最后一个元素的 `const` 反向迭代器。
`crend()`	返回指向 `deque` 第一个元素之前位置的 `const` 逆向迭代器。

参考

deque的介绍-对其内存布局进行图解