一、vector 的基礎(chǔ)遍歷與迭代器這個函數(shù)只做一件事把同一個 vector 用五種方式讀出來/改出來借此展示 C 容器的各種訪問接口。void test01() { vectorint v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); // ① 下標訪問 for (size_t i 0; i v1.size(); i) cout v1[i] ; cout endl; // ② 正向迭代器 vectorint::iterator it1 v1.begin(); while (it1 ! v1.end()) { cout *it1 ; it1; } cout endl; // ③ 范圍 for引用可改值 for (auto a : v1) { a; } cout endl; // ④ 反向迭代器 vectorint::reverse_iterator it2 v1.rbegin(); while (it2 ! v1.rend()) { cout *it2 ; it2; } cout endl; // ⑤ 只讀 const_iterator vectorint::const_iterator it3 v1.begin(); while (it3 ! v1.end()) { //--(*it3); cout *it3 ; it3; } cout endl; }準備構(gòu)造一個 vectorvectorint v1;是默認構(gòu)造得到一個空的動態(tài)數(shù)組size 0、capacity 0底層還沒分配任何元素空間。v1.push_back(1..4)連續(xù)在尾部追加 4 個元素此時v1內(nèi)是{1,2,3,4}。push_back是 vector 最常用的寫操作專門在末尾追加——因為 vector 是一個連續(xù)內(nèi)存的數(shù)組尾部追加最快。① 下標訪問v1[i]v1[i]調(diào)用的是operator[]按下標直接定位到第 i 個元素時間復雜度 O(1)。關(guān)鍵陷阱operator[]不做越界檢查。i 超出size不會報錯而是未定義行為可能讀到垃圾值或崩潰。想安全訪問應該用v1.at(i)越界會拋std::out_of_range。返回的是引用所以既能讀也能寫v1[i] 99是合法的。v1.size()返回類型是size_t無符號整數(shù)所以循環(huán)下標也用size_t i避免符號/無符號比較的告警。② 正向迭代器begin() / end()迭代器是 STL 的核心概念能指向容器中的某個元素并支持*解引用取值、前進到下一個、!比較是否相等。begin()指向第一個元素end()指向最后一個元素的下一個位置叫哨兵/尾后迭代器。這是一個半開區(qū)間[begin, end)。循環(huán)條件it1 ! v1.end()判斷還沒走到末尾it1讓迭代器前進一位。*it1解引用得到元素本身。這里只讀輸出1 2 3 4。為什么要用迭代器而不是下標因為迭代器對所有容器通用list、map、set 都能用而下標只對支持隨機訪問的容器可用。學 STL 就要習慣用迭代器而不是下標去遍歷。③ 范圍 for范圍 for 是 C11 引入的語法糖本質(zhì)就是把迭代器遍歷包裝成更簡潔的寫法等價于上面的while循環(huán)。這里的auto a是引用a是容器里每個元素的別名所以a會直接修改容器里的值。執(zhí)行后 v1 變成{2,3,4,5}。如果寫成for (auto a : v1)沒有那a只是每個元素的拷貝a改的是副本容器不變。這是想改值必須用的最典型場景。只想讀、不想改時寫成for (const auto a : v1)更安全、也更省拷貝。注意此處cout endl只是打一個換行沒有輸出內(nèi)容。④ 反向迭代器rbegin() / rend()反向迭代器讓從尾部往前遍歷變得和正向一樣自然。rbegin()指向最后一個元素反向意義上的 beginrend()指向第一個元素之前反向哨兵。區(qū)間仍是[rbegin, rend)只是方向反了。it2在反向迭代器上意味著向容器頭部移動。在 v1 已被改成{2,3,4,5}后反向輸出是5 4 3 2。反向迭代器用起來和普通迭代器幾乎一樣唯一的心理落差是居然在倒退。這是它最重要的記憶點。⑤ 只讀const_iteratorconst_iterator解引用后得到const 引用只能讀、不能寫。被注釋的--(*it3)如果放開會編譯報錯——因為*it3是 const 的不允許自減。編譯器在編譯期就攔住了這類誤寫。有意思的是即使v1本身不是 const 對象你也可以顯式用const_iterator強制只讀遍歷作為紀律性的手段。此時 v1 是{2,3,4,5}只讀輸出仍是2 3 4 5。同一個 vector五種視角示意2345begin()end()→rbegin()←rend()v1[2] → 4下標[]、正向迭代器、范圍for、反向迭代器、const_iterator 五種方式都在這條連續(xù)內(nèi)存上工作示意非精確布局vector 的元素存放在一段連續(xù)內(nèi)存里五種訪問方式只是視角不同小結(jié)遍歷方式本身不難真正要記住的是三個區(qū)別——下標無越界檢查、范圍 for 想改值必須用引用、const_iterator 只讀。二、構(gòu)造、擴容、insert 與 erase這個函數(shù)在演示三件事用個數(shù)值構(gòu)造 vector、觀察 capacity 是怎么翻倍增長的、以及insert/erase怎么在中間增刪元素。void test02() { vectorint v1(10, 2); for (size_t i 0; i v1.size(); i) cout v1[i] ; cout endl; vectorsize_t v2; size_t old v2.capacity(); cout old endl; // 0 for (size_t i 0; i 100; i) { v2.push_back(i); if (old ! v2.capacity()) { old v2.capacity(); cout old endl; } } v2.insert(v2.begin(), 1000); // 頭插 v2.insert(v2.begin(), 10); for (auto a : v2) cout a ; cout endl; v2.insert(v2.begin() 8, 10); // 任意位置插 for (auto a : v2) cout a ; cout endl; size_t x; cin x; auto it find(v2.begin(), v2.end(), x); if (it ! v2.end()) v2.insert(it, 10000); for (auto a : v2) cout a ; cout endl; size_t t; cin t; it find(v2.begin(), v2.end(), t); if (it ! v2.end()) v2.erase(it); for (auto a : v2) cout a ; cout endl; }①vectorint v1(10, 2)fill 構(gòu)造這是 vector 的填充構(gòu)造函數(shù)第一個參數(shù)是元素個數(shù)第二個是每個元素的初值。這里得到 10 個值全部為 2 的元素。如果只寫vectorint v1(10)那就是 10 個元素初值為該類型的默認值int 為 0。注意它和vectorint v1{10, 2}的區(qū)別大括號是列表初始化會解釋成兩個元素10 和 2。小括號才是個數(shù) 值。這是新手最容易踩的坑。② capacity 與擴容機制核心中的核心先厘清兩個概念size()是當前實際元素個數(shù)capacity()是當前已分配的內(nèi)存能容納的元素個數(shù)。后者是預留容量兩者常常不相等?？?vector 的 capacity 為 0所以第一次打印 old 是0。循環(huán)里連續(xù)push_back100 次每次檢查 capacity 是否變化在vs里面第一次是二倍擴容后面都是1.5倍擴容。這個翻倍增長就是 vector 高效的原因之一push_back的均攤時間復雜度是 O(1)——雖然擴容一次要搬動所有元素O(n)但擴容次數(shù)少log n 次均攤下來每次追加幾乎都是常數(shù)時間。擴容的內(nèi)部步驟① 申請一塊更大的新數(shù)組 → ② 把舊元素逐個拷貝/移動過去 → ③ 釋放舊數(shù)組 → ④ 更新_ptr、_size、_capacity。每次擴容都會讓所有迭代器/引用/指針失效。擴容四步示意以 capacity 2 → 4 為例舊數(shù)組(cap2)AB① 申請更大的新數(shù)組(cap4)????②③④ 拷貝舊元素 釋放舊數(shù)組 更新指針ABCD示意擴容 申請新內(nèi)存 搬運舊元素 釋放舊內(nèi)存A/B 是原有元素C/D 是剛 push 進去的新元素vs下的擴容:Linux下的擴容③ 頭插insertinsert(pos, val)把val插到迭代器pos指向的位置之前。v2.begin()是頭部所以兩次insert(begin(), …)都是頭插先插 1000 再插 10最終 10 在最前面、1000 在第二位。代價頭部插入會讓后面所有元素整體后移復雜度 O(n)。在 vector 里頻繁頭插是非常低效的——這種場景應該用deque或list。插入前 vector 已有 100 個元素0..99。④ 任意位置插入insertv2.begin() 8用到了迭代器的隨機訪問能力vector 的迭代器是隨機訪問迭代器支持n。對 list/set 就不能這么寫。把 10 插到當前第 8 個元素之前同樣是 O(n) 的搬移代價。擴容的連帶作用如果插入導致size撞上capacity會先觸發(fā)一次擴容之前拿到的begin()等迭代器會失效。⑤findinsert按值定位再插入std::find(begin, end, x)來自algorithm在[begin,end)里線性查找第一個等于x的元素返回指向它的迭代器找不到就返回end()。所以if (it ! v2.end())是在判斷找到了。v2.insert(it, 10000)把 10000 插到找到的那個元素之前。注意find是線性掃描 O(n)insert也是 O(n)。⑥erase刪除指定位置的元素v2.erase(it)把迭代器指向的那個元素刪掉后面的元素整體前移size減 1。capacity不會因 erase 而縮小——刪除只是邏輯上減少元素底層內(nèi)存還留著。迭代器失效erase之后被刪位置及其之后的迭代器/引用/指針都失效了不要繼續(xù)用它們。想一次刪多個可用erase(it1, it2)區(qū)間版本。同樣的if (it ! v2.end())保護找不到就不刪。? 重要提醒insert/erase以及觸發(fā)擴容后舊迭代器會失效。這是 C 里最常見的懸空引用事故源頭——用完舊的it前千萬別先 insert/erase。另外find只做線性查找別在大數(shù)據(jù)量下期望它很快。三、emplace_back 與 push_back 的差異這個函數(shù)通過一個會打印構(gòu)造痕跡的結(jié)構(gòu)體 A直觀展示push_back和emplace_back在拷貝次數(shù)上的差別。先看結(jié)構(gòu)體 Astruct A { A(int a 0, int b 0) : _a(a), _b(b) { cout A(int,int) endl; } A(const A a) { _a a._a; _b a._b; cout A(const A) endl; } int _a, _b; };構(gòu)造函數(shù)帶默認參數(shù)(int a0, int b0)并用成員初始化列表:_a(a), _b(b)初始化兩個成員。初始化列表比在函數(shù)體里賦值更高效、更規(guī)范?？截悩?gòu)造函數(shù)A(const A)手動逐個成員拷貝并在里面打印一行標記。這行打印就是為了讓我們?nèi)庋劭匆娍截惏l(fā)生了幾次——是這段代碼的觀察工具。因為是struct成員_a/_b默認公有外面能直接訪問。注意這個 A 沒有定義移動構(gòu)造函數(shù)所以后面出現(xiàn)的移動都會退化成調(diào)用拷貝構(gòu)造。主體void test03() { // 對 int 而言 push_back / emplace_back 完全等價 vectorint v1; v1.push_back(1); vectorint v2; v2.emplace_back(1); vectorA v3; A aa1(3, 3); v3.push_back(aa1); // ① 左值 → 拷貝構(gòu)造 1 次 v3.push_back(A(3, 3)); // ② 臨時對象 → 構(gòu)造1次 拷貝1次 v3.push_back({ 3,3 }); // ③ 列表初始化臨時 → 構(gòu)造1次 拷貝1次 vectorA v4; A aa2(3, 3); v4.emplace_back(aa2); // ④ 傳左值 → 仍是拷貝 1 次 v4.emplace_back(A(3, 3)); // ⑤ 傳臨時 → 構(gòu)造拷貝 v4.emplace_back(3, 3); // ⑥ 直接傳構(gòu)造參數(shù) → 就地構(gòu)造0 拷貝 ? // 迭代器解引用用 - 訪問成員 vectorA::iterator it1 v3.begin(); while (it1 ! v3.end()) { cout it1-_a : it1-_b endl; it1; } // C11 范圍 for用 . 訪問成員 for (auto e1 : v3) cout e1._a : e1._b endl; // C17 結(jié)構(gòu)化綁定 for (auto [x, y] : v4) cout x : y endl; }核心對比push_back vs emplace_back兩者都是尾部插入唯一的區(qū)別是怎么把元素放進容器push_back接受一個已經(jīng)構(gòu)造好的對象左值或臨時對象把它拷貝/移動進容器。也就是說它需要先構(gòu)造、再拷貝兩步。emplace_back接受的是構(gòu)造函數(shù)的參數(shù)在容器已分配的內(nèi)存里就地構(gòu)造對象——少了一次拷貝/移動。所以代碼里的⑥v4.emplace_back(3,3)是最高效的直接把 3、3 傳給 A 的構(gòu)造函數(shù)只構(gòu)造一次、零拷貝就是注釋里寫的效率更高傳構(gòu)造 A 的參數(shù)。但是①④ 傳的是左值對象aa1/aa2無論 push 還是 emplace 都免不了拷貝——因為對象已經(jīng)存在必須復制一份進容器。②③⑤ 傳臨時對象也類似。一句話總結(jié)emplace 只有在直接傳構(gòu)造參數(shù)時才真正省一次拷貝如果你手里已經(jīng)有一個對象要放進去兩者區(qū)別不大。構(gòu)造流程對比示意push_back(3,3) 做不到——必須給對象臨時 A(3,3)→ 拷貝容器里的 A先構(gòu)造、再拷貝 2 次動作emplace_back(3,3) 直接給參數(shù)就地構(gòu)造 A(3,3)→ 直接放進容器里的 A只構(gòu)造 1 次0 拷貝關(guān)鍵emplace 的優(yōu)勢只在你直接傳構(gòu)造參數(shù)時才體現(xiàn)emplace_back 在容器內(nèi)就地構(gòu)造省掉一次拷貝/移動三種讀對象的方式迭代器 -it1-_a。因為迭代器解引用后得到對象-等價于(*it1)._a這是迭代器習慣的寫法。范圍 for .for (auto e1 : v3)里e1直接就是對象引用所以用點號e1._a。C17 結(jié)構(gòu)化綁定for (auto [x, y] : v4)把每個 A 的_a、_b直接解構(gòu)到x、y兩個變量上。它是 C17 的新語法要求類型所有非靜態(tài)成員都是公有的、且無基類并按聲明順序綁定。A恰好滿足所以能編譯。被注釋的auto [x,y] aa1;同理。三種寫法都能用日常最推薦范圍 for要同時拿多個字段就上結(jié)構(gòu)化綁定。小結(jié)emplace_back 的省拷貝只在直接傳構(gòu)造參數(shù)時成立讀取對象的三種方式-、.、結(jié)構(gòu)化綁定只是語法差異本質(zhì)都是訪問同一個對象。④ 楊輝三角C 版vectorvectorint用二維動態(tài)數(shù)組實現(xiàn)楊輝三角展示vectorvectorint怎么充當二維數(shù)組。class Solution { public: vectorvectorint generate(int numRows) { vectorvectorint vv; vv.resize(numRows, vectorint()); // 外層先開 numRows 行空 vector for (size_t i 0; i numRows; i) vv[i].resize(i 1, 1); // 第 i 行 resize 成 i1 個元素全置 1 for (size_t i 2; i numRows; i) { for (size_t j 1; j i; j) // ? 邊界細節(jié)見下文 vv[i][j] vv[i - 1][j] vv[i - 1][j - 1]; } return vv; } };① 理解vectorvectorint是什么外層 vector 的每個元素又是一個vectorint。也就是說vv是一個裝了很多個一維數(shù)組的數(shù)組。vv[i]得到第 i 行的那個一維 vectorvv[i][j]再取這行的第 j 個元素——語法上和二維數(shù)組一模一樣。但它是動態(tài)的每行長度可以不同。普通二維數(shù)組int a[n][n]必須每行等長而楊輝三角每行長度是i1天然適合vectorvector。② 兩遍 resize先建骨架再填值vv.resize(numRows, vectorint())把外層擴容到 numRows 行每行暫時是一個空的vector。vv[i].resize(i 1, 1)把第 i 行擴成i1個元素全部初始化為 1。因為楊輝三角每行兩端本來就是 1所以先把整行鋪滿 1邊界就不需要再單獨處理。于是現(xiàn)在vv已經(jīng)是一張邊緣全是 1 的三角形骨架只剩中間的數(shù)字要填。③ 遞推填數(shù)楊輝三角的核心遞推式vv[i][j] vv[i-1][j] vv[i-1][j-1]即當前數(shù) 左上 正上。從i 2開始前兩行全 1不用算對第 i 行內(nèi)部j 1 … i逐個覆蓋。復雜度 O(n2)因為要填滿整個三角形共n(n1)/2個元素空間也是 O(n2)。⑤ 楊輝三角C 風格int** malloc同一個問題換到 C 語言沒有容器得自己用二級指針 動態(tài)內(nèi)存分配手工搭一個二維數(shù)組。int** generate(int numRows, int* returnSize, int** returnColumnSizes) { // ① 建空間先開行指針數(shù)組再給每行開數(shù)組 int** aa (int**)malloc(sizeof(int*) * numRows); for (size_t i 0; i numRows; i) aa[i] (int*)malloc(sizeof(int) * (i 1)); // ② 設置返回參數(shù) *returnSize numRows; *returnColumnSizes (int*)malloc(sizeof(int) * numRows); for (int i 0; i numRows; i) (*returnColumnSizes)[i] i 1; // ③ 填數(shù)兩端置 1中間遞推 for (int i 0; i numRows; i) for (int j 0; j i; j) { if (i j || j 0) aa[i][j] 1; else aa[i][j] aa[i - 1][j] aa[i - 1][j - 1]; } return aa; }① 用int**模擬二維數(shù)組C 里沒有 vector最接近的二維數(shù)組就是二級指針int**aa是一個指針的指針。結(jié)構(gòu)是aa指向一塊存放 int* 指針的數(shù)組其中aa[i]又指向第 i 行的int 數(shù)組頭。所以aa[i][j]等價于*(*(aai)j)。malloc分配原始內(nèi)存第一句給行指針數(shù)組開numRows個int*循環(huán)里給每一行開i1個int。這正好對應 C 版的兩遍 resize。(int**)malloc(...)是 C 風格強制轉(zhuǎn)換。嚴格說malloc返回void*C 里可以不轉(zhuǎn)但int**的寫法在混編/可讀性上更清晰。② 用指針帶出多個返回值C 函數(shù)只能返回一個值但這里調(diào)用方需要三樣信息行數(shù)、每行長度、數(shù)據(jù)本身。于是用輸出參數(shù)解決returnSize行數(shù)指針、returnColumnSizes每行長度的數(shù)組。*returnSize numRows;把行數(shù)寫進調(diào)用者提供的 int 變量。*returnColumnSizes (int*)malloc(...)先分配一個記錄每行長度的 int 數(shù)組然后(*returnColumnSizes)[i] i1逐行記錄。注意括號優(yōu)先級(*returnColumnSizes)[i]是先解引用、再下標如果漏掉括號寫成*returnColumnSizes[i]含義就完全不同了先下標再解引用。這是 C 里很經(jīng)典的一個坑。③ 邊界處理與 C 版的對照C 版顯式用if (ij || j0) aa[i][j] 1;處理兩端中間才遞推——邊界完全正確不會像 C 版那樣越界。對比價值C 版靠resize(i1, 1)把邊界預置成 1更省心但容易在循環(huán)邊界上出問題C 版全手動繁瑣但每一步都顯式。C 版的代價所有內(nèi)存都要自己管理——用完要逐行free(aa[i])再free(aa)、free(*returnColumnSizes)漏一個就內(nèi)存泄漏。C 版vector析構(gòu)時自動全部釋放。這也是為什么現(xiàn)代 C 更推薦vector而不是裸指針 malloc的最好例子同樣的邏輯C 更安全、更不易錯。aa 指向一組行指針每個 aa[i] 指向一行的 int 數(shù)組——這就是 C 版二維數(shù)組⑥ 總結(jié)一份知識點清單話題要點一句話記憶遍歷下標 []、迭代器 begin/end、范圍 for、反向迭代器、const_iterator想改值用想只讀用const auto下標越界operator[] 不檢查越界是未定義行為安全用 at()[] 快但野at() 慢但穩(wěn)擴容capacity 約 2 倍增長擴容新內(nèi)存搬運釋放更新push_back 均攤 O(1)insert/erase中間插入刪除都是 O(n)會搬移元素會失效迭代器別再碰舊迭代器emplace vs pushemplace 直接傳構(gòu)造參數(shù)就地構(gòu)造省一次拷貝手里有對象用 push有參數(shù)用 emplace二維容器vectorvectorint 每行可變長注意內(nèi)層循環(huán)的邊界j 別越到 iC 風格二維int** malloc用輸出參數(shù)帶返回值手動 free括號優(yōu)先級 ( *p )[i]記得逐行 freevector 本質(zhì)封裝 _ptr/_size/_capacity 的動態(tài)數(shù)組三個量看懂容器就懂了練習建議把test01里auto改成auto觀察值變不變體會引用的作用。打印擴容前后的begin()地址親眼看看擴容后舊迭代器指向的內(nèi)存是否已被釋放。