1.大體對比

在軟件開發的漫長歷程中，數據結構與算法始終占據著核心地位，猶如大廈的基石，穩固支撐著整個程序的運行。在眾多編程語言中，數據的存儲與管理方式各有千秋，而 C++ 憑借其豐富且強大的工具集脫穎而出，尤其是在處理序列數據方面，C++ 標準模板庫（STL）中的序列容器?vector、list?和?deque?更是展現出卓越的性能與高度的靈活性。

和一些編程語言中單一的數據存儲方式相比，C++ 這三種序列容器的存在，無疑為開發者提供了更多樣化的選擇。例如，在 Python 中，主要通過列表（list）來存儲序列數據，其本質上是一種動態數組，但在處理大規模數據的隨機訪問和頻繁插入刪除操作時，性能表現往往不盡如人意。反觀 C++ 的?vector，它與傳統數組有相似之處，卻具備了自動調整大小的功能，這一特性讓其在面對數據量動態變化的場景時，能夠輕松應對，極大地提升了開發效率。

再將目光投向鏈表結構。在 Java 語言中，雖然沒有像 C++?list?這樣直接對應的雙向鏈表容器，但開發者可以通過自定義類和節點來構建鏈表結構。然而，這種方式不僅實現起來較為繁瑣，而且在進行常見的元素操作，如插入和刪除時，其效率遠不及 C++ 的?list。C++ 的?list?作為雙向鏈表，每個節點都包含指向前一個節點和后一個節點的指針，這種數據結構使得在任意位置進行插入和刪除操作的時間復雜度都保持在常數級別，在需要頻繁修改序列數據的場景中，它的優勢便得以充分彰顯。

deque?則是 C++ 序列容器中的一顆獨特 “新星”，它巧妙地融合了?vector?和?list?的部分優勢。和 Java 中的雙端隊列（ArrayDeque）相比，C++ 的?deque?不僅在兩端進行元素的插入和刪除操作時具有高效性，而且在支持隨機訪問方面也毫不遜色。這意味著，在既需要快速在兩端增減元素，又要對序列中的元素進行隨機訪問的復雜場景下，deque?能夠提供更為平衡和高效的解決方案。

正是基于這些顯著的特性差異，深入了解 C++ 的?vector、list?和?deque?這三種序列容器，對于每一位追求卓越編程質量的開發者而言，都顯得尤為重要。接下來，讓我們撥開迷霧，詳細剖析這三種序列容器的獨特之處，探尋它們在不同編程場景下的最佳應用方式

?2.數據結構

1.vector(連續)

?2.list（指針）

3.deque

3.成員函數

這個三個人的成員函數是一樣

3.1 創建

vector()：默認構造函數，創建一個空的 vector。
vector(size_type n, const T& value = T())：創建一個包含 n 個值為 value 的元素的 vector。
vector(const vector& other)：拷貝構造函數，創建一個 other 的副本。
vector(InputIterator first, InputIterator last)：使用迭代器 first 到 last 范圍內的元素初始化list()：默認構造函數，創建一個空的 vector。
list(size_type n, const T& value = T())：創建一個包含 n 個值為 value 的元素的 vector。
list(const vector& other)：拷貝構造函數，創建一個 other 的副本。
list(InputIterator first, InputIterator last)：使用迭代器 first 到 last 范圍內的元素初始化 deque()：默認構造函數，創建一個空的 vector。
deque(size_type n, const T& value = T())：創建一個包含 n 個值為 value 的元素的 vector。
deque(const vector& other)：拷貝構造函數，創建一個 other 的副本。
deque(InputIterator first, InputIterator last)：使用迭代器 first 到 last 范圍內的元素初始化 

?3.2 訪問

back()//返回隊列尾部元素的引用。
front()//返回隊列頭部元素的引用。
clear()//清空隊列中的所有元素。
empty()//判斷隊列是否為空。
size()//返回隊列中元素的個數。
begin()//返回頭位置的迭代器
end()//返回尾+1位置的迭代器//vector沒有
rbegin()//返回逆頭位置的迭代器 
rend()//返回逆尾-1位置的迭代器 //list沒有
下標訪問 []

?3.3刪除

pop_back()//刪除隊列尾部的元素。
pop_front()//刪除隊列頭部的元素
erase(iterator pos)：移除 pos 位置的元素。
erase(iterator first, iterator last)：移除 first 到 last 范圍內的元素。
clear()：移除 vector 中的所有元素

3.4插入

push_back(const T& value)
push_front(const T& value)
insert(iterator pos, const T& value)

?4.實現隊列和棧

?棧：一種先進后出的數據結構

隊列：一種先進先出的數據結構

用vector實現棧：

