当前位置：首页 > article >正文

手撕算法之`vector` 扩容、`string` 分割、链表翻转

article 2025/3/22 3:21:03

手写常见操作：`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=0

v.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();
    }
}