C++(STL库)之顺序容器vector的使用

什么是vector

vector是C++ STL中的一种顺序容器，由于其高效的随机存储和动态调整大小的特点，使用非常广泛。vector容器存放的是一个数组，它允许高效的在尾部插入和删除元素，并支持在序列运行时动态调整容量大小，在操作上与原生数组相似但更加方便且更加安全。

vector基本操作

向vector中插入数据

向vector中插入数据可以使用push_back方法，在vector末尾插入一个元素，例如：

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> vec;
    vec.push_back(1);
    vec.push_back(2);
    vec.push_back(3);
    vec.push_back(4);

    for (int i = 0; i < vec.size(); i++) {
        cout << vec[i] << " ";
    }
    return 0;
}

输出结果为: 1 2 3 4。

遍历vector

遍历vector可以使用for循环结合下标来访问和修改vector中的元素，例如：

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> vec;
    for (int i = 0; i < 10; i++) {
        vec.push_back(i);
    }

    for (int i = 0; i < vec.size(); i++) {
        cout << vec[i] << " ";
    }

    return 0;
}

输出结果为：0 1 2 3 4 5 6 7 8 9。

插入和删除vector元素

在vector中，可以使用insert方法在指定的位置插入一个元素，例如：

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> vec;
    vec.push_back(1);
    vec.push_back(2);
    vec.push_back(3);

    auto it = vec.begin() + 2;
    vec.insert(it, 4);

    for (int i = 0; i < vec.size(); i++) {
        cout << vec[i] << " ";
    }

    return 0;
}

输出结果为：1 2 4 3。

在vector中，还可以使用erase方法删除元素，例如：

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> vec;
    for (int i = 0; i < 10; i++) {
        vec.push_back(i);
    }

    auto it = vec.begin() + 5;
    vec.erase(it);

    for (int i = 0; i < vec.size(); i++) {
        cout << vec[i] << " ";
    }

    return 0;
}

输出结果为：0 1 2 3 4 6 7 8 9。

示例说明

示例一：用vector实现快速排序

快速排序是一种常用的排序算法，它的基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后再按此方法对这两部分记录分别进行快速排序，整个排序过程可以递归进行，以此达到整个序列有序的目的。

使用vector可以方便地实现快速排序，代码如下：

#include <iostream>
#include <vector>

using namespace std;

void quick_sort(vector<int>& vec, int left, int right) {
    if (left >= right) {
        return;
    }

    int pivot = left;
    int i = left + 1;
    int j = right;

    while (i <= j) {
        if (vec[i] > vec[pivot] && vec[j] < vec[pivot]) {
            swap(vec[i], vec[j]);
            i++;
            j--;
        }
        if (vec[i] <= vec[pivot]) {
            i++;
        }
        if (vec[j] >= vec[pivot]) {
            j--;
        }
    }
    swap(vec[j], vec[pivot]);
    quick_sort(vec, left, j - 1);
    quick_sort(vec, j + 1, right);
}

int main() {
    vector<int> vec{3, 4, 2, 1, 6, 5, 7, 9, 8};
    quick_sort(vec, 0, vec.size() - 1);
    for (auto i : vec) {
        cout << i << " ";
    }
    return 0;
}

输出结果为：1 2 3 4 5 6 7 8 9。

示例二：利用vector实现图的邻接表表示

在图的算法中，邻接表常用来表示有向图或无向图，并且实现简单、使用方便。在邻接表中，每个元素都是一个vector（即表），表示从某一个节点出发，所能到达的节点列表。例如下面的图，用邻接表表示如下：

graph LR
    1 -- 4
    1 -- 2
    2 -- 5
    2 -- 3
    3 -- 6

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<vector<int>> graph = {{4, 2},
                                 {5, 3},
                                 {6},
                                 {},
                                 {},
                                 {}};

    for (int i = 0; i < graph.size(); i++) {
        cout << i << "->";
        for (auto j : graph[i]) {
            cout << j << " ";
        }
        cout << endl;
    }
    return 0;
}

输出结果为：

0->4 2 
1->5 3 
2->6 
3->
4->
5->