#include<vector>
#include<string>
using namespace std;template<class T> class stack {
private:std::vector<T> data;
public://創建stack();stack(const stack& other):data(other.data){};stack& operator=(const stack& other){data=other.data;return *this;}stack(int n, T val):data(n,val){}//訪問int size()const {return data.size();}bool empty()const{if(data.size()==0)return true;elsereturn false;}T top() const{if(data.empty()==true)throw string("stack is empty");elsereturn data.back();}//插入void push(T val){data.push_back(val);}//刪除void pop(){if(data.empty()==true)throw string("stack is empty");else{data.pop_back();}}~stack();};

5.總結

對比維度	std::vector	std::list	std::deque
底層結構	動態數組，在內存中分配連續的存儲空間。當容量不足時，通常會重新分配更大的內存塊，將原數據復制過去并釋放舊內存。	雙向鏈表，由一系列節點構成，每個節點包含數據、指向前一個節點的指針和指向后一個節點的指針。	由多個固定大小的數組塊組成，每個數組塊內部連續存儲，數組塊之間通過指針連接，形成雙端隊列結構。
訪問操作	- 支持隨機訪問，可通過下標直接訪問元素，時間復雜度為?\(O(1)\)。 - 訪問元素非常高效，就像操作普通數組一樣。	- 不支持隨機訪問，若要訪問特定位置元素，需從頭或尾開始遍歷鏈表，時間復雜度為 (O(n))。 - 只能順序訪問元素。	- 支持隨機訪問，通過下標訪問元素的時間復雜度為(O(1))。 - 雖然能隨機訪問，但由于是分段連續存儲，在效率上可能略低于?vector。
插入操作	?在尾部插入元素效率高，平均時間復雜度為 (O(1))，但若觸發內存重新分配，時間復雜度為 (O(n))。?在中間或頭部插入元素，需要移動插入位置之后的所有元素，時間復雜度為 (O(n))。	- 在任意位置插入元素的時間復雜度均為 (O(1))，只需修改相鄰節點的指針。 - 插入操作非常靈活，效率高。	- 在頭部和尾部插入元素效率高，時間復雜度為 (O(1))。 - 在中間插入元素，需要移動部分元素，時間復雜度為 (O(n))，但通常比?vector?移動元素的開銷小。
刪除操作	- 在尾部刪除元素效率高，時間復雜度為(O(1))。 - 在中間或頭部刪除元素，需要移動刪除位置之后的所有元素，時間復雜度為 (O(n))。	?在任意位置刪除元素的時間復雜度均為 (O(1))，只需修改相鄰節點的指針。	- 在頭部和尾部刪除元素效率高，時間復雜度為?\(O(1)\)。 - 在中間刪除元素，需要移動部分元素，時間復雜度為?\(O(n)\)，但通常比?vector?移動元素的開銷小。
空間利用	- 由于是連續存儲，可能會有內存碎片問題。當容量不足重新分配內存時，可能會預留一定的額外空間，造成空間浪費。 - 不過，它的空間利用率相對較高，因為沒有額外的指針開銷。	每個節點都需要額外的指針來指向前一個和后一個節點，增加了內存開銷。 - 但鏈表節點在內存中可以不連續存儲，不會因為預留空間而造成浪費。	- 由于需要維護多個數組塊以及塊之間的連接信息，會有一定的額外開銷。 - 不過，它在動態擴展時不需要像?vector?那樣重新分配并復制大量數據，空間管理相對靈活。
迭代器	-隨機訪問迭代器，支持?++、--、+、-?等操作，可以像指針一樣靈活地在容器中移動。	- 雙向迭代器，支持?++?和?--?操作，能雙向遍歷鏈表，但不支持隨機訪問。	- 隨機訪問迭代器，與?vector?的迭代器類似，支持高效的隨機訪問操作。
迭代器失效情況	- 當發生插入或刪除操作導致內存重新分配時，所有迭代器、指針和引用都會失效。 - 在插入或刪除元素后，插入或刪除位置之后的迭代器、指針和引用會失效。	- 插入操作不會使任何迭代器、指針和引用失效。 - 刪除操作只會使指向被刪除節點的迭代器、指針和引用失效。	在頭部或尾部插入元素時，迭代器一般不會失效，但指向元素的引用和指針可能會失效。 - 在中間插入或刪除元素時，插入或刪除位置之后的迭代器、指針和引用會失效。
使用場景	?適合需要頻繁隨機訪問元素，且插入和刪除操作主要在尾部進行的場景，如存儲一組數據并經常通過下標訪問。 - 實現棧、隊列等數據結構時，若操作主要集中在尾部，vector?是不錯的選擇。	- 適合需要頻繁在任意位置進行插入和刪除操作，而對隨機訪問需求較少的場景，如實現鏈表類的數據結構。 - 當需要頻繁進行元素的移動、插入和刪除，且不需要隨機訪問元素時，list?更合適。	- 適合需要在頭部和尾部頻繁進行插入和刪除操作，同時也需要隨機訪問元素的場景，如實現雙端隊列。 - 當數據量較大，且需要在兩端進行高效操作時，deque?是一個較好的選擇。