STL 源碼剖析筆記（四）：deque、stack、queue 容器實作詳解

本文基於 SGI STL 源碼，深入剖析雙端佇列 deque 及其衍生適配器 stack、queue 的實作細節。

deque：分段連續空間的雙端佇列

設計動機

vector 單向開口 (尾部擴充)，deque 雙向開口，頭尾皆可 O(1) 插入刪除。無 capacity 概念，動態以定長緩衝區串接。

中控器與緩衝區

map (中控器) 為指標陣列 (T**)，每項指向一塊緩衝區 (預設 512 bytes)。邏輯上呈現連續空間，物理上分段。

template 
class deque {
    typedef T* pointer;
    typedef pointer* map_pointer; // T**

    map_pointer map;       // 中控器
    size_type map_size;    // map 可容納指標數
    iterator start, finish; // 首尾迭代器
};

迭代器設計

迭代器維護四個指標：cur (當前元素)、first/last (緩衝區邊界)、node (指向 map 項)。支援隨機存取。

struct __deque_iterator {
    T* cur; T* first; T* last; map_pointer node;
    // 關鍵操作
    void SetNode(map_pointer n) {
        node = n; first = *n; last = first + buffer_size();
    }
    self& operator++() { // 前綴++
        ++cur;
        if (cur == last) { SetNode(node + 1); cur = first; }
        return *this;
    }
    self& operator--() { // 前綴--
        if (cur == first) { SetNode(node - 1); cur = last; }
        --cur; return *this;
    }
    self& operator+=(difference_type n) { // 隨機跳躍
        difference_type offset = n + (cur - first);
        if (0 <= offset && offset < buffer_size()) cur += n;
        else {
            difference_type node_offset = offset > 0 ? offset / buffer_size()
                : -difference_type((-offset - 1) / buffer_size()) - 1;
            SetNode(node + node_offset);
            cur = first + (offset - node_offset * buffer_size());
        }
        return *this;
    }
};

核心操作實作

• 建構：create_map_and_nodes 分配 map 與緩衝區，start/finish 置中，頭尾預留擴充空間
• 擴充 map：reallocate_map 分配更大 map，複製指標，重設迭代器
• push_back/push_front：緩衝區有備用空間直接構造；否則 push_back_aux 分配新緩衝區、更新 map
• pop_back/pop_front：銷毀元素、移動迭代器；緩衝區空時釋放並更新 map
• clear：銷毀所有元素，釋放頭尾外緩衝區，保留一個緩衝區回初始狀態
• erase/insert：就近端移動元素 (前半段往前移、後半段往後移)，再呼叫 pop_front/pop_back 處理多餘元素

stack：LIFO 適配器

以 deque 為預設底層容器 (可指定 vector/list)，封裝介面：

template >
class stack {
    Sequence c; // 底層容器
public:
    bool empty() const { return c.empty(); }
    size_type size() const { return c.size(); }
    reference top() { return c.back(); }
    void push(const value_type& x) { c.push_back(x); }
    void pop() { c.pop_back(); }
};

無迭代器介面，僅支援頂端操作。

queue：FIFO 適配器

同樣以 deque 為預設底層：

template >
class queue {
    Sequence c;
public:
    bool empty() const { return c.empty(); }
    size_type size() const { return c.size(); }
    reference front() { return c.front(); }
    reference back() { return c.back(); }
    void push(const value_type& x) { c.push_back(x); }
    void pop() { c.pop_front(); }
};

效能特性總結

建議：除非需要雙端操作，優先使用 vector。deque 迭代器較複雜，排序時建議先複製至 vector 再排序。