核心数据结构与内存布局

在 C++ 标准库中，std::deque（双端队列）的设计核心在于其"分段连续"的内存模型。与 std::vector 的单一连续内存块不同，deque 通过一个中央控制数组（Map）来管理多个固定大小的数据块（Block）。这种设计使其在两端进行插入和删除操作时，无需像 vector 那样进行大规模的数据搬迁。

为了清晰展示其底层逻辑，以下对 MSVC 实现中的核心状态管理结构进行了重构与简化。真正的数据生命周期与内存布局由一个核心状态类来维护：

template <typename T>
struct DequeCoreState {
    static constexpr size_t kElementBytes = sizeof(T);
    
    // 动态计算数据块大小，确保每个块约 16 字节，且块容量必须为 2 的幂
    static constexpr int kBlockSize = (kElementBytes <= 1) ? 16 :
                                      (kElementBytes <= 2) ? 8  :
                                      (kElementBytes <= 4) ? 4  :
                                      (kElementBytes <= 8) ? 2  : 1;

    T** map_array;       // 中央控制数组，存储指向各个数据块的指针
    size_t map_capacity; // 控制数组的容量，必须严格保持为 2 的幂
    size_t start_offset; // 首个元素的全局逻辑偏移量
    size_t total_size;   // 当前容器内的元素总数

    // 通过全局偏移量计算对应的数据块索引，利用位运算优化取模操作
    size_t GetBlockIndex(size_t global_offset) const noexcept {
        return (global_offset / kBlockSize) & (map_capacity - 1);
    }
};

上述结构中，kBlockSize 根据元素类型的大小动态决定，以平衡内存碎片与分配开销。map_capacity 被强制要求为 2 的幂，这是为了在 GetBlockIndex 中能够使用高效的位与运算（&）来实现环形缓冲的索引回绕。

前端插入与指针回绕机制

在双端队列的头部插入元素（如 push_front）是 deque 的核心优势之一。其核心逻辑在于递减 start_offset，并在到达边界时触发控制数组的扩容或指针回绕。

template <typename... Args>
void PushFront(Args&&... args) {
    InvalidateIterators(); // 触发迭代器失效机制

    // 评估是否需要扩展中央控制数组
    if (start_offset % kBlockSize == 0 && 
        map_capacity <= (total_size + kBlockSize) / kBlockSize) {
        GrowMap(1);
    }

    // 限制全局偏移量在有效范围内，防止溢出
    start_offset &= (map_capacity * kBlockSize - 1);
    
    // 计算新的全局偏移量，若到达 0 则回绕到逻辑末尾
    size_t new_offset = (start_offset == 0) ? (map_capacity * kBlockSize) : start_offset;
    --new_offset;

    size_t block_idx = GetBlockIndex(new_offset);
    
    // 惰性分配：仅在指针为空时分配实际的数据块内存
    if (map_array[block_idx] == nullptr) {
        map_array[block_idx] = AllocateBlock(kBlockSize);
    }

    // 计算块内局部索引并构造对象
    size_t local_idx = new_offset % kBlockSize;
    ConstructObject(&map_array[block_idx][local_idx], std::forward<Args>(args)...);

    start_offset = new_offset;
    ++total_size;
}

在此过程中，start_offset 的递减操作使得新元素被放置在逻辑上的"最前端"。当 start_offset 减至 0 时，下一次插入会将其回绕至 map_capacity * kBlockSize 的末尾位置，从而实现空间的高效复用。

控制数组（Map）的动态扩容

当现有的控制数组无法容纳更多的数据块指针时，必须触发 GrowMap 操作。与 vector 的简单倍增不同，deque 的 Map 扩容需要处理复杂的指针重排，以维持 start_offset 的逻辑正确性。

void GrowMap(size_t min_additional_blocks) {
    size_t new_capacity = (map_capacity > 0) ? map_capacity : 1;
    
    // 确保新容量是 2 的幂，且满足最小扩容阈值
    while (new_capacity - map_capacity < min_additional_blocks || 
           new_capacity < kMinimumMapSize) {
        if (new_capacity > max_size() / 2) throw std::length_error("Deque too large");
        new_capacity *= 2;
    }

    size_t actual_growth = new_capacity - map_capacity;
    size_t start_block_idx = start_offset / kBlockSize;

    // 分配新的控制数组
    T** new_map = AllocateMapArray(new_capacity);
    T** dest_ptr = new_map + start_block_idx;

    // 拷贝旧数组中从起始块到末尾的有效指针
    dest_ptr = std::uninitialized_copy(map_array + start_block_idx, 
                                       map_array + map_capacity, dest_ptr);

    // 处理旧数组前半部分的拷贝及新数组空白区域的初始化
    if (start_block_idx <= actual_growth) {
        dest_ptr = std::uninitialized_copy(map_array, map_array + start_block_idx, dest_ptr);
        std::uninitialized_value_construct_n(dest_ptr, actual_growth - start_block_idx);
        std::uninitialized_value_construct_n(new_map, start_block_idx);
    } else {
        std::uninitialized_copy(map_array, map_array + actual_growth, dest_ptr);
        dest_ptr = std::uninitialized_copy(map_array + actual_growth, 
                                           map_array + start_block_idx, new_map);
        std::uninitialized_value_construct_n(dest_ptr, actual_growth);
    }

    // 销毁并释放旧的控制数组
    DestroyAndDeallocateMap(map_array, map_capacity);

    map_array = new_map;
    map_capacity = new_capacity;
}

该扩容算法的核心在于将旧数组中的有效指针"居中"或"偏移"放置到新数组中，同时使用 std::uninitialized_value_construct_n 将新增的空白槽位初始化为空指针。这种设计保证了扩容后，原有的 start_offset 依然能够正确映射到对应的数据块。

尾部插入逻辑

尾部插入（push_back）的逻辑与前端插入高度对称，主要区别在于偏移量的递增方向以及对控制数组扩容条件的评估。

template <typename... Args>
void PushBack(Args&&... args) {
    // 当尾部插入触及块边界，且剩余块容量不足时，触发扩容
    if ((start_offset + total_size) % kBlockSize == 0 && 
        map_capacity <= (total_size + kBlockSize) / kBlockSize) {
        GrowMap(1);
    }

    start_offset &= (map_capacity * kBlockSize - 1);
    size_t new_offset = start_offset + total_size;
    size_t block_idx = GetBlockIndex(new_offset);

    // 按需分配数据块
    if (map_array[block_idx] == nullptr) {
        map_array[block_idx] = AllocateBlock(kBlockSize);
    }

    size_t local_idx = new_offset % kBlockSize;
    ConstructObject(&map_array[block_idx][local_idx], std::forward<Args>(args)...);

    ++total_size;
}

通过计算 start_offset + total_size，系统能够精确定位尾部元素的全局偏移量。结合位运算与取模操作，元素被准确路由到目标数据块的特定槽位中，完成了双端队列在尾端的O(1)复杂度扩展。