iT邦幫忙

1

【c++標準函式庫(STL)筆記】vector介紹

c++

今天學習c++裡面的vector工具,
感覺蠻實用的,筆記一下

vector簡介

vector是一個大小有彈性的陣列,
可以快速刪除或新增在尾端的元素,
若是插入或刪除不在後端的元素會較慢,
支援快速的隨機存取

一、引入函式庫

要使用map,需要在程式開頭加入這兩行

#include <vector>
using namespace std;

二、宣告

vector的宣告方式如下:

vector<T> myVector; //T填入你想要的型別,範例如下

宣告的同時初始化

初始化有以下幾種方式:

vector<int> v2(v1); //v2複製v1中的每個元素
vector<int> v2 = v1; //等同於vector<int> v2(v1);
vector<int> v3(10, 1); //v3有10個值為1的元素
vector<int> v4(10); //v4有10個元素,初始值未定
vector<int> v5{1, 2, 3, 4, 5}; //v5有5個元素,分別為1,2,3,4,5
vector<int> v5 = {1, 2, 3, 4, 5}; //等同於vector<int> v5{1, 2, 3, 4, 5};

宣告一個n*m的二維陣列,初始值為0

vector<vector<int>> arr(n, vector<int>(m,0));

三、存取元素

  • vec[i] (或寫vec.at(i))- 存取vector裡index為 i 的元素值。
  • vec.front() - 回傳 vector 第一個元素的值。
  • vec.back() - 回傳 vector 最後一個元素的值。

四、插入/刪除元素

  • vec.push_back() - 新增元素至 vector 的尾端。
  • vec.pop_back() - 刪除 vector 最尾端的元素。
  • vec.insert() - 插入一個或多個元素至 vector 內的任意位置。
  • vec.erase() - 刪除 vector 中一個或多個元素。
  • vec.clear() - 清空所有元素。

五、取得或改變vector大小

  • vec.empty() - 如果 vector 內部為空,則傳回 true 值,否則為false
  • vec.size() - 取得 vector 目前的元素個數。
  • vec.resize() - 改變 vector 目前的元素個數。

六、遍歷元素

有幾種方法拜訪vector內的元素

  1. 類似陣列用中括號取index
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector<int> arr= {2,4,6,8,10};
    for (int i = 0; i<arr.size(); i++) {
        cout << arr[i]<< endl;
    }
    return 0;
}

結果:
2
4
6
8
10

  1. 用迭代器
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector<int> arr= {2,4,6,8,10};
    for (auto it = arr.begin(); it != arr.end(); it++) {
        cout << *it << endl;
    }
    return 0;
}

結果:
2
4
6
8
10

  1. 用代表範圍的冒號(自c++11標準後可以用,個人覺得很像python的for...in語法)
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector<int> arr= {2,4,6,8,10};
    for (int i : arr) {
        cout << i << endl;
    }
    return 0;
}

結果:
2
4
6
8
10

補充: 反向迭代器

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector<int> arr= {2,4,6,8,10};
    for (auto it = arr.rbegin(); it < arr.rend(); it++) {
        cout << *it << endl;
    }
    return 0;
}

結果:
10
8
6
4
2

練習題- Leetcode26. Remove Duplicates from Sorted Array

參考題目: Leetcode26. Remove Duplicates from Sorted Array

題意:
給定一個排序過的陣列,例如nums = [0,0,1,1,1,2,2,3,3,4]
去除重複的元素並回傳新的長度。
例如本範例的結果為: nums=[0,1,2,3,4],回傳新長度5

函數型式: int removeDuplicates(vector<int>& nums);
題目分析: 其實題目的邏輯不難,但因需要在原地修改vector,可以很好的練習c++ vector函數操作

思路: 因為陣列是排序過的,所以重複的元素一定會相鄰,只要檢查元素與上一個元素是相同的就刪除即可
以下分享幾個容易寫錯的程式:

<錯誤程式碼一>,不是每次都要推進迭代器

int removeDuplicates(vector<int>& nums) {
    if(nums.size()==0)
        return 0; //若vector本身為空,直接回傳0
    vector<int>::iterator it = nums.begin();
    int n=nums[0]; //記錄vector的第一個元素
    for(it=it+1;it!=nums.end();it++){
        if(*it==n){
            it=nums.erase(it); //錯誤: 迭代器刪除後會指向下一個元素,故在for迴圈內不要it++
        }
        else{
            n=*it;
        }
    }
    return nums.size();    
}

若刪除了一個迭代器,
it=nums.erase(it);便會指向下一個元素,
如果在for迴圈再做it++的話,
便會再跳過一個元素

<正確程式碼>

int removeDuplicates(vector<int>& nums) {
    if(nums.size()==0)
        return 0; //若vector本身為空,直接回傳0
    vector<int>::iterator it = nums.begin();
    int n=nums[0]; //記錄vector的第一個元素
    for(it=it+1;it!=nums.end();){
        if(*it==n){
            it=nums.erase(it);
        }
        else{
            n=*it;
            it++; //若沒有刪除元素,才需要推進迭代器
        }
    }
    return nums.size();    
}

<錯誤程式碼二>,先儲存end()回傳的迭代器

還有一個比較不容易發現問題的錯誤版本,
便是嘗試先儲存以end()回傳的迭代器。

int removeDuplicates(vector<int>& nums) {
    if(nums.size()==0)
        return 0; //若vector本身為空,直接回傳0
    vector<int>::iterator it = nums.begin();
    int n=nums[0]; //記錄vector的第一個元素
    vector<int>::iterator end_it = nums.end();
    for(it=it+1;it!=end_it;){
        if(*it==n){
            it=nums.erase(it);
        }
        else{
            n=*it;
            it++; //若沒有刪除元素,才需要推進迭代器
        }
    }
    return nums.size();    
}

本程式跟正解程式僅僅差在將for(it=it+1;it!=nums.end();)拆成
vector<int>::iterator end_it = nums.end();
for(it=it+1;it!=end_it;) 兩行來寫,
乍看之下好像意思完全一樣,
但事實上如果我們對vector新增或刪除元素,
原先end()所回傳的元素便會無效化,
故需要每次做for迴圈迭代時都重新產生新的nums.end()做為條件判斷

參考資料

  1. Mr. Opengate. C/C++ - Vector (STL) 用法與心得完全攻略
  2. cplusplus.com- vector

尚未有邦友留言

立即登入留言