tags: 大一程設-下 東華大學 東華大學資管系 基本程式概念 資管經驗分享

進階 vector，疊代器與 insert / erase

• 進階 vector，疊代器與 insert / erase
  • vector 的 疊代器 Iterator
    • 宣告疊代器
    • begin & end
  • 進階的插入與刪除進 vector
    • 更重要的插入法 insert
    • 更重要的插入法 erase
  • Reference

vector 的 疊代器 Iterator

請注意!之所以教疊代器是因為想要教大家怎麼使用 insert 與 erase 去修改陣列元素，基本的 vector 取資料，用 at(i) 或是 [i] 就可以了哦，千萬不要用牛刀切小菜!

疊代器的概念對現在的各位而言有點困難，所以我不打算講清楚，但我會讓你們知道如何最基本的使用他們。

這邊需要有指標的知識你才會懂，我先把參考資料放旁邊，有興趣可以先去看，不想看或看不懂就先繼續往下~ -> 旁邊 -> 旁邊的旁邊(裡面說的向量其實就是 vector -> 旁邊的旁邊的旁邊

簡單的說，你可以想像疊代器就像一根指針，你可以告訴這個指針要指在你的陣列的哪裡，然後你可以透過一些技巧去取出那格位置的資料。

宣告疊代器

那你可能會納悶，我要如何透過程式來叫出這根指針呢? 對於 vector 來說，你可以建立一個 vector 專屬的指針，所以你必須宣告他。

vector<int>::iterator n;

:: 這個符號，你可以用中文的 的 去理解他，所以翻譯過來就是有一個名字叫 n 的疊代器他的型態是 vector<int>。

既然資料型態是 vector<int> 那這個 iterator 就只能指向 vector 且存的資料都必須是 int。

begin & end

而針對 vector 這個函式庫，他有提供幾個成員函式來讓你去移動你的指針，最常見的分別是 begin() 與 end()。

• begin()
  • 讓你把疊代器的指針指到陣列的第一個位置
• end()
  • 讓你把疊代器的指針指到陣列的最後一個位置的下一個位置

話以至此，來教如何使用吧!

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 的最後一個位置的下一個位置) 則迴圈會一直執行下去。
   • 最後的步進則是讓指針一直往下指。

你一定會納悶針對指針 ++ 是什麼概念，因為還沒學指標，這邊就先記著就對了。
你可以先記，針對一個指標做 ++，指針就會往下指下一個位置。

而 * 是什麼呢?
* 是用來取得指標所指向的位置所儲存的數值。

聽不懂吧!學過指標再回頭來看，或是先往下。 -> 指標傳送門
Orange

上面的程式碼，我們用圖來看會像這樣。

而在移動的那個箭頭，就是我們的 h。

那既然針對指針做 ++ 再用 * 號可以得到下一個位置的值，所以也可以對指針直接 +1 或 -1，+2 或 -2 摟?
沒錯!你答對了，我們可以先移動我們的指針，接著再取值(取值就是針對指標套用 * 號)!
Orange

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 種。我們這邊介紹比較常見的兩種。

有興趣歡迎這裡

• insert 1
  • vector_name.insert(開始插入的 iterator 位置, 數值)
• insert 2
  • vector_name.insert(開始插入的 iterator 位置，要插入的元素個數， 數值)

馬上來看看例子!

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 << ",";
    }
}

以上程式碼輸出如下:

更重要的插入法 erase

接著來介紹 erase!

• erase 1
  • vector_name.erase(欲消除元素的 iterator 位置)
• erase 2
  • vector_name.erase(要被消除的元素的首位 iterator 位置, 要被消除的元素的末位 iterator 位置(不包含最後一個))

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 的時候空間大小是怎麼變動的吧!

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;
}

所以可以知道 erase 只有刪除元素而已，但沒有改變 capacity 哦，所以你可以養成習慣做一次 shrink。

Reference

• C++ 迭代器 iterator
• Cplusplus - iterator