我見過太多人把 STL 里的stack和queue當(dāng)成“裝數(shù)據(jù)的盒子”push 一下、pop 一下用起來比誰都熟?？梢坏┍粏柕健斑@倆的底層到底是什么”“讓你自己實(shí)現(xiàn)一個能不能寫出來”不少人就卡住了。原因其實(shí)很統(tǒng)一我們習(xí)慣了站在使用者的角度去看容器卻很少站到實(shí)現(xiàn)者的角度去思考它的內(nèi)存布局、邊界條件、生命周期管理。這個項目不復(fù)雜但很值得認(rèn)真做一遍——從一個空類開始手寫 stack 和 queue 的全部關(guān)鍵操作把模板、動態(tài)內(nèi)存、拷貝語義、邊界判斷這些東西一次性捋清楚。這篇文章就圍繞“從零實(shí)現(xiàn)”展開。我會先從兩個容器的設(shè)計本質(zhì)上拆解思路再分別給出 stack 和 queue 的完整實(shí)現(xiàn)代碼配合測試和避坑經(jīng)驗。不論你是準(zhǔn)備面試還是想把 STL 底層搞得更透這篇都適合你慢慢讀。1. 為什么要從零實(shí)現(xiàn) stack 和 queue1.1 先看清 STL 里的 stack/queue 到底是什么很多人對std::stack和std::queue有一個誤解認(rèn)為它們是獨(dú)立的數(shù)據(jù)結(jié)構(gòu)。實(shí)際上它們都是容器適配器container adapter。也就是說它們本身不管理內(nèi)存也不存儲數(shù)據(jù)而是通過包裝另一個容器默認(rèn)是std::deque來提供受限的接口。std::stack只讓你操作棧頂push 從頂入、pop 從頂出、top 看棧頂。std::queue只讓你操作兩端push 從隊尾入、pop 從隊頭出、front 看隊頭、back 看隊尾。你看它們把底層容器的“自由度”砍掉了——deque 能提供隨機(jī)訪問但 stack/queue 把這些能力鎖了起來只暴露出符合語義的那幾個操作。這是接口約束上的典型設(shè)計用最少的方法表達(dá)最清晰的數(shù)據(jù)結(jié)構(gòu)語義。從零實(shí)現(xiàn)的意義就在這里當(dāng)你自己動手的時候你才會意識到實(shí)現(xiàn)一個 stack 根本不需要從頭發(fā)明什么新東西——你只需要一個“能存東西、能按順序訪問”的底層結(jié)構(gòu)然后把外部接口限制起來。這個“把底層容器封裝成語義明確的適配器”的思路比單純背幾個函數(shù)名重要得多。1.2 從零實(shí)現(xiàn)能換來什么收獲我之所以推薦你親手寫一遍而不是直接打印源碼看是因為寫的過程中你會被迫回答這幾類問題內(nèi)存管理問題棧的容量不夠了怎么辦是每次 push 都擴(kuò)容還是提前預(yù)留擴(kuò)容系數(shù)取多少生命周期問題pop 之后被移除的元素它的析構(gòu)函數(shù)是否被調(diào)用了對象持有的資源有沒有真正釋放拷貝語義問題容器被拷貝時是淺拷貝還是深拷貝如果直接復(fù)制指針兩份“獨(dú)立”的容器會不會在析構(gòu)時爭搶同一塊內(nèi)存邊界條件問題空棧上調(diào)用 top 會發(fā)生什么隊列只有一個元素時 pop會不會把隊尾指針弄丟只調(diào)用現(xiàn)成 API 的人是永遠(yuǎn)不會思考這些的。但如果你要寫自己的容器這些問題一個個都會冒出來。正因如此“從零實(shí)現(xiàn) stack/queue”才是一個性價比極高的練習(xí)項目——它不大但足夠的細(xì)節(jié)密度讓你把 C 的內(nèi)存和對象模型真正串起來。2. 整體設(shè)計思路適配器語義與底層容器的取舍2.1 第一步不是寫代碼是列清楚操作清單動手之前先明確目標(biāo)。一個合格的 stack 起碼要有這些操作操作含義復(fù)雜度push(const T)入棧在棧頂插入元素O(1) 攤還pop()出棧移除棧頂元素O(1)top()返回棧頂元素的引用O(1)empty()判斷棧是否為空O(1)size()返回棧中元素個數(shù)O(1)拷貝構(gòu)造/賦值深拷貝保證容器獨(dú)立O(n)析構(gòu)釋放所有資源O(n)queue 的操作類似但把 top 拆成了 front 和 back操作含義復(fù)雜度push(const T)入隊在隊尾插入元素O(1)pop()出隊移除隊頭元素O(1)front()返回隊頭元素的引用O(1)back()返回隊尾元素的引用O(1)empty()/size()判斷空、查數(shù)量O(1)把這些接口列出來再動手后面寫代碼時會省力很多。因為你知道自己在實(shí)現(xiàn)什么而不是“寫一步看一步”。2.2 底層容器選型數(shù)組、鏈表還是分段連續(xù)stack 和 queue 的語義其實(shí)對底層結(jié)構(gòu)沒有硬性要求只要滿足兩端插入刪除的復(fù)雜度需求即可。常見的底層方案有四種底層方案入棧/入隊出棧/出隊內(nèi)存局部性擴(kuò)容代價實(shí)現(xiàn)復(fù)雜度動態(tài)數(shù)組vector 式O(1) 攤還O(1)很好拷貝舊數(shù)據(jù)中等雙向鏈表list 式O(1)O(1)差無擴(kuò)容但每節(jié)點(diǎn)有指針開銷較高環(huán)形緩沖區(qū)O(1) 攤還O(1)很好需重新排列數(shù)據(jù)高分段連續(xù)deque 式O(1) 攤還O(1)好不需要整體搬移非常高STL 默認(rèn)選擇deque核心原因是它能在兩端高效插入刪除同時內(nèi)存局部性又比鏈表好——擴(kuò)容時它不用像 vector 那樣搬移所有元素只需要新分配一段 buffer 并連接起來。這個設(shè)計精妙但實(shí)現(xiàn)起來非常復(fù)雜。從零實(shí)現(xiàn)的角度我建議分兩條路線stack 用動態(tài)數(shù)組實(shí)現(xiàn)和 vector 的內(nèi)存管理方式一致邏輯直觀擴(kuò)容時拷貝元素的機(jī)制也容易講清楚。queue 用鏈表實(shí)現(xiàn)同時我會在后面的章節(jié)額外講一下環(huán)形緩沖區(qū)的思路讓你看到第二種方案的優(yōu)缺點(diǎn)。這樣安排你既能看到“連續(xù)內(nèi)存”路徑的實(shí)現(xiàn)細(xì)節(jié)也能對比“節(jié)點(diǎn)式”結(jié)構(gòu)帶來的內(nèi)存管理差異。兩種結(jié)構(gòu)都過一遍手比只盯著一種強(qiáng)太多。2.3 模板設(shè)計從一開始就支持泛型既然是模仿 STL模板是必須的。用模板的好處很直接一份代碼能承載 int、string、自定義對象等任意類型。類定義寫成template typename T class MyStack { // ... };但這也帶來一些代價。比如某些類型沒有默認(rèn)構(gòu)造函數(shù)或者拷貝成本很高這些都會影響底層內(nèi)存管理策略的選擇。所以我會在實(shí)現(xiàn)時重點(diǎn)考慮“如何避免對 T 的額外要求”。換句話說只要 T 支持拷貝構(gòu)造和拷貝賦值我的容器就應(yīng)該能正常工作。另外一個細(xì)節(jié)成員命名。我習(xí)慣在成員變量后面加_后綴例如capacity_、size_用來區(qū)分形參和成員。這是很多 C 工程里的約定讓代碼一眼就能看出哪些是成員、哪些是局部變量。3. 從零實(shí)現(xiàn) stack完整代碼與關(guān)鍵操作拆解3.1 動態(tài)數(shù)組版 MyStack 的整體框架我用動態(tài)數(shù)組來實(shí)現(xiàn) stack。整體結(jié)構(gòu)是這樣的data_指向堆上數(shù)組的指針真正存儲元素的地方。capacity_當(dāng)前已經(jīng)分配的內(nèi)存能容納多少元素。size_棧里當(dāng)前有多少個元素。這三個成員構(gòu)成一個完整的動態(tài)數(shù)組容器。size_永遠(yuǎn)小于等于capacity_當(dāng)兩者相等時下一次 push 必須擴(kuò)容?；A(chǔ)版本如下#include iostream #include stdexcept template typename T class MyStack { private: T* data_; size_t capacity_; size_t size_; public: explicit MyStack(size_t cap 16) : data_(new T[cap]), capacity_(cap), size_(0) {} ~MyStack() { delete[] data_; } // 禁用拷貝先不后面會給出正確做法 MyStack(const MyStack) delete; MyStack operator(const MyStack) delete; void push(const T value) { if (size_ capacity_) { grow(); } data_[size_] value; } void pop() { if (empty()) { throw std::runtime_error(stack underflow: pop from empty stack); } --size_; } T top() { if (empty()) { throw std::runtime_error(stack empty: no top element); } return data_[size_ - 1]; } const T top() const { if (empty()) { throw std::runtime_error(stack empty: no top element); } return data_[size_ - 1]; } bool empty() const { return size_ 0; } size_t size() const { return size_; } private: void grow() { size_t new_capacity capacity_ * 2; T* new_data new T[new_capacity]; for (size_t i 0; i size_; i) { new_data[i] data_[i]; } delete[] data_; data_ new_data; capacity_ new_capacity; } };這段代碼把核心操作都實(shí)現(xiàn)了。注意幾個關(guān)鍵細(xì)節(jié)構(gòu)造函數(shù)里的explicit是為了避免隱式轉(zhuǎn)換。比如MyStackint s 100;這種寫法可能會誤導(dǎo)讀者加上explicit之后必須寫成MyStackint s(100);意圖更清晰。pop()只做了--size_沒有真正銷毀棧頂對象。原因很簡單我們用new T[]分配數(shù)組時所有元素從一開始就構(gòu)造好了數(shù)組不銷毀它們的生命周期就不會結(jié)束。減少size_只是把它們“遮蔽”起來后續(xù) push 時會用賦值運(yùn)算符覆蓋舊值。這種寫法對常規(guī)類型完全沒問題但嚴(yán)格意義上對象占用的資源沒有被提前釋放。我后面會給出更嚴(yán)格的實(shí)現(xiàn)。top()有 const 版本和非 const 版本。非 const 版本允許調(diào)用方修改棧頂元素const 版本用于只讀場景。這是 STL 中非常常見的雙版本模式。3.2 擴(kuò)容機(jī)制與拷貝語義的坑grow()里我選擇了capacity_ * 2也就是每次翻倍。為什么是 2 而不是別的數(shù)這里有一個攤還復(fù)雜度的經(jīng)典論證假設(shè)從 1 開始按 2 倍擴(kuò)容到 n總共會拷貝1 2 4 ... n/2 n ≈ 2n次也就是說push n 個元素的總拷貝量是 O(n)平均到每次 push 是 O(1)。如果按固定大小擴(kuò)容比如每次加 16那總拷貝量會變成 O(n2)平均成本就不是 O(1) 了。但拷貝構(gòu)造和賦值運(yùn)算符被我禁用 delete這意味著?？梢员粍?chuàng)建、使用、銷毀但不能被拷貝。這在功能上是不完整的。為什么我要先禁用因為如果直接使用默認(rèn)的拷貝行為data_指針會被逐字節(jié)復(fù)制兩個 MyStack 對象會指向同一塊內(nèi)存析構(gòu)時就會發(fā)生double free——同一塊內(nèi)存被釋放兩次程序直接崩潰。正確的做法是深拷貝?？截悩?gòu)造需要分配新內(nèi)存逐一復(fù)制元素賦值運(yùn)算符需要先處理“自賦值”和“異常安全”的問題。一個常見的寫法是copy-and-swap 慣用法#include algorithm template typename T class MyStack { private: T* data_; size_t capacity_; size_t size_; void swap(MyStack other) noexcept { std::swap(data_, other.data_); std::swap(capacity_, other.capacity_); std::swap(size_, other.size_); } public: MyStack(const MyStack other) : data_(new T[other.capacity_]), capacity_(other.capacity_), size_(other.size_) { for (size_t i 0; i size_; i) { data_[i] other.data_[i]; } } MyStack operator(MyStack other) { swap(other); return *this; } // 其余方法同上 };這里賦值運(yùn)算符的形參不是const MyStack而是直接按值傳MyStack other。這樣other是從實(shí)參拷貝出來的臨時對象swap 之后舊數(shù)據(jù)被裝進(jìn)了這個臨時對象函數(shù)結(jié)束時自動析構(gòu)完成資源清理。如果實(shí)參拷貝過程中拋異常賦值操作就整體失敗原對象狀態(tài)不受影響。這就是 copy-and-swap 的優(yōu)雅之處用拷貝構(gòu)造來保證異常安全。3.3 進(jìn)階用 placement new 讓容器更嚴(yán)謹(jǐn)前面的實(shí)現(xiàn)雖然很好理解但有一個明顯的局限new T[cap]要求 T 必須支持默認(rèn)構(gòu)造。如果 T 沒有默認(rèn)構(gòu)造函數(shù)代碼就無法編譯。而且用賦值運(yùn)算符覆蓋舊值本質(zhì)上是對“活著的對象”進(jìn)行賦值而不是構(gòu)造新對象。更嚴(yán)謹(jǐn)?shù)淖龇ㄊ侵环峙鋬?nèi)存不構(gòu)造對象push 時用 placement new 構(gòu)造pop 時手動調(diào)用析構(gòu)。關(guān)鍵代碼如下template typename T class MyStack { private: T* data_; size_t capacity_; size_t size_; void grow() { size_t new_capacity capacity_ * 2; T* new_data static_castT*(::operator new(sizeof(T) * new_capacity)); size_t i 0; try { for (; i size_; i) { new (new_data[i]) T(data_[i]); // 拷貝構(gòu)造而不是賦值 } } catch (...) { for (size_t j 0; j i; j) { new_data[j].~T(); } ::operator delete(new_data); throw; } for (size_t j 0; j size_; j) { data_[j].~T(); } ::operator delete(data_); data_ new_data; capacity_ new_capacity; } public: explicit MyStack(size_t cap 16) : data_(static_castT*(::operator new(sizeof(T) * cap))), capacity_(cap), size_(0) {} ~MyStack() { for (size_t i 0; i size_; i) { data_[i].~T(); } ::operator delete(data_); } void push(const T value) { if (size_ capacity_) { grow(); } new (data_[size_]) T(value); // placement new size_; } void pop() { if (empty()) { throw std::runtime_error(stack underflow); } --size_; data_[size_].~T(); // 手動析構(gòu) } // top/empty/size 同前 };::operator new(sizeof(T) * n)只分配裸內(nèi)存不調(diào)用構(gòu)造函數(shù)new (data_[size_]) T(value)在指定位置上構(gòu)造對象data_[size_].~T()顯式調(diào)用析構(gòu)函數(shù)。這一套組合拳讓容器可以存放沒有默認(rèn)構(gòu)造函數(shù)的類型也讓 pop 真正釋放了對象持有的資源。代價是代碼復(fù)雜度明顯提高。我的建議是先把第一版搞懂、跑通再升級到這一版。學(xué)習(xí)路徑本身比直接抄一個“最強(qiáng)版本”更重要。3.4 測試 MyStack不只測功能更要測邊界寫測試時不要只驗證“能 push 能 pop”。真正的邊界測試長這樣int main() { MyStackint stack; // 空棧狀態(tài)檢查 std::cout empty: stack.empty() std::endl; // 1 std::cout size: stack.size() std::endl; // 0 // 連續(xù)壓入觸發(fā)多次擴(kuò)容 for (int i 1; i 100; i) { stack.push(i); } std::cout after push 100: size stack.size() // 100 top stack.top() std::endl; // 100 // 邊 pop 邊看 top while (!stack.empty()) { int topVal stack.top(); stack.pop(); std::cout pop topVal std::endl; } // 空棧 top/pop 應(yīng)該拋異常 try { stack.pop(); } catch (const std::exception e) { std::cout caught: e.what() std::endl; } // 拷貝獨(dú)立性測試 MyStackint copy stack; // 空?？截?for (int i 0; i 5; i) { copy.push(i); } MyStackint assigned; assigned copy; assigned.top() 100; // 修改副本不影響原對象 std::cout copy top copy.top() assigned top assigned.top() std::endl; return 0; }跑起來之后重點(diǎn)觀察幾件事擴(kuò)容是否正常、pop 后 size 是否正確遞減、空棧異常是否被拋出、拷貝出來的棧是否和原棧完全獨(dú)立。這些測試點(diǎn)覆蓋了大部分實(shí)現(xiàn)里容易出 bug 的地方。4. 從零實(shí)現(xiàn) queue鏈表核心操作與環(huán)形緩沖區(qū)對比4.1 用鏈表實(shí)現(xiàn) queue兩個指針撐起全部操作queue 和 stack 最大的不同在于queue 需要兩端操作。stack 只需要操作棧頂一端但 queue 的 push 在隊尾、pop 在隊頭、front 要看隊頭、back 要看隊尾。如果我用動態(tài)數(shù)組實(shí)現(xiàn) queue隊頭出隊時就會面臨“前面空出來但后面滿了”的尷尬局面必須引入環(huán)形緩沖或者移動數(shù)據(jù)。而用鏈表實(shí)現(xiàn)情況會變得很簡單每個節(jié)點(diǎn)包含數(shù)據(jù)和下一個節(jié)點(diǎn)的指針front_指向隊頭節(jié)點(diǎn)back_指向隊尾節(jié)點(diǎn)。push 時在鏈表尾部掛新節(jié)點(diǎn)pop 時摘掉頭節(jié)點(diǎn)。完整實(shí)現(xiàn)如下#include iostream #include stdexcept template typename T class MyQueue { private: struct Node { T data_; Node* next_; Node(const T data, Node* next nullptr) : data_(data), next_(next) {} }; Node* front_; Node* back_; size_t size_; public: MyQueue() : front_(nullptr), back_(nullptr), size_(0) {} ~MyQueue() { while (front_ ! nullptr) { Node* temp front_; front_ front_-next_; delete temp; } } MyQueue(const MyQueue other) : front_(nullptr), back_(nullptr), size_(0) { Node* cur other.front_; while (cur ! nullptr) { push(cur-data_); cur cur-next_; } } MyQueue operator(MyQueue other) { std::swap(front_, other.front_); std::swap(back_, other.back_); std::swap(size_, other.size_); return *this; } void push(const T value) { Node* new_node new Node(value); if (back_ nullptr) { front_ back_ new_node; } else { back_-next_ new_node; back_ new_node; } size_; } void pop() { if (empty()) { throw std::runtime_error(queue underflow: pop from empty queue); } Node* old_front front_; front_ front_-next_; if (front_ nullptr) { back_ nullptr; } delete old_front; --size_; } T front() { if (empty()) { throw std::runtime_error(queue empty: no front element); } return front_-data_; } const T front() const { if (empty()) { throw std::runtime_error(queue empty: no front element); } return front_-data_; } T back() { if (empty()) { throw std::runtime_error(queue empty: no back element); } return back_-data_; } const T back() const { if (empty()) { throw std::runtime_error(queue empty: no back element); } return back_-data_; } bool empty() const { return size_ 0; } size_t size() const { return size_; } };這個實(shí)現(xiàn)里最需要留意的地方是pop()中的這個細(xì)節(jié)front_ front_-next_; if (front_ nullptr) { back_ nullptr; }當(dāng)隊列只有一個元素時pop 之后front_變成nullptr但此時back_還指著那個已被刪除的節(jié)點(diǎn)。如果不把back_也置空下一次push時就會訪問懸空指針程序崩潰。這個 bug 非常經(jīng)典我見過不少人在手寫隊列時翻車在這個地方。另外operator用了 copy-and-swap。MyQueue other按值傳入相當(dāng)于自動完成了深拷貝三個 swap 交換成員之后舊數(shù)據(jù)被臨時對象帶走了函數(shù)結(jié)束時自動析構(gòu)。這樣寫異常安全和自賦值問題一次全解決。4.2 鏈表 vs 環(huán)形緩沖區(qū)兩種 queue 方案的深度對比鏈表方案最大的優(yōu)勢是實(shí)現(xiàn)直觀、節(jié)點(diǎn)生命周期清晰。每個節(jié)點(diǎn)獨(dú)立分配push 時創(chuàng)建新節(jié)點(diǎn)pop 時刪除舊節(jié)點(diǎn)不需要擔(dān)心擴(kuò)容和元素搬移。但它的缺點(diǎn)也很明顯每個節(jié)點(diǎn)都要通過new單獨(dú)分配內(nèi)存這些零散的堆分配導(dǎo)致內(nèi)存碎片化而且訪問節(jié)點(diǎn)時的緩存局部性很差。當(dāng)隊列頻繁 push/pop 時每次都要 malloc/free性能會明顯下降。相比之下環(huán)形緩沖區(qū)用一個連續(xù)數(shù)組模擬隊列head_和tail_兩個索引在數(shù)組里“轉(zhuǎn)圈”。核心思路是push 時把元素寫到tail_然后tail_ (tail_ 1) % capacity_pop 時讀取head_然后head_ (head_ 1) % capacity_。這個取模操作讓索引到數(shù)組末尾時自動回到開頭形成“環(huán)”。環(huán)形緩沖區(qū)最頭疼的地方是擴(kuò)容。數(shù)組滿了之后你不能直接把數(shù)組翻倍復(fù)制就完事——因為當(dāng)前隊列的頭可能在任意位置元素在邏輯上是“繞圈”排列的。擴(kuò)容時必須把舊元素重新排列到新數(shù)組的前面邏輯上仍然保持隊頭在前、隊尾在后。結(jié)合上一章提到的 placement new 知識你可以寫出一個能支持任意類型的 RingQueue但代碼量會比鏈表方案多不少。從實(shí)際取舍來看如果是教學(xué)、面試或快速原型鏈表方案優(yōu)先邏輯清晰、不容易出錯。如果是性能敏感的高頻入隊出隊場景環(huán)形緩沖區(qū)更合適。在 C 里STL 的std::queue默認(rèn)用std::deque其實(shí)就相當(dāng)于“分段連續(xù)”的環(huán)形緩沖區(qū)優(yōu)化版這才是它性能好的真正原因。4.3 擴(kuò)展思考用兩個棧實(shí)現(xiàn)隊列既然手寫了 stack你還可以玩一個經(jīng)典題目用兩個棧實(shí)現(xiàn)隊列。思路是這樣的棧 A 負(fù)責(zé)入隊push 直接壓入 A。棧 B 負(fù)責(zé)出隊當(dāng) B 為空時把 A 的所有元素依次 pop 并 push 進(jìn) B然后從 B 的棧頂彈出就等價于從隊頭出隊。這個技巧很有意思因為兩個 LIFO 結(jié)構(gòu)疊起來竟然能模擬出 FIFO 的行為。實(shí)測下來平均時間復(fù)雜度依然是 O(1)只有 A 往 B 倒數(shù)據(jù)的那一瞬間是 O(n) 的攤還下來完全可接受。理解了這篇實(shí)現(xiàn)的 stack再去做這道題會非常輕松這里先留給你自己試一試。5. 常見問題與排查技巧實(shí)錄5.1 淺拷貝導(dǎo)致的雙重釋放這是手寫容器時最容易踩的坑?，F(xiàn)象是程序運(yùn)行到析構(gòu)時直接報double free or corruption。原因就是我前面說的默認(rèn)的拷貝構(gòu)造是逐字節(jié)復(fù)制兩個對象的data_指針指向同一塊內(nèi)存析構(gòu)時兩次delete[]同一地址。排查技巧很簡單在類里臨時禁用拷貝構(gòu)造和賦值運(yùn)算符如果崩潰消失基本可以斷定是淺拷貝問題。修復(fù)方案也很唯一實(shí)現(xiàn)深拷貝。要么手動寫拷貝構(gòu)造和賦值運(yùn)算符要么用 copy-and-swap 一勞永逸。5.2 空容器上的 undefined behaviorSTL 的std::stack::top()在棧為空時是未定義行為不會幫你做檢查。但自己實(shí)現(xiàn)的容器如果也這樣照搬測試時很容易出現(xiàn)莫名其妙的崩潰。我推薦的做法是顯式拋異常比如throw std::runtime_error(stack empty)。雖然現(xiàn)場會多一次分支判斷但它能幫你快速暴露邏輯錯誤。這個取舍在實(shí)際工程中很值得寧可慢一點(diǎn)也不能讓未定義行為蟄伏在代碼里。5.3 模板編譯報錯的定位思路手寫模板類時最常見的編譯錯誤是“no default constructor exists for class X”或者“cannot assign”。原因往往不是你的邏輯錯了而是你底層用的new T[]對類型提出了額外要求。當(dāng) T 沒有默認(rèn)構(gòu)造函數(shù)時new T[cap]無法編譯。遇到這種情況先別慌檢查兩個方向你是不是用了new T[]如果是換成::operator new placement new 方案參考 3.3 節(jié)。你的自定義類型是否缺少拷貝構(gòu)造或拷貝賦值模板實(shí)例化時所有用到的方法都會被編譯即使你沒調(diào)用編譯器也會檢查其合法性。這類報錯信息往往很長但真正的有效信息在第一個error位置往那兒找效率最高。5.4 性能對比自實(shí)現(xiàn) vs STL我用一個簡單的程序壓了十萬次 push/pop得出了幾個參考數(shù)據(jù)不同機(jī)器會有差異但趨勢一致容器10萬次 push/pop 耗時內(nèi)存分配次數(shù)自實(shí)現(xiàn)動態(tài)數(shù)組 stack較低擴(kuò)容僅十幾次STL stack (deque)略高但極穩(wěn)分批分配自實(shí)現(xiàn)鏈表 queue較高10萬次 new/deleteSTL queue (deque)中等分批分配結(jié)論很明顯鏈表的單次操作雖然也是 O(1)但常數(shù)很大因為每次 push 都涉及一次堆分配。這就是為什么 STL 的 stack/queue 默認(rèn)都用 deque 而不是 list——連續(xù)內(nèi)存的訪問效率遠(yuǎn)高于零散的鏈表節(jié)點(diǎn)。自己做性能測試時記得把編譯器的優(yōu)化選項打開比如-O2否則測出來的是調(diào)試模式的數(shù)據(jù)參考價值不大。一些實(shí)在的心得把這兩個容器從頭實(shí)現(xiàn)一遍之后我最大的感受是STL 看似簡單的接口背后藏著相當(dāng)多的設(shè)計決策。比如為什么 queue 不用 vector因為 vector 在頭部刪除是 O(n)。為什么不用 list因為 list 每個節(jié)點(diǎn)單獨(dú)分配內(nèi)存緩存不友好。而 deque 通過分段連續(xù)存儲兼顧了兩端的操作效率和訪問局部性。這些結(jié)論如果你只看教科書是記不牢的但親手寫一遍代碼、壓一次性能就全通了。如果你想把練習(xí)再往上推一步我建議你試試這幾個方向給 stack 增加emplace接口用變參模板直接構(gòu)造元素給 queue 增加移動構(gòu)造和移動賦值減少拷貝開銷或者把底層容器策略做成模板參數(shù)模擬 STL 容器適配器的設(shè)計方式。每做一個你都會對 C 的泛型和對象模型有更深一層理解。最后說一點(diǎn)實(shí)在的這篇里的代碼是為了教學(xué)清晰而精簡過的用來面試和自學(xué)完全夠。如果你要在正式生產(chǎn)項目里用直接用std::stack和std::queue就好了不要重復(fù)造輪子。造輪子的意義在于弄懂輪子而不在于替換輪子。