--- GA: G-RZYLL0RZGV --- ###### tags: `大一程設-下` `東華大學` `東華大學資管系` `基本程式概念` `資管經驗分享` 進階 vector,疊代器與 insert / erase === [TOC] ## vector 的 疊代器 Iterator <span style="color:green">**請注意!之所以教疊代器是因為想要教大家怎麼使用 insert 與 erase 去修改陣列元素,基本的 vector 取資料,用 `at(i)` 或是 `[i]` 就可以了哦,千萬不要用牛刀切小菜!**</span> 疊代器的概念對現在的各位而言有點困難,所以我不打算講清楚,但我會讓你們知道如何最基本的使用他們。 這邊需要有指標的知識你才會懂,我先把參考資料放旁邊,有興趣可以先去看,不想看或看不懂就先繼續往下~ -> [旁邊](https://dd654321.pixnet.net/blog/post/80880065-%5Bc-c%2B%2B%5D-vector%E7%B0%A1%E6%98%93%E7%94%A8%E6%B3%95) -> [旁邊的旁邊(裡面說的向量其實就是 vector](https://crmne0707.pixnet.net/blog/post/318479072-c%2B%2B-%E8%BF%AD%E4%BB%A3%E5%99%A8-iterator) -> [旁邊的旁邊的旁邊](https://www.itread01.com/content/1546712044.html) 簡單的說,你可以想像疊代器就像一根指針,你可以告訴這個指針要指在你的陣列的哪裡,然後你可以透過一些技巧去取出那格位置的資料。 ### 宣告疊代器 那你可能會納悶,我要如何透過程式來叫出這根指針呢? 對於 vector 來說,你可以建立一個 vector 專屬的指針,所以你必須宣告他。 ```cpp= vector<int>::iterator n; ``` `::` 這個符號,你可以用中文的 `的` 去理解他,所以翻譯過來就是有一個名字叫 n 的疊代器他的型態是 `vector<int>`。 既然資料型態是 `vector<int>` 那這個 iterator 就只能指向 vector 且存的資料都必須是 int。 ### begin & end 而針對 vector 這個函式庫,他有提供幾個成員函式來讓你去移動你的指針,最常見的分別是 `begin()` 與 `end()`。 * `begin()` * 讓你把疊代器的指針指到陣列的第一個位置 * `end()` * 讓你把疊代器的指針指到陣列的最後一個位置的<span style="color:red">**下一個位置**</span> 話以至此,來教如何使用吧! ```cpp= int main(){ vector<int> a; vector<int>::iterator h; for(int i = 0; i < 10; i++){ a.push_back(i); } for(h = a.begin(); h != a.end(); h++){ cout << *h; } return 0; } ``` 1. 一開始的時候我們宣告了一個 `vector<int>` 名為 a,跟一個只能拿來指 `vector<int>` 的一個 iterator 叫做 h。 2. 接著我們 push 10 個元素進到 vector 裡面。 3. 再來說明第七行的這個迴圈 * 初值我們設定 h 指向 `a.begin()`,所以把 `a.begin()` assign 給 h。 * 中間的條件則是,若 h 指的地方還不是 a 的 end (也就是 a 的最後一個位置的下一個位置) 則迴圈會一直執行下去。 * 最後的步進則是讓指針一直往下指。 > 你一定會納悶針對指針 ++ 是什麼概念,因為還沒學指標,這邊就先記著就對了。 > 你可以先記,針對一個指標做 ++,指針就會往下指下一個位置。<br> > 而 `*` 是什麼呢? > `*` 是用來取得指標所指向的位置所儲存的數值。<br> > 聽不懂吧!學過指標再回頭來看,或是先往下。 -> [指標傳送門](https://hackmd.io/@ndhu-programming-2021/ryreRN0TF) > [name=Orange] 上面的程式碼,我們用圖來看會像這樣。 <span style="color:red">**而在移動的那個箭頭,就是我們的 h。**</span> ![](https://i.imgur.com/OgpOZ2p.gif) > 那既然針對指針做 ++ 再用 `*` 號可以得到下一個位置的值,所以也可以對指針直接 +1 或 -1,+2 或 -2 摟? > 沒錯!你答對了,我們可以先移動我們的指針,接著再取值(取值就是針對指標套用 `*` 號)! > [name=Orange] ```cpp= int main(){ vector<int> a; vector<int>::iterator h; for(int i = 0; i < 10; i++){ a.push_back(i); } for(h = a.begin(); h != a.end(); h++){ cout << *h; } cout << endl; cout << *(h-1) << endl; //印出 9 cout << *(h-2) << endl; //印出 8 cout << *(h-3) << endl; //印出 7 return 0; } ``` 希望到了這邊,你能夠對 iterator 有基本的了解,那接下來就要來說明如何透過 iterator 使用 insert 還有 erase 來做插入跟刪除摟! ## 進階的插入與刪除進 vector ### 更重要的插入法 insert insert 跟 erase 也是 vector 的成員函式,所以要想使用他們,必須透過 vector 陣列來呼叫他們。 那針對 insert 這個 function,vector 有多種 overloading function。一共有 5 種。我們這邊介紹比較常見的兩種。 [有興趣歡迎這裡](https://www.cplusplus.com/reference/vector/vector/insert/) * insert 1 * `vector_name.insert(開始插入的 iterator 位置, 數值)` * insert 2 * `vector_name.insert(開始插入的 iterator 位置,要插入的元素個數, 數值)` 馬上來看看例子! ```cpp= int main(){ vector<int> a; vector<int>::iterator h; for(int i = 0; i < 5; i++){ a.push_back(i); } // 目前陣列內是 0,1,2,3,4 // insert 1 a.insert(a.begin(), 3); // 變成 3,0,1,2,3,4 a.insert(a.begin()+3, 8); // 變成 3,0,1,8,2,3,4 //insert 2 a.insert(a.begin()+4, 3, 5); // 變成 3,0,1,8,5,5,5,2,3,4 // 以下兩種方式都能夠遍歷 vector // 單純依靠 size 跟索引值 cout << "traversal 1: "; for(int i = 0; i < a.size(); i++){ cout << a[i] << ","; } cout << endl; cout << "traversal 2: "; // 利用 iterator for(h = a.begin(); h != a.end(); h++){ cout << *h << ","; } } ``` 以上程式碼輸出如下: ![](https://i.imgur.com/yc91v6l.png) ### 更重要的插入法 erase 接著來介紹 erase! * erase 1 * `vector_name.erase(欲消除元素的 iterator 位置)` * erase 2 * `vector_name.erase(要被消除的元素的首位 iterator 位置, 要被消除的元素的末位 iterator 位置(不包含最後一個))` ```cpp= int main(){ vector<int> a({1,2,3,4,5,6,7,8,9}); vector<int>::iterator h; a.erase(a.begin()); // 剩下 {2,3,4,5,6,7,8,9} a.erase(a.begin()+3); // 剩下 {2,3,4,6,7,8,9} a.erase(a.begin()+2, a.end()-2); // 剩下{2,3,8,9} for(h = a.begin(); h != a.end(); h++){ cout << *h << ","; } return 0; } ``` 如果到這邊都沒問題,那再結合前面的 size、capacity 來看看 erase 的時候空間大小是怎麼變動的吧! ```cpp= int main(){ vector<int> a({1,2,3,4,5,6,7,8,9}); vector<int>::iterator h; cout << "size:" << a.size() << ", capacity:" << a.capacity() << endl; a.erase(a.begin()); // 剩下 {2,3,4,5,6,7,8,9} cout << "size:" << a.size() << ", capacity:" << a.capacity() << endl; a.erase(a.begin()+3); // 剩下 {2,3,4,6,7,8,9} cout << "size:" << a.size() << ", capacity:" << a.capacity() << endl; a.erase(a.begin()+2, a.end()-2); // 剩下{2,3,8,9} cout << "size:" << a.size() << ", capacity:" << a.capacity() << endl; for(h = a.begin(); h != a.end(); h++){ cout << *h << ","; } cout << endl; a.shrink_to_fit(); cout << "size:" << a.size() << ", capacity:" << a.capacity() << endl; return 0; } ``` ![](https://i.imgur.com/BECHcGG.png) 所以可以知道 erase 只有刪除元素而已,但沒有改變 capacity 哦,所以你可以養成習慣做一次 shrink。 ## Reference * [C++ 迭代器 iterator](https://crmne0707.pixnet.net/blog/post/318479072-c%2B%2B-%E8%BF%AD%E4%BB%A3%E5%99%A8-iterator) * [Cplusplus - iterator](https://www.cplusplus.com/reference/iterator/)