标准模板库vector

代码仓库shanchuann/CPP-Learninng

在 C++的标准模板库（ STL ）中， vector 无疑是最常用、最基础的容器之一。它以动态数组的形式实现，既拥有数组般高效的随机访问能力，又能灵活地动态调整大小，是绝大多数场景下存储序列数据的首选。本文将从底层实现原理出发，全面剖析 vector 的核心机制、接口使用、性能优化以及常见陷阱，帮助你彻底掌握这个强大的容器。

STL （ Standard Template Library ，标准模板库）是 C++标准库的核心组成部分，它通过模板技术将常用的数据结构与算法实现了分离，让开发者可以直接复用高效、通用的组件，而无需重复造轮子。

vector 正是 STL 容器家族中的明星成员。它的本质是一个动态管理的连续内存数组，这意味着：

• 它支持像原生数组一样的 O(1)时间复杂度随机访问；
• 它可以在运行时自动调整大小，无需开发者手动管理内存；
• 它的内存布局完全连续，因此可以完美兼容 C 风格的接口；
• 它在尾部添加或删除元素的效率极高（通常为 O(1)），但在中间位置插入或删除元素则需要移动大量数据（ O(n)）。

这些特性使得 vector 成为了处理“需要频繁访问、主要在尾部增删”的序列数据的最佳选择。

vector 的底层实现

要真正理解 vector 的行为，必须深入它的底层实现。虽然不同编译器的 STL 实现细节略有差异（如 GCC 的 libstdc++、 MSVC 的 STL 实现），但核心逻辑都是通过三个指针来维护内存空间的：

// 简化版的vector底层结构示意
template <class _Tp>
class vector {
protected:
    _Tp* _M_start;          // 指向内存块的起始位置
    _Tp* _M_finish;         // 指向最后一个有效元素的下一个位置
    _Tp* _M_end_of_storage; // 指向已分配内存块的末尾
};

这三个指针清晰地划分了 vector 的内存区域：

• _M_start：标记整个内存块的起点，也是第一个元素的位置。
• _M_finish：标记“已使用内存”的终点，它指向最后一个有效元素的下一位。因此，_M_finish - _M_start 的结果就是当前容器中实际存储的元素个数，即 size()。
• _M_end_of_storage：标记“已分配内存”的终点。_M_end_of_storage - _M_start 的结果就是当前容器在不重新分配内存的情况下最多能存储的元素个数，即 capacity()。

空 vector 的状态：当我们创建一个空的 vector 时，这三个指针通常都被初始化为 nullptr，表示尚未分配任何内存。此时 size() 和 capacity() 都为 0 。

插入数据后的状态：当我们向 vector 中插入元素时，它会先分配一块内存（通常比当前需要的大一些，为后续增长预留空间），然后将元素存入，并移动 _M_finish 指针。此时：

• _M_start 固定指向内存起点；
• _M_finish 随着元素的增加向后移动；
• _M_end_of_storage 保持不变，直到内存不足触发扩容。

这种设计使得 vector 可以高效地统计元素个数和剩余容量，只需进行简单的指针减法即可。

核心接口详解

构造函数

vector 提供了多种构造函数，以满足不同的初始化需求：

#include <vector>
int main() {
    // 1. 默认构造：创建一个空的vector
    std::vector<int> vec1;
    // 2. 填充构造：创建包含n个值为val的元素的vector
    std::vector<int> vec2(10, 23); // 10个int，每个值都是23
    std::vector<int> vec3(10);      // 10个int，每个值都是0（默认构造）
    // 3. 范围构造：从迭代器区间复制元素
    int arr[] = {1, 2, 3, 4, 5};
    std::vector<int> vec4(arr, arr + 5); // 从C数组复制
    // 4. 初始化列表构造（C++11）
    std::vector<int> vec5 = {1, 2, 3, 4, 5, 6, 7};
    // 5. 拷贝构造：复制另一个vector
    std::vector<int> vec6(vec5);
    // 6. 移动构造（C++11）：转移另一个vector的所有权，不拷贝
    std::vector<int> vec7(std::move(vec6)); // vec6现在变为空
}

移动构造是 C++11 引入的重要特性，它通过简单地交换三个指针来“偷取”另一个 vector 的内存，时间复杂度为 O(1)，在不需要原 vector 的情况下可以极大提升性能。

元素访问

vector 提供了多种访问元素的方式，它们在安全性和效率上各有取舍：

