C++ STL deque容器底層實現原理（深度剖析）

事實上，STL 中每個容器的特性，和它底層的實現機制密切相關，deque 自然也不例外。《C++ STL deque容器》一節中提到，deque 容器擅長在序列的頭部和尾部新增或刪除元素。本節將介紹 deque 容器的底層實現機制，探究其擁有此特點的原因。

想搞清楚 deque 容器的實現機制，需要先了解 deque 容器的儲存結構以及 deque 容器迭代器的實現原理。

deque容器的儲存結構

和 vector 容器採用連續的線性空間不同，deque 容器儲存資料的空間是由一段一段等長的連續空間構成，各段空間之間並不一定是連續的，可以位於在記憶體的不同區域。

為了管理這些連續空間，deque 容器用陣列（陣列名假設為 map）儲存著各個連續空間的首地址。也就是說，map 陣列中儲存的都是指標，指向那些真正用來儲存資料的各個連續空間（如圖 1 所示）。

---