【STL】std::vector 详解

0 快问快答

学习的首要原则是避免感到枯燥。小问题敲击你的大脑神经。

Q1：std::vector 底层数据结构是什么？

A：连续内存的动态数组。支持随机访问，大小可动态变化。

Q2：size() 和 capacity() 的区别？

A：size() 是实际元素个数；capacity() 是已分配内存能容纳的元素总数（capacity >= size）。

Q3：push_back 的时间复杂度？可能发生什么操作？

A：均摊 O(1)。当 size == capacity 时，会重新分配内存（通常以 1.5~2 倍增长），拷贝/移动所有旧元素到新空间。

Q4：reserve(n) 和 resize(n) 区别？

A：reserve 只改变容量，不构造元素；resize 改变大小，若 n > size 则添加默认构造元素。

Q5：如何主动释放 vector 占用的多余内存？

A：shrink_to_fit()（仅请求，不保证）或通过交换技巧：vector<T>().swap(vec);

Q6：vector<bool> 有什么特别？

A：模板特化，采用位压缩存储，不满足标准容器要求（如无法取 bool&）。一般建议用 deque<bool> 或 vector<char> 替代。

Q7：哪些操作会使迭代器失效？

A：

扩容（push_back/insert 导致重分配）：所有迭代器失效。

不扩容时：insert/erase 使插入/删除点之后的迭代器失效。

reserve/shrink_to_fit 可能失效。

swap 不影响迭代器（只要不交换容器本身）。

Q8：emplace_back 比 push_back 好在哪？

A：直接传递构造参数在容器内构造对象，避免临时对象拷贝/移动。对不可拷贝类型尤其有用。

Q9：vector 适合做队列或频繁头插/删吗？

A：不适合，头插/删是 O(n)。用 deque 或 list。

Q10：vector 与 array 的主要区别？

A：array 是固定大小栈内存；vector 动态堆内存。

Q11：vector 与 list 何时选谁？

A：需要随机访问、内存连续 → vector。频繁中间插入/删除、无需随机访问 → list。

Q12：vector 是否保证 C 风格的连续内存？

A：C++11 起保证 &v[0] 或 v.data() 返回连续数组，适用于 C 接口。

1 概述

std::vector 是 C++ 标准模板库（STL）中最常用的序列容器之一。它封装了动态数组，能够自动管理内存扩容，同时提供与原生数组接近的访问性能。vector 将元素存储在连续的内存块中，因此支持常数时间的随机访问，并且在末尾添加或删除元素具有较高的效率（均摊常数时间）。

要使用 std::vector，需要包含头文件：

#include <vector>

核心特点：

• 动态大小：运行时自动调整容量

• 连续存储：支持指针偏移运算，兼容 C 风格数组接口

• 类型安全：模板化，存储任意类型元素

• 内存自动管理：析构时自动释放内存

时间复杂度：

• 随机访问：O(1)

• 尾部插入/删除：均摊 O(1)

• 中间插入/删除：O(n)

• 查找：O(n)

2 构造与赋值

2.1 构造函数

vector 提供多种重载的构造函数，方便初始化。

示例：

#include <vector>
#include <iostream>

int main() {
    std::vector<int> v1;                     // 空容器
    std::vector<int> v2(5);                  // {0,0,0,0,0}
    std::vector<int> v3(5, 10);              // {10,10,10,10,10}
    std::vector<int> v4(v3.begin(), v3.end());// 拷贝区间
    std::vector<int> v5(v4);                 // 拷贝构造
    std::vector<int> v6(std::move(v5));      // 移动构造后 v5 为空
    std::vector<int> v7 = {1,2,3,4,5};       // 初始化列表

    for (int x : v7) std::cout << x << ' ';  // 1 2 3 4 5
    std::cout << "\nSize of v5: " << v5.size() << '\n'; // 0
    return 0;
}

2.2 赋值操作

• operator=：拷贝、移动或初始化列表赋值

• assign()：重新设置容器内容（可指定区间或重复值）

std::vector<int> v = {1,2,3};
v.assign(4, 100);           // v = {100,100,100,100}
v.assign({5,6,7});          // v = {5,6,7}