std::vector<int> vec = {10, 20, 30, 40, 50};
// 1. operator[]：下标访问，不检查越界
int a = vec[0]; // 10
// vec[100]; // 未定义行为！可能导致程序崩溃或数据混乱
// 2. at()：带边界检查的访问
int b = vec.at(1); // 20
// vec.at(100); // 抛出 std::out_of_range 异常，安全但稍慢
// 3. front() 和 back()：访问首尾元素
int first = vec.front(); // 10
int last = vec.back();   // 50
// 4. data()：获取底层数组的指针（C++11）
int* p = vec.data();
std::cout << *(p + 2) << std::endl; // 30，可用于与C接口交互

关键区别：

• operator[] 追求效率，不做边界检查，越界访问会导致未定义行为（ Windows 下通常触发断言， Linux 下可能段错误）。
• at() 追求安全，会检查索引是否越界，越界时抛出异常，适合索引不确定的场景。
• 对空 vector 调用 front() 或 back() 也是未定义行为，调用前务必检查 empty()。

容量操作

这是 vector 最核心也最容易混淆的一组接口，理解它们的区别至关重要：

std::vector<int> vec;
// size()：返回当前元素个数
// capacity()：返回当前容量（不扩容最多能存的元素数）
// empty()：判断是否为空
std::cout << "size: " << vec.size() << ", capacity: " << vec.capacity() << std::endl; // 0, 0
// reserve(n)：预分配至少n个元素的容量，只改capacity，不改size
vec.reserve(20); 
std::cout << "size: " << vec.size() << ", capacity: " << vec.capacity() << std::endl; // 0, 20
// 注意：reserve分配的内存未初始化，直接访问 vec[0] 是未定义行为！
// resize(n)：调整size为n，会创建/销毁对象
vec.resize(10); 
std::cout << "size: " << vec.size() << ", capacity: " << vec.capacity() << std::endl; // 10, 20
// 如果n < 当前size，会删除末尾的元素
// 如果n > 当前size，会在末尾添加默认构造的元素
// resize(n, val)：调整size为n，新增元素用val初始化
vec.resize(15, 100); // 新增的5个元素都是100
// shrink_to_fit()：请求将capacity收缩到与size相等（C++11）
vec.shrink_to_fit(); // 非强制，编译器可能忽略
// 经典缩容技巧（强制）：利用临时对象交换内存
std::vector<int>(vec).swap(vec); 
// 原理：创建一个容量=size的临时拷贝，交换指针后临时对象销毁释放旧内存

方法	作用	改变 size	改变 capacity	构造/销毁对象
reserve(n)	预分配容量	×	√ (至少 n)	×
resize(n)	调整元素个数	√ (变为 n)	可能增大	√
shrink_to_fit	收缩容量	×	可能减小	×
clear()	清空元素	√ (变为 0)	×	√

对于 assign 方法，有以下例子：assign(15, 12)对于已初始化的空间，会完全替换容器内容变为 15 ，resize(15, 12) 则会保留前 10 个。

函数	作用	改变 size	改变 capacity	清空旧元素
assign(15, 12)	完全替换容器内容	√ 变为 15	不变（≤当前容量）	√ 清空
resize(15, 12)	调整容器大小	√ 变为 15	可能增大	× 保留前 10 个
reserve(150)	预分配容量	× 不变	√ 变为 150	× 无影响

修改操作

vector 的修改操作是日常使用最频繁的，其中 push_back 和 emplace_back 的区别尤为重要：

std::vector<int> vec;
vec.reserve(10); // 好习惯：先预分配

// 1. push_back：在尾部添加元素
vec.push_back(1);
vec.push_back(2);

// 2. emplace_back：在尾部直接构造元素（C++11）
// 对于复杂对象，emplace_back 比 push_back 更高效，因为它避免了临时对象的拷贝
class Person {
public:
    Person(std::string name, int age) : name_(name), age_(age) {}
private:
    std::string name_;
    int age_;
};
std::vector<Person> people;
// push_back 需要先构造临时对象，再拷贝/移动到容器中
people.push_back(Person("Alice", 20));
// emplace_back 直接在容器内存中构造对象，零拷贝
people.emplace_back("Bob", 25); // 直接传构造函数参数

// 3. pop_back：删除尾部元素
vec.pop_back();

// 4. insert：在指定位置插入元素（返回新元素的迭代器）
auto it = vec.insert(vec.begin(), 0); // 在开头插入0，O(n)复杂度

