第九章：vector思维导图

第九章：vector

一、vector基础认知

  1. vector的本质定义：vector是STL中的顺序容器（sequence container），底层为动态数组结构，是支持动态改变元素个数的顺序表，内存连续存储，访问效率和原生数组一致，是C++开发中最常用的STL容器之一。

  2. 命名说明：vector单词本意是“向量”，STL中用其命名顺序表，具体命名的历史设计原因无需深究，直接遵循C++标准使用即可。

  3. 基础使用规范

  • 头文件引入：需包含#include <vector>，vector位于std命名空间内；
  • 类模板特性：vector是类模板，可实例化出存储任意类型的vector对象，包括内置类型（int、double）、自定义类型（string），甚至vector自身类型。
  1. 学习核心逻辑：string容器的接口设计、迭代器体系、空间管理逻辑和vector高度相似，掌握string的使用后，vector的基础接口可快速上手，无需重复学习底层通用逻辑。

二、vector的模板参数与空间配置器

vector本质是一个类模板，支持自定义存储的元素类型，老师详细讲解了模板参数的设计与底层原理：

  1. vector类模板核心声明 
    template<class T, class Alloc = allocator<T>>
class vector;
  2. 模板参数逐点详解
    模板参数 核心作用 细节说明
    第一个参数T 元素数据类型 必须显式传入，决定vector中存储的元素类型，比如vector<int>就表示存储int类型的vector
    第二个参数Alloc 空间配置器（俗称内存池） 带有缺省值，日常开发无需手动传入；是STL六大组件之一，专门负责容器的内存管理
  3. 空间配置器的底层原理
    • 核心作用：解决STL容器高频向系统申请堆空间的效率问题。容器不会直接向堆申请空间，而是优先向内存池申请；内存池空间不足时，再由内存池向堆申请批量空间，减少系统调用的次数，大幅提升内存申请效率。
    • 自定义扩展能力：模板参数预留了自定义扩展的口子，若对默认内存池的效率不满意，可按照STL规范实现自定义内存池，将类型传入第二个模板参数，vector就会使用自定义的内存池管理空间。
  4. 补充语法知识点：模板参数支持缺省类型，和函数的缺省参数逻辑完全一致，不手动传参时，自动使用编译器提供的默认缺省值，这个特性是本节课首次补充讲解的语法点。

三、vector的核心遍历方式

vector底层为数组结构，支持三种主流遍历方式，均支持元素的读取与修改，和string容器的遍历逻辑完全一致，老师快速过了核心用法：

  1. 下标+[]运算符访问
    • 语法：vector对象名[下标索引]
    • 核心特点：和原生数组访问逻辑完全一致，支持元素的读和写，使用便捷、访问效率最高，是日常开发首选的访问方式。
    • 补充细节：string容器早期用length()获取有效长度，后续STL容器统一用size()获取有效元素个数，string也兼容了size()接口；而vector仅提供size()，无length()接口。
    • 完整代码示例 
      #include<iostream>
#include<vector>
using namespace std;

int main()
{
    vector<int> v = {1,2,3,4,5};
    // 下标遍历，支持读和写
    for (size_t i = 0; i < v.size(); i++)
    {
        v[i] += 1; // 修改元素
        cout << v[i] << " ";
    }
    cout << endl;
    return 0;
}
  2. 迭代器遍历
    • 迭代器本质：行为类似指针，底层不一定是原生指针，是定义在容器类域内的嵌套类型，使用时必须指定类域。
    • 基础语法与代码示例 
      #include<iostream>
#include<vector>
using namespace std;

int main()
{
    vector<int> v = {1,2,3,4,5};
    // 正向迭代器遍历，支持读和写
    vector<int>::iterator it = v.begin();
    while(it != v.end())
    {
        *it += 1; // 解引用修改元素
        cout << *it << " ";
        ++it;
    }
    cout << endl;
    return 0;
}
    • 迭代器类型：vector支持4种迭代器，分别是正向迭代器、反向迭代器、const正向迭代器、const反向迭代器，和string容器的迭代器体系完全一致。
  3. 范围for遍历
    • 语法：for(auto e : 容器对象)，如需修改元素，使用auto& e引用接收。
    • 底层原理：范围for的底层由迭代器实现，因此所有支持迭代器的容器，天然支持范围for。
    • 特点：语法极简，无需关心下标和边界，日常遍历场景优先使用。
    • 代码示例 
      #include<iostream>
#include<vector>
using namespace std;

int main()
{
    vector<int> v = {1,2,3,4,5};
    // 范围for遍历，加&可修改元素
    for (auto& e : v)
    {
        e += 1;
        cout << e << " ";
    }
    cout << endl;
    return 0;
}

四、vector的构造与初始化方式

vector支持多种初始化方式，核心构造函数如下，其中无参构造、拷贝构造、初始化列表构造使用频率最高：

  1. 无参默认构造（全缺省构造）
    • 语法：vector<T> v;
    • 作用：创建一个空的vector对象，size为0，capacity根据编译器实现有默认初始值。
    • 补充细节：构造函数的最后一个参数支持传入自定义空间配置器对象，仅当自定义内存池没有默认构造函数、需要带参构造时才会使用，日常开发几乎不会涉及该场景。
  2. n个val值构造
    • 语法：vector<T> v(n, val);
    • 作用：创建一个包含n个val元素的vector对象，直接完成批量初始化。
    • 代码示例：vector<int> v(5, 10); 创建包含5个10的vector。
  3. 迭代器区间构造
    • 语法：vector<T> v(iterator first, iterator last);
    • 作用：用一段迭代器区间内的元素初始化vector，支持其他容器的迭代器区间，兼容性极强。
    • 代码示例 
      int arr[] = {1,2,3,4,5};
vector<int> v(arr, arr + sizeof(arr)/sizeof(int)); // 用数组区间初始化
vector<int> v2(v.begin(), v.end()); // 用已有vector的区间初始化
  4. 拷贝构造函数
    • 语法：vector<T> v(v2);
    • 作用：用已有的vector对象拷贝创建新对象，底层为深拷贝，无需手动管理内存，避免同一块空间被多次释放的问题。
  5. C++11 initializer_list（初始化列表）构造
    这是本节课老师重点补充的C++11新特性，详细讲解了底层原理和用法：
    • 语法：vector<int> v = {1,2,3,4}; 或 vector<int> v{1,2,3,4};
    • 底层原理：花括号包裹的元素会被编译器自动识别为initializer_list类型，vector提供了对应的构造函数，底层会遍历initializer_list中的元素，通过push_back批量插入到vector中。
    • 底层结构：initializer_list底层本质是两个指针，分别指向栈上开辟的连续空间的起始和结束位置，支持begin()、end()迭代器和size()接口，迭代器就是原生指针。
    • 特点：语法简洁，支持直接批量初始化元素，是C++11新增的核心实用特性。

五、vector空间管理相关接口

vector的空间管理接口和string容器高度相似，老师快速讲解了核心接口的用法、规则和与string的异同点：

  1. 基础属性获取接口
    接口 核心作用 细节说明
    size() 获取vector中有效元素的个数 日常开发高频使用
    capacity() 获取vector当前的容量 即底层已开辟空间可容纳的最大元素个数
    empty() 判断vector是否为空 为空返回true，非空返回false
    max_size() 获取理论上vector可容纳的最大元素个数 无实际业务价值，日常开发几乎不用
  2. 空间扩容接口reserve()
    • 核心作用：专门用于扩容，只改变capacity，不改变size，不会对元素进行初始化。
    • 执行规则：当传入的n大于当前capacity时，会触发扩容；当n小于等于当前capacity时，vector中该接口不会做任何操作（和string不同，string不同平台对缩容的处理规则不确定）。
    • 扩容机制：不同编译器的STL实现扩容倍数不同，VS下PJ版本STL按1.5倍扩容，g++下SGI版本STL按2倍扩容。
    • 性能优化：如果提前知道vector需要存储的元素个数，提前用reserve开辟足够空间，可以避免边插入边扩容带来的效率损耗（扩容需要重新开辟空间、拷贝元素、释放旧空间，时间成本极高）。
    • 完整测试代码 
      #include<iostream>
#include<vector>
using namespace std;