std::vector<int> w;
w = v;                      // 拷贝赋值
w = std::move(v);           // 移动赋值
w = {8,9};                  // 初始化列表赋值

3 元素访问

vector 提供多种方式访问元素，需注意边界检查。

std::vector<char> vec = {'a','b','c'};
std::cout << vec[0];            // 'a'
std::cout << vec.at(1);         // 'b'
std::cout << vec.front();       // 'a'
std::cout << vec.back();        // 'c'

char* ptr = vec.data();         // 指向 'a'
ptr[1] = 'x';                   // vec 变为 {'a','x','c'}

⚠️ 注意：对于空容器调用 front()/back() 是未定义行为；operator[] 需确保索引有效。

4 迭代器

vector 提供的迭代器属于随机访问迭代器，支持 +、-、[]、< 等运算。

std::vector<int> v = {10,20,30};
for (auto it = v.begin(); it != v.end(); ++it) {
    *it += 5;
}
// v 变为 {15,25,35}

for (auto it = v.cbegin(); it != v.cend(); ++it) {
    // *it = 0;  错误：常量迭代器不可修改
}

for (auto rit = v.rbegin(); rit != v.rend(); ++rit) {
    std::cout << *rit << ' ';   // 35 25 15
}

由于 vector 的内存连续，可以通过 &v[0] + i 获得迭代器效果，但推荐使用迭代器以保持泛型兼容性。

5 容量管理

理解 size 与 capacity 的区别是高效使用 vector 的关键。

• size()：当前元素个数

• capacity()：当前已分配内存所能容纳的元素个数（capacity() >= size()）

• empty()：检查是否为空

• max_size()：理论上可容纳的最大元素数（通常很大）

5.1 扩容机制

当插入新元素导致 size == capacity 时，vector 会分配一块更大的新内存（通常为原容量的 1.5 倍或 2 倍，取决于实现），将原有元素移动或复制过去，最后释放旧内存。这个操作称为 扩容（reallocation），开销较大。

为了减少扩容次数，可以使用 reserve() 预分配容量。

std::vector<int> v;
std::cout << "Size: " << v.size() << ", Cap: " << v.capacity() << '\n'; // 0,0

v.push_back(1);
std::cout << v.capacity(); // 常见实现结果为 1

v.push_back(2);            // 触发扩容，capacity 变为 2 
v.push_back(3);            // 触发扩容，capacity 变为 4 
// 继续插入...

5.2 预留与缩容

std::vector<int> v;
v.reserve(100);            // capacity >= 100
for (int i = 0; i < 100; ++i) v.push_back(i); // 无扩容发生

v.clear();                 // size = 0, capacity 不变
v.shrink_to_fit();         // 实现可能释放内存，capacity 可能变为 0

在已知元素个数的场景下，务必使用 reserve() 避免多次扩容，显著提升性能。

6 修改操作

6.1 尾部操作

• push_back(const T& value) / push_back(T&& value)（C++11）

• pop_back() – 删除末尾元素（不返回该元素）

• emplace_back(Args&&... args)（C++11）– 就地构造元素，避免拷贝/移动

struct Point { int x, y; Point(int a, int b) : x(a), y(b) {} };

std::vector<Point> points;
points.emplace_back(3, 4);   // 直接调用 Point(3,4)，无临时对象
points.push_back(Point(1,2));// 先构造临时，再移动（或拷贝）到容器

对于复杂类型，emplace_back 通常比 push_back 更高效。

6.2 任意位置插入与删除

• insert(iterator pos, const T& value) / (重载版本)

• erase(iterator pos) / erase(iterator first, iterator last)

• clear() – 清空所有元素（size = 0）

• emplace(iterator pos, Args&&... args) – 就地构造于指定位置前

std::vector<int> v = {1,2,3,4,5};
v.insert(v.begin() + 2, 99);      // {1,2,99,3,4,5}
v.erase(v.begin() + 1, v.begin() + 3); // 删除索引 1~2 → {1,4,5}
v.emplace(v.begin(), -1);         // {-1,1,4,5}

⚠️ 注意：中间插入/删除会导致该位置之后的所有元素移动，时间复杂度 O(n)。