// 5. erase：删除指定位置或区间的元素（返回下一个元素的迭代器）
it = vec.erase(vec.begin()); // 删除开头元素

// 6. assign：赋值新内容，会清空原有内容
vec.assign(5, 100); // 变为5个100
vec.assign({1, 2, 3, 4, 5}); // 变为初始化列表中的内容

// 7. swap：交换两个vector的内容（O(1)，只交换指针）
std::vector<int> other = {10, 20, 30};
vec.swap(other);

内存管理与扩容

扩容的触发条件

当我们向 vector 中添加元素（如 push_back、insert）时，如果 size() == capacity()，说明当前已分配的内存已经用完，此时 vector 会触发扩容流程：

1. 分配新内存：申请一块更大的连续内存空间。不同编译器的扩容策略不同，通常是按1.5 倍或2 倍增长（ GCC/libstdc++是 2 倍， MSVC 是 1.5 倍）。
2. 迁移元素：将旧内存中的元素拷贝或移动到新内存中。
3. 销毁旧元素：调用旧内存中元素的析构函数。
4. 释放旧内存：将旧内存块归还给操作系统。
5. 更新指针：将 _M_start、_M_finish、_M_end_of_storage 更新为指向新内存。

扩容的代价

扩容是一个O(n) 的操作，因为它需要移动所有元素。如果 vector 存储的是复杂对象，且没有移动构造函数，那么每一次扩容都会伴随着大量的拷贝构造和析构调用，代价非常高昂。这就是为什么 reserve() 如此重要：如果你能预先知道 vector 大概要存储多少元素，提前调用 reserve(n) 可以避免多次扩容，极大提升性能。

移动语义对扩容的优化（ C++11 ）

C++11 引入的移动语义极大地缓解了扩容的代价。如果 vector 的元素类型拥有移动构造函数（且标记为 noexcept），那么在扩容时 vector 会优先使用移动而不是拷贝来迁移元素。移动操作只是转移资源的所有权（如指针），而不复制数据，速度极快。因此，为你的自定义类型实现移动构造函数和移动赋值运算符，是配合 vector 使用的最佳实践之一。

迭代器的失效

vector 的迭代器类型

vector 支持多种迭代器：普通迭代器，iterator，可读写；常量迭代器，const_iterator，只读， C++11 推荐使用 cbegin() 和 cend() 获取以及反向迭代器 reverse_iterator，从尾到头遍历，使用 rbegin() 和 rend()。

std::vector<int> vec = {1, 2, 3, 4, 5};
// 正向遍历
for (auto it = vec.begin(); it != vec.end(); ++it) {
    std::cout << *it << " ";
}
// 反向遍历
for (auto it = vec.rbegin(); it != vec.rend(); ++it) {
    std::cout << *it << " ";
}
// 范围for循环（C++11），本质是迭代器的语法糖
for (const auto& val : vec) { // 推荐加const&，避免拷贝
    std::cout << val << " ";
}

迭代器失效的场景与后果

扩容操作导致所有迭代器失效

任何可能触发扩容的操作（如 push_back、insert、emplace_back），一旦真的发生了扩容，那么所有指向旧内存的迭代器、指针、引用都会失效。

std::vector<int> vec;
vec.reserve(3);
vec = {1, 2, 3};
auto it = vec.begin();
std::cout << *it << std::endl; // 正常
vec.push_back(4); // 触发扩容（假设capacity从3变为6）
// std::cout << *it << std::endl; // 崩溃！it指向的旧内存已被释放

• 调用可能扩容的函数后，务必重新获取迭代器。
• 如果在循环中调用 push_back，尽量不要在循环外保存迭代器。

插入操作导致插入点及之后的迭代器失效

即使没有扩容，在 vector 中间插入元素也会导致插入点及之后的所有迭代器失效，因为插入位置后面的元素都要向后移动。

std::vector<int> vec = {1, 2, 3, 4, 5};
auto it = vec.begin() + 2; // 指向元素3
auto it_end = vec.end();

vec.insert(it, 100); // 在3前面插入100
// 此时 it 和 it_end 都失效了！

• 利用 insert 的返回值：它会返回指向新插入元素的迭代器。

it = vec.insert(it, 100); // 重新获取有效迭代器

删除操作导致删除点及之后的迭代器失效

erase 或 pop_back 会导致被删除元素及之后的迭代器失效。

std::vector<int> vec = {1, 2, 3, 4, 5};
auto it = vec.begin() + 2; // 指向3

