std:: vector

除了 std::vector<bool> 部分特化之外，元素都是连续存储的，这意味着不仅可以通过迭代器访问元素，还可以使用指向元素的常规指针的偏移量来访问。这意味着可以将指向vector元素的指针传递给任何期望指向数组元素指针的函数。

vector的存储空间由自动管理，会根据需要自动扩展。vector通常比静态数组占用更多空间，因为会分配更多内存以应对未来增长。这样vector就不需要在每次插入元素时重新分配内存，仅在额外内存耗尽时才需要重新分配。已分配内存的总量可以通过 capacity() 函数查询。额外内存可以通过调用 shrink_to_fit() ^[1] 返还给系统。

在性能方面，重新分配通常是代价高昂的操作。如果预先知道元素数量，可以使用 reserve() 函数来避免重新分配。

向量常见操作的时间复杂度（效率）如下：

• 随机访问 - 常数时间复杂度 𝓞(1) 。
• 末尾元素的插入或移除 - 均摊常数时间复杂度 𝓞(1) 。
• 元素的插入或移除 - 与到向量末尾的距离成线性关系 𝓞(n) 。

std::vector （对于 T 类型不为 bool 的情况）满足 Container 、 AllocatorAwareContainer （自 C++11 起） 、 SequenceContainer 、 ContiguousContainer （自 C++17 起） 以及 ReversibleContainer 的要求。

1. ↑ 在 libstdc++ 中， shrink_to_fit() 在 C++98 模式下 不可用 。

#include <iostream>
#include <vector>
int main()
{
    // 创建包含整数的vector
    std::vector<int> v = {8, 4, 5, 9};
    // 向vector添加两个整数
    v.push_back(6);
    v.push_back(9);
    // 覆盖位置2处的元素
    v[2] = -1;
    // 输出vector内容
    for (int n : v)
        std::cout << n << ' ';
    std::cout << '\n';
}

8 4 -1 9 6 9