// 测试vector默认扩容机制
void TestVectorExpand()
{
    size_t sz;
    vector<int> v;
    sz = v.capacity();
    cout << "vector默认扩容测试：" << endl;
    for (int i = 0; i < 100; ++i)
    {
        v.push_back(i);
        if (sz != v.capacity())
        {
            sz = v.capacity();
            cout << "capacity changed: " << sz << '\n';
        }
    }
}

// 提前reserve优化扩容性能
void TestVectorExpandOP()
{
    vector<int> v;
    size_t sz = v.capacity();
    v.reserve(100); // 提前开辟100个元素的空间，避免频繁扩容
    cout << "提前reserve后的扩容测试：" << endl;
    for (int i = 0; i < 100; ++i)
    {
        v.push_back(i);
        if (sz != v.capacity())
        {
            sz = v.capacity();
            cout << "capacity changed: " << sz << '\n';
        }
    }
}

int main()
{
    TestVectorExpand();
    TestVectorExpandOP();
    return 0;
}
  3. 大小调整接口resize()
    • 核心作用：改变vector的有效元素个数size，当新size超过当前capacity时会触发扩容，同时会对新增元素进行初始化。
    • 执行规则：
      1. 新size < 当前size：删除尾部多余的元素，size缩小到新size，capacity保持不变；
      2. 新size > 当前size：在尾部新增元素，并用指定值初始化（不指定则用元素类型的默认值），新size超过capacity时会自动触发扩容。
  4. 缩容接口：vector提供了专用的缩容接口，和string的平台不确定性不同，vector的缩容行为有明确的规则，具体底层实现会在后续模拟实现课程中详细讲解。

六、vector增删查改核心接口

老师讲解了vector增删查改的核心接口，对比了和string的异同点，重点强调了接口的使用场景和效率问题：

  1. 尾插push_back()
    • 作用：在vector的尾部插入一个元素，是最常用的插入接口。
    • 时间复杂度：O(1)（扩容时为O(n)，均摊后为O(1)）。
  2. 尾删pop_back()
    • 作用：删除vector尾部的最后一个元素，时间复杂度O(1)。
  3. 插入insert()
    • 作用：在指定迭代器position位置之前插入元素，支持3种重载：插入单个元素、插入n个相同元素、插入一段迭代器区间的元素。
    • 效率说明：头插和中间插入需要挪动后续所有元素，时间复杂度O(n)，效率较低，不推荐高频使用。
    • 补充说明：vector没有提供push_front头插接口，就是因为头插效率极低，若需要头插，可通过insert(v.begin(), val)实现。
  4. 删除erase()
    • 作用：删除指定迭代器位置的元素，或删除一段迭代器区间的元素。
    • 效率说明：中间位置删除需要挪动后续元素，时间复杂度O(n)，效率较低。
  5. 交换swap()
    • 作用：交换两个vector对象的底层数据，vector自己实现了swap成员函数，比算法库中的通用swap效率更高。
    • 实现原理：直接交换两个vector底层的数组指针、size、capacity，无需拷贝任何元素，时间复杂度O(1)。
  6. operator[]运算符重载
    • 作用：像数组一样通过下标访问元素，支持读和写，是vector最常用的元素访问方式。
    • 性能说明：返回对应位置元素的引用，编译器会优化为内联函数，无额外性能损耗。
  7. 查找find()
    • 注意：find不是vector的成员函数，是STL算法模块实现的通用函数，使用时需要包含对应头文件，支持在迭代器区间内查找指定元素，找到后返回对应迭代器，找不到返回end()。
  8. 流插入/流提取说明：vector没有实现流插入、流提取运算符重载，因为vector存储的元素类型不确定，打印格式没有统一标准，而string作为字符串有明确的连续打印需求，因此实现了该功能；若需要打印vector，需自行通过遍历逐个打印元素。
例题：找只出现一次的数字（单身狗）
  1. 题目要求：数组中除了一个数字只出现一次，其他数字都成对出现，找出这个只出现一次的数字。
  2. 解题核心思路：利用异或运算的三大特性
    • 两个相同的数字异或，结果为0；
    • 0和任何数字异或，结果为数字本身；
    • 异或运算支持交换律和结合律。
  3. 完整实现代码 
    #include <vector>
using namespace std;

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        // 范围for遍历vector，依次异或所有元素
        for(auto e : nums) 
        {
            ret ^= e;
        }
        return ret;
    }
};

// 测试代码
#include <iostream>
int main()
{
    Solution s;
    vector<int> nums = {4,1,2,1,2};
    cout << s.singleNumber(nums) << endl; // 输出4
    return 0;
}
  4. 补充说明：这道题是基础题，核心考察vector的遍历，使用范围for语法最简洁高效，无需关心下标和边界。

