STL 深度解析之vector【C++每日一学】

---

如果觉得本文对您有所帮助，请点个赞和关注吧，谢谢！！！你的支持就是我持续更新的最大动力

---

一、引言

std::vector 是 C++ 标准模板库（STL）中封装动态数组的序列容器。其核心优势在于提供了对元素的随机访问（常数时间复杂度 O(1)）和在尾部进行快速插入/删除（均摊常数时间复杂度 O(1)）的能力。所有元素在内存中是连续存储的，这使得 std::vector 与 C 风格数组具有良好的互操作性，并能极大地受益于现代 CPU 的缓存机制。

头文件引入:

#include <vector>

二、核心内部机制

理解 std::vector 的行为，首先要理解其内部数据模型。一个 std::vector 对象通常可以被抽象为三个指针（或等价的迭代器）来管理其内存：

1. _Myfirst: 指向已分配内存块的起始位置。
2. _Mylast: 指向最后一个元素的下一个位置。
3. _Myend: 指向已分配内存块的末尾之后的位置。

基于此模型，我们可以精确定义：

• size() 等价于 _Mylast - _Myfirst
• capacity() 等价于 _Myend - _Myfirst

当执行 push_back 且 size() == capacity() 时，会触发内存重分配（Reallocation）：

1. 分配新内存: 按照一定的增长因子（通常为 1.5 或 2），分配一块更大的连续内存。
2. 转移元素: 将旧内存中的所有元素移动到新内存中。这里有关键的细节：
   • 如果元素的移动构造函数是 noexcept 的，编译器会优先使用 std::move，这极其高效（仅移动资源所有权，不涉及深拷贝）。
   • 如果移动构造函数可能抛出异常，为了维持强异常安全保证，vector 会退而求其次使用拷贝构造函数。这确保了即使在拷贝过程中发生异常，原 vector 的状态依然有效。
3. 释放旧内存: 销毁旧内存中的对象（如果它们是拷贝而非移动的）并释放旧的内存块。

[性能关键]: 编写自定义类型时，为其提供 noexcept 的移动构造函数和移动赋值运算符对 std::vector 的性能至关重要。

---

三、构造与初始化 (Construction & Initialization)

默认构造函数

• 作用: 创建一个空的 vector。
• 原型: vector();
• 复杂度: O(1)
• 状态: size() == 0, capacity() == 0。

填充构造函数

• 作用: 创建一个包含 n 个元素的 vector，并用 value 初始化它们。
• 原型: explicit vector(size_type n, const T& value = T());
• 复杂度: O(N)，其中 N 是 n。
• 注意: 如果 T 是一个复杂的类，这会调用 N 次 T 的拷贝构造函数。

范围构造函数

• 作用: 从迭代器范围 [first, last) 拷贝元素来构造 vector。
• 原型: template <class InputIterator> vector(InputIterator first, InputIterator last);
• 复杂度: O(N)，其中 N 是 std::distance(first, last)。

拷贝与移动构造函数

• 作用: 创建一个 vector 的副本或从中转移资源。
• 原型:

  vector(const vector& other);      // 拷贝构造
  vector(vector&& other) noexcept;  // 移动构造 (C++11)
  

• 复杂度:
  • 拷贝: O(N)，其中 N 是 other.size()。
  • 移动: O(1)。
• 注意: 移动构造后，other 处于一个有效但未指定的状态，通常为空。

初始化列表构造函数

• 作用: 使用 std::initializer_list 进行构造。
• 原型 (C++11): vector(std::initializer_list<T> il);
• 复杂度: O(N)，其中 N 是 il.size()。
• 示例:

  std::vector<int> v1;                    // 默认构造
  std::vector<int> v2(5, 100);            // 填充构造: {100, 100, 100, 100, 100}
  int arr[] = {1, 2, 3, 4, 5};
  std::vector<int> v3(arr, arr + 5);      // 范围构造
  std::vector<int> v4 = {1, 2, 3, 4, 5};  // 初始化列表
  

[常见陷阱]: std::vector<int> v(10); 创建一个包含10个默认初始化（值为0）的 int 的 vector。而 std::vector<int> v{10}; 创建一个只包含一个元素，其值为10的 vector。请注意 () 和 {} 的区别。

---

四、容量管理 (Capacity)

size() / max_size() / empty()

• size_type size() const noexcept;
  • 作用: 返回当前元素数量。
  • 复杂度: O(1)。
• size_type max_size() const noexcept;
  • 作用: 返回 vector 由于系统或库的限制所能容纳的最大元素数量。这通常是一个巨大的理论值。
  • 复杂度: O(1)。
• bool empty() const noexcept;
  • 作用: 检查 vector 是否为空 (size() == 0)。
  • 复杂度: O(1)。

reserve(size_type n)