vec.erase(it); // 删除3
// 此时 it 失效了，原本指向4、5的迭代器也失效了

• 同样利用 erase 的返回值：它会返回指向被删元素下一个位置的迭代器。

// 正确的删除循环写法
for (auto it = vec.begin(); it != vec.end(); ) {
    if (should_delete(*it)) it = vec.erase(it); // 删除并获取下一个迭代器
    else ++it;
}

1. 只要发生扩容，所有迭代器、指针、引用全部失效。
2. 只要发生插入，插入点及之后的迭代器失效（若扩容则全部失效）。
3. 只要发生删除，删除点及之后的迭代器失效。
4. pop_back 只会让尾迭代器失效。
5. clear 会让所有迭代器失效。

性能优化

预分配内存：这是最简单也最有效的优化。如果你知道 vector 大概要存多少元素，一定要提前 reserve，避免多次扩容。

// 坏代码：可能触发多次扩容
std::vector<int> vec;
for (int i = 0; i < 10000; ++i) {
    vec.push_back(i);
}

// 好代码：一次分配到位
std::vector<int> vec;
vec.reserve(10000); // 预分配
for (int i = 0; i < 10000; ++i) {
    vec.push_back(i);
}

优先使用 emplace_back 而非 push_back：对于自定义类型，emplace_back 直接在容器内存中构造对象，避免了临时对象的构造和析构，效率更高。

std::vector<std::string> vec;
// push_back：构造临时string -> 拷贝到容器 -> 销毁临时
vec.push_back(std::string("hello"));
// emplace_back：直接在容器中构造string
vec.emplace_back("hello");

避免不必要的拷贝，善用移动语义：如果一个 vector 不再需要了，用 std::move 把它的资源转移给另一个 vector ，而不是拷贝。

std::vector<int> source = {1, 2, 3, 4, 5};
// std::vector<int> target = source; // 拷贝，O(n)
std::vector<int> target = std::move(source); // 移动，O(1)，source变为空

同样，在范围 for 循环中，如果不需要修改元素，尽量用 const auto&，避免值拷贝：

std::vector<Person> people = /* ... */;
// for (auto p : people) { ... } // 每次循环都拷贝一个Person
for (const auto& p : people) { ... } // 只绑定引用，零拷贝

及时释放不需要的内存：clear() 只会清空元素，不会释放内存（capacity 不变）。如果你确定不再需要那么多内存，可以用 shrink_to_fit 或 swap 技巧释放：

vec.clear(); // size=0, capacity不变
vec.shrink_to_fit(); // 尝试释放多余内存
// 或者强制释放：
std::vector<int>(vec).swap(vec);

存储指针或智能指针而非大对象

如果你的对象非常大，且拷贝成本很高，可以考虑在 vector 中存储指针或智能指针（如 std::unique_ptr 或 std::shared_ptr），这样移动和扩容的代价只是指针的拷贝。

如果存储裸指针，务必记得在销毁 vector 前手动 delete 每个元素，否则会内存泄漏

std::vector<Person*> people;
people.push_back(new Person("Alice", 20));
// ... 使用 ...
// 销毁前必须手动释放
for (auto p : people) {
    delete p;
}
people.clear();

更推荐使用 std::unique_ptr，它会自动管理内存：

std::vector<std::unique_ptr<Person>> people;
people.emplace_back(std::make_unique<Person>("Bob", 25));
// 离开作用域时，unique_ptr会自动delete，无需手动操作

避免使用 vector<bool>

vector<bool> 并不是一个真正的存储 bool 类型的 vector ，而是一个位压缩的特化版本。它为了节省空间，将每个 bool 存储为一个 bit ，而不是一个 byte 。

这导致了几个问题：

• 它不满足 STL 容器的要求（比如 data() 返回的不是 bool*）；
• 它的迭代器行为很奇怪（解引用返回的是一个代理对象，不是真正的 bool&）；
• 它的性能可能比普通 vector 更差。

如果你需要固定大小的位集合，用 std::bitset；如果你需要动态大小的，用 std::vector<char> 或 std::deque<bool>。

常见陷阱

对空 vector 调用 front() 或 back()

std::vector<int> vec;
// int a = vec.front(); // 未定义行为！
// int b = vec.back();  // 未定义行为！

注意：调用前务必检查 empty()。

混淆 resize 和 reserve