八、vector的嵌套使用（vector<vector> 二维数组）

  1. 嵌套实例化的核心逻辑

    • 基础实例化：vector<int>实例化出存储int的顺序表，vector<string>实例化出存储string的顺序表，本质是管理自定义类型的数组；
    • 嵌套实例化：先实例化出vector<int>这个类型，再将其作为vector模板的参数，实例化出vector<vector<int>>，本质是存储vector的顺序表，对应动态二维数组。
    • 核心类比：vector<int>是指向int数组的顺序表，vector<vector<int>>是指向vector<int>数组的顺序表。

  2. 二维vector的空间开辟

    • 构造函数初始化：可通过构造函数直接指定行数，例如vector<vector<int>> vv(10, vector<int>())，实例化出10行，每行都是一个空的vector<int>；
      补充说明：vector<int>() 是匿名临时对象，该临时对象会被拷贝10次作为vv的元素，临时对象本身在构造结束后销毁，拷贝出的元素独立存在于vector中，不会消失。
    • resize动态开辟列空间：
      • 规则二维数组：通过vv[i].resize(5, 1)给每行开辟5列，初始值为1，实现10行5列的固定二维数组；
      • 不规则二维数组（杨辉三角场景）：第0行1个元素、第1行2个元素、第2行3个元素，可通过循环vv[i].resize(i+1, 1)实现，每行的列数随行数动态变化。
    • 初始化规则：若不给第二个模板参数，会调用vector<int>的默认构造，创建空的vector<int>对象。

  3. 二维vector的元素访问

    • 访问语法：通过vv[4][3] = 5的方式访问第4行第3列的元素；
    • 底层本质：该语法完全等价于vv.operator[](sslocal://flow/file_open?url=4&flow_extra=eyJsaW5rX3R5cGUiOiJjb2RlX2ludGVycHJldGVyIn0=).operator[](sslocal://flow/file_open?url=3&flow_extra=eyJsaW5rX3R5cGUiOiJjb2RlX2ludGVycHJldGVyIn0=) = 5，是两次operator[]运算符的调用：
      1. 第一次调用外层vector的operator[]，返回下标为4的vector<int>对象；
      2. 第二次对返回的vector<int>对象调用operator[]，返回下标为3的int元素的左值引用，完成赋值。
    • 关键细节：两次operator[]调用，分别属于两个不同的vector实例，这是嵌套vector访问的核心逻辑。
例题：杨辉三角
  1. 题目要求：给定一个非负整数numRows，生成杨辉三角的前numRows行。
  2. 杨辉三角核心规律
  • 每一行的第一个元素和最后一个元素都是1；
  • 中间位置的元素，等于上一行同下标元素 + 上一行前一个下标的元素，即 vv[i][j] = vv[i-1][j] + vv[i-1][j-1]；
  • 第i行（从0开始计数）有i+1个元素。
（一）C语言实现超详细全拆解（含所有难点、参数、二级指针讲解）
1. 接口设计的核心痛点

C语言没有vector这样的容器，函数只能返回一个二级指针int**来表示二维数组，但调用者拿到这个二级指针后，无法得知两个关键信息：

  1. 这个二维数组有多少行；
  2. 杨辉三角每行元素个数不同，调用者无法得知每一行有多少个元素。

因此，C语言必须通过输出型参数，把这两个信息从函数内部传递给外部调用者，这也是二级指针、一级指针参数的核心来源。

2. 完整接口与每个形参的逐点详解
// 生成杨辉三角的完整接口
int** generate(int numRows, int* returnSize, int** returnColumnSizes)

每个参数的详细意义如下表：

参数 类型 参数性质 超详细意义与底层逻辑
numRows int 输入参数 用户传入的、要求生成的杨辉三角的行数，比如要生成前5行，就传入5。
returnSize int* 输出型参数（一级指针） 核心作用：把杨辉三角的行数从函数内部传递给外部。C语言核心规则：函数参数是值传递，函数内部直接修改形参，外部的变量不会发生任何改变。要想让函数内部修改外部的int变量，必须传入这个int变量的地址（也就是int*指针）。使用方式：外部先定义一个int变量（比如int size;），调用函数时传入&size；函数内部通过*returnSize = numRows;，解引用指针，直接修改外部int变量的值，调用者就能通过size拿到二维数组的行数。
returnColumnSizes int** 输出型参数（二级指针） 本节课最大难点，核心作用：把“每一行有多少个元素”的数组从函数内部传递给外部。我们需要在函数内部动态开辟一个一维数组，数组里的每个元素对应杨辉三角每一行的元素个数（比如第0行1个，第1行2个，第2行3个…）。为什么必须用二级指针？要想让函数内部修改外部的int*指针变量（让这个指针指向我们新开辟的数组），必须传入这个int*指针变量的地址，而int*变量的地址就是int**二级指针。使用方式：外部先定义一个int*指针变量（比如int* colSizes;），调用函数时传入&colSizes；函数内部先malloc开辟存储列数的数组，再通过*returnColumnSizes = 开辟的数组地址;，解引用二级指针，让外部的colSizes指针指向新开辟的数组，调用者就能通过colSizes[i]拿到第i行的元素个数。
3. 完整C语言实现代码与逐行讲解
#include <stdio.h>
#include <stdlib.h>

// 生成杨辉三角
// numRows: 输入参数，要生成的杨辉三角行数
// returnSize: 输出参数，返回二维数组的行数（传外部int变量的地址）
// returnColumnSizes: 输出参数，返回存储每行元素个数的数组（传外部int*指针的地址）
int** generate(int numRows, int* returnSize, int** returnColumnSizes)
{
// ====================== 步骤1：给输出型参数赋值行数 ======================
// 解引用returnSize，把行数赋值给外部的int变量
*returnSize = numRows;

// ====================== 步骤2：开辟二维数组的第一维（指针数组） ======================
// 二级指针ret，指向一个存储int*指针的数组，每个指针对应杨辉三角的一行
// malloc的大小：每个元素是int*类型，共numRows个，所以是sizeof(int*) * numRows
int** ret = (int**)malloc(sizeof(int*) * numRows);

// ====================== 步骤3：开辟存储每行元素个数的数组 ======================
// 解引用二级指针returnColumnSizes，让外部的int*指针指向我们新开辟的数组
// 这个数组有numRows个int元素，每个元素存对应行的元素个数
*returnColumnSizes = (int*)malloc(sizeof(int) * numRows);

// ====================== 步骤4：为每一行开辟空间，初始化首尾元素为1 ======================
for (int i = 0; i < numRows; i++)
{
// 第i行有i+1个元素，所以为第i行开辟i+1个int大小的空间
ret[i] = (int*)malloc(sizeof(int) * (i + 1));

// 给输出型参数赋值：第i行有i+1个元素
// 注意：[]的优先级比*高，必须加括号！先解引用拿到数组指针，再用[]访问元素
(*returnColumnSizes)[i] = i + 1;

// 初始化每行的首尾元素为1
ret[i][0] = 1; // 每行第一个元素固定为1
ret[i][i] = 1; // 每行最后一个元素固定为1（第i行下标到i）
}

// ====================== 步骤5：计算杨辉三角中间元素的值 ======================
// 从第2行开始计算（i=2），因为第0行、第1行所有元素已经是1了
for (int i = 2; i < numRows; i++)
{
// 每行的第0个和第i个已经是1，只需要计算j从1到i-1的中间元素
for (int j = 1; j < i; j++)
{
// 杨辉三角核心公式：当前元素 = 上一行同下标元素 + 上一行前一个下标元素
ret[i][j] = ret[i-1][j] + ret[i-1][j-1];
}
}

// ====================== 步骤6：返回二维数组首地址 ======================
return ret;
}

// 测试主函数
int main()
{
int numRows = 5; // 生成前5行杨辉三角

// 1. 定义两个变量，用来接收函数的输出结果
int returnSize; // 存储杨辉三角的行数
int* returnColumnSizes; // 存储每行元素个数的数组的地址

// 2. 调用生成函数
// 重点：必须传变量的地址！！！才能实现输出型参数的效果
int** yanghui = generate(numRows, &returnSize, &returnColumnSizes);

// 3. 打印杨辉三角
for (int i = 0; i < returnSize; i++) // returnSize告诉我们有多少行
{
// returnColumnSizes[i]告诉我们第i行有多少个元素
for (int j = 0; j < returnColumnSizes[i]; j++)
{
printf("%d ", yanghui[i][j]);
}
printf("\n");
}

// ====================== 步骤7：释放内存（避免内存泄漏） ======================
// 释放顺序必须严格遵守：先释放每一行的一维数组，再释放指针数组和列数数组
// 绝对不能先释放yanghui，否则就找不到每一行的地址了，会造成内存泄漏
for (int i = 0; i < returnSize; i++)
{
free(yanghui[i]); // 释放第i行的一维数组
}
free(yanghui); // 释放存储行指针的数组
free(returnColumnSizes); // 释放存储列数的数组

return 0;
}
4. 内存结构图解（辅助理解）

当numRows=5时，完整的内存结构如下：

yanghui (int** 二级指针)
|
↓ 指向一个int*类型的指针数组（共5个元素）
[ int* ] --> 指向一维数组 [1] （第0行，1个元素）
[ int* ] --> 指向一维数组 [1, 1] （第1行，2个元素）
[ int* ] --> 指向一维数组 [1, 2, 1] （第2行，3个元素）
[ int* ] --> 指向一维数组 [1, 3, 3, 1] （第3行，4个元素）
[ int* ] --> 指向一维数组 [1, 4, 6, 4, 1] （第4行，5个元素）

returnColumnSizes (int** 二级指针)
|
↓ 解引用后指向一个int类型的一维数组（共5个元素）
[ 1, 2, 3, 4, 5 ] （每个元素对应杨辉三角每一行的元素个数）
5. 杨辉三角题目中，返回的行数、每行的列数都能通过输入的numRows直接推导，为什么C语言接口还要设计int* returnSize、int** returnColumnSizes这两个参数？为什么C++就不用？

核心原因有两点：

  1. 通用接口设计要求：该接口是LeetCode为所有不规则二维数组题目设计的通用格式，并非仅针对杨辉三角。对于无固定规律的二维数组（如每行元素个数随机的场景），主函数无法提前推导出行数和每行列数，必须通过这两个参数从函数内部获取结果。
  2. C语言函数的天生限制：C语言函数只能通过return返回一个值，本题中return已经用于返回二维数组本身，剩余的“二维数组行数”“每行元素个数”两个关键信息，只能通过输出型参数传递给主函数。
  • int* returnSize：一级指针输出型参数，用于向主函数传递返回的二维数组的总行数；
  • int** returnColumnSizes：二级指针输出型参数，用于向主函数传递存储“每行元素个数”的一维数组的地址。
    C++ vector的类封装优势：
    C++直接返回vector<vector<int>>对象，无需任何输出型参数，因为：
  1. vector自动封装了大小信息：外层vector的size()成员函数直接返回二维数组的行数；每个内层vector的size()成员函数直接返回对应行的元素个数，调用者可直接通过vv.size()和vv[i].size()获取，无需额外传递。
  2. C++函数可以直接返回对象：vector类通过深拷贝（或C++11的移动语义），可以直接将整个二维数组的对象作为返回值传递给主函数，无需手动管理内存，也无需通过输出型参数拆分信息。
（二）C++ vector实现（对比讲解）
#include <vector>
using namespace std;

class Solution {
public:
vector<vector<int>> generate(int numRows) {
// 定义二维vector，直接设置行数为numRows
vector<vector<int>> vv(numRows);
// 初始化每行的元素个数，全部初始化为1
for(int i = 0; i < numRows; ++i)
{
vv[i].resize(i+1, 1);
}
// 计算中间元素的值
for(int i = 2; i < numRows; ++i)
{
for(int j = 1; j < i; ++j)
{
vv[i][j] = vv[i-1][j] + vv[i-1][j-1];
}
}
// 直接返回，无需手动管理内存，无需输出型参数
return vv;
}
};

// 测试代码
#include <iostream>
int main()
{
Solution s;
vector<vector<int>> vv = s.generate(5);
// 打印杨辉三角
for (auto& row : vv)
{
for (auto e : row)
{
cout << e << " ";
}
cout << endl;
}
return 0;
}
（三）补充知识点
  1. vector<vector<int>>的底层结构：本质是套娃式的类模板实例化，先实例化出vector<int>类，再用vector<int>作为模板参数，实例化出vector<vector<int>>类。
  • 外层vector的底层，是一个存储vector<int>对象的数组；
  • 每个内层的vector<int>对象，又有自己的底层数组、size、capacity，分别对应杨辉三角的每一行；
  • 外层vector的size，就是杨辉三角的行数；每个内层vector的size，就是对应行的元素个数，完全不需要手动传递输出型参数。
  1. vv[i][j]的底层原理：是两次operator[]运算符的函数调用。
  • 第一步vv[i]：调用外层vector的operator[]，返回第i个vector<int>对象的引用；
  • 第二步[j]：对返回的vector<int>对象，再次调用operator[]，返回第j个int元素的引用；
  • 编译器会把这两次函数调用优化为内联，没有额外的性能损耗，使用起来和原生二维数组完全一致。

九、vector扩容机制全解析

  1. 扩容触发条件
    当vector的有效元素个数size等于总容量capacity时，再插入元素（如push_back、insert）会触发扩容，避免数组越界。
  2. C++标准的扩容规范说明
    C++标准仅规定了vector需要实现的接口和功能，没有规定具体的扩容倍数，不同平台、不同编译器的STL实现可以有差异，类似“规定每天吃三顿饭，但不规定吃米饭还是面条”。
  3. 不同平台的扩容策略
    平台 容器 扩容规则 特殊说明
    VS（Windows） vector 1.5倍扩容 无特殊初始规则
    VS（Windows） string 初始15字节内置buffer，第一次扩容到31（2倍），后续1.5倍扩容 内置buffer是为了减少短字符串频繁申请堆内存，因为日常使用的string大多存储短文本（名字、手机号等）
    Linux（g++） vector/string 标准2倍扩容 无特殊初始规则
  4. reserve与resize的核心区别（老师反复强调的易错点）
    这是本节课重点强调的内容，二者功能完全不同，绝对不能混用：
    • reserve：单纯开辟内存空间，不初始化元素，不改变size，仅扩容不缩容，当传入的n小于当前capacity时，不做任何操作；
    • resize：改变vector的有效元素个数size，同时对元素进行初始化，当n大于capacity时会触发扩容，n小于size时会删除尾部元素。
    • 关键使用规则：如果想提前开空间避免频繁扩容，必须使用reserve，绝对不能用resize。例如resize(100)会让size直接变为100，后续push_back会从101位置开始，依然会触发扩容，完全达不到预开空间的效果。
  5. 扩容机制测试代码
    老师课上演示的扩容测试代码，用于验证扩容倍数和reserve的优化效果： 
    void TestVectorExpand()
{
    size_t sz;
    vector<int> v;
    v.reserve(100); // 提前预开100个元素的空间，避免频繁扩容
    sz = v.capacity();
    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';
        }
    }
}

