C++ std::vector
std::vector 是 C++ STL 中最常用的序列容器之一，它提供了动态数组的功能，结合了数组的高效访问和链表的动态扩展能力。1、底层结构与核心原理
1.1 内存布局
[*]连续内存空间：vector 底层是一块连续的动态分配内存，这使得它支持 随机访问（通过下标 [] 或 at() 方法，时间复杂度 O(1)）。
[*]三个核心指针：
[*]start：指向内存块的起始位置（第一个元素）。
[*]finish：指向最后一个元素的下一个位置。
[*]end_of_storage：指向内存块的结束位置。
三者关系：[start, finish) 是已使用空间，[finish, end_of_storage) 是未使用的预留空间。
1.2 容量（capacity）与大小（size）
[*]size：当前存储的元素数量（finish - start）。
[*]capacity：总分配的内存可容纳的元素数量（end_of_storage - start）。
[*]当 size == capacity 时，继续插入元素会触发 扩容。
1.3 扩容机制
[*]触发条件：插入元素后 size 超过当前 capacity。
[*]扩容步骤：
[*]分配一块更大的内存（通常是原容量的 1.5 倍或 2 倍，不同编译器实现不同，如 GCC 是 2 倍，VS 是 1.5 倍）。
[*]将旧内存中的元素复制/移动到新内存。
[*]释放旧内存。
[*]更新 start、finish、end_of_storage 指针。
[*]注意：扩容后，原有的迭代器、指针、引用都会失效（因为指向的旧内存已释放）。
1.4 迭代器类型
[*]随机访问迭代器 (RandomAccessIterator)： 支持所有指针算术运算，如 iter + n, iter - n, iter, iter1 < iter2 等。功能最强大的迭代器。
1.5 主要优点
[*]高效的随机访问： 通过 [] 或 .at() 访问任何元素的时间复杂度是 O(1)。
[*]高效的尾部操作： 在尾部进行 push_back 和 pop_back 的平摊时间复杂度是 O(1)。
[*]缓存友好性： 由于内存连续，遍历时具有良好的空间局部性，CPU 缓存命中率高，遍历速度极快。
1.6 主要缺点
[*]低效的中间/头部插入删除： 在 vector 头部或中间插入/删除元素，需要移动后续的所有元素，时间复杂度是 O(n)。
[*]潜在的迭代器失效： 任何可能引起内存重新分配的操作（如 push_back 导致扩容）都会使所有指向该 vector 的迭代器、引用和指针失效。
2、常用操作与示例代码
2.1 包含头文件与创建 vector
#include <iostream>
#include <vector>
int main() {
// 1. 创建空 vector
std::vector<int> vec1;
// 2. 创建并初始化 (C++11)
std::vector<int> vec2 = {1, 2, 3, 4, 5};
// 3. 创建包含 n 个相同元素的 vector
std::vector<int> vec3(5, 100); // {100, 100, 100, 100, 100}
// 4. 通过迭代器范围创建
int arr[] = {6, 7, 8};
std::vector<int> vec4(arr, arr + 3); // {6, 7, 8}
// 5. 拷贝构造
std::vector<int> vec5(vec2); // vec5 是 vec2 的副本
return 0;
}2.2 添加元素
std::vector<int> vec;
// 在尾部添加元素 (最常用！)
vec.push_back(1); // vec: {1}
vec.push_back(2); // vec: {1, 2}
vec.push_back(3); // vec: {1, 2, 3}
// C++11: 在尾部就地构造元素，避免拷贝/移动，更高效
vec.emplace_back(4); // vec: {1, 2, 3, 4}
// 在指定位置前插入元素 (谨慎使用！成本高)
auto it = vec.begin() + 2; // 指向第3个元素 (3)
vec.insert(it, 999); // 在 3 之前插入 999 -> {1, 2, 999, 3, 4}
// C++11: 在指定位置就地构造元素
vec.emplace(it, 888); // -> {1, 2, 888, 999, 3, 4}
// 插入多个元素或一个区间
vec.insert(vec.end(), 3, 100); // 在末尾插入3个1002.3 访问元素
std::vector vec = {10, 20, 30};// 1. 使用下标运算符 [] (最快，但不做边界检查)std::cout
页:
[1]