C++ write your own STL - Deque

在 C++ STL（标准模板库）中，std::deque 是一种 双端队列（double-ended queue），它是一种支持在 序列两端高效插入和删除 的序列式容器。

一、deque 的基本概念

deque 是 “double-ended queue” 的缩写。
它类似于 std::vector，但有一个关键区别：

特性	vector	deque
随机访问	✅ O(1)	✅ O(1)
在末尾插入/删除	✅ O(1)	✅ O(1)
在开头插入/删除	❌ O(n)	✅ O(1)
连续内存	✅	❌ （分段存储）

因此：

如果你只在尾部操作，用 vector；

如果你需要频繁在两端插入或删除，用 deque。

二、deque 的底层结构

deque 并不是像 vector 一样存放在一整块连续内存中，而是：

由一系列固定大小的内存块（buffer）组成，再由一个中央的“map（指针数组）”来管理这些块。

大致结构如下：

[block1] → [block2] → [block3] → …
↑ ↑
| |
map[0] map[1] …

每个 block 存放若干元素，
这样在两端扩容时，只需分配或释放一个新的 block，而不需要像 vector 那样整体拷贝。

三、deque 的常用接口

dq.push_back(1);   // 尾插
dq.push_front(2);  // 头插
dq.pop_back();     // 尾删
dq.pop_front();    // 头删
dq.front();   // 访问第一个元素
dq.back();    // 访问最后一个元素
dq[i];        // 随机访问

四、时间复杂度总结

操作	时间复杂度
随机访问（operator[]）	O(1)
push_back / push_front	O(1) 均摊
pop_back / pop_front	O(1)
插入/删除中间元素	O(n)
查找	O(n)

五、典型应用场景

滑动窗口问题

// 维护单调队列
deque dq;

用于存储窗口中的元素索引，常见于算法题（如最大滑动窗口）。

队列实现

比如 BFS（广度优先搜索）

queue q; // 底层一般就是用 deque 实现的

需要双端插入删除的缓存结构

LRU 缓存、任务调度、模拟双端队列等。

六、注意事项

因为 deque 的存储不是连续的，
不能直接使用 &dq[0] 获得一个连续数组指针。

若需要和 C 接口交互（如 memcpy），应使用 vector。

迭代器在扩容或插入删除时可能失效（尤其是中间位置）。

deque 的 iterator

deque_iterator —— 双端块迭代器
1️⃣ 数据结构
pointer cur; // 当前元素
pointer first; // 当前块的起始位置
pointer last; // 当前块的末尾（one past）
map_pointer node; // 当前块在 map_ 中的位置

这些成员让迭代器能定位在“块 + 块内偏移”两个层面上。

// Helper function for buffer size calculation
constexpr size_t __deque_buffer_size(size_t n, size_t sz){
    return n != 0 ? n : (sz < 512 ? size_t(512 / sz) : size_t(1));
}

// ====================
// deque iterator (block-aware)
// ====================

template <typename T, typename Ref, typename Ptr>
class deque_iterator : public mystl::iterator<mystl::random_access_iterator_tag, T>{
public:
    using self = deque_iterator<T,Ref, Ptr>;
    using base_type = mystl::iterator<mystl::random_access_iterator_tag, T>;
    using value_type = typename base_type::value_type;
    using difference_type = typename base_type::difference_type;

    using pointer = Ptr;
    using reference = Ref;
    using map_pointer = T**; // pointer to current node in map

    pointer cur{nullptr};   // current element
    pointer first{nullptr}; // start of block
    pointer last{nullptr};  // end of block (one past)
    map_pointer node{nullptr}; // pointer into map

    static size_t buffer_size(){ return __deque_buffer_size(0, sizeof(T)); }

    deque_iterator() = default;
    deque_iterator(pointer c, map_pointer n) : cur(c), first(*n), last(*n + buffer_size()), node(n) {}

    void set_node(map_pointer new_node){ node = new_node; first = *new_node; last = first + buffer_size(); }

    reference operator*() const { return *cur; }
    pointer operator->() const { return 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 && static_cast<size_t>(offset) < buffer_size()) cur += n;
        else {
            difference_type bs = static_cast<difference_type>(buffer_size());
            difference_type node_offset = offset > 0 ? offset / bs : -(( -offset - 1) / bs) - 1;
            set_node(node + node_offset);
            cur = first + (offset - node_offset * bs);
        }
        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; }

    difference_type operator-(const self& rhs) const {
        return difference_type(buffer_size()) * (node - rhs.node - 1) + (cur - first) + (rhs.last - rhs.cur);
    }
    reference operator[](difference_type n) const { return *(*this + n); }

    bool operator==(const self& rhs) const { return cur == rhs.cur && node == rhs.node; }
    bool operator!=(const self& rhs) const { return !(*this == rhs); }

    bool operator<(const self& rhs) const { return (node == rhs.node) ? (cur < rhs.cur) : (node < rhs.node); }
};