十、vector与STL算法库的配合

  1. 迭代器的核心作用
    迭代器是算法和容器之间的桥梁，让算法可以不用关心容器的底层数据结构，实现泛型编程。vector的迭代器本质是原生指针，所有容器都提供迭代器接口，算法只需接收迭代器即可适配所有容器。
    • 迭代器区间必须遵循左闭右开原则：[begin, end)，begin()指向第一个有效元素，end()指向最后一个有效元素的下一个位置，这是STL算法的通用规则。
    • 头文件要求：使用算法库需包含#include <algorithm>。
  2. sort排序算法的使用
    • 默认行为：sort(v.begin(), v.end())对vector内所有元素做升序排序，底层通过小于号<实现比较；
    • 局部排序：支持指定迭代器区间，仅对部分元素排序，例如sort(v.begin()+1, v.begin()+5)，仅对下标1到4的元素排序（左闭右开，不包含下标5）；
    • 降序排序：通过STL库提供的仿函数greater<T>实现，greater是类模板，使用时需实例化对应元素类型。
      • 写法1：定义有名对象 
        greater<int> gt;
sort(v.begin(), v.end(), gt);
      • 写法2：使用匿名对象（老师推荐，工业界常用） 
        sort(v.begin(), v.end(), greater<int>());
    • 仿函数补充说明：老师明确说明，仿函数的底层原理会在后续栈和队列章节（优先级队列）详细讲解，现阶段只需会用库提供的greater和less即可，less是默认的升序仿函数。
sort(v.begin(), v.end());

就等价于：

sort(v.begin(), v.end(), less<int>());
  1. find查找算法的使用
    • 核心说明：vector本身没有提供find成员函数，string有find成员函数（支持查找字符和子串），但vector使用算法库提供的全局find函数；
    • 函数用法：find(iterator first, iterator last, const T& val)，在[first, last)区间内查找值为val的元素；
    • 返回值规则：找到则返回对应元素的迭代器，找不到则返回传入的区间右边界last；
    • 典型使用场景：先查找元素位置，再对该位置执行insert插入操作。

十一、vector 与 string 的核心区别

核心误区：vector绝对不能替代string，二者有两个本质差异：

  1. 字符串结束符\0的差异
    • string的底层字符数组末尾，一定会自动添加\0结束符，目的是兼容C语言的字符串接口；
    • vector的底层数组不会自动添加\0，没有字符串结束符的概念。
    • 实际影响：C语言标准库接口（如fopen）需要const char*类型的参数，string可以通过c_str()方法返回带\0的底层字符串指针，而vector无法满足该需求，会导致未定义行为。
  2. 功能接口的差异
    string是为字符串处理专门设计的，提供了大量vector不具备的专属功能：
    • 字符串拼接：支持+=运算符，可直接拼接单个字符或完整字符串，vector仅支持插入单个char元素；
    • 查找功能：string提供find、rfind等成员函数，支持查找单个字符和子串，vector没有该功能，只能用算法库的find查找单个元素；
    • 子串提取、字符串替换等专属字符串操作，vector均不支持。

十二、STL vector源码阅读方法与源码剖析

  1. STL源码版本选择
    STL主流有两个版本，学习阶段优先选择SGI版本：
    • PJ版本：VS编译器使用的版本，代码加入了大量平台适配、异常处理，复杂度高，新手阅读难度极大，不推荐入门学习；
    • SGI版本：Linux g++编译器使用的版本，代码简洁、逻辑纯粹，也是侯捷老师《STL源码剖析》一书采用的版本，是新手学习的首选。
    • 版本选择细节：老师推荐使用十几年前的老版本SGI源码，而非最新版。原因是新版本加入了大量C++新语法、模板特化、优化逻辑，阅读成本极高；老版本核心逻辑完全一致，更适合新手理解底层原理。
  2. 源码阅读核心技巧（结合职场场景重点讲解）
    结合新人入职后看项目源码的场景，总结了通用的源码阅读技巧，适用于STL源码和公司项目源码：
    1. 先懂功能，再看源码：先熟练掌握这个类/模块的使用方法、核心功能，再去看底层实现，绝对不能上来就逐行硬读；
    2. 抓核心枝干，忽略细节：先找类的核心成员变量、核心成员函数，梳理整体框架，无关的宏定义、平台适配、异常处理先放一放，不要陷入细节；
    3. 连蒙带猜+代码验证：通过变量名、函数名猜测其作用，再通过代码逻辑验证猜测，不认识的类型/宏先跳过，先抓主线逻辑；
    4. 善用工具提升效率：推荐使用source insight软件，支持跨文件的定义跳转，看源码时可以快速跳转到函数、类型的定义处，大幅提升效率；VS的「转到定义」功能也可以实现基础跳转。
    • 职场补充说明：新人入职后，第一件事通常是阅读项目源码，领导只会给3天到1周的时间，逐行阅读会导致进度严重落后。必须先梳理核心模块、核心类的关系，再看具体功能的实现细节，这是职场必备能力。
  3. 侯捷老师与《STL源码剖析》
    重点推荐了侯捷老师的《STL源码剖析》，说明这本书是学习STL底层的经典书籍，本节课讲解的SGI源码版本和这本书完全一致，源码会上传到课程板书里，供同学们下载。同时说明，侯捷老师是C++领域的知名专家，翻译和写作了大量C++经典书籍，是C++学习必须了解的行业前辈。
  4. SGI vector核心源码框架剖析
    拆解SGI vector的核心源码结构：
    • 核心成员变量：SGI版本vector没有用指针+size+capacity，而是用三个迭代器（原生指针）管理内存，这是源码的核心： 
      template <class T, class Alloc = alloc>