• 作用: 请求将 vector 的容量至少增加到 n。如果 n 大于当前容量，将发生一次内存重分配。如果 n 小于或等于当前容量，则此调用无效。
• 返回值: void
• 复杂度: 若发生重分配，则为 O(N)；否则为 O(1)。
• 异常安全: 强保证。如果元素类型的移动/拷贝构造函数抛出异常，vector 自身状态不变。
• 使用场景: 在已知将要添加大量元素时，预先调用 reserve 可以避免多次昂贵的重分配，是 vector 的关键性能优化手段。

  std::vector<int> v;
  v.reserve(1000); // 预分配空间
  for (int i = 0; i < 1000; ++i) {v.push_back(i); // 在此循环中不会发生任何重分配
  }
  

capacity()

• 作用: 返回当前已分配的存储容量。
• 原型: size_type capacity() const noexcept;
• 复杂度: O(1)。

shrink_to_fit()

• 作用: 请求释放未使用的容量，使 capacity() 尽可能等于 size()。这是一个非绑定请求，实现可以忽略它。
• 原型 (C++11): void shrink_to_fit();
• 复杂度: O(N)，因为它可能触发内存重分配和元素移动。
• 使用场景: 在 vector 经历过大规模增长后，又大量删除了元素，且在未来一段时间内不会再增长时，可以使用此函数回收内存。

resize(size_type n, const T& value = T())

• 作用: 改变 vector 的大小 (size())。
  • 若 n < size(): 销毁末尾的 size() - n 个元素。
  • 若 n > size(): 在末尾添加 n - size() 个新元素。若提供了 value，则用 value 的拷贝进行初始化；否则进行值初始化（例如，int 初始化为0，类类型调用默认构造函数）。
• 返回值: void
• 复杂度: 与 n 和 size() 的差值成线性关系。如果需要扩容，还需加上重分配的开销。

---

五、元素访问 (Element Access)

operator[]

• 作用: 访问指定索引的元素，不进行边界检查。
• 原型: reference operator[](size_type n);, const_reference operator[](size_type n) const;
• 复杂度: O(1)。
• 场景: 在性能关键代码段中，当程序员能百分之百保证索引有效时使用。

at()

• 作用: 访问指定索引的元素，进行边界检查。如果索引越界，会抛出 std::out_of_range 异常。
• 原型: reference at(size_type n);, const_reference at(size_type n) const;
• 复杂度: O(1)。
• 场景: 在需要保证程序健壮性、不确定索引是否有效的情况下使用。

front() / back()

• 作用: 分别返回对第一个和最后一个元素的引用。
• 原型: reference front();, reference back(); 等。
• 复杂度: O(1)。
• 注意: 对空 vector 调用这些函数是未定义行为。

data()

• 作用: 返回指向底层连续内存数组的指针。
• 原型 (C++11): T* data() noexcept;, const T* data() const noexcept;
• 复杂度: O(1)。
• 场景: 与需要原始指针和长度的 C 风格 API 进行交互。

  void c_api_function(const int* arr, size_t len);
  std::vector<int> my_vector = {1, 2, 3};
  c_api_function(my_vector.data(), my_vector.size());
  

---

六、迭代器 (Iterators)

迭代器是访问容器元素的通用接口。vector 提供的是随机访问迭代器，功能最强，支持 ++, --, +n, -n, < 等所有算术和比较操作。

函数	返回类型	描述
begin()	iterator	指向第一个元素的迭代器
cbegin()	const_iterator	指向第一个元素的 const 迭代器
end()	iterator	指向末尾元素之后的迭代器（哨兵）
cend()	const_iterator	指向末尾元素之后的 const 迭代器
rbegin()	reverse_iterator	指向最后一个元素的反向迭代器
crbegin()	const_reverse_iterator	指向最后一个元素的 const 反向迭代器
rend()	reverse_iterator	指向第一个元素之前的反向迭代器
crend()	const_reverse_iterator	指向第一个元素之前的 const 反向迭代器

---

七、修改器 (Modifiers)

push_back() / emplace_back()

• push_back(const T& value): 在末尾拷贝构造一个元素。
• push_back(T&& value): 在末尾移动构造一个元素。
• emplace_back(Args&&... args): 在末尾就地构造一个元素，将参数 args完美转发给 T 的构造函数。
• 复杂度: 均摊 O(1)。最坏情况（触发重分配）为 O(N)。
• 性能对比: emplace_back 通过避免创建临时对象，通常比 push_back 更高效。

  struct MyObject {MyObject(int a, double b) { /* ... */ }
  };
  std::vector<MyObject> vec;
  // push_back: 创建临时对象 MyObject(10, 3.14)，然后移动/拷贝到 vector 中
  vec.push_back(MyObject(10, 3.14));
  // emplace_back: 直接在 vector 的内存中调用 MyObject 的构造函数 MyObject(10, 3.14)
  vec.emplace_back(10, 3.14);
  

