先讀語法與例子，再操作互動圖解並完成四選一自測。忘記寫法時回看速查表，最後用中英詞彙卡複習。
vector 一次解決先看你已經會的東西壞在哪裡。int a[5]; 這行有三個你改不掉的限制：
| 痛點 | 原生陣列 | vector |
|---|---|---|
| 長度能不能變 | 不能。int a[5] 就是永遠 5 格 | 能，push_back 隨時加 |
| 傳進函式會怎樣 | 一般 T arr[] 參數調整為 T*，不攜帶長度；陣列參考等寫法可保留型別 | 照樣是完整的物件，size() 還在 |
| 自己知不知道多長 | 陣列型別本身保有長度；以一般指標參數接收後，通常需另傳 n | 知道，v.size() |
原生陣列：main 裡 sizeof(a) = 20 bytes 函式裡 sizeof(arr) = 8 bytes（指標的大小） vector：main 裡 v.size() = 5 函式裡 v.size() = 5 push_back 之後 v.size() = 6
int arr[] 作為函式參數會調整成 int*，因此函式內 sizeof(arr) 是指標大小，實際 bytes 依平台而定。在陣列原本的作用域中，sizeof(a) 仍是整個陣列大小。vector 以參考傳入時保有完整型別與 size() 介面。
這一頁同時介紹操作方式與成本：尾端加入、中間插入、容量搬移和字串累積看似都在改資料，實際需要的工作可能不同。
| 情境 | 語法或操作 | 要注意的事 |
|---|---|---|
| 保存讀數 | vector<int> | 長度會隨輸入增加，用 push_back 加到尾端。 |
| 預先知道資料量 | reserve | 先安排容量，避免已知範圍內的重複配置。 |
| 保留原始資料 | 複製容器 | 獨立副本適合之後要各自修改的情況。 |
| 更新一筆資料 | v[i] 或 v.at(i) | 索引要合法，需要範圍檢查時選 at。 |
| 刪除無效記錄 | erase | 接住回傳的迭代器，避免繼續使用已失效的位置。 |
| 保存分列資料 | vector<vector<int>> | 每一列各自管理長度；稍後以座位表練習。 |
vector 要先 #include <vector>。建立的四種寫法對應四種情境：
| 寫法 | 結果 | 什麼時候用 |
|---|---|---|
| vector<int> v; | 空的，size() 是 0 | 邊跑邊 push_back |
| vector<int> v(5, 0); | 5 個 0 | 已知長度、要先填預設值（計數陣列） |
| vector<int> v = {31, 17, 93}; | 照清單填好 | 寫測試資料 |
| vector<int> w(v); | 整份複製一份新的 | 要留原本那份不動時 |
存取有兩個：v[i] 和 v.at(i)。功能一樣，差別只在越界時的反應。
a.size()=0 b.size()=5 c.size()=3 d.size()=3 c[1] = 17 <- 不檢查範圍，快 c.at(1) = 17 <- 檢查範圍 c.at(5) 丟出 out_of_range：vector::_M_range_check: __n (which is 5) >= this->size() (which is 3)
at(5) 在只有 3 個元素的 vector 上會丟出 out_of_range，訊息裡連 5 和 3 都寫出來了，非常好 debug。換成 c[5] 就什麼檢查都不做：讀到隔壁那塊記憶體，印出一個看起來像亂數的值，或者直接當掉，而且當掉的位置常常離出錯的那一行很遠。
v.at(5)： [執行結束碼 -6] terminate called after throwing an instance of 'std::out_of_range' what(): vector::_M_range_check: __n (which is 5) >= this->size() (which is 3)
沒有相符的 catch 時，例外一路離開 main，系統會呼叫 std::terminate；預設處理通常使程式異常終止。診斷文字格式由實作決定，正式程式仍應在能處理問題的層級接住例外。
確定索引合法時可使用 v[i]；不確定來自輸入或計算的索引時，可用 at(i) 檢查範圍。越界時 at 會以例外回報，而 [] 不保證替你檢查；不要靠試跑未定義行為判斷安全。
Type 變數(引數);：宣告變數與呼叫建構式，同一行發生取出測量資料的一段時，可以寫 vector<int> left(aList.begin(), aList.begin() + midpoint);。這一行宣告 left，同時把一對區間位置交給建構式。這稱為直接初始化，以下仍逐項拆開型別、名稱與引數。
| 片段 | 身分 |
|---|---|
| vector<int> | 型別 |
| left | 變數名稱 |
| (aList.begin(), aList.begin() + midpoint) | 傳給建構式的引數 |
Type variable(arguments); 讀成「建立 variable，並呼叫 Type 的建構式」。vector 提供好幾個建構式，編譯器照引數的個數與型別挑一個 —— 挑選的過程正是 P8 講的多載解析。
同一個語法家族可以用來建立不同資料，以下逐列比較。
| 寫法 | 呼叫到的建構式 | 使用情境 |
|---|---|---|
| vector<int> x(2000000); | 計數：200 萬個元素，各是 0 | 效能實測 |
| vector<int> hashTable(11, -1); | 計數＋初值：11 個 −1 | 雜湊表 |
| vector<int> left(a.begin(), a.begin()+mid); | 範圍建構式：把 [first, last) 那一段抄成新的 vector（尾端不含）—— C++ 的「切片」就是這招 | 複製一段連續資料 |
| string s("hello"); | string 的建構式 —— 完全同一個概念 | 各章 |
| listSum({1, 3, 5, 7, 9}); | 初始化清單直接當引數：函式收的是 vector<int>，編譯器就照這個型別把 {…} 現場建成一個 vector 傳進去 —— {…} 不是只能寫在等號右邊 | 遞迴加總 |
| string(1, convertString[n]); | 「n 個字元 c」建構式：string(1, 'D') 就是長度 1 的 "D"。用來把單一 char 變成 string，才能跟別的字串用 + 接起來 | 進位轉換 |
寫成 auto sub = vector<double>(v.begin()+1, v.begin()+3); 也合法：先把右邊的物件建出來，再用它初始化 sub，結果相同。[first, last) 為什麼含頭不含尾、begin()／end() 到底指哪裡，圖解見 P6 的迭代器。
sub.size()=2 sub[0]=9.2 sub[1]=7.3 a.size()=3 a[0]=0 b.size()=1 b[0]=3 s=hello t.size()=2
第 8 行就是本頁速查表那招「C++ 切片」：[first, last) 尾端不含，所以抄到的是索引 1、2 兩格。第 12、13 行是下面警告框要講的陷阱。
vector<int> a(3); 是「3 個元素，各是 0」；vector<int> b{3}; 卻是「1 個元素，值是 3」——大括號會優先配對 initializer_list 建構式。計數用小括號、列出元素用大括號，可讓意圖更清楚。
為什麼初學會覺得亂？因為 C 和 Python 都沒有把「宣告」跟「建構」黏在同一行的寫法：
| 寫法 | 概念 | |
|---|---|---|
| C | int x = 5; | 宣告＋給值就結束了，沒有建構式這個概念 |
| Python | v = list(range(5)) | 概念上類似 —— 呼叫型別建立物件 —— 但變數不必宣告型別，「建構」只出現在等號右邊 |
| C++ | vector<int> v(5); | 宣告與建構黏在同一行，所以長得像函式呼叫 —— 其實兩件事同時發生 |
vector<int> v(3); 和 vector<int> w{3}; 各裝了什麼？
增刪的成本只看一件事：你動的是尾巴，還是尾巴以外的地方。動尾巴不影響任何人；動前面或中間，後面每一個元素都要跟著挪一格。
起始 size=3 [ 31 17 93 ] push_back(26) size=4 [ 31 17 93 26 ] pop_back() size=3 [ 31 17 93 ] insert(begin) size=4 [ 54 31 17 93 ] erase(begin+1) size=3 [ 54 17 93 ] clear() 之後 size=0 capacity=[依實作而異，且不小於 4] <- 容量沒有跟著變 0
看 insert(v.begin(), 54) 那一步：31、17、93 三個元素全部往後挪一格，54 才放得進第 0 格。erase(v.begin() + 1) 同理，後面的元素往前補位。最後一行的 clear() 把 size 清成 0，但 capacity 保持清空前的值；確切數字由實作與先前配置決定，下次 push_back 可以直接使用既有容量。
尾端加入通常只需處理新元素；前端插入還需把原元素往後移。前者攤還 O(1)，後者為 O(n)，不能因為兩個操作都叫「加入」就忽略位置差異。
尾端 push_back 0.10 ms 前端 insert 0.80 ms 兩份長度 5000 5000
push_back 將元素加在尾端；insert(begin(), x) 插在前端，需要搬移既有元素。觀察資料量增加時，兩種寫法的耗時如何變化。
獨立程式使用時間工具時，應明確 #include <chrono>，不要依賴執行環境間接帶入標頭。若 steady_clock 未宣告，先檢查標頭及 std::chrono 名稱範圍。
size() 是住了幾個，capacity() 是有幾個位子vector 的元素一定放在一整塊連續記憶體裡——這是 v[i] 能 $O(1)$ 的原因。連續就代表不能隨便往後長，隔壁可能已經被別人佔走了。所以位子坐滿時，vector 的做法是：另外找一塊更大的，把所有元素搬過去，再把舊的還掉。
▲ 圖中採用「容量倍增」的示範模型：新空間建立後，既有元素需逐一搬移或複製，這部分工作量隨元素數量增加。倍增模型可用等比級數理解攤還成本；C++ 標準保證 vector 尾端加入的攤還複雜度，但不規定實際容量必須每次翻倍，也不能據此假設配置本身一定耗時固定。重新配置後，舊元素的指標與迭代器失效。
一開始 size=0 capacity=0 第 1 次 push_back：capacity 0 -> 1，搬了 0 個元素 第 2 次 push_back：capacity 1 -> 2，搬了 1 個元素 第 3 次 push_back：capacity 2 -> 4，搬了 2 個元素 第 5 次 push_back：capacity 4 -> 8，搬了 4 個元素 第 9 次 push_back：capacity 8 -> 16，搬了 8 個元素 第 17 次 push_back：capacity 16 -> 32，搬了 16 個元素 17 次 push_back，總共搬移 31 個元素 平均每次 push_back 搬 1.82353 個 -> 這就是攤還 O(1)
容量走的是 0 → 1 → 2 → 4 → 8 → 16 → 32，每次翻倍（這是 libstdc++ 的策略，標準只要求攤還 $O(1)$）。17 次 push_back 裡只有 6 次搬了家，總共搬移 31 個元素，平均每次不到 2 個。這就是攤還分析：個別一次可能很貴，但把成本分攤到所有操作上，平均仍是常數。
如果每次只多加一格，塞 n 個元素要搬 1+2+…+(n-1) 次，是 $O(n^2)$。改成翻倍之後，搬家次數只有 $\log_2 n$ 回，搬移總量是 1+2+4+…+n，不超過 2n。把 2n 分攤到 n 次 push_back，平均每次是常數。
已經知道要放幾個的話，先 v.reserve(n) 把位子訂好，一次搬家都不會發生。
reserve(1000) 之後塞 1000 個，擴容次數 = 0 沒有 reserve 塞 1000 個，擴容次數 = 11
圖中採用示範性的倍增策略；實際標準庫不保證容量恰好兩倍。先 reserve(1000) 可確保在大小不超過預留容量的加入過程中不因容量不足而重配置，原有操作與 reserve 對照仍可逐步觀察。
&對本例的 int 而言，三種寫法都逐項走訪，複雜度同為 $O(n)$；實際常數成本與是否複製元素仍取決於寫法與元素型別。選擇時要看你需不需要索引、要不要改到元素本人。
| 寫法 | 拿得到索引嗎 | 什麼時候用 |
|---|---|---|
| for (unsigned i = 0; i < v.size(); i++) | 拿得到 | 要比較 v[i] 與 v[i+1]、要換位置（排序全部用這種） |
| for (int x : v) | 拿不到 | 只是把每個值讀一遍，最好讀 |
| for (auto it = v.begin(); it != v.end(); ++it) | 間接可以 | 要呼叫 insert／erase（它們吃的就是 iterator） |
① 索引： 31 17 93 26 ② 範圍 for： 31 17 93 26 ③ iterator： 31 17 93 26 for (int x : v) x*=10 之後： 31 17 93 26 for (int& x : v) x*=10 之後： 310 170 930 260
前三行印出一樣的東西。重點在後面兩組：for (int x : v) 的 x 是複製品，改它等於改一個馬上就要丟掉的暫存值，原本的 vector 一動也沒動；加了 & 寫成 for (int& x : v)，x 才是元素本人，改了就真的改到。
兩個常見理由是：需要修改原元素，或元素較大而不想取得副本。只讀字串時可寫 for (const string& s : words)；這不複製既有字串，也禁止透過 s 修改它。
unsigned 而不是 intv.size() 與 s.length() 回傳無號大小型別。拿帶號 int 比較可能收到不同符號的警告；要選合適的計數型別，並小心無號值的減法與倒數。不要只為消除警告就把所有數字轉成無號。
代價是要記住一件事：無號數相減永遠不會是負的，減過頭會從最大值繞回來。v.size() - 1 在空 vector 上不是 −1；在 64 位元大小型別的環境中會成為 18446744073709551615。所以 for (unsigned i = 0; i < v.size() - 1; i++) 這種寫法碰到空 vector 會執行極多次並越界——想比較相鄰兩格時，改寫成 i + 1 < v.size() 才安全。
迭代器常寫成 for (auto it = v.begin(); it != v.end(); ++it)，讓編譯器從初值推導型別。它仍是固定型別，不是變成可以裝任意資料的變數；完整名稱 vector<int>::iterator 也合法。從 iterator 改寫成範圍 for 的逐步對照，見 P6 的 map 範例。
push_back 之後，舊的指標可能指到空地PART 03 說擴容會把元素整批搬到新位址。那你在搬家前記下來的位址呢？它還指著舊地址——而舊那塊已經還給系統了。這就是 iterator 失效。
before 與 after 的 first 都是 31，after 的容量大於 before。 最後一行：new pointer reads 31 確切 capacity 依實作而異。
初始化清單不保證 capacity 剛好等於 size，因此本例用 reserve(oldCapacity + 1) 明確觸發重新配置。元素的值仍保留，但舊指標 p 已失效，不能再解參考，也不把舊位址拿來當可依賴的輸出。重新以 &v[0] 取址才可繼續使用。
若 push_back 沒有重新配置，指向既有元素的指標仍有效；一旦重新配置便全部失效。索引可用來在搬家後重新取得元素，但插入或刪除也可能改變索引所對應的元素，不能把「記索引」當成所有操作的通用解法。
| 操作 | 誰失效 |
|---|---|
| push_back / insert | 重新配置時全部失效；否則 insert 在插入點及其後失效，push_back 使舊 end() 失效 |
| erase(it) | 刪除位置及其後的迭代器、參考失效，包含舊 end()；erase 回傳刪除後的下一個有效迭代器 |
| pop_back | 被刪除元素的迭代器／參考及舊 end() 失效 |
| clear | 全部失效 |
| v[i] = x | 沒有人失效，改值不影響配置 |
有人想在走訪時把等於 0 的元素刪掉，寫成 for (auto it = v.begin(); it != v.end(); ++it) if (*it == 0) v.erase(it);。問題在哪？
vector<vector<int>>：一個裝著 vector 的 vector二維 vector 是「每個元素本身又是一個 vector」。例如 vector<vector<int>> seats(3, vector<int>(4, 0)); 建立三列，每列有四個初值為 0 的元素。下例用 0 表示空位、1 表示已預訂，練習列與欄兩層索引。
row 0: 0 1 0 0 row 1: 0 0 1 0 row 2: 1 0 0 0 rows = 3, first row seats = 4
seats[row][col] 先用 row 找到某列，再用 col 存取該列的座位。seats.size() 是列數，seats[row].size() 才是該列座位數。存取前兩層索引都要有效；若外層是空的，seats[0] 就不能使用。
每一列是獨立的 vector，所以可用 seats[1].push_back(0) 只替第二列多加一個座位。這和固定長寬的原生二維陣列不同，也表示不能拿第一列長度當作所有列的上限。若要按分類存可變長度名單，P6 再介紹 map 搭配 vector。
stack／queue／deque：現成容器的介面標準函式庫已提供 stack、queue、deque。下面比較同樣的「加入、查看、移除」需求，在不同容器上要使用哪些介面；這些型別都由標準標頭提供。
這三種容器分別需要 <stack>、<queue>、<deque>。自己建立程式時應明確引入所需標頭。
三個容器的成員協定不一樣，而且不是誰包含誰——記錯就會呼叫到不存在的方法：
| 容器 | 放進去 | 看一眼 | 拿掉 | 其他 | 使用情境 |
|---|---|---|---|---|---|
| stack<T> | push(x) | top() | pop() | empty() size() | 編輯版本：stack<string> versions; |
| queue<T> | push(x) | front() back() | pop() | empty() size() | 一般排隊：queue<string> line; |
| deque<T> | push_front(x) push_back(x) | front() back() | pop_front() pop_back() | empty() size() d[i] | 兩端讀數：deque<int> readings; |
三個要點：stack 用 top 查看，queue 用 front/back；deque 的兩端操作名稱明確帶方向。容器可以保存物件，也可以保存指標，但保存指標不代表容器自動擁有或釋放所指物件。
pop() 不回傳東西STL 的 stack::pop() 回傳型別是 void。要值就得分成兩步——先 top() 抄下來，再 pop() 移除：
| 你想做的事 | 常見誤寫 | 正確寫法 |
|---|---|---|
| 取出並移除頂端 | T x = s.pop(); | T x = s.top(); s.pop(); |
| 只移除、不要值 | s.top(); | s.pop(); |
把標準 stack 的 pop() 當成回傳元素會編譯失敗；只呼叫 top() 又不會移除元素。需要取出並移除時，先讀 top，再 pop；queue/deque 的對應移除介面也不回傳值。
versions.size() = 2 top = v2 移除 v2 之後 top = v1 size = 1 queue front = Ada back = Cora pop 之後 front = Ben back = Cora deque front = 16 back = 20 size = 3
stack 用 top() 讀到最新版本 v2，再用 pop() 移除它；queue 的 pop() 只移除排頭 Ada，因此新的 front() 是 Ben，而 back() 仍是 Cora；deque 的 push_front(16) 把較早讀數補到前端，尾端仍是 20。
手上是 STL 的 stack<string> s;，你想取出頂端元素並把它移除。哪一種寫法對？
std::string 與 vector<char> 是不同類別。兩者都提供連續儲存、size、capacity 與下標存取等概念，但不能把全部介面、失效規則和成本保證視為相同。string 額外提供子字串、文字搜尋與 C 字串介面；以下從獨立文字例子認識它。
length = 4, size = 4 first = b, last = k substr(1, 2) = oo substr(2) = ok find(oo) = 1 xy not found label = bo-ok after += : books!
四個要記住的細節：① length() 和 size() 完全一樣，兩個名字而已。② substr(pos, len) 的第二個參數是長度，不是結束位置（跟 Python 的切片不同）。③ find 找不到時回傳 string::npos，那是一個超大的數字，所以判斷要寫 == string::npos，不要寫 < 0。④ += 接字元或接字串都可以。
len 超出尾端不會出錯，substr 給你到字串結尾為止。但 pos 超出長度會丟 out_of_range，跟 at() 一樣的例外。
| 你在 Python 寫 | C++ 寫成 | 注意 |
|---|---|---|
| len(s) | s.length() | 回傳的是無號整數，跟 int 比大小會被編譯器警告 |
| s[1:3] | s.substr(1, 2) | 第二個參數是長度，不是結束位置 |
| s.find("oo") | s.find("oo") | 找不到 Python 給 -1，C++ 給 string::npos |
| s += "x" | s += "x" | 寫法一樣，成本差很多，見下一節 |
| s[0] | s[0] | Python 給長度 1 的字串，C++ 給一個 char |
char 可以做算術：s[i] - 'a' 是什麼意思char 說穿了就是一個小整數（一個 byte），存的是字元的編碼值。ASCII 把 'a' 到 'z' 排成連續的 97 到 122，所以兩個字元相減，得到的是它們在字母表上差幾格：'c' - 'a' 是 2、't' - 'a' 是 19、'a' - 'a' 是 0。
在常見 ASCII 相容編碼中，減去字元 a 可把小寫英文字母映射到 0–25，用來計數。但要先確認輸入確實是該範圍；一般字串可能有空白、大小寫或多位元組文字，不能直接當成合法索引。
+= 便宜，s = s + x 很貴兩行看起來只差一個等號，累積工作量卻不同。原因回到 PART 03：s += 'x' 在容量足夠時直接加在尾端；s = s + 'x' 每一輪都要先建立新字串並複製目前全部內容，再賦值回去。字串愈長，逐輪重複複製的差距愈明顯。
累積 += 0.10 ms 重建 + 0.80 ms 內容相同 1
這裡各累積一萬個字元。+= 那條走的是攤還 $O(1)$，總成本 $O(n)$；s = s + 'x' 每一輪都複製一次現有內容，總成本是 $O(n^2)$。增加字元數，觀察兩種累積方式的耗時如何成長。
Python 的字串是不可變的，s += x 骨子裡也是重新配一個新字串（CPython 有特例最佳化，但不保證），所以那邊教你改用 "".join(parts)。C++ 的 string 是可變的，+= 就是真的就地長大，不需要繞路。記法很簡單：C++ 裡的 += 跟 push_back 是同一種東西。
char 與 string 是兩種東西'a' 是一個 char，而 C++ 規定 sizeof(char) == 1；它屬於整數型別，但實際字元編碼由實作決定。"a" 則是含結尾空字元的字元陣列，兩者型別與可用運算不同：
[編譯失敗]
cell.cpp: In function ‘int main()’:
cell.cpp:6:21: error: invalid operands of types ‘const char [3]’ and ‘const char [3]’ to binary ‘operator+’
6 | string s = "ab" + "cd"; // 兩個字面值相加：這行過不了"ab" 和 "cd" 的型別是 const char[3]，兩個陣列不能用 + 相加。解法是讓其中一邊先變成 string：string("ab") + "cd"，或者宣告成 string a = "ab"; a += "cd";。
stoi("1453") + 1 = 1454
to_string(2906) + "!" = 2906!
s[0] 是 char：1，佔 1 bytes
s.substr(0,1) 是 string：1，物件佔 [依實作而異] bytes
string(1, c) + "X" = 1X
在 ASCII 相容編碼中：c - '0' = 1stoi 把字串轉整數、to_string 把數字轉字串，兩個都在 <string> 裡。sizeof(char) 依定義是 1 byte，但 string 物件本身的 byte 數由實作決定，應以程式實際印出的值為準。在 ASCII 相容編碼中，數字字元連續排列，所以確認 c 在 '0' 到 '9' 後，可用 c - '0' 取得數值；這項技巧不可直接套用到任意文字編碼或任意字元。
一個空的 vector<int> 連續 push_back 8 次，容量走 0→1→2→4→8。整個過程中被「搬家」搬過的元素總共幾個？
| 操作 | 複雜度 | 為什麼 |
|---|---|---|
| v[i] | $O(1)$ | 連續記憶體，位址直接算得出來。不檢查範圍 |
| v.at(i) | $O(1)$ | 同上，多一次範圍檢查；越界丟 out_of_range |
| v.size() | $O(1)$ | 長度是存起來的，不用數 |
| v.empty() | $O(1)$ | 就是問 size 是不是 0 |
| v.capacity() | $O(1)$ | 同樣是存起來的欄位 |
| v.push_back(x) | 攤還 $O(1)$ | 通常只是寫進下一格；容量滿時要搬 n 個，但平攤下來是常數 |
| v.pop_back() | $O(1)$ | size 減一，沒有人需要移動 |
| v.insert(pos, x) | $O(n)$ | pos 之後每個元素都往後挪一格 |
| v.erase(pos) | $O(n)$ | pos 之後每個元素都往前挪一格 |
| v.clear() | $O(n)$ | 要一個一個解構（int 這種簡單型別實務上很快）；capacity 不變 |
| v.reserve(n) | $O(n)$ | 一次搬完，之後就不用再搬 |
| 走訪一遍 | $O(n)$ | 三種寫法都一樣 |
| find(v.begin(), v.end(), x) | $O(n)$ | 沒排序就只能一個一個看（的主題） |
| s.length() | $O(1)$ | 跟 size() 是同一個東西 |
| s[i] | $O(1)$ | 回傳的是 char，不是長度 1 的字串 |
| s += x | 攤還 $O(1)$ | 就地加在尾端，跟 push_back 同一回事 |
| s = s + x | $O(n)$ ／次 | 先做出一個全新的字串再賦值。放在迴圈裡整體是 $O(n^2)$ |
| s.substr(pos, len) | $O(len)$ | 複製出一個新字串 |
| s.find(t) | 最差 $O(n \cdot m)$ | 逐位置比對；找不到回傳 string::npos |
| 你在 Python 寫 | C++ 寫成 | 差在哪 |
|---|---|---|
| a = [] | vector<int> a; | C++ 的容器要先講好裝什麼型別，而且只能裝那一種 |
| a = [0] * 5 | vector<int> a(5, 0); | — |
| a.append(x) | a.push_back(x); | 兩邊都是攤還 $O(1)$ |
| a.pop() | x = a.back(); a.pop_back(); | C++ 的 pop_back 不回傳值，要先 back() 拿 |
| a.insert(0, x) | a.insert(a.begin(), x); | C++ 吃的是 iterator，不是索引 |
| del a[0] | a.erase(a.begin()); | 同上，兩邊都是 $O(n)$ |
| len(a) | a.size() | C++ 回傳無號整數，跟 int 比大小會被警告 |
| a[1:3] | a.substr(1, 2)（string） vector<int> b(a.begin()+1, a.begin()+3); | C++ 沒有切片語法，要自己給起訖 |
| for x in a: | for (int x : a) | 要改到元素就寫 int& x |
| x in a | find(a.begin(), a.end(), x) != a.end() | 要 #include <algorithm> |
| a.sort() | sort(a.begin(), a.end()); | 兩邊都是 $O(n \log n)$ |
| b = a[:] | vector<int> b(a); | C++ 的 b = a 本來就是複製一整份，不是共用同一個物件 |
① 動尾巴便宜（push_back／pop_back／+=），動前面或中間就是 $O(n)$。
② size() 是住了幾個，capacity() 是有幾個位子；clear() 只清前者。
③ 知道要放幾個就先 reserve()，一次搬家都不會發生。
④ push_back 之後，之前記下來的 iterator 與指標都當作失效——記索引，不要記位址。
⑤ substr 的第二個參數是長度；find 找不到回傳 string::npos。
| 資源 | 看什麼 |
|---|---|
| cppreference · std::vector | 每個成員函式的完整規格，包括各操作會讓哪些 iterator 失效。 |
| cppreference · std::string | substr、find、npos 的精確定義。 |
| C++ Tutor | 把本頁的擴容範例貼進去單步跑，看記憶體真的被重新配置。 |
| 本站 · 演算法分析 | 用 <chrono> 實測本頁這張成本表。 |
| 本站 · 陣列與稀疏矩陣 | 理解 size 與 capacity 的差別，並以 reserve 減少不必要的重新配置。 |
每個選項都有解說：選錯也點開看看為什麼錯。全對之後再往下翻詞彙卡。
vector<int> v = {31, 17, 93};
v.insert(v.begin(), 54);
v.erase(v.begin() + 2);
for (int x : v) cout << x << " ";
vector<int> v = {1, 2, 3};
for (int x : v) x = x * 10;
for (int& y : v) y = y + 1;
for (int x : v) cout << x << " ";
vector<int> v(3, 7);
try {
cout << v.at(3) << endl;
} catch (out_of_range& e) {
cout << "caught" << endl;
}
cout << v.size() << endl;
vector<int> v = {1, 2, 3, 4};
auto before = v.capacity();
v.clear();
cout << v.size() << " " << (v.capacity() == before);
string s = "fool";
s += "s";
cout << s.substr(1, 2) << " " << s.find("ol") << " " << s.length();
先看正面術語，心中默想定義再翻面對答案；洗牌後再過一輪，直到每張都能不假思索說出來。