class vector {
protected:
    iterator start;         // 内存空间的起始位置
    iterator finish;        // 有效元素的末尾位置（最后一个有效元素的下一个位置）
    iterator end_of_storage;// 整个内存空间的末尾位置（指向 vector 向系统申请的总内存空间的最后一个位置的下一个地址）
public:
    typedef T* iterator; // vector迭代器本质就是原生指针T*
};
    • size和capacity的计算：
      • size() = finish - start，两个指针相减得到有效元素个数；
      • capacity() = end_of_storage - start，得到总容量大小。
    • push_back核心源码逻辑：
      先判断空间是否充足，充足则直接在finish位置构造元素，++finish；空间不足则调用insert_aux完成扩容+插入。
    • construct函数底层原理：
      construct函数是STL的底层工具，本质是对定位new表达式placement new的封装。作用是在已经申请的、未初始化的裸内存上，调用对象的构造函数完成初始化。
      • 为什么不用直接赋值：vector的内存来自内存池，是未初始化的裸内存，对于自定义类型（如string），直接赋值会访问随机值内存，触发未定义行为，必须先通过构造函数初始化。
    • insert_aux扩容核心逻辑：
      1. 计算新容量：原容量为0则开1个空间，否则2倍扩容；
      2. 申请新的内存空间；
      3. 拷贝原数据到新空间，同时处理插入位置的元素；
      4. 释放旧的内存空间；
      5. 更新start、finish、end_of_storage三个核心指针，指向新空间。
  5. 源码阅读的职场延伸
    老师强调，入职后看项目源码，代码规范和注释极其重要。如果上一任同事写了清晰的注释和规范的变量名，读代码会轻松很多；如果变量名乱取（如i1、i2、i3），会极大增加阅读难度，所以平时写代码一定要养成良好的规范习惯。

十三、vector的模拟实现（bit::vector）

老师本节课带着从零实现了vector的核心接口，每一个细节、踩的坑都完整记录如下：

  1. 命名空间规范
    • 老师定义了namespace bit用于模拟实现，但明确提醒同学们：自己写的时候不要用bit这个命名空间，避免暴露培训经历，建议用自己的名字、名字首字母或者自己喜欢的单词作为命名空间。
  2. 整体框架与核心成员变量
    完全贴合SGI源码，用三个原生指针作为核心成员变量，同时定义迭代器类型，完整类框架如下（含后续课程补充的所有接口声明）： 
    #pragma once
#include<assert.h>
#include<iostream>
// 用于std::swap，赋值重载现代写法需要
#include<algorithm>
using namespace std;

namespace bit
{
    template<class T>
    class vector
    {
    public:
        // 迭代器定义：vector迭代器本质是原生指针，属于随机访问迭代器
        typedef T* iterator;
        typedef const T* const_iterator;

        // 普通迭代器接口
        iterator begin() { return _start; }
        iterator end() { return _finish; }

        // const迭代器接口：必须提供，否则const对象无法遍历，也不支持范围for
        const_iterator begin() const { return _start; }
        const_iterator end() const { return _finish; }

        // 无参构造函数
        vector()
            :_start(nullptr)
            , _finish(nullptr)
            , _end_of_storage(nullptr)
        {}

        // n个val值构造函数（size_t版本）
        vector(size_t n, const T& val = T());
        // n个val值构造函数（int版本）【解决重载匹配坑点】
        vector(int n, const T& val = T());

        // 迭代器区间构造函数【模板函数】
        template <class InputIterator>
        vector(InputIterator first, InputIterator last);

        // initializer_list列表初始化构造函数（C++11）
        vector(initializer_list<T> il);

        // 拷贝构造函数【深拷贝核心】
        vector(const vector<T>& v);

        // 析构函数
        ~vector();

        // 赋值重载运算符【现代写法】
        vector<T>& operator=(vector<T> v);

        // 容量与大小接口
        size_t capacity() const { return _end_of_storage - _start; }
        size_t size() const { return _finish - _start; }
        bool empty() const { return _start == _finish; }

        // 扩容接口
        void reserve(size_t n);
        // 修改有效元素个数接口
        void resize(size_t n, T val = T());