pop_back()

• 作用: 移除并销毁最后一个元素。
• 原型: void pop_back();
• 复杂度: O(1)。
• 注意: 对空 vector 调用是未定义行为。

insert() / emplace()

• 作用: 在迭代器 pos 指向的位置之前插入元素。
• insert(pos, value): 插入单个或多个元素。
• emplace(pos, args...): 在 pos 处就地构造一个元素。
• 返回值: 指向第一个被插入元素的迭代器。
• 复杂度: O(N)，其中 N 是从插入点到末尾的元素数量，因为需要移动这些元素。

erase()

• 作用: 移除迭代器 pos 指向的单个元素，或 [first, last) 范围内的元素。
• 返回值: 指向被删除的最后一个元素之后的元素的迭代器。
• 复杂度: O(N)，其中 N 是从删除点到末尾的元素数量。
• 关键用法: 在循环中安全地删除元素。

  // 错误的方式，it 在 erase 后失效
  // for (auto it = v.begin(); it != v.end(); ++it) {
  //     if (*it % 2 == 0) v.erase(it);
  // }// 正确的方式
  for (auto it = v.begin(); it != v.end(); /* no increment here */) {if (*it % 2 == 0) {it = v.erase(it); // erase 返回下一个有效迭代器} else {++it;}
  }
  

clear()

• 作用: 销毁所有元素，使 size() 变为 0。
• 原型: void clear() noexcept;
• 复杂度: O(N)，其中 N 是 size()，因为需要调用每个元素的析构函数。
• 注意: capacity() 保持不变。要同时释放内存，请使用 shrink_to_fit() 或 swap 技巧: std::vector<T>().swap(my_vec);。

swap()

• 作用: 与另一个 vector 交换内容。
• 原型: void swap(vector& other) noexcept;
• 复杂度: O(1)。这是一个极其高效的操作，只交换内部的三个指针。

---

八、迭代器失效的精确规则

这是使用 vector 时最容易出错的地方，必须严格遵守。

1. 导致重分配的操作:

   • 任何调用 reserve() 且新容量大于旧容量。
   • 任何调用 resize() 且新尺寸大于旧容量。
   • 任何 insert, push_back, emplace, emplace_back 调用，如果其导致 size() 超过 capacity()。
   • 后果: 所有 指向该 vector 的迭代器、指针和引用都会失效。

2. 不导致重分配的插入操作 (insert, emplace):

   • 后果: 指向插入点及之后的所有迭代器、指针和引用都会失效。指向插入点之前的元素不受影响。

3. 删除操作 (erase, pop_back, clear):

   • 后果: 指向被删除元素及之后的所有迭代器、指针和引用都会失效。指向被删除元素之前的元素不受影响。pop_back 会使指向最后一个元素的迭代器和 end() 迭代器失效。clear 会使所有迭代器失效。

4. 不会使迭代器失效的操作:

   • 所有 const 成员函数（如 size, capacity, empty, operator[], at, front, back, data）。
   • swap(): 迭代器本身不会失效，但它们在交换后会“跟随”原来的元素，即指向另一个容器。

---

九、特化：std::vector<bool>

std::vector<bool> 是一个特殊的模板特化，旨在优化空间。它将每个 bool 值存储为一个比特位，而不是一个 char 或 int。

• 优点: 空间效率极高。
• 缺点 (严重):
  1. 非标准容器: 它不完全满足标准容器的所有要求。
  2. 非连续内存: 虽然逻辑上是 bool 序列，但你不能像 std::vector<int> 那样获得一个 bool* 指针，因为比特位没有独立的地址。data() 方法不存在。
  3. 代理对象: operator[] 和解引用迭代器返回的不是 bool&，而是一个特殊的代理对象（std::vector<bool>::reference），该对象模拟了 bool& 的行为。这可能导致在泛型编程和 auto 类型推导中出现意外行为。

[建议]: 除非你面临极端的内存限制，并且确定只需要 vector<bool> 提供的功能，否则避免使用它。可以考虑使用 std::vector<char> 或 std::deque<bool>（它没有这种特化）作为替代。

---

十、总结

std::vector 是 C++ 工具箱中的瑞士军刀。其连续内存布局带来的缓存友好性和随机访问性能，使其成为大多数场景下的默认首选序列容器。精通其内存管理模型、性能特点和迭代器失效规则，是编写高效、健壮的 C++ 代码的基石。在性能敏感的场景下，合理使用 reserve、emplace_back 和 noexcept 的移动语义，能够将 vector 的性能发挥到极致。

如果觉得本文对您有所帮助，请点个赞和关注吧，谢谢！！！你的支持就是我持续更新的最大动力