[C++] 程式設計教學：向量 (Vector)

前言

此處的向量是 C++ 標準函式庫中的動態陣列 (dynamic array)，而非數學上的向量。陣列 (array) 是一種連續、線性的容器，主要的優勢在於隨機存取的時間為 O(1) (常數時間)。

C++ 有三種陣列：

• C 陣列
• std::array 物件
• std::vector 物件

本文介紹 std::vector 物件，前兩種陣列已經在前文介紹過。向量和陣列儲存資料的方式相同，但向量可動態增減長度而陣列不行。

建立向量

使用以下語法宣告及初始化向量：

std::vector<int> v = { 3, 4, 5, 6, 7 };

由於向量的長度可動態改變，不需預先宣告其容量。

也可以先宣告空向量後，再逐一推入元素：

#include <vector>

int main(void)
{
    std::vector<int> v = {};

    v.push_back(3);
    v.push_back(4);
    v.push_back(5);
    v.push_back(6);
    v.push_back(7);

    return 0;
}

存取向量元素

取得向量中頭尾端元素

向量的方法 .front() 可以存取 (但不移出) 向量頭端的元素。方法 .back() 可以存取 (但不移出) 尾端的元素。以下是範例：

#include <cassert>
#include <iostream>
#include <vector>

int main(void)
{
    std::vector<int> v = {3, 4, 5, 6, 7};

    assert(v.front() == 3);
    assert(v.back() == 7);

    return 0;
}

取得向量中任意位置元素

使用陣列下標可存取任意位置的元素：

#include <cassert>
#include <vector>

int main(void)
{
    std::vector<int> v = { 3, 4, 5, 6, 7 };

    assert(v[0] == 3);
    assert(v[2] == 5);
    assert(v[4] == 7);

    return 0;
}

也可以使用方法 .at() 來存取任意位置的元素：

#include <cassert>
#include <vector>

int main(void)
{
    std::vector<int> v = { 3, 4, 5, 6, 7 };

    assert(v.at(0) == 3);
    assert(v.at(2) == 5);
    assert(v.at(4) == 7);

    return 0;
}

修改向量中位意任置元素

承上，陣列下標也可用來修改元素：

#include <cassert>
#include <vector>

int main(void)
{
    std::vector<int> v = { 3, 4, 5, 6, 7 };

    assert(v[0] == 3);
    assert(v[2] == 5);
    assert(v[4] == 7);

    v[2] =  99;

    assert(v[0] == 3);
    assert(v[2] == 99);
    assert(v[4] == 7);

    return 0;
}

同理，向量的方法 .at() 也可用來修改元素：

#include <cassert>
#include <vector>

int main(void)
{
    std::vector<int> v = { 3, 4, 5, 6, 7 };

    assert(v.at(0) == 3);
    assert(v.at(2) == 5);
    assert(v.at(4) == 7);

    v.at(2) = 99;

    assert(v.at(0) == 3);
    assert(v.at(2) == 99);
    assert(v.at(4) == 7);

    return 0;
}

走訪向量

使用計數器走訪向量

最基本的方式是使用計數器 (counter) 來走訪向量：

#include <cstddef>
#include <iostream>
#include <vector>

int main(void)
{
    std::vector<int> v = {3, 4, 5, 6, 7};

    for (size_t i = 0; i < v.size(); i++) {
        std::cout << v.at(i) << std::endl;
    }

    return 0;
}

能夠使用計數器的前提是向量下標是遞增的自然數。不一定每種資料結構都能用計數器，其通用性較差。

使用 for 迴圈走訪向量

另外一種方是使用 for 迴圈來走訪向量：

#include <iostream>
#include <vector>

int main(void)
{
    std::vector<int> v = {3, 4, 5, 6, 7};

    for (auto i : v) {
        std::cout << i << std::endl;
    }

    return 0;
}

使用 for 迴圈的好處在於不用知道向量的結構。但使用 for 迴圈時不能修改向量元素。

使用迭代器走訪向量

另一種方是使用迭代器 (iterator) 來走訪向量：

#include <iostream>
#include <vector>

int main(void)
{
    std::vector<int> v = {3, 4, 5, 6, 7};

    for (auto iter = v.begin(); iter != v.end(); iter++) {
        std::cout << *iter << std::endl;
    }

    return 0;
}

注意要從迭代器取值時要先解址 (dereferencing)。

使用迭代器也不需要知道向量的結構。必要時可以修改向量元素的值。但不能更動向量本身。

增減向量元素

從向量尾端加入元素

使用向量方法 .push_back() 可以從向量尾端推入元素：

#include <cassert>
#include <iostream>
#include <vector>

int main(void)
{
    std::vector<int> v = {3, 4, 5, 6, 7};

    assert(v.size() == 5);
    assert(v.at(0) == 3);
    assert(v.at(2) == 5);
    assert(v.at(4) == 7);

    v.push_back(8);

    assert(v.size() == 6);
    assert(v.at(0) == 3);
    assert(v.at(2) == 5);
    assert(v.at(4) == 7);
    assert(v.at(5) == 8);

    return 0;
}

從向量任意位置加入元素

使用向量方法 .insert() 可以在向量任意位置加入元素。這個方法會搭配迭代器使用：

#include <cassert>
#include <iostream>
#include <vector>

int main(void)
{
    std::vector<int> v = {3, 4, 5, 6};

    assert(v.size() == 4);
    assert(v.at(0) == 3);
    assert(v.at(2) == 5);
    assert(v.at(3) == 6);

    auto it = v.begin();

    // 10, 3, 4, 5, 6
    it = v.insert(it, 10);

    assert(v.size() == 5);
    assert(v.at(0) == 10);
    assert(v.at(2) == 4);
    assert(v.at(3) == 5);

    // 10, 3, 11, 4, 5, 6
    it = v.insert(it+2, 11);

    assert(v.size() == 6);
    assert(v.at(0) == 10);
    assert(v.at(2) == 11);
    assert(v.at(3) == 4);

    return 0;
}

從向量尾端移除元素

使用向量方法 .pop_back() 可以移除向量尾端的元素。該方法不會回傳移除的元素：

#include <cassert>
#include <iostream>
#include <vector>

int main(void)
{
    std::vector<int> v = {3, 4, 5, 6, 7};
    assert(v.size() == 5);

    v.pop_back();
    assert(v.size() == 4);

    return 0;
}