std::deque 與 std::TextPool：分段連續容器的性能優勢深度解析

引言：被低估的 STL 容器

std::deque（雙端隊列）在 C++ 開發中使用率遠低於 vector 與 list，但從綜合性能指標看，它是基於值語義容器中綜合表現最優的選擇。本文剖析其分段連續數據結構，對比 vector/list 的時空複雜度，並說明為何 std::TextPool（基於 deque 實現）同樣受益於這一設計。

數據結構：分段連續存儲

deque 內部維護一個「塊指針數組」（vector<Block*>），每塊固定大小（典型 512 元素），首尾兩塊可能部分填充，故需額外迭代器 m_first、m_last 標記邊界：

template <class _E>
class deque {
    enum { BlockSize = 512 };
    typedef _E Block[BlockSize];
    std::vector<Block*> m_storage; // 塊指針動態數組
    iterator m_first, m_last;      // 邊界迭代器
};

這種「介於數組與鏈表之間」的結構，賦予了 deque 獨特的性能特徵。

時間性能對比

空間性能對比（以存儲指針類型 _E = pointer 為例）

• vector (2倍擴容)： 平均空間復雜度 1.5N，最差近 2N（~50% 浪費）
• list： 每節點額外 2 指針，空間復雜度 3N
• deque (BlockSize=512)： 最差 N + N/256，浪費 < 0.4%

deque 的塊指針數組極小（海量數據下僅數千指針），擴容搬移成本可忽略，空間利用率極高。

獨特特性：元素地址穩定性

關鍵差異： deque 在無 insert/erase 情況下，push_back/push_front 不會導致現有元素地址失效；vector 則會因擴容搬移導致引用/指針失效。

// vector：危險
std::vector<int> vec; int& ref = vec[0]; vec.push_back(1); ref = 99; // UB!

// deque：安全
std::deque<int> dq; int& ref = dq[0]; dq.push_back(1); ref = 99; // OK

注意： 迭代器在 push_back/push_front 後仍會失效，僅元素地址（裸指針/引用）穩定。

結論與建議

• 海量數據、高頻雙端操作、需隨機訪問： 首選 deque（及基於它的 TextPool）
• 僅尾部操作、極度追求緊湊內存： vector 配合 reserve()
• 頻繁中間插刪、不需隨機訪問： list

deque 兼具數組的隨機訪問與鏈表的雙端高效，是大數據場景下的「瑞士軍刀」，值得提升使用優先級。