手写常见操作：vector 扩容、string 分割、链表翻转
（一）vector扩容
在 C++ 中，vector 的扩容机制是动态数组实现的核心特性，直接关系到性能和内存使用效率。以下是深入剖析：
1. 扩容触发条件
vector<int> v;
v.push_back(1); // 当 size() == capacity() 时触发扩容
- 当插入新元素时，若当前元素数量
size()等于容量capacity()，则触发扩容
2. 扩容算法核心步骤
// 伪代码逻辑
void push_back(const T& value) {if (size == capacity) { // 需要扩容new_cap = max(2 * capacity, 1); // 典型增长策略new_data = allocate(new_cap); // 1. 申请新内存copy_or_move(old_data, new_data); // 2. 迁移数据deallocate(old_data); // 3. 释放旧内存}// 插入新元素...
}
3. 关键特性与复杂度分析
(1) 扩容因子（Growth Factor）
| 编译器实现 | 扩容策略 | 数学证明最优性 |
|---|---|---|
| GCC | 2 倍扩容（常见） | 分摊 O(1) 时间复杂度 |
| MSVC | 1.5 倍扩容 | 更好内存利用率 |
(2) 时间复杂度
- 单次
push_back：最坏 O(n)（触发扩容时） - 均摊时间复杂度：O(1)（通过分摊分析证明）
4. 扩容过程可视化
vector<int> v;
// 初始状态: capacity=0, size=0v.push_back(1); // 第1次扩容 → capacity=1
v.push_back(2); // 第2次扩容 → capacity=2
v.push_back(3); // 第3次扩容 → capacity=4
v.push_back(4); // 无需扩容
v.push_back(5); // 第4次扩容 → capacity=8
5. 性能优化技巧
(1) 预分配内存
vector<int> v;
v.reserve(1000); // 直接分配足够容量，避免多次扩容
(2) 移动语义优化（C++11+）
class BigObject {
public:BigObject(BigObject&& other) noexcept; // 移动构造函数
};vector<BigObject> v;
v.push_back(BigObject()); // 触发移动而非拷贝
6. 不同编译器的扩容策略
通过代码验证不同编译器的扩容行为：
vector<int> v;
size_t last_cap = 0;for (int i = 0; i < 100; ++i) {v.push_back(i);if (v.capacity() != last_cap) {cout << "Size: " << v.size() << ", New Capacity: " << v.capacity() << endl;last_cap = v.capacity();}
}
- GCC 输出：1 → 2 → 4 → 8 → 16 → 32 → 64 → 128…
- MSVC 输出：1 → 2 → 3 → 4 → 6 → 9 → 13 → 19…
7. 扩容时的元素迁移
- 拷贝语义：调用元素的拷贝构造函数（深拷贝）
- 移动语义（C++11+）：优先调用移动构造函数（高效）
