`std::vector`

首先介绍最容易理解的 std::vector 容器。简单说，std::vector 代表一个长度可变化的数组。首先，它是一个类模板，接受一个类型参数做为其元素类型。你可以像数组一样初始化 std::vector，可选地给出类型模板实参：

#include <iostream>
#include <vector> // std::vector 定义于 <vector> 头文件

int main() {
    std::vector<int> a{1, 2, 3}; // 定义 std::vector 对象
    std::vector b{4, 5};         // 可省略类型实参

    // 像数组一样使用 std::vector
    std::cout << a[0] << std::endl; // 输出 1
    std::cout << b[1] << std::endl; // 输出 4
}

数组的元素个数是恒定的常量，但 std::vector 的“长度可变”，所以无需再声明中指明其大小。相对应的，使用 size 成员函数来获取当前 std::vector 内元素的个数：

#include <iostream>
#include <vector>

int main() {
    std::vector<int> a{1, 2, 3};
    std::vector b{4, 5};

    // b.size() 即 b 中元素的个数
    std::cout << b.size() << std::endl; // 输出 2
    for (int i{0}; i < a.size(); i++) {
        std::cout << a[i] << " ";       // 遍历 a 的元素
    }
}

push_back 成员函数可以在尾部添加一个元素：

#include <iostream>
#include <vector>
// 遍历输出一个 std::vector 的所有元素
void print(const std::vector<int>& x) {
    for (int i{0}; i < a.size(); i++) {
        std::cout << x[i] << " ";
    }
    std::cout << std::endl;
}
int main() {
    std::vector a{1, 2, 3};
    print(a); // 输出 1 2 3
    a.push_back(4);
    print(a); // 输出 1 2 3 4
}

对应地，pop_back 成员函数可以删除尾部的一个元素。

添加或者删除 std::vector 非尾部（中间或头部）的元素将留到之后的迭代器章节中再讲。

此外，聪明的你一定想到了，能通过 a[0] 这种方式使用 std::vector，说明它定义了 operator[] 的运算符重载。不过需要注意的是，std::vector 和数组一样，访问元素不检查是否越界；如果访问元素的下标超过了 std::vector 的长度，则导致未定义行为。

std::vector 还提供了一些构造函数、其它成员函数如 clear empty front back 等，以及比较运算符重载。我们并不在这里展开介绍，如有需要请查阅 CppReferenceopen in new window。

注意

出于历史原因，尽可能不使用 std::vector<bool>。std::vector<bool> 相比其它 std::vector 做了空间上的优化，但其性能可能有所下降。如有需求，可用 std::vector<char> 代替。

std::vector 保证其元素在内存中的存储是连续的。这使得它在不进行元素增删的前提下和数组拥有相同的性能。进一步可以分析得到，std::vector 在尾部插入和删除元素的平均代价是比较小的，但在非尾部的位置增删则更费力气一点。

上述的“平均代价”指的是均摊代价，“比较小”指其只需 $O(1)$ 的时间完成，“费力气”指的是有超过 $O(1)$ 的时间复杂度：具体而言，增删元素的时间开销与增删位置到尾部的距离呈线性关系（ $O(n)$ ）。

# std::vector

`std::vector`