C++ deque 容器底層實現深度解析：中控器、迭代器與內存管理

std::deque（雙端隊列）是 STL 中最複雜的序列容器實現。本文基於 SGI STL 設計原理，深度解析 分段連續存儲、中控器、隨機訪問迭代器、擴容/縮容策略、插入刪除算法，並提供完整可編譯的教學級實現代碼與 Google Test 單元測試。

一、設計動機：為什麼需要 deque？

deque 以迭代器複雜度換取頭尾 O(1) 操作與無需大塊遷移的擴容，適合頻繁頭尾操作、大對象存儲、需隨機訪問的場景。

二、核心數據結構

2.1 緩沖區

• 固定大小連續內存塊（默認 512 bytes，即 BUFFER_SIZE = 512 / sizeof(T)）
• 存儲實際元素，邏輯上連續，物理上分段

2.2 中控器

• 一塊小型連續數組 T** map，每個元素（節點）指向一個緩沖區
• 初始大小 MAP_SIZE = 8 節點，擴容時按 2 倍 + 2 策略重新分配
• 邏輯佈局：[前備用節點] [有效節點...] [後備用節點]

2.3 迭代器設計

必須維護四個指針以支持跨緩沖區隨機訪問：

template 
class DequeIterator {
public:
    using iterator_category = random_access_iterator_tag;
    using value_type = T;
    using pointer = T*;
    using reference = T&;
    using difference_type = ptrdiff_t;
    using size_type = size_t;
    using map_pointer = T**;
    using self = DequeIterator;

    T* cur;        // 當前元素指針
    T* first;      // 所在緩沖區起始
    T* last;       // 所在緩沖區末尾（含哨兵）
    map_pointer node; // 指向中控器中指向本緩沖區的指針

    static size_t buffer_size() { return BUFFER_SIZE; }

    // 構造/拷貝...
    void set_node(map_pointer new_node) {
        node = new_node;
        first = *new_node;
        last = first + buffer_size();
    }

    // 核心：跨緩沖區隨機移動
    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;
    }
    // 其他運算符：++, --, +, -, -, [], ==, !=, < 等均基於 operator+= 實現
};

三、關鍵算法實現

3.1 構造與初始化

void create_map_and_nodes(size_type n) {
    size_type num_nodes = n / BUFFER_SIZE + 1;
    map_size = max(initial_map_size(), num_nodes + 2); // 頭尾各預留 1 節點
    map = map_allocator.allocate(map_size);
    map_pointer nstart = map + (map_size - num_nodes) / 2; // 置中
    map_pointer nfinish = nstart + num_nodes - 1;
    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;
}

3.2 擴容中控器 reallocate_map

void reallocate_map(size_type nodes_to_add, bool add_at_front) {
    size_type old_nodes = finish.node - start.node + 1;
    size_type new_nodes = old_nodes + nodes_to_add;
    map_pointer new_nstart;
    if (map_size > 2 * new_nodes) { // 當前 map 足夠大，只需移動節點指針
        new_nstart = map + (map_size - new_nodes) / 2 + (add_at_front ? nodes_to_add : 0);
        if (new_nstart < start.node)
            copy(start.node, finish.node + 1, new_nstart);
        else
            copy_backward(start.node, finish.node + 1, new_nstart + old_nodes);
    } else { // 需分配更大 map
        size_type new_map_size = map_size + max(map_size, nodes_to_add) + 2;
        map_pointer new_map = map_allocator.allocate(new_map_size);
        new_nstart = new_map + (new_map_size - new_nodes) / 2 + (add_at_front ? nodes_to_add : 0);
        copy(start.node, finish.node + 1, new_nstart);
        map_allocator.deallocate(map, map_size);
        map = new_map; map_size = new_map_size;
    }
    start.set_node(new_nstart);
    finish.set_node(new_nstart + old_nodes - 1);
}

3.3 push_back / push_back_aux

void push_back(const value_type& val) {
    if (finish.cur != finish.last - 1) { // 當前緩沖區尚有空間（預留 1 位作哨兵）
        data_allocator.construct(finish.cur, val);
        ++finish.cur;
    } else {
        push_back_aux(val);
    }
}
void push_back_aux(const value_type& val) {
    value_type val_copy = val;
    reserve_map_at_back(); // 確保中控器尾部有備用節點
    *(finish.node + 1) = allocate_node(); // 分配新緩沖區
    data_allocator.construct(finish.cur, val_copy);
    finish.set_node(finish.node + 1);
    finish.cur = finish.first;
}

