一、入門

1、deque與vector的區別

deque的迭代器包含以下信息：

• 當前緩沖區指針（current_buffer）
• 當前元素在緩沖區內的位置（current）
• 中控器的位置（map）
  每次移動迭代器時，需檢查是否跨越緩沖區邊界，必要時跳轉到下一個緩沖區

deque（雙端隊列）是C++標準庫中的序列容器，支持在頭部和尾部高效插入/刪除元素，同時允許隨機訪問。
與vector的主要區別：

• ?存儲結構：vector使用連續內存塊，而deque由多個分段緩沖區組成，邏輯連續但物理非連續
• ?操作效率：deque在頭部插入/刪除時間復雜度為O(1)，而vector頭部操作需移動所有元素，效率為O(n)
• ?內存擴展：vector擴容時需整體復制，deque僅需新增緩沖區

2、如何初始化一個deque?（int 類型為例）

deque<int> d1;                   // 默認構造
deque<int> d2(10, 5);           // 10個元素，每個為5
deque<int> d3(d2.begin(), d2.end()); // 范圍復制
deque<int> d4(d3);              // 拷貝構造

3、deque常用成員函數有哪些？

• push_front()/push_back()：頭尾插入
• pop_front()/pop_back()：頭尾刪除
• operator[]或at()：隨機訪問
• size()/empty()：容量查詢

4、deque允許隨機訪問是怎么做到的？性能怎么樣？

效率略低于vector。
?原因：deque的隨機訪問需通過中控器定位到具體緩沖區，再計算元素在緩沖區內的偏移，多了一層間接尋址；而vector直接通過連續內存的基地址+偏移量訪問，無需額外查找步驟。

a、?確定目標緩沖區：假設每個緩沖區存儲block_size個元素，則目標緩沖區在中控器中的索引為：

buffer_index = (n / block_size) + start_buffer_index;

b、確定元素在緩沖區內的偏移

element_offset = n % block_size;

c、??訪問元素

value = *(中控器[buffer_index] + element_offset);

二、進階

1、解釋deque的底層實現原理（中控器的作用）

deque底層由多個固定大小的緩沖區組成，通過“中控器”（通常是一個指針數組）管理這些緩沖區的地址。

• 中控器維護各緩沖區的起始地址，使得邏輯上呈現連續空間。
• 插入元素時，若當前緩沖區已滿，則分配新緩沖區并更新中控器，避免整體擴容

2、在中間位置插入元素時，deque和list的性能差異如何？為什么？

• list在已知迭代器位置時，中間插入/刪除時間復雜度為O(1)，僅需調整指針。
• deque的中間插入/刪除需移動元素，時間復雜度為O(n)
  ?原因：deque需保持邏輯連續性，插入點后的元素需整體移動；而list作為雙向鏈表無需移動數據

3、deque的迭代器失效場景有哪些？與vector有何不同？

在中間插入/刪除元素：可能導致后續元素的迭代器失效（需移動元素）。vector在插入/刪除元素時，所有后續迭代器均失效；而deque僅在涉及緩沖區重新分配時影響部分迭代器。

vector的所有元素存儲在單個連續內存塊中。當插入/刪除元素時：

• ?插入導致擴容：會分配更大的內存塊，將舊元素整體復制到新內存，此時所有迭代器（包括首尾指針）均失效。
• ?刪除或中間插入：后續元素需要向前或向后移動，所有指向移動元素的迭代器（包括之后的迭代器）均失效

deque由多個固定大小的緩沖區組成，通過中控器（指針數組）管理。插入/刪除時：

• ?頭尾插入不觸發緩沖區擴容：僅修改中控器的頭尾指針，其他迭代器仍有效。
• ?頭尾插入觸發緩沖區擴容：中控器可能需要擴展（例如中控器的指針數組已滿），此時所有迭代器可能失效（但實際實現會盡量避免）。
• ?中間插入/刪除：需移動元素，導致部分迭代器失效，但其他緩沖區的迭代器仍有效。

三、高階

1、在實際開發中，deque適合哪些應用場景？舉例說明

• 雙端操作頻繁的場景：如實現滑動窗口算法、任務調度隊列
• ?需要隨機訪問的隊列：例如需要快速訪問歷史記錄的撤銷/重做功能（結合push_front和隨機訪問）
• ?替代vector的中間插入場景：若僅在兩端操作，deque性能優于vector，且避免內存頻繁重分配

2、為何deque在STL的stack和queue中作為默認底層容器？

• 內存效率：deque的內存利用率高于list（無節點指針開銷）
• ?性能平衡：stack和queue僅需操作一端或兩端，deque的O(1)頭尾操作和連續內存訪問特性更合適
• ?歷史原因：vector曾作為stack默認容器，但deque的頭部擴展能力更靈活

3、?多線程環境下使用deque需要注意什么？

• ?線程安全性：C++標準庫容器本身不保證線程安全，需外部同步（如互斥鎖）。
• ?操作原子性：例如push_back()和pop_front()需加鎖，避免競爭條件

4、如何優化deque的性能？是否支持自定義內存分配器？

• 預分配緩沖區（如通過構造函數指定初始大小）。
• 避免頻繁的中間插入/刪除操作。
• ?自定義內存分配器：支持。可通過模板參數替換默認分配器，優化內存管理策略