dequeue具体实现：

#ifndef MY_DEQUE_H
#define MY_DEQUE_H

#include "my_allocator.h"
#include "my_iterator.h"

#include <cstddef>

namespace mystl{


template <typename T, class Alloc = MyAllocator<T>>
class MyDeque{
public:
    using value_type = T;
    using allocator_type = Alloc;
    using size_type = std::size_t;
    using reference = value_type&;
    using const_reference = const value_type&;
    using iterator = deque_iterator<T, T&, T*>;
    using const_iterator = deque_iterator<T, const T&, const T*>;

private:
    using map_pointer = T**;

    allocator_type alloc_;
    map_pointer map_{nullptr};
    size_type map_size_{0};
    iterator start_{};
    iterator finish_{};
    size_type size_{0};

    static size_t buffer_size(){ return __deque_buffer_size(0, sizeof(T)); }
    T* allocate_node(){ return alloc_.allocate(buffer_size()); }
    void deallocate_node(T* p){ alloc_.deallocate(p, buffer_size()); }

    void create_map_and_nodes(size_type n){
        size_type num_nodes = n / buffer_size() + 1;

        //那为什么要 num_nodes + 2？
        // 我们希望：
        // 除了存放当前使用的块，还要留出一定的空位，以便后续从两端扩展（push_front / push_back）；
        // 所以预留出额外的 “2” 个空指针空间（分别在前后各一个）。
        // 那 > 8 ? ... : 8 是干啥？
        // 这是最小容量限制。
        // 即便一开始元素很少（比如 1~2 个），我们也希望 map_ 至少有 8 个指针空间
        // 原因：
        // 避免频繁的 map 扩容；
        // 小 deque 初始化时也有一定扩展余地；
        // 模仿 SGI STL 的实现策略（它默认最小 map 大小是 8）。

        map_size_ = (num_nodes + 2 > 8) ? num_nodes + 2 : 8;
        map_ = new T*[map_size_];
        
        // Initialize map to nullptrs
        for (size_type i = 0; i < map_size_; ++i) {
            map_[i] = nullptr;
        }
        
        map_pointer nstart = map_ + (map_size_ - num_nodes) / 2;
        map_pointer nfinish = nstart + num_nodes - 1;
        
        // Allocate nodes
        for (map_pointer cur = nstart; cur <= nfinish; ++cur) {
            *cur = allocate_node();
        }
        
        start_.set_node(nstart);
        start_.cur = start_.first;
        finish_.set_node(nfinish);
        finish_.cur = finish_.first + (n % buffer_size());
    }

    void reallocate_map(size_type nodes_to_add, bool add_at_front){
        size_type old_num_nodes = finish_.node - start_.node + 1;
        size_type new_num_nodes = old_num_nodes + nodes_to_add;
        
        if (map_size_ >= new_num_nodes + 2){
            map_pointer new_start = map_ + (map_size_ - new_num_nodes) / 2 + (add_at_front ? nodes_to_add : 0);
        
            if (new_start != start_.node){
                if (new_start < start_.node){
                    for (size_type i = 0; i < old_num_nodes; ++i) {
                        new_start[i] = start_.node[i];
                    }
                } else {
                    for (size_type i = old_num_nodes; i > 0; --i) {
                        new_start[i - 1] = start_.node[i - 1];
                    }
                }
                start_.set_node(new_start);
                finish_.set_node(new_start + old_num_nodes - 1);
            }
            return;
        }
        
        // Allocate new larger map
        size_type new_map_size = map_size_ ? map_size_ * 2 : 8;
        while (new_map_size < new_num_nodes + 2) new_map_size *= 2;
        
        map_pointer new_map = new T*[new_map_size];
        // Initialize new map to nullptrs
        for (size_type i = 0; i < new_map_size; ++i) {
            new_map[i] = nullptr;
        }
        
        map_pointer new_start = new_map + (new_map_size - new_num_nodes) / 2 + (add_at_front ? nodes_to_add : 0);
        
        // Copy existing node pointers
        for (size_type i = 0; i < old_num_nodes; ++i) {
            new_start[i] = start_.node[i];
        }
        
        delete [] map_;
        map_ = new_map;
        map_size_ = new_map_size;
        start_.set_node(new_start);
        finish_.set_node(new_start + old_num_nodes - 1);
    }
    