6.3 其他修改

• resize(size_type n) / resize(size_type n, const T& value)

  • 若 n < size()：截断尾部

  • 若 n > size()：尾部添加值初始化（或 value 副本）的元素

• swap(vector& other) – 交换两个容器的内容（常数时间，仅交换内部指针）

std::vector<int> a = {1,2,3};
std::vector<int> b = {4,5};
a.swap(b);              // a = {4,5}, b = {1,2,3}

7. 迭代器失效问题

对 vector 的某些修改操作可能导致已有迭代器、指针或引用失效。理解失效规则是避免悬垂引用的关键。

示例常见错误：

std::vector<int> v = {1,2,3};
for (auto it = v.begin(); it != v.end(); ++it) {
    if (*it == 2) v.insert(it, 99);   // 危险！insert 会使 it 失效
}

正确做法：利用插入返回的新迭代器或者改变遍历逻辑。

std::vector<int> v = {1,2,3};
for (auto it = v.begin(); it != v.end(); ) {
    if (*it == 2) it = v.insert(it, 99) + 1; // insert 返回指向 99 的迭代器，+1 后指向原来的 2
    else ++it;
}

8 vector<bool> 特化

std::vector<bool> 是 vector 的一个模板特化，为了节省空间，它用位（bit）存储布尔值，而不是字节。这导致一些与普通 vector 不同的行为：

• 无法直接取 bool& 引用（因为位不可寻址），operator[] 返回一个代理类 std::vector<bool>::reference

• 迭代器、data() 成员不可用（没有连续的内存数组）

• 性能可能不及普通 vector<char>

• 在多线程环境下需特别注意

如果需要 bool 的动态数组且不在乎空间占用，推荐使用 std::vector<char> 以获得标准容器行为。

std::vector<bool> flags(10, true);
flags[0] = false;           // 正常工作，但引用是代理
// bool* p = flags.data();  // 错误：没有 data()

9 性能分析与使用建议

9.1 扩容策略

大多数标准库实现采用 1.5 倍 或 2 倍 扩容因子。例如 GCC 使用 2 倍，而 Clang 使用 1.5 倍（更利于重用已释放的内存碎片）。假设初始 capacity=0，经过 k 次扩容后的容量约为 initial * factor^k。

测试代码（GCC）：

std::vector<int> v;
for (int i = 0; i < 100; ++i) {
    v.push_back(i);
    std::cout << "size=" << v.size() << " cap=" << v.capacity() << '\n';
}

输出典型序列：0→1→2→4→8→16→32→64→128...

9.2 高效使用指南

• 预分配内存：已知元素数量时，使用 reserve(n)

• 避免频繁的中间插入：优先考虑 deque 或 list

• 移动语义：在存储大型对象时，使用 emplace_back 和 push_back(T&&)

• 使用 shrink_to_fit：在长期不再增长后释放多余内存（但注意它可能触发拷贝）

• 使用 swap 技巧清空内存：旧标准中常用 vector<T>().swap(v); 来强制释放内存，现在 shrink_to_fit 更清晰

// 强制释放内存（C++11 以前风格）
std::vector<int>().swap(v);
// C++11 及以后
v.clear();
v.shrink_to_fit();

9.3 与其他序列容器的对比

选择建议：

• 默认使用 vector，除非有明确的特殊需求

• 大量头部插入/删除 → deque

• 频繁中间插入且不关心随机访问 → list / forward_list

• 编译期固定大小 → std::array

10 异常安全性

vector 操作提供基本的异常安全保证（某些操作提供强保证）：

• push_back / emplace_back：如果元素构造或内存分配抛出异常，容器保持原状（强保证）

• insert / emplace：通常提供基本保证，也可能强保证（取决于元素类型和位置）

• pop_back / clear：不抛出异常（除非元素析构抛出，但不应发生）

当元素类型是不可复制的移动类型时，vector 会在扩容时使用移动而非复制以提升性能。但为了强异常安全，标准库要求移动操作声明为 noexcept，否则将回退到复制。

class Noisy {
public:
    Noisy(Noisy&&) noexcept { ... }  // 帮助 vector 高效扩容
};