C++ STL 容器 vector 详解：特性、用法与底层实现

3. 特殊类型的 vector 初始化

// 自定义结构体
struct Person { string name; int age; Person(string n, int a) : name(n), age(a) {} };
vector<Person> people = {{"Alice", 20}, {"Bob", 25}};

// 指针类型（注意：需手动管理内存，避免内存泄漏）
vector<int*> v;
v.push_back(new int(20)); // 存储堆指针（需手动 delete）

三、vector 核心成员函数

1. 迭代器相关函数

注意：迭代器可能失效（如扩容、删除元素后），失效后不可再使用。

2. 容量与大小操作

关键区别：reserve 只改容量、不改大小；resize 既改大小、可能改容量。

3. 元素增删改查操作

尾部操作（高效）

• push_back(val)：在尾部插入元素 val。
• emplace_back(args...)：在尾部直接构造元素（C++11+），避免拷贝开销。
• pop_back()：删除尾部元素。

中间 / 头部插入（低效）

• insert(pos, val)：在迭代器 pos 位置插入 val。
• erase(pos)：删除迭代器 pos 指向的元素。
• clear()：删除所有元素（size=0），容量不变。

4. 元素访问函数

四、vector 内存管理深度解析

1. 扩容机制

当 push_back/emplace_back 插入元素时，若 size() == capacity()，vector 会自动扩容：

1. 分配新内存：新容量通常是原容量的 2 倍（GCC）或 1.5 倍（VS）；
2. 拷贝旧元素：将旧内存中的所有元素拷贝（或移动）到新内存；
3. 释放旧内存：销毁旧内存中的元素并释放空间；
4. 更新指针。

2. 扩容的问题

• 性能开销：频繁扩容会导致多次'分配 - 拷贝 - 释放'；
• 迭代器失效：扩容后旧内存被释放，指向旧内存的迭代器、指针、引用全部失效。

3. 内存优化技巧

• 提前预留容量：若已知元素数量范围，提前用 reserve(n) 预分配容量。
• 用 emplace_back 替代 push_back：减少拷贝开销。
• 释放多余内存：shrink_to_fit() 或 swap 技巧。

五、vector 高级用法

1. 结合 STL 算法

#include <algorithm>
vector<int> v{3,1,4,1,5,9,2,6};
sort(v.begin(), v.end()); // 排序
auto it = find(v.begin(), v.end(), 5); // 查找
v.erase(unique(v.begin(), v.end()), v.end()); // 去重
reverse(v.begin(), v.end()); // 反转

2. 遍历方式

• 普通 for 循环：直观，支持随机访问。
• 范围 for 循环 (C++11+)：简洁，for (int& x : v)。
• 迭代器遍历：兼容所有 STL 容器。
• std::for_each：支持复杂逻辑。

3. 特殊场景用法

• 多维 vector：vector<vector<int>> mat(3, vector<int>(4, 0));（内存不连续）。
• 函数参数 / 返回值：优先用引用传递，依赖 NRVO 优化返回值。
• 存储智能指针：优先用 unique_ptr/shared_ptr 替代裸指针。

六、vector 常见坑与避坑指南

1. 迭代器失效

• 扩容后：所有迭代器失效。解决方案：提前 reserve 避免扩容。
• erase 后：删除位置后的迭代器失效。解决方案：用 erase 的返回值更新迭代器。
• clear 后：所有迭代器失效。

2. 空 vector 访问元素

空 vector 调用 v[0]、v.front() 会触发未定义行为。访问前需检查 !v.empty()。

3. 混淆 size() 和 capacity()

• size() 是元素个数；capacity() 是容量。
• clear() 仅清空元素，容量不变。

4. 频繁在中间插入 / 删除元素

vector 不适合此场景，应改用 list 或 deque。

七、vector 与其他容器对比

八、vector 底层实现的深度细节

以 GCC 的 std::vector 实现为例，其内部成员简化后如下：