        // 元素访问接口
        T& operator[](sslocal://flow/file_open?url=size_t+i&flow_extra=eyJsaW5rX3R5cGUiOiJjb2RlX2ludGVycHJldGVyIn0=);
        const T& operator[](sslocal://flow/file_open?url=size_t+i&flow_extra=eyJsaW5rX3R5cGUiOiJjb2RlX2ludGVycHJldGVyIn0=) const;

        // 增删接口
        void push_back(const T& x);
        void pop_back();
        // 指定位置插入，返回新插入位置的迭代器
        iterator insert(iterator pos, const T& x);
        // 指定位置删除，返回删除位置的下一个有效迭代器
        iterator erase(iterator pos);

        // 交换两个vector的核心数据
        void swap(vector<T>& v);

    private:
        // 核心成员变量
        iterator _start;         // 有效内存起始位置
        iterator _finish;        // 有效元素末尾的下一个位置
        iterator _end_of_storage;// 总申请内存末尾的下一个位置
    };
}
    • 关键细节：迭代器必须定义在public下，否则类外无法使用；const版本的begin/end必须加const修饰，保证const对象可以调用；三个核心指针的定义是所有接口实现的基础。
  3. reserve扩容接口实现【双坑点】
    老师重点讲解了实现时的2个核心坑点，完整代码与细节讲解如下： 
    // 类外实现，需加类域bit::vector<T>
template<class T>
void bit::vector<T>::reserve(size_t n)
{
    if (n > capacity())
    {
        // 【重点坑点1】必须提前保存旧的size，不能更新_start后再计算
        size_t old_size = size();
        // 申请新空间
        T* tmp = new T[n];
        if (_start)
        {
            // 【坑点2 重点补充】memcpy浅拷贝问题，仅内置类型可用，自定义类型会崩溃
            // memcpy(tmp, _start, sizeof(T) * old_size);
            // 正确写法：循环赋值，调用自定义类型的赋值重载，完成深拷贝
            for (size_t i = 0; i < old_size; i++)
            {
                tmp[i] = _start[i];
            }
            // 释放旧空间
            delete[] _start;
        }
        // 更新三个核心指针
        _start = tmp;
        _finish = tmp + old_size;
        _end_of_storage = _start + n;
    }
}
    • 坑点1讲解：如果先更新_start，再用size()计算旧大小，会用新的_start和旧的_finish相减，得到错误的结果，导致_finish赋值错误，程序崩溃。必须在更新指针前，提前计算并保存old_size。
    • 坑点2讲解：memcpy是内存字节逐位拷贝，属于浅拷贝。对于int等内置类型无问题，但对于string等涉及堆资源管理的自定义类型，只会拷贝指针值，不会拷贝指针指向的堆空间。旧空间释放后，新空间的指针会变成野指针，导致程序崩溃、乱码。必须改用循环赋值的方式，调用自定义类型的赋值重载完成深拷贝。
    • 模板编译说明：老师明确提醒，模板的声明和定义不能分离到两个不同的文件，否则会出现链接错误，这个知识点会在后续模板进阶章节详细讲解，现阶段只需把声明和定义都放在.h文件里即可。
  4. operator[]下标访问接口 
    template<class T>
T& bit::vector<T>::operator[](sslocal://flow/file_open?url=size_t+i&flow_extra=eyJsaW5rX3R5cGUiOiJjb2RlX2ludGVycHJldGVyIn0=)
{
    // 断言检查下标越界，调试模式快速定位问题
    assert(i < size());
    // 返回左值引用，支持修改元素
    return _start[i];
}

// const版本，支持const对象的只读访问
template<class T>
const T& bit::vector<T>::operator[](sslocal://flow/file_open?url=size_t+i&flow_extra=eyJsaW5rX3R5cGUiOiJjb2RlX2ludGVycHJldGVyIn0=) const
{
    assert(i < size());
    return _start[i];
}
    • 关键细节：必须同时提供普通版本和const版本，否则const修饰的vector对象无法使用下标访问；返回引用避免拷贝，同时支持对元素的修改。
  5. push_back尾插接口 
    template<class T>
void bit::vector<T>::push_back(const T& x)
{
    // 【重点】参数必须加const&，避免传值拷贝的性能消耗，尤其是自定义类型的深拷贝代价极大
    if (_finish == _end_of_storage)
    {
        // 初始容量为4，否则2倍扩容（SGI版本规则）
        size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
        reserve(newcapacity);
    }
    // 插入元素，更新finish
    *_finish = x;
    ++_finish;
}
    • 补充细节：VS下PJ版本STL是1.5倍扩容，g++下SGI版本是2倍扩容，模拟实现采用2倍规则，和课程讲解一致。
  6. pop_back尾删接口 
    template<class T>
void bit::vector<T>::pop_back()
{
    // 断言检查：禁止对空vector执行尾删
    assert(_finish > _start);
    // 只需将finish--，无需处理删除的元素，区间外视为无效
    --_finish;
}
  7. insert指定位置插入接口【迭代器失效核心坑点】
    老师重点讲解了迭代器失效的处理，以及返回值的作用，完整实现如下： 
    template<class T>
typename bit::vector<T>::iterator bit::vector<T>::insert(iterator pos, const T& x)
{
    // 断言检查插入位置的合法性：[begin, end]区间内
    assert(pos >= _start);
    assert(pos <= _finish);

    // 空间不足则扩容
    if (_finish == _end_of_storage)
    {
        // 【核心】保存pos相对于_start的偏移量，解决扩容后迭代器失效
        size_t len = pos - _start;
        size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
        reserve(newcapacity);
        // 扩容后更新pos，指向新空间的对应位置
        pos = _start + len;
    }

    // 元素后移：从后往前挪，避免数据覆盖
    iterator it = _finish - 1;
    while (it >= pos)
    {
        *(it + 1) = *it;
        --it;
    }

    // 插入元素，更新finish
    *pos = x;
    ++_finish;

    // 【课程补充】返回新插入位置的迭代器，解决外部迭代器失效问题
    return pos;
}
    • 迭代器失效处理：扩容会释放旧空间，传入的pos是旧空间的地址，变为野指针。必须提前保存pos相对于_start的偏移量，扩容后用新的_start加上偏移量，重新计算出pos在新空间的位置，保证迭代器有效。
    • 返回值补充说明：insert的返回值是新插入元素位置的迭代器，外部调用时可通过接收返回值，更新失效的迭代器，这是C++标准规定的通用解决方案。
  8. 补充的构造函数
    老师在课程中补充了多个常用构造函数，包含所有坑点细节如下：
    1. n个val值构造函数 
      // size_t版本
template<class T>
bit::vector<T>::vector(size_t n, const T& val)
{
    // 初始化三个指针为nullptr，避免reserve时释放野指针
    _start = nullptr;
    _finish = nullptr;
    _end_of_storage = nullptr;

    reserve(n);
    for (size_t i = 0; i < n; i++)
    {
        push_back(val);
    }
}

// 【课程重点坑点】int重载版本，解决模板匹配编译错误
template<class T>
bit::vector<T>::vector(int n, const T& val)
{
    _start = nullptr;
    _finish = nullptr;
    _end_of_storage = nullptr;

    reserve(n);
    for (int i = 0; i < n; i++)
    {
        push_back(val);
    }
}
      • 缺省值细节：val = T()使用T类型的匿名对象作为缺省值。C++为了支持模板泛型编程，对内置类型做了升级，内置类型也支持构造语法：int()默认值为0，double()默认值为0.0，指针类型默认值为nullptr。
      • 重载匹配坑点：如果只提供size_t版本，调用vector<int> v(10, 1)时，两个int参数会优先匹配模板迭代器区间构造，导致"非法间接寻址"编译错误。必须同时提供int版本，让整数入参优先匹配普通构造，解决编译问题。
    2. initializer_list列表初始化构造函数（C++11） 
      template<class T>
bit::vector<T>::vector(initializer_list<T> il)
{
    _start = nullptr;
    _finish = nullptr;
    _end_of_storage = nullptr;

    // 提前开空间，避免多次扩容
    reserve(il.size());
    for (auto& e : il)
    {
        push_back(e);
    }
}
      • 功能说明：支持vector<int> v = {1,2,3,4,5,6}的花括号列表初始化写法；
      • 底层本质：initializer_list内部只有两个指针，分别指向数组的开始和结束位置，size就是两个指针相减的结果，支持范围for遍历。
  9. 迭代器区间构造函数【编译坑点】
    老师重点讲解了该构造的设计意义、实现和编译坑点，完整内容如下： 
    // 类内声明已写，类外实现
template<class T>
template<class InputIterator>
bit::vector<T>::vector(InputIterator first, InputIterator last)
{
    // 初始化指针为nullptr
    _start = nullptr;
    _finish = nullptr;
    _end_of_storage = nullptr;

    // 遍历迭代器区间，尾插元素
    while (first != last)
    {
        push_back(*first);
        ++first;
    }
}
    • 设计意义：设计为模板函数，不仅支持vector自身的迭代器，还支持list、string等其他容器的迭代器初始化，通用性极强，符合STL的泛型设计思想。
    • 测试场景： 
      // 用vector的迭代器区间初始化
bit::vector<int> v1 = {1,2,3,4,5,6};
bit::vector<int> v2(v1.begin(), v1.begin() + 5);
// 用string的迭代器初始化，存储字符的ASCII码
string s("hello world");
bit::vector<int> v3(s.begin(), s.end());
    • 编译错误排查方法：老师讲解了工业界常用的屏蔽法，逐步屏蔽代码片段，缩小错误范围，最终锁定重载匹配的问题，这是排查复杂编译错误的核心技巧。
  10. erase指定位置删除接口实现
    老师课程核心讲解的接口，完整实现与细节如下： 
    template<class T>
typename bit::vector<T>::iterator bit::vector<T>::erase(iterator pos)
{
    // 断言检查删除位置的合法性：必须在[begin, end)区间内
    assert(pos >= _start);
    assert(pos < _finish);

    // 数据覆盖：从pos+1开始，向前挪动数据，覆盖pos位置
    iterator it = pos + 1;
    while (it < _finish)
    {
        *(it - 1) = *it;
        ++it;
    }

    // 更新有效元素边界
    --_finish;
    // 返回删除位置的有效迭代器（即原pos位置的新元素地址）
    return pos;
}
    • 实现逻辑细节：
      1. 合法性校验：确保待删除位置在有效元素区间内，防止越界访问；
      2. 数据挪动：从pos的下一个位置开始，所有元素依次向前挪动一位，完成对pos位置元素的覆盖删除；
      3. 边界更新：_finish指针前移一位，更新有效元素个数；
      4. 迭代器返回：C++标准规定erase返回删除位置的下一个有效迭代器，用于解决迭代器失效问题。
    • 测试与使用方法：通常配合std::find算法使用，先查找目标值的迭代器，找到后执行删除，未找到则不操作。 
      void test_vector_erase()
{
    bit::vector<int> v = {1,2,3,4,5,6};
    int x;
    cin >> x;
    // 查找目标值的迭代器
    auto p = find(v.begin(), v.end(), x);
    if (p != v.end())
    {
        v.erase(p);
    }
    else
    {
        cout << "没有找到"<<x<< endl;
    }
}
  11. resize接口实现与原理
    老师重点区分了resize和reserve的核心区别，完整实现与细节如下： 
    template<class T>
void bit::vector<T>::resize(size_t n, T val)
{
    if (n > size())
    {
        // 场景1：n大于当前size，需要新增元素
        // 先保证空间充足，空间不足时自动扩容
        reserve(n);
        // 从当前finish位置开始，填充默认值val，直到达到n个元素
        while (_finish != _start + n)
        {
            *_finish = val;
            ++_finish;
        }
    }
    else
    {
        // 场景2：n小于当前size，需要删除尾部元素
        // 直接修改finish指针，丢弃尾部多余元素
        _finish = _start + n;
    }
}
    • resize与reserve的核心区别：
      接口 核心作用 影响size 影响capacity 初始化操作
      resize 修改有效元素个数 是 新size>capacity时触发扩容 是，新增元素会填充默认值
      reserve 仅修改容量，预留空间 否 仅当n>当前capacity时生效 否，仅开空间，不修改现有数据
    • 测试场景： 
      void test_vector_resize()
{
    bit::vector<int> v = { 1,2,3,4,5,6 };
    // 扩容到20个元素，新增元素填充1
    v.resize(20, 1);
    // 缩容到5个元素，仅保留前5个
    v.resize(5);
}
  12. 拷贝构造函数（深浅拷贝核心问题）
    老师重点讲解了浅拷贝的危害和深拷贝的实现，完整内容如下： 
    template<class T>
bit::vector<T>::vector(const vector<T>& v)
{
    // 初始化三个指针为nullptr
    _start = nullptr;
    _finish = nullptr;
    _end_of_storage = nullptr;

    // 提前开辟和源对象相同的容量，避免多次扩容
    reserve(v.capacity());
    // 【重点】范围for必须加引用&，避免自定义类型触发额外的拷贝构造
    for (auto& e : v)
    {
        push_back(e);
    }
}
    • 深浅拷贝核心问题：
      1. 浅拷贝：编译器默认生成的拷贝构造是浅拷贝，仅拷贝_start、_finish、_end_of_storage三个指针的值，导致两个vector对象指向同一块堆空间。析构时同一块空间会被释放两次，引发程序崩溃；同时一个对象修改数据会影响另一个对象，出现逻辑错误。
      2. 深拷贝：为新对象开辟独立的堆空间，将源对象的所有元素拷贝到新空间，两个对象互不影响，彻底解决浅拷贝问题。
    • 关键细节：范围for遍历必须加&引用，若不加引用，遍历每个元素时都会触发一次拷贝构造，对于string等自定义类型，性能损耗极大。
  13. swap成员函数
    老师讲解了swap的高效实现和核心作用，完整代码如下： 
    template<class T>
void bit::vector<T>::swap(vector<T>& v)
{
    // 仅交换三个核心指针，无需拷贝任何数据，时间复杂度O(1)
    std::swap(_start, v._start);
    std::swap(_finish, v._finish);
    std::swap(_end_of_storage, v._end_of_storage);
}
    • 实现原理：vector的所有核心数据都存储在三个指针中，交换指针就等价于交换了两个对象的全部数据，无需拷贝任何元素，效率远高于传统的临时对象拷贝交换。
    • 核心作用：是赋值重载现代写法的核心基础，同时可用于高效清空vector、交换两个容器数据。

14. 拷贝构造函数的现代写法补充（基于迭代器区间构造 + swap）
在第12点的基础上，补充一种和 string 现代写法逻辑一致的 vector 拷贝构造实现，两种写法均为正确的深拷贝方案，无优劣之分，仅代码风格不同。

template<class T>
bit::vector<T>::vector(const vector<T>& v)
    // 【重点】必须在初始化列表将自身初始化为空壳对象
    :_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{
    // 复用已实现的「迭代器区间构造函数」，创建临时对象tmp完成深拷贝
    vector<T> tmp(v.begin(), v.end());
    // 调用本类swap成员函数，交换tmp与当前对象的资源
    swap(tmp);
    // 函数结束后tmp自动析构，带走原空壳资源（无代价）
}
  • 核心逻辑拆解：
    1. 掏空自己：初始化列表将三个核心指针置为 nullptr，确保当前对象无任何资源，为后续交换做准备；
    2. 借刀杀人：调用迭代器区间构造，让临时对象 tmp 完成开空间、拷贝元素的深拷贝工作；
    3. 鹊巢鸠占：通过 swap 交换指针，将 tmp 的资源转移到当前对象；
    4. 毁尸灭迹：tmp 出作用域自动析构，顺便释放原空壳资源（nullptr 析构无风险）。
  • 关键细节说明：

    1. 【重点】初始化列表置空是前提：若不置空，swap 后临时对象析构会释放随机野指针，导致程序崩溃；

    2. 与 string 现代写法完全互通：体现了STL容器「资源转移+复用已有接口」的统一设计思想；

    3. this-> 可省略：成员函数内调用本类 swap，编译器会自动在当前类作用域查找，无需显式标注。

    4. 赋值重载运算符【现代写法】
      老师重点讲解了传统写法的弊端和现代写法的优势，完整实现如下：

template<class T>
typename bit::vector<T>::vector<T>& bit::vector<T>::operator=(vector<T> v)
{
// 形参v是值传递，已调用拷贝构造生成深拷贝临时对象
swap(v);
// 返回自身引用，支持连续赋值
return *this;
}
  • 实现原理：
  1. 形参v采用值传递，调用拷贝构造生成源对象的深拷贝临时对象；
  2. 调用swap交换当前对象和临时对象的指针，当前对象拿到深拷贝的完整数据；
  3. 函数结束后，临时对象v出作用域，自动调用析构函数释放原当前对象的旧空间，无需手动delete。
  • 核心优势：
  1. 代码极简，无需手动管理内存，异常安全；
  2. 无需处理自己给自己赋值的极端场景，值传递已生成独立拷贝，不会出现问题；
  3. 复用拷贝构造和析构函数，代码复用性高，不易出错。
  • 补充说明：传统写法需要先释放旧空间、再开新空间、再拷贝数据，还需要判断自己给自己赋值，代码繁琐且容易出现内存泄漏，老师推荐优先使用现代写法。

16. string 与 vector 的「现代写法 vs 原始写法」对比总结
STL容器的设计思想高度统一，string 和 vector 在拷贝构造与赋值重载的实现逻辑上完全一致，仅因底层数据结构不同，具体深拷贝代码略有差异。

// ---------- string 拷贝构造：原始写法 ----------
string::string(const string& s)
{
    _str = new char[s._capacity + 1];
    memcpy(_str, s._str, s._size + 1);
    _size = s._size;
    _capacity = s._capacity;
}

// ---------- string 拷贝构造：现代写法 ----------
string::string(const string& s)
    :_str(nullptr), _size(0), _capacity(0)
{
    string tmp(s.begin(), s.end());
    swap(tmp);
}

// ---------- string 赋值重载：原始写法 ----------
string& string::operator=(const string& s)
{
    if (this != &s) // 必须手动判断自赋值
    {
        char* tmp = new char[s._capacity + 1];
        memcpy(tmp, s._str, s._size + 1);
        delete[] _str; // 必须手动释放旧资源
        _str = tmp;
        _size = s._size;
        _capacity = s._capacity;
    }
    return *this;
}

// ---------- string 赋值重载：现代写法 ----------
string& string::operator=(string tmp) // 值传递自动生成深拷贝
{
    swap(tmp); // 直接交换资源，无需手动管理内存
    return *this;
}

// ---------- vector 拷贝构造：原始写法（课程标准写法） ----------
template<class T>
bit::vector<T>::vector(const vector<T>& v)
{
    _start = nullptr;
    _finish = nullptr;
    _end_of_storage = nullptr;

    reserve(v.capacity());
    // 【重点】范围for必须加引用&，避免自定义类型触发额外拷贝
    for (auto& e : v)
    {
        push_back(e);
    }
}

// ---------- vector 拷贝构造：现代写法（补充写法） ----------
template<class T>
bit::vector<T>::vector(const vector<T>& v)
    :_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{
    vector<T> tmp(v.begin(), v.end());
    swap(tmp);
}

// ---------- vector 赋值重载：原始写法 ----------
template<class T>
typename bit::vector<T>::vector<T>& bit::vector<T>::operator=(const vector<T>& v)
{
    if (this != &v) // 必须手动判断自赋值
    {
        // 手动释放旧空间
        delete[] _start;
        // 手动开新空间
        size_t old_size = v.size();
        T* tmp = new T[v.capacity()];
        // 手动深拷贝数据
        for (size_t i = 0; i < old_size; i++)
        {
            tmp[i] = v._start[i];
        }
        // 手动更新指针
        _start = tmp;
        _finish = tmp + old_size;
        _end_of_storage = _start + v.capacity();
    }
    return *this;
}

// ---------- vector 赋值重载：现代写法（课程推荐写法） ----------
template<class T>
typename bit::vector<T>::vector<T>& bit::vector<T>::operator=(vector<T> v)
{
    swap(v);
    return *this;
}
  • 现代写法的核心逻辑统一：
    1. 无论是 string 还是 vector，现代写法都遵循「值传递生成深拷贝临时对象 + swap交换核心指针 + 临时对象自动析构释放旧资源」的流程；
    2. 完全复用已写好的「拷贝构造 + swap + 析构」接口，代码复用性极高。
  • 现代写法的核心优势统一：
    1. 代码极简：赋值重载仅需2-3行代码，无需手动管理内存；
    2. 异常安全：若拷贝过程中抛出异常，原对象资源不受任何影响；
    3. 自赋值安全：无需手动判断 this != &源对象，值传递已生成独立拷贝。
  • swap的核心地位统一：
    1. 二者的 swap 都仅交换核心成员指针（string 交换 _str/_size/_capacity；vector 交换 _start/_finish/_end_of_storage）；
    2. 时间复杂度为 O(1)，无需拷贝任何元素，这是现代写法高效的基础。
    总结表格
    在这里插入图片描述

十四、迭代器失效问题深度解析

  1. 迭代器失效的本质
    vector的迭代器本质是原生指针T*，迭代器失效的本质是：指针指向的空间被释放，变为野指针；或指针指向的位置语义发生改变，导致非法访问、逻辑错误、程序崩溃。
  2. insert导致的迭代器失效场景
    • 触发原因：insert插入元素时，如果空间不足会触发扩容，扩容会释放旧空间、申请新空间，传入的pos迭代器依然指向旧空间，变为野指针，后续访问会触发未定义行为，程序崩溃。
    • 内部解决方法：在insert函数内部，扩容前保存pos相对于_start的偏移量，扩容后用新的_start加上偏移量，重新更新pos，保证迭代器有效。
    • 外部使用解决方法：insert会返回新插入位置的有效迭代器，外部调用时通过接收返回值，重新赋值迭代器，彻底解决失效问题。
  3. 外部迭代器失效的问题
    • 问题场景：在函数外部定义迭代器p，将p传入insert函数，insert执行完成后，外部的p依然是失效的。
    • 根本原因：insert函数的pos参数是传值传参，函数内部对pos的修改，不会影响外部的实参p。
    • 为什么不能用传引用：如果用传引用，当传入的实参是临时对象（如v.begin()+1）时，临时对象具有常性，无法传给非const引用，会编译报错，STL库里面的insert也没有用传引用。
    • 通用规则：insert执行完成后，之前传入的迭代器绝对不能再访问，因为不确定是否发生了扩容，不同平台的扩容机制不同，访问失效的迭代器会导致程序崩溃。
  4. erase操作导致的迭代器失效（课程核心重点）
    老师用了大量时间拆解erase迭代器失效的所有场景、平台差异和解决方案，完整细节如下：
    1. 失效的底层逻辑
      erase删除元素后，pos位置之后的元素会全部向前挪动，底层空间本身不会改变；但如果pos是最后一个元素，删除后pos就等于end()，而end()位置无有效元素，迭代器逻辑上已失效。即使不是最后一个元素，VS平台也会强制标记该迭代器失效。
    2. 不同平台的处理差异
      • VS平台（PJ版本STL）：对迭代器失效做了强制严格检查，只要执行了erase，无论什么位置，原迭代器都会被标记为失效，只要访问（包括解引用、++it、循环判断）就会直接崩溃。VS的vector迭代器不是原生指针，是封装后的自定义类，内部做了失效标记。
      • g++平台（SGI版本STL）：对迭代器失效的检查不严格，erase后若空间未变化，指针位置仍有效，程序可能不会崩溃，但会出现严重的逻辑错误。
    3. 典型错误场景与问题分析
      需求：删除vector中所有的偶数，老师拆解了2种错误写法的核心问题：
      • 错误写法1：无脑++it，全平台存在问题 
        vector<int> v{ 1,2,3,4 };
auto it = v.begin();
while (it != v.end())
{
    if (*it % 2 == 0)
    {
        v.erase(it);
    }
    ++it; // 无论是否删除，都执行++it
}
        问题分析：
        1. VS下：直接崩溃，erase后it已失效，执行++it属于访问失效迭代器；
        2. g++下：
          • 连续偶数场景：会漏删元素。例如{1,2,2,3}，删除第一个2后，第二个2向前挪动，++it直接跳过第二个2，导致删不干净；
          • 末尾是偶数场景：会触发越界段错误。删除最后一个偶数后，_finish前移，++it后it超过end()，循环条件失效，访问野指针。
      • 错误写法2：仅奇数时++it，VS下仍崩溃 
        vector<int> v{ 1,2,3,4 };
auto it = v.begin();
while (it != v.end())
{
    if (*it % 2 == 0)
    {
        v.erase(it);
    }
    else
    {
        ++it; // 仅奇数时++it
    }
}
        问题分析：该写法在g++下逻辑可正常运行，但VS下仍会崩溃。因为erase后it已失效，下一次循环的it != v.end()判断仍属于访问失效迭代器，VS的强制检查会直接报错。
    4. 标准正确写法：接收erase返回值更新迭代器，全平台兼容 
      vector<int> v{ 1,2,2,3,4,5,6 };
auto it = v.begin();
while (it != v.end())
{
    if (*it % 2 == 0)
    {
        // erase返回删除位置的下一个有效迭代器，重新赋值解决失效
        it = v.erase(it);
    }
    else
    {
        ++it;
    }
}
      优势：完全符合C++标准，不依赖平台底层实现，VS和g++下均可正常运行，无崩溃、无逻辑错误。
  5. 其他会触发迭代器失效的操作
    所有会引起vector底层空间改变的操作，都有可能导致迭代器失效，包括：resize、reserve、assign、push_back等。这些操作可能触发扩容，释放旧空间，导致原迭代器变为野指针。
    • 解决方式：以上操作执行完成后，如果需要继续使用迭代器，必须给迭代器重新赋值，禁止使用操作前的旧迭代器。
  6. 扩容与缩容的设计思路补充
    老师结合迭代器失效，讲解了vector的设计思想：
    1. 空间换时间（主流设计）：vector的扩容机制预留额外空间，避免频繁申请释放内存，用少量冗余空间换取更高的执行效率。这是工业界主流方案，因为随着硬件发展，内存空间充足，执行效率是核心瓶颈。
    2. 时间换空间（极少使用）：erase后若剩余数据占比过低，可执行缩容，释放冗余空间。但缩容需要开辟新空间、拷贝数据、释放旧空间，性能开销极大，一般vector不会实现缩容逻辑。同时缩容会导致所有迭代器失效，风险极高。
    3. 摩尔定律补充：集成电路性能每18-24个月提升一倍，目前该定律已逐渐失效，芯片制程突破遇到瓶颈，但硬件内存资源仍相对充足，设计上仍优先空间换时间。
  7. 迭代器失效的通用解决原则
    失效后的迭代器绝对禁止访问，必须通过接收接口返回值重新赋值后，才能继续使用。无论平台是否有强制检查，都必须遵循该原则，保证代码的跨平台兼容性和稳定性。
  8. 迭代器分类与算法匹配规则
    老师在课程结尾补充了迭代器的分类，以及和算法的匹配要求，完整内容如下：
    1. 迭代器分类（按功能从弱到强）
      1. 输入迭代器：只读，仅支持单向++、解引用读、==/!=判断
      2. 输出迭代器：只写，仅支持单向++、解引用写
      3. 前向迭代器：可读可写，支持单向++，继承输入输出迭代器功能
      4. 双向迭代器：可读可写，支持++和--，如list、map/set的迭代器
      5. 随机访问迭代器：可读可写，支持++、--、+、-、[]、大小比较等所有算术操作，如vector、string的迭代器（功能最强）
    2. 算法与迭代器的匹配要求
      不同算法对迭代器类型有强制要求，不匹配则无法编译：
      • std::find：仅需输入迭代器，所有容器迭代器均支持
      • std::reverse：需要双向迭代器，list、vector均支持
      • std::sort：必须使用随机访问迭代器，仅vector、string等支持；list的迭代器是双向的，无法使用std::sort，必须调用list自带的sort成员函数。
# c语言 # c++ # visual studio # 开发语言 # 算法
Logo
https://edu.csdn.net/learn/39067/627173?utm_source=2019755004

汇聚全球AI编程工具，助力开发者即刻编程。

更多推荐

cover

AI写小说用什么模型最好？DeepSeek、Claude、豆包实测对比，别只盯着一个用

avatar AI编程社区
cover

[论文学习]ToolEmu:用语言模型模拟沙盒识别语言模型智能体的风险

avatar AI编程社区
cover

【生产力】Claude Opus 5 新特性与行为变化：完整更新与迁移指南

avatar AI编程社区