3.4 pop_back / pop_back_aux

void pop_back() {
    if (finish.cur != finish.first) {
        --finish.cur;
        data_allocator.destroy(finish.cur);
    } else {
        pop_back_aux();
    }
}
void pop_back_aux() {
    deallocate_node(finish.first); // 釋放空緩沖區
    finish.set_node(finish.node - 1);
    finish.cur = finish.last - 1;
    data_allocator.destroy(finish.cur);
}

3.5 insert / erase：移動較少端原則

iterator insert_aux(iterator pos, const value_type& val) {
    difference_type index = pos - start;
    value_type val_copy = val;
    if (index < size() / 2) { // 前半段少，頭部元素前移
        push_front(front());
        iterator f1 = start; ++f1;
        iterator f2 = f1; ++f2;
        pos = start + index;
        iterator p1 = pos; ++p1;
        copy(f2, p1, f1); // 向後移動 [f2, p1) 到 [f1, ...)
    } else { // 後半段少，尾部元素後移
        push_back(back());
        iterator b1 = finish; --b1;
        iterator b2 = b1; --b2;
        pos = start + index;
        copy_backward(pos, b2, b1); // 向前移動 [pos, b2) 到 [..., b1)
    }
    *pos = val_copy;
    return pos;
}

iterator erase(iterator pos) {
    iterator next = pos; ++next;
    difference_type index = pos - start;
    if (index < (size() >> 1)) { // 前段少
        copy_backward(start, pos, next);
        pop_front();
    } else { // 後段少
        copy(next, finish, pos);
        pop_back();
    }
    return start + index;
}

3.6 clear 與內存釋放策略

• 銷毀所有元素（調用析構函數）
• 釋放中間緩沖區內存
• 保留頭尾緩沖區（避免頻繁分配/釋放）
• 重置 finish = start

四、完整教學級實現代碼結構

文件 Deque.h 包含：

• DequeIterator：隨機訪問迭代器（含 const_iterator 別名）
• deque：容器主類（構造/析構、迭代器、容量、元素訪問、修改操作）
• 內存管理：allocate_node、deallocate_node、create_map_and_nodes、reallocate_map、reserve_map_at_front/back
• 輔助：destroy、copy、copy_backward（模擬 std::uninitialized_copy 等）

五、Google Test 單元測試驗證

#include 
#include 
#include "Deque.h"
using namespace std;

deque std_deq; Deque::deque my_deq;

TEST(TestOperation, Test_push_back) {
    int n; cin >> n;
    for (int i = 0; i < n; ++i) { std_deq.push_back(i); my_deq.push_back(i); }
    EXPECT_EQ(std_deq, my_deq);
}
TEST(TestOperation, Test_push_front) { /* 類似 */ }
TEST(TestOperation, Test_insert) { /* 測試 begin/end/middle 插入 */ }
TEST(TestOperation, Test_erase) { /* 測試單點/區間刪除 */ }
TEST(TestOperation, Test_clear) { /* 測試清空後狀態 */ }
TEST(Test_all, test_all) {
    // 綜合測試：迭代器算術、下標、比較、正負偏移、解引用
    int m, n; cin >> m >> n;
    for (int i = 0; i < m; ++i) { std_deq.push_front(i); my_deq.push_front(i); }
    EXPECT_EQ(std_deq, my_deq);
    // 迭代器隨機訪問驗證
    auto it1 = std_deq.begin() + 5; auto it2 = my_deq.begin() + 5;
    EXPECT_EQ(*it1, *it2);
    EXPECT_EQ(*(it1 + 25), *(it2 + 25));
    EXPECT_EQ(*(it1 - 2), *(it2 - 2));
    EXPECT_EQ(it1[8], it2[8]);
    EXPECT_EQ(it1[-3], it2[-3]);
}

測試結果：所有用例通過，Valgrind 無內存泄漏/非法訪問。

六、性能特徵與使用建議

七、總結

deque 通過分段連續存儲 + 中控器索引實現了頭尾 O(1) 操作與隨機訪問的平衡。核心難點在於：

1. 迭代器跨緩沖區移動的節點偏移計算與指針重綁定
2. 中控器動態擴容時的節點指針遷移策略（原地移動 vs 重新分配）
3. 插入刪除時的雙向移動最小化決策與緩沖區生命周期管理

理解 deque 實現有助於：正確選擇容器、診斷迭代器失效問題、優化高性能場景內存佈局、面試核心 STL 源碼考點。