C++ STL vector 详解：基础用法、核心接口与实战算法

实践示例：

void test_vector1() {
    vector<int> v1;              // 空 vector
    vector<int> v2(10, 1);       // 10 个 1
    vector<int> v3(v2);          // 拷贝构造
    vector<int> v4(v3.begin(), v3.end()); // 范围构造
    vector<int> v6 = { 1, 2, 3, 4, 5 };   // 列表初始化
    
    Print(v2);
    Print(v6);
}

2. 空间增长机制

vector 底层是连续内存，扩容时涉及内存分配和拷贝，开销较大。理解其增长策略对性能优化至关重要。

扩容倍数差异

不同编译器实现的 STL 版本，扩容策略不同：

• VS (PJ 版本): 通常按 1.5 倍增长。
• g++ (SGI 版本): 通常按 2 倍增长。

不要固化认为都是 2 倍，具体取决于实现。测试代码可验证这一现象：

void TestVectorExpand() {
    size_t sz = 0;
    vector<int> v;
    cout << "making v grow:\n";
    for (int i = 0; i < 100; ++i) {
        v.push_back(i);
        if (sz != v.capacity()) {
            sz = v.capacity();
            cout << "capacity changed: " << sz << '\n';
        }
    }
}

Reserve 优化

如果已知需要存储的元素数量，提前调用 reserve 可以避免多次扩容带来的性能损耗。

void TestVectorExpandOP() {
    vector<int> v;
    v.reserve(100); // 提前预留空间
    for (int i = 0; i < 100; ++i) {
        v.push_back(i);
    }
}

3. 增删查改操作

vector 只支持尾部插入和删除（push_back, pop_back），因为头部操作需要移动大量数据，效率低。若需头插/头删，可使用 insert 和 erase。

实践示例：

void test_vector3() {
    vector<int> v1 = { 1, 2, 3 };
    v1.push_back(4);
    
    // 头插
    v1.insert(v1.begin(), 0);
    // 中间插入
    v1.insert(v1.begin() + 3, 0);
    
    // 头删
    v1.erase(v1.begin());
    // 中间删除
    v1.erase(v1.begin() + 3);
}

4. Emplace 机制

emplace 系列函数（如 emplace_back）在 C++11 引入，相比 push_back 能直接在容器内构建对象，避免临时对象的拷贝构造，效率更高。

struct AA {
    int _a1 = 1, _a2 = 1;
    AA(int a1 = 1, int a2 = 1) :_a1(a1), _a2(a2) {}
};

void test_vector4() {
    vector<AA> v1;
    AA aa1 = { 0, 0 };
    
    v1.push_back(aa1);      // 先构造再拷贝
    v1.emplace_back(aa1);   // 转发参数构造
    v1.emplace_back(2, 2);  // 直接传参构造，无需临时对象
}

三、经典算法题实战

1. 只出现一次的数字

题目描述： 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

思路： 利用异或运算性质，相同为 0，不同为 1。所有数异或一遍，成对的抵消，剩下的即为答案。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int val = 0;
        for (auto e : nums) {
            val ^= e;
        }
        return val;
    }
};

• 时间复杂度： O(n)
• 空间复杂度： O(1)

2. 杨辉三角

题目描述： 给定行数 numRows，生成杨辉三角的前 numRows 行。

思路： 二维 vector 模拟。每行第一个和最后一个元素为 1，中间元素等于上一行同列与前一列之和。

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> vv;
        vv.resize(numRows);
        
        for (size_t i = 0; i < numRows; ++i) {
            vv[i].resize(i + 1, 1);
            for (size_t j = 1; j < vv[i].size() - 1; ++j) {
                vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
            }
        }
        return vv;
    }
};

• 时间复杂度： O(n²)
• 空间复杂度： O(n²)（用于存储结果）

四、完整代码展示

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

void Print(const vector<int>& v) {
    for (auto e : v) {
        cout << e << " ";
    }
    cout << endl;
}

void test_vector1() {
    vector<int> v1;
    vector<int> v2(10, 1);
    vector<int> v3(v2);
    vector<int> v4(v3.begin(), v3.end());
    vector<int> v6 = { 1, 2, 3, 4, 5 };
    Print(v2);
    Print(v6);
}

void test_vector2() {
    vector<int> v1;
    const int n = 100;
    v1.reserve(n);
    size_t begin = clock();
    for (size_t i = 0; i < n; i++) {
        v1.push_back(i);
    }
    size_t end = clock();
    cout << end - begin << endl;
}

void test_vector3() {
    vector<int> v1 = { 1, 2, 3 };
    v1.push_back(4);
    v1.insert(v1.begin(), 0);
    v1.erase(v1.begin());
    Print(v1);
}

struct AA {
    int _a1 = 1, _a2 = 1;
    AA(int a1 = 1, int a2 = 1) :_a1(a1), _a2(a2) {}
};

void test_vector4() {
    vector<AA> v1;
    AA aa1 = { 0, 0 };
    v1.push_back(aa1);
    v1.emplace_back(aa1);
    v1.emplace_back(2, 2);
}

int main() {
    test_vector4();
    return 0;
}