C++：vector(3)

一.vector扩容的深拷贝问题

#include <iostream>
#include <cstring>
#include <string>template <typename T>
class MyVector {
private:T* _start;T* _finish;T* _endofstorage;public:MyVector() : _start(nullptr), _finish(nullptr), _endofstorage(nullptr) {}void reserve(size_t n) {if (n > capacity()) {size_t old_size = size();T* tmp = new T[n];if (_start) {// 错误：使用memcpy导致浅拷贝std::memcpy(tmp, _start, sizeof(T) * old_size); delete[] _start;}_start = tmp;_finish = _start + old_size;_endofstorage = _start + n;}}size_t size() const { return _finish - _start; }size_t capacity() const { return _endofstorage - _start; }~MyVector() { delete[] _start; }
};

当使用 memcpy 来拷贝 std::string 时，之所以会出现浅拷贝问题，根源在于 memcpy 自身的特性以及 std::string 的内部结构 ：

1.memcpy 的特性

memcpy 是C语言中的内存拷贝函数，它仅仅是按字节对内存进行逐位复制。它不关心所操作数据的类型和对象的内部结构，不会调用对象的构造函数、析构函数或赋值运算符 。比如，它只是把一块内存区域的二进制数据原封不动地搬到另一块内存区域。

2.std::string 的内部结构

std::string 并非简单地将字符串内容直接存储在对象内部。它内部通常包含一个指针，该指针指向动态分配的堆内存空间，在那里实际存储字符串的字符序列。例如创建 std::string s = "example"; 时，std::string 对象里有个指针指向堆上存放 "example\0" 的内存区域。

3.浅拷贝问题产生过程

在模拟 vector 的 reserve 函数中用 memcpy 拷贝 std::string 时：

1. 当重新分配内存并使用 memcpy 拷贝 std::string 对象时，它只是把 std::string 对象本身（包含指针等少量成员）的字节数据复制过去。新的 std::string 对象中的指针和旧对象中的指针指向了同一块堆内存空间（存放字符串内容的地方） ，这就是浅拷贝。
2. 之后如果旧的内存被释放（比如原 vector 的存储区被释放 ），新的 std::string 对象中的指针就成了悬垂指针，再访问这个对象就会引发未定义行为。而且如果后续再次释放这块内存（比如对象析构时 ），就会出现双重释放错误。

4.浅拷贝的具体情况如下

以上这张图在展示 vector 相关内存操作，特别是涉及字符串存储时可能出现的问题。结合之前关于 vector 的 reserve 函数和 std::string 浅拷贝问题来看：

• 图中 _start 指向原 vector 的起始位置，里面存储着类似 std::string 结构的数据（包含 _str 指针指向实际字符串内容，还有 _size 和 _capacity 字段 ）。
• tmp 指向新分配的内存空间，用于扩容后存储数据。
• 紫色和蓝色的线表示使用 memcpy 进行拷贝时，只是简单复制了对象内指针等成员的值，使得新旧对象中的 _str 指针都指向相同的字符串内容（蓝色矩形区域），这就是浅拷贝。当原内存释放时，新对象的 _str 指针就会变成悬垂指针，后续访问会引发未定义行为。

5.改进方法:用赋值代替memcpy

用赋值代替 memcpy 有诸多好处：

• 避免浅拷贝：memcpy 只是按字节复制内存，对含指针的对象（如 std::string ），会让新旧对象指针指向同一块资源，形成浅拷贝，易引发悬垂指针、双重释放等问题。而赋值操作会调用对象的赋值运算符，自动完成深拷贝，为新对象分配独立资源并复制内容。
• 正确调用构造析构函数：memcpy 不涉及对象构造和析构，在处理已构造对象时，可能导致内存泄漏或对象未初始化等未定义行为。赋值操作则建立在对象已正确构造基础上，遵循对象生命周期管理规则，能正确管理资源。
• 代码更符合规范：赋值是C++ 核心操作，更契合C++ 编程范式和标准库习惯，使代码更易读、易维护。

#include <iostream>
#include <string>template <typename T>
class MyVector {
private:T* _start;T* _finish;T* _endofstorage;public:MyVector() : _start(nullptr), _finish(nullptr), _endofstorage(nullptr) {}void reserve(size_t n) {if (n > capacity()) {size_t old_size = size();T* tmp = new T[n];if (_start) {// 使用赋值操作代替uninitialized_copyfor (size_t i = 0; i < old_size; ++i) {tmp[i] = _start[i]; // 调用T的赋值运算符}// 手动析构原对象for (size_t i = 0; i < old_size; ++i) {_start[i].~T();}delete[] _start;}_start = tmp;_finish = _start + old_size;_endofstorage = _start + n;}}// 添加push_back方法以便测试void push_back(const T& value) {if (_finish == _endofstorage) {reserve(capacity() ? capacity() * 2 : 1);}new (_finish) T(value); // 定位new表达式构造对象++_finish;}size_t size() const { return _finish - _start; }size_t capacity() const { return _endofstorage - _start; }~MyVector() {for (T* p = _start; p != _finish; ++p) {p->~T(); // 手动调用析构函数}delete[] _start;}
};

二.对vector<vector>的理解

以杨辉三角为例：

解题思路
可以使用动态规划的方法来生成杨辉三角。杨辉三角有以下性质：
第 i 行（从 0 开始计数）有 i + 1 个元素。
每行的第一个和最后一个元素都是 1。
对于中间的元素，第 i 行第 j 个元素（1 <= j < i） 等于第 i - 1 行第 j - 1 个元素与第 i - 1 行第 j 个元素之和。

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

代码功能与逻辑分析

C++ 代码定义了一个名为 Solution 的类，其中 generate 函数用于生成杨辉三角的前 numRows 行。以下是具体逻辑：

1. 初始化二维向量：
   • vector<vector<int>> vv; 声明了一个二维向量 vv 用于存储杨辉三角的结果。
   • vv.resize(numRows,vector<int>()); 将 vv 的大小调整为 numRows 行，每行初始化为空的 vector<int> 。
2. 设置每行首尾元素为1：
   • 通过外层循环 for(int i = 0; i < numRows; i++) 遍历每一行，然后使用 vv[i].resize(i + 1, 1); 将第 i 行的大小设置为 i + 1 ，并将该行所有元素初始化为 1 。这是利用了杨辉三角每行首尾元素都是 1 的特性 。
3. 计算中间元素：
   • 外层循环 for(int i = 2; i < vv.size(); i++) 从第3行（索引为2，因为索引从0开始）开始遍历。
   • 内层循环 for(int j = 1; j < vv[i].size() - 1; j++) 遍历当前行（第 i 行）除了首尾（索引为0和 i ）的元素。
   • 在循环内部，vv[i][j]=vv[i - 1][j - 1]+vv[i - 1][j]; 根据杨辉三角的性质，即每个数是它左上方和右上方的数的和，计算并设置当前位置的元素值。
4. 返回结果：最后通过 return vv; 将生成好的杨辉三角（存储在 vv 中）返回。

以上是 C++ 中 vector 模板类及嵌套 vector（二维动态数组）实现杨辉三角初始化逻辑 的示意图，核心实体信息梳理：

1. 模板类基础

• 最上方是 vector 类模板定义（template<class T>），包含私有成员：
  • T* _a：指向动态分配内存的指针，存储元素
  • size_t _size：当前有效元素个数
  • size_t _capacity：已分配内存可容纳的最大元素个数（不扩容时）

2. 模板实例化

• 通过实例化（vector<int>、vector<vector<int>> ），生成具体类型的 vector 类：
  • vector<int>：存储 int 类型元素的动态数组，operator[] 用于按下标访问 int 元素
  • vector<vector<int>>：存储 vector<int> 类型元素的动态数组（即二维动态数组），operator[] 用于按下标访问 vector<int> 子数组

3. 二维 vector 逻辑（杨辉三角初始化示例）

• 函数 generate(int numRows) 演示二维 vector（vector<vector<int>> vv ）的初始化：
  • vv.resize(numRows, vector<int>())：先给外层 vector 分配 numRows 个“空 vector<int>” ，作为二维数组的行
  • 内层循环 vv[i].resize(i + 1, 1)：给第 i 行的 vector<int> 分配 i + 1 个元素，且初始值设为 1（杨辉三角每行首尾为 1 的基础逻辑 ）

4. 下标访问原理

• vv[i][j] 是两次调用 operator[] 的语法糖：
  • 先通过 vv.operator[](i) 获取第 i 行的 vector<int> 对象
  • 再通过该对象的 operator[](j) 获取该行第 j 列的 int 元素

简单说，以上这张图用 “类模板定义→实例化→二维数组初始化→下标访问拆解” 的流程，清晰展示了 C++ 中 vector 作为动态数组（及嵌套动态数组）的实现原理 ，常用于讲解 STL 容器底层逻辑和二维动态数组操作~

三. 迭代器失效

// 要求删除所有偶数
auto it = v.begin();
while (it != v.end())
{if (*it % 2 == 0){// erase也会迭代器失效，失效的迭代器就不能再使用了// 要重新赋值更新这个迭代器才能使用it = v.erase(it);++it;}
}

1.失效原因

在C++ 中，使用erase方法导致迭代器失效，主要原因在于容器内部结构发生改变：

• 内存重分配：当调用erase删除元素后，一些容器（如vector）为了优化内存，可能会重新分配内存空间。一旦内存重新分配，原来指向旧内存地址的迭代器就不再有效，因为其指向的内存区域已经不存在或者被重新利用了。
• 元素位置变动：对于像vector和deque这类连续存储元素的容器，删除一个元素后，其后的元素会向前移动来填补空缺位置 。迭代器指向的是特定位置的元素，元素位置改变，迭代器也就不再指向预期元素，导致失效。

代码中，v.erase(it)删除元素后，erase成员函数会返回一个指向删除元素之后位置的迭代器，所以要将其赋值给it， 让it指向正确位置，以保证后续迭代的正常进行。

2.改进方法

• 去除多余操作：删除了原代码中v.erase(it)之后多余的++it语句，保证迭代器正确指向。
• 增加示例及输出：添加了main函数作为示例，展示代码实际运行过程。创建了一个简单的std::vector<int>容器并初始化，同时在删除偶数元素后，增加了输出语句，用于显示处理后的容器内容，方便测试和理解代码功能。

#include <iostream>
#include <vector>int main() {std::vector<int> v = {1, 2, 3, 4, 5};  // 示例容器，可替换为实际的容器vauto it = v.begin();while (it != v.end()) {if (*it % 2 == 0) {// erase会使迭代器失效，这里通过赋值更新迭代器it = v.erase(it); } else {++it;}}return 0;
}