template <typename T, typename Allocator = std::allocator<T>>
class vector {
private:
    T* _M_start;          // 指向首元素
    T* _M_finish;         // 指向尾元素的下一个位置
    T* _M_end_of_storage; // 指向内存块末尾
    Allocator _M_get_allocator();
};

• size() = _M_finish - _M_start
• capacity() = _M_end_of_storage - _M_start

1. 分配器的作用

vector 通过分配器管理内存，包括 allocate、deallocate、construct、destroy。

2. 不同编译器的扩容策略差异

九、vector 与自定义类型的交互

1. 默认构造函数要求

vector<T> v(n) 会默认构造 n 个 T 对象，因此 T 必须有可访问的默认构造函数。若无，需用 vector<T> v(n, val)。

2. 拷贝与移动语义

• 若自定义类型无移动构造函数，扩容时会进行深拷贝，开销大。
• 若定义了移动构造函数，扩容时会优先移动元素，性能大幅提升。

十、异常安全性

• 插入操作：若在构造新元素时抛出异常，vector 保持原有状态。
• 删除操作：析构函数不应抛异常，否则视为程序错误。

十一、C++ 标准对 vector 的更新

• C++11：移动语义、emplace 系列函数、初始化列表、data() 方法。
• C++17：emplace_back 返回引用、并行算法支持。
• C++20：constexpr vector、erase_if。

十二、性能优化的极致技巧

• 批量操作：用 insert(begin, first, last) 批量插入，替代多次 push_back。
• 避免不必要的 shrink_to_fit：仅在确定不再添加元素且需释放内存时使用。
• 利用内存连续性：vector 的连续内存布局友好于 CPU 缓存。

十三、边缘场景与特殊用法

1. 存储 bool 类型的特殊性

vector<bool> 是特化版本，每个元素占 1 位，不支持 data() 方法，迭代器返回代理对象。若需高效访问，可改用 vector<char>。

2. 零容量 vector 的 data() 行为

空 vector 的 data() 可返回 nullptr 或任意非空指针，解引用是未定义行为。

十四、总结

vector 的核心优势是随机访问高效 + 动态扩容 + 接口丰富。使用时需重点关注：

1. 内存管理：用 reserve() 提前预留容量；
2. 迭代器失效：erase 后用返回值更新迭代器；
3. 效率优化：优先用 emplace_back 替代 push_back；
4. 避坑：不访问空 vector 元素，不混淆 size() 和 capacity()。

十五、示例代码

#include<iostream>
#include<vector>
using namespace std;

void testvectorconstructor() {
    std::vector<int> v1;
    vector<int> v2(5, 1);
    for (int i = 0; i < v2.size(); ++i) {
        cout << v2[i] << " ";
    }
    cout << endl;

    vector<float> v6(5, 1.00);
    for (int i = 0; i < v6.size(); ++i) {
        cout << v6[i] << " ";
    }
    cout << endl;

    vector<string> v8(5, "hello");
    for (int i = 0; i < v8.size(); ++i) {
        cout << v8[i] << " ";
    }
    cout << endl;

    // 二维 vector
    vector<vector<int>> vv1(5);
    for (int i = 0; i < vv1.size(); ++i) {
        vv1[i].resize(4);
    }

    // 迭代器遍历
    auto it = v2.begin();
    while (it != v2.end()) {
        cout << *it << " ";
        it++;
    }
    cout << endl;
}

void testvectorpush() {
    vector<int> v1;
    v1.push_back(1);
    v1.push_back(2);
    v1.insert(v1.begin(), 0);
    v1.insert(v1.end(), 7);
    v1.insert(v1.begin()+2, 9);

    vector<int> v2(10, 2);
    cout << "v2 capacity:" << v2.capacity() << endl;
    v2.reserve(100);
    cout << "v2 capacity:" << v2.capacity() << endl;
}

void teststdfind() {
    vector<int> v1;
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    v1.push_back(5);
    v1.push_back(6);

    vector<int>::iterator pos = std::find(v1.begin(), v1.end(), 2);
    cout << pos - v1.begin() << endl;
}

int main() {
    testvectorconstructor();
    testvectorpush();
    teststdfind();
    return 0;
}