std::vector<int> vec;
vec.reserve(10); // 只分配内存，不创建对象
// for (int i = 0; i < 10; ++i) {
//     vec[i] = i; // 错误！vec[i] 未初始化，未定义行为
// }

// 正确做法1：用 resize
vec.resize(10);
for (int i = 0; i < 10; ++i) {
    vec[i] = i;
}

// 正确做法2：用 reserve + push_back
vec.reserve(10);
for (int i = 0; i < 10; ++i) {
    vec.push_back(i);
}

在 vector 中存储引用

vector 要求元素必须是可拷贝或可移动的，而引用不能重新赋值，也不满足可拷贝的要求。

// std::vector<int&> refs; // 编译错误！

如果需要引用语义，可以存储 std::reference_wrapper 或指针。

认为 shrink_to_fit 一定会释放内存

shrink_to_fit() 只是一个请求， C++标准并不强制要求编译器实现它。编译器可能会忽略这个请求，或者有自己的策略。如果一定要释放内存，使用 vector<T>(v).swap(v) 技巧更可靠。

现代 C++中的 vector

C++11 ：移动语义、 emplace 、 initializer_list

• 移动构造和移动赋值让 vector 的转移成本降为 O(1)；
• emplace 和 emplace_back 让构造元素更高效；
• 初始化列表构造让 vector 的初始化更简洁；
• cbegin()/cend() 方便获取常量迭代器；
• data() 方便获取底层数组指针。

C++14/17 ：更完善的辅助

• C++14 ：std::make_unique 配合 vector<std::unique_ptr<T>> 使用更安全；
• C++17 ：emplace 的返回值优化，可以更方便地获取插入元素的引用；
• C++17 ：std::as_const 方便获取 const 版本的 vector 。

C++20 ： constexpr vector 与范围操作

• constexpr vector： C++20 允许 vector 在编译期使用！你可以在编译期创建 vector 、填充数据、进行计算，然后将结果作为常量使用，极大提升了编译期编程的能力。
• std::erase / std::erase_if：终于不用写那个容易出错的 erase 循环了！

std::vector<int> vec = {1, 2, 3, 4, 5, 2, 2};
std::erase(vec, 2); // 删除所有值为2的元素
std::erase_if(vec, [](int x) { return x % 2 == 0; }); // 删除所有偶数

与其他容器的对比

vector 虽然强大，但不是万能的。了解它与其他容器的对比，能帮助你在正确的场景选择正确的工具：

特性	vector	deque	list / forward_list	array
内存布局	连续	分段连续	不连续（链表）	连续
随机访问	O(1)，极快	O(1)，较快	不支持	O(1)，极快
尾部增删	O(1)（均摊）	O(1)	O(1)	不支持
头部增删	O(n)，慢	O(1)	O(1)	不支持
中间增删	O(n)，慢	O(n)，较慢	O(1)，极快	不支持
迭代器失效	扩容/插入/删除易失效	插入/删除易失效	仅删除当前节点失效	不失效
内存开销	小	中等	大（每个节点有指针开销）	固定

1. 首选 vector：如果你需要随机访问，且主要在尾部增删元素， vector 永远是首选。它的内存连续性最好，缓存友好，性能最高。
2. 用 deque：如果你需要频繁在头部和尾部都增删元素（如队列）， deque 是更好的选择。
3. 用 list：如果你需要频繁在中间位置插入或删除大量元素，且不需要随机访问， list （双向链表）或 forward_list （单向链表）更合适。
4. 用 array：如果你需要固定大小的数组，且大小在编译期已知， array 比 vector 更轻量（栈上分配，无动态内存开销）。

vector 是 C++ STL 中最基础、最常用的容器，它的设计哲学是“为最常用的场景做最极致的优化”。回顾全文，我们可以总结出使用 vector 的最佳实践：

1. 理解底层：记住它是三个指针维护的动态数组，理解 size 和 capacity 的区别。
2. 预分配内存：提前用 reserve() 避免频繁扩容，这是最有效的优化。
3. 安全访问：确定索引有效时用 operator[] 追求效率，不确定时用 at() 追求安全。
4. 高效插入：优先用 emplace_back 代替 push_back，善用移动语义。
5. 警惕失效：时刻注意迭代器失效的场景，操作后及时重新获取迭代器，或利用返回值。
6. 及时释放：不需要的内存及时用 shrink_to_fit 或 swap 技巧释放。
7. 现代特性：拥抱 C++11/14/17/20 的新特性，如范围 for 、std::erase_if、constexpr 等。