    void reserve_map_at_back(size_type nodes_to_add = 1){
        if (nodes_to_add > size_type(map_ + map_size_ - 1 - finish_.node)){
            reallocate_map(nodes_to_add, false);
        }
    }
    
    void reserve_map_at_front(size_type nodes_to_add = 1){
        if (nodes_to_add > size_type(start_.node - map_)){
            reallocate_map(nodes_to_add, true);
        }
    }

public:
    MyDeque() = default;
    
    explicit MyDeque(size_type n){
        create_map_and_nodes(n);
        size_ = n;
        iterator it = start_;
        for (size_type i = 0; i < n; ++i, ++it){
            alloc_.construct(&*it);
        }
    }
    
    
    MyDeque(std::initializer_list<T> init){
        create_map_and_nodes(init.size());
        size_ = 0;
        for (const auto& v : init){
            push_back(v);
        }
    }
    
    ~MyDeque(){
        // Destroy all elements
        if (size_) {
            for (iterator it = start_; it != finish_; ++it) {
                alloc_.destroy(&*it);
            }
        }
        
        // Deallocate all blocks
        if (map_) {
            for (size_type i = 0; i < map_size_; ++i) {
                if (map_[i]) {
                    deallocate_node(map_[i]);
                }
            }
            delete [] map_;
        }
    }

    bool empty() const noexcept { return size_ == 0; }
    size_type size() const noexcept { return size_; }


    reference front() {
        if (empty()) throw std::out_of_range("deque is empty");
        return *start_;
    }

    reference back(){
        if (empty()) throw std::out_of_range("deque is empty");
        iterator tmp = finish_;
        --tmp;
        return *tmp;
    }

    const_reference front() const{
        if (empty()) throw std::out_of_range("deque is empty");
        return *start_;
    }
    const_reference back() const{
        if (empty()) throw std::out_of_range("deque is empty");
        const_iterator tmp = finish_;
        --tmp;
        return *tmp;
    }

    iterator begin() noexcept { return start_; }
    iterator end() noexcept { return finish_; }
    const_iterator begin() const noexcept { return const_iterator(start_.cur, start_.node); }
    const_iterator end() const noexcept { return const_iterator(finish_.cur, finish_.node); }

    void clear(){
        for (iterator it = start_; it != finish_; ++it) {
            alloc_.destroy(&*it);
        }
        start_.cur  = start_.first;
        finish_.set_node(start_.node);
        finish_.cur = finish_.first;
        size_ = 0;
    }
    

    void push_back(const_reference value){
        if (!map_) create_map_and_nodes(0);
        
        if (finish_.cur != finish_.last - 1){
            // Construct in-place
            alloc_.construct(finish_.cur, value);
            ++finish_.cur;
        } else {
            // Allocate new block at back
            reserve_map_at_back(1);
            *(finish_.node + 1) = allocate_node();
            alloc_.construct(finish_.cur, value);
            finish_.set_node(finish_.node + 1);
            finish_.cur = finish_.first;
        }
        ++size_;
    }
    
    void push_front(const_reference value){
        if (!map_) create_map_and_nodes(0);
        
        if (start_.cur != start_.first){
            --start_.cur;
            alloc_.construct(start_.cur, value);
        } else {
            // Allocate new block at front
            reserve_map_at_front(1);
            *(start_.node - 1) = allocate_node();
            start_.set_node(start_.node - 1);
            start_.cur = start_.last - 1;
            alloc_.construct(start_.cur, value);
        }
        ++size_;
    }
    
    void pop_back(){
        if (empty()) throw std::out_of_range("deque is empty");
        
        if (finish_.cur != finish_.first){
            --finish_.cur;
            alloc_.destroy(finish_.cur);
        } else {
            // Move to previous block
            finish_.set_node(finish_.node - 1);
            finish_.cur = finish_.last - 1;
            alloc_.destroy(finish_.cur);
        }
        --size_;
    }
    
    void pop_front(){
        if (empty()) throw std::out_of_range("deque is empty");
        
        if (start_.cur != start_.last - 1){
            alloc_.destroy(start_.cur);
            ++start_.cur;
        } else {
            alloc_.destroy(start_.cur);
            start_.set_node(start_.node + 1);
            start_.cur = start_.first;
        }
        --size_;
    }
};

} // namespace mystl

#endif // MY_DEQUE_H