【C++】STL——vector 深度剖析 及 模拟实现
【C++】STL——vector 深度剖析 及 模拟实现
前言
这篇文章我们来学习一下STL里面的vector，它属于STL中容器的一员，我们先来学习一下它的使用，然后，我们也会对vector进行一个深度的剖析和模拟实现。
1. vector的介绍及使用
1.1 vector的介绍
vector的文档介绍 vector 是表示大小可以更改的数组的序列容器：
其实大家可以认为vector就是我们之前数据结构学的顺序表，那说到顺序表，相信就不用给大家过多解释了。
1.2 vector的使用
下面我们来学习一下vector的使用：
其实我们看一下，vector提供的接口跟string是非常相似的，所以经过前面string的学习，再去学习vector，成本就很低了。
那下面我们还是给大家介绍一些常用的接口。
1.2.1 构造函数
首先我们来看一下vector的构造函数：
首先看第一个
explicit vector (const allocator_type& alloc = allocator_type());
只有一个参数，而且有缺省值，但是这个我们平时一般不用管，这个是用来传空间配置器的
它也可以在模板参数这里传。 我们可以认为这个就是无参的构造函数就行了，就是构造一个空的vector。
注意使用vector需要包对应的头文件。 那vector是一个类模板，经过之前的学习我们知道： 类模板实例化只能显式实例化，即需要在类模板名字后跟<>，然后将实例化的类型放在<>中即可。 类模板不是真正的类，其实例化的结果才是真正的类。 这里我们想往vector里放什么类型的数据，直接指定就行了。
我们继续往下看：
第二个的话就是支持用n个val去构造一个vector对象
然后第三个：
就是支持用一段迭代器区间去构造，这里在string的使用里面我们没有给大家演示，现在我们可以试一下：
另外大家可能注意到了它是一个模板：
也就是说这里我们不仅可以传vector的迭代器，也可以传其它容器的迭代器，只要它们的数据类型能够匹配或者能进行一个转换。 我们可以试一下，比如我们传一个string类型的迭代器：
当然这里s里面是char类型的数据，给vector 其实给过去的是ASCII码值。 另外我们是可以控制传过去的这个迭代器区间的范围的，怎么控制呢？ 🆗，其实迭代器我们之前讲的什么正向反向，const迭代器，这些是使用属性；那还有一个特性属性，迭代器严格来说还可以细分为单向迭代器，双向的和随机的，单向的就是只能++不能- -，双向就是可以++也可以- -，那随机就是除了可以++和- -之外还可以+或- 。 那我们学的string和vector的迭代器其实本质就是随机迭代器。 我们试一下：
我们对左边的迭代器++，右边的- -，那这样两边的两个数据是不是就没有放进去啊。 当然这里把数据类型换成char更好看一点：
当然我们说它是随机的，就还可以这样：
不过其实这个构造函数用的不多。
那最后一个就是拷贝构造：
1.2.2 vector对象的遍历
那想遍历vector对象，有哪些方式呢？
我们先创建一个vector对象，尾插几个数据。 有哪些遍历的方式？
首先vector也重载了[ ]，我们可以用for循环+[ ]：
另外：
可以用迭代器，那也就支持了范围for：
当然遍历的同时我们也可以修改它。
1.2.3 vector的迭代器
那vector的迭代器呢我们看到其实还是这几个：
跟string的一样，那在之前文章里我们也对这几个迭代器进行了介绍，所以这里我就不再过多解释了。
直接给大家简单演示一下：
当然如果是const对象就会自动去调用const版本的。
1.2.4 reserve和resize
首先我们来看一下vector的扩容机制：
int main()
{
// 测试vector的默认扩容机制
size_t sz;
vector<int> v;
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';
}
}
return 0;
}在vs上，我们运行一下：
LinuxG++下：
我们看到和string一样，vector的扩容，在vs上基本上也是1.5倍扩容，在G++上也是二倍去扩。 vs是PJ版本STL，g++是SGI版本STL。
那这个时候：
如果我们知道需要多少空间，直接用reserve把空间开好，是不是就可以减少频繁扩容的一个消耗。
reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。
然后还有resize：
resize在开空间的同时还会进行初始化，影响size。当然如果传的n比size小，那它还会删除多余的数据。
1.2.5 insert和erase
vector的insert和erase于string相比，差别就有点大了：
string的insert和erase呢，还支持我们传下标去确定位置
但是vector呢：
就只支持我们去传迭代器和迭代器区间了。
那要传迭代器的话：
我们就需要先找到目标位置的迭代器，怎么找呢？ 我们发现vector并没有提供find这个接口（大家可以去文档里翻，确实没有），那我们怎么获取目标位置的迭代器呢？ 🆗，虽然vector自己没有提供，不过算法库里面提供了一个find：
也是一个函数模板，可以传任意类型的迭代器，在指定的迭代器范围去寻找要查找的值，找到就返回该位置的迭代器，找不到就返回last（即我们传过来的迭代器区间的右边界）。
为什么返回last，因为任何一个迭代器区间都是左闭右开的，
那我们来演示一下：
首先试一下insert：
🆗，那我们现在想把pos位置的元素再删掉，可以这样吗？
哦豁，怎么回事？ 挂了？ 🆗，这里涉及到一个迭代器失效的问题，我们后面也会讲到。 所以，这里要删的话，需要我们重新去找：
当然如果我们可以直接确定要insert或者erase的位置的迭代器，那就没必要find了，比如头删：
那我们vector使用的讲解就差不多到这里了：
因为本身我们已经学了string了，那上手vector就很容易了，成本就很低了，剩下我们没提到的接口，要么就是不重要的，不常用的，要么就是大家一看就会，很简单的，没必要再过多解释了。
1.2.6 vector< char > 能否替代string
然后大家来思考一个问题：vector< char > 能否替代string呢？
答案肯定是不行的！ vector< char >和string感觉好像挺像的，但是还是有差别的： 首先string的话，结尾是有\0的，
vector<char>有吗？ 没有啊，除非我们自己插入。 另外，string对象之间的比较是不是有一套自己的规则啊，一个字符一个字符比较ASCII码值。 vector和string是不一样的：
再其次string有+=和find，这下vector根本都没有。
所以vector<char> 是满足不了string的需求的。
2. vector的模拟实现
那接下来，我们就对vector进行一个模拟实现。
2.1 STL_vector源码浏览
那首先我们来一起简单浏览一下STL里面vector的源码，看看源码大致是怎样实现的：
那我们之前介绍STL就说了，STL有好几个版本，我们这里看源码的话推荐大家去看SGI版本的3.0这个版本，大家可能听说过一本书《STL源码剖析》就是用的这个版本。
那大家想一下，我们要了解一个类，首先应该看什么？
是不是要看一下它有哪些成员变量和成员函数啊，然后你想了解哪一个函数，可以再去看它具体的实现。 我们来看一下：
首先我们可以找到这三个应该是它的成员变量，那跟我们之前学的顺序表的结构是不是还有点差异啊，我们之前写顺序表是一个指针指向动态数组，然后一个size，一个capacity是吧。 我们看到它们的类型都是iterator，这不是迭代器嘛。那我们说了迭代器可以理解成一个像指针一样的东西，但不一定是指针，不过我们看到再当前的SGI版本中：
迭代器的实现就是用的原生指针。 也就是说它可以用原生指针实现，但不一定都是用原生指针，那我们现在用的vs（采用的PJ版本）上其实就不是原生指针。 我们可以看一下：
我们看到是一个类，这个版本的实现是比较复杂的。
那这样的话呢：
也就是说它的三个成员变量其实就是三个指针，那它们三个是什么功能呢？我们怎么去源码中去探索呢？ 🆗，那我们可以先去考虑看一下构造，在构造函数里是怎么对它们初始化的。
有个无参的构造吧它们都初始化成0 了，但是从这好像看不出什么东西。 那接着我们可以考虑看一下size和capacity，它这里三个指针，是怎么求size和capacity呢？ 或许从中我们能发现它们的关系。
首先看到有个size_type其实就是一个typedef：
就是size_t。
那我们再看它这里求size就是end() - begin()，求capacity是end_of_storage - begin()，那这里的end() 和 begin()是啥？
那我们又可以找到end()其实就是finish，begin()就是start。 🆗，那根据这些东西，我们大致就能猜出它们的含义了。
所以它的结构大致是这样一个样子的。
那了解了它的结构，我们就可以自己去实现了。
2.2 vector的结构
新建一个vector.h，定义一个名为vector的类模板
namespace yin
{
template<class T>
class vector
{
public:
typedef T* iterator;
private:
iterator _start;
iterator _finish;
iterator _end_of_storagre;
};
}为了防止冲突，我们还是定义在自己的命名空间里。 vector本质是一个类模板，那我们实例化时指定什么数据类型，vector里面就放什么类型的数据。
那结构定义好，接下来我们就可以实现它的成员函数了。
2.3 常用接口实现
有了string模拟实现的经历，那我们来快速的实现一下。
构造
首先写一下构造：
最开始呢，我们都初始化成空。
push_back
然后来一下push_back：
那push_back的话首先是不是要判断是否需要扩容啊，那确保容量够了，然后就插入数据：
size和capacity
那现在扩容还没实现，扩容会影响capacity，先写一下size()和capacity()
有了之前string模拟实现的经历，相信有些东西就不用给大家过多解释了。
reserve
接着我们来实现一下reserve：
同样为了防止缩容，这里也是n大于capacity才去扩，那扩的话就直接开新空间，然后如果原来有数据，就拷贝到新空间来，并释放旧空间，记得更新_start，_finish和_end_of_storagre
回过头来看push_back：
扩容的逻辑我们就可以实现了： 那我们这里就选择扩两倍，但是注意要进行一个判断，如果capacity为0，不能直接乘2，可以给个初始大小
operator[ ]
再来重载一下[]：
🆗，那先写到这里，我们来简单测试一下：
但是呢，我们发现程序挂掉了。
什么原因呢？
通过调式，我们会发现问题出现在这里：
大家看出来是什么问题了吗？
size()怎么算的啊？
是不是_finish - _start，但是，这里扩容之后，程序走到这一步，_finish 还是原来的_finish ，但是_start是不是已经变了啊。
这里第一次扩容之后，_start有了一个有效的地址，但是_finish还是空指针（0）
_finish = _start + size();
即_finish = _start + （_finish - _start）;
所以最后_finish 还是空指针，那后面后面一解引用就挂了。
那这里我们修改一下：
扩容之前，先保存一下原来的size
然后：
就可以了。
begin和end
然后我们再来写一下begin和end：
那这下我们是不是就可以用迭代器访问我们的vector了，那当然也就支持范围for了：
pop_back
接着再来实现一下pop_back:
怎么删？ 是不是直接
--_finish;但是，如果一直pop的话，_finish是不是就会越界走到_start前面了，所以这里我们可以加一个断言判断一下：
不为空，再尾删。 那我们实现一下判空的接口：
测试一下：
就可以了，我们一直删断言也可以检查出来。
const成员函数
那同样的，有些成员函数包括迭代器我们是不是要提供普通版本和const两个版本啊:
这样普通对象就调普通版本，const对象就调const版本，那这个我们在之前string的模拟实现里也给大家进行了比较详细的讲解，所以这里我们就直接实现了。
我们看到直接调的话是会存在权限放大的问题。
然后就可以了：
resize
然后我们来实现一下resize：
那resize的话就要分情况了，string我们也实现过嘛，如果n<当前的size，那要删除数据，但不缩容；如果n>size，那又要分一下，n>size并且n>capacity，那要扩容，然后初始化，n>size但n<capacity，那就直接初始化：
那现在有一个问题，这里的val是有缺省值的，也就是我们指定初始化的内容就按缺省值初始化，那这里val的缺省值要怎么给？
给个0，可以吗？
如果是vector<int>那给0当然可以，但是，现在我们实现的是一个类模板，针对所有类型，包括自定义类型，那都给0，肯定是不合适的，怎么办？
🆗，我们来看一下库里面的实现是怎么写的：
这里的value_type其实就是T的typedef。
所以库里面是这样写的： 什么意思啊？ 🆗，它这里这样写是不是调用默认构造函数产生一个匿名对象去作为这个缺省值啊。 那这样的话，如果这里的模板参数T是string或者其它的一些自定义类型，那这样是不是都说得过去啊，但是如果是int、double这样的内置类型呢？ 它们好像没有默认构造函数这一说啊，那它们也可以吗？ 🆗，那既然库里面这么写了，那就肯定是可以的。 理论上来说，内置类型是没有构造函数这一说的，构造函数是针对自定义类型的，但是有了模板以后呢？ 内置类型就也需要支持有构造函数了。 我们可以试一下：
可以的，但是我们正常不会这样写的。 所以能够这样最主要还是为了模板。 不过这里对于指针类型我们直接这样写会报错：
而本身我们也不会这样写，但是到了模板里面指针类型也照样支持：
所以：
这里写成这样，就可以统一处理任何类型了。
那我们继续实现我们的resize：
完成了上面的内容，那就剩初始化了，那搞定了val的问题，接下来直接填值就行了
那就写好了，我们来试一下：
2.4 迭代器失效问题
会引起其底层空间改变的操作
会引起其底层空间改变的操作，都有可能导致迭代器失效，比如：resize、reserve、insert、assign、push_back等。 出错原因： 以上操作，都有可能会导致vector扩容，也就是说vector底层原理旧空间被释放掉，而在打印时，it还使用的是释放之间的旧空间，在对it迭代器操作时，实际操作的是一块已经被释放的空间，而引起代码运行时崩溃。 解决方式： 在以上操作完成之后，如果想要继续通过迭代器操作vector中的元素，可以更新it。
insert
首先我们先来实现一下insert：
怎么实现？ 逻辑是不是很简单啊，就是挪动数据，然后填值嘛。 首先应该判断一下pos是否合法以及是否需要扩容：
这就写好了。 来，测试一下：
嗯？？？
怎么回事？
第一次insert还正常，第二次怎么出来个个随机值啊。 🆗，通过调式和分析我们会发现原因在于第二次insert的时候发生了扩容，那为什么发生了扩容就出问题了呢？
我们这里扩容是不是异地开一块新空间，然后拷贝数据，释放旧空间啊，那这样的话，扩容之后，_start和_finish是不是就变了啊，现在它们指向一块新空间，而pos呢，是不是还是原来的pos
那现在pos和end的大小关系是不是未知的啊，这里循环会走多少次我们也不知道。 此时pos指向的空间以及被释放了，即pos此时是一个野指针了，但我们又把val放到了pos指向的空间，但是对扩容后的新空间并没有影响，只是把_finish++了一次，所以打印出来是随机值。 🆗，那这里其实就是迭代器失效的一种情况，扩容之后pos位置的这个迭代器就失效了。 怎么解决？ 是不是如果扩容的话，我们得去更新一下pos啊
然后我们再来测试一下：
🆗，就没问题了。 当然这只是迭代器失效中的一种情况，后面可能还会有一些更复杂的场景，等着我们解决。
再来看一个问题：
我们现在通过find获取元素3的位置pos，然后在该位置insert一个新元素。 那我们现在想去修改pos位置的这个值。可以吗？
我们find的是3的位置，但是后面++却++的不是3，为什么？ 因为我们又insert了一个值到pos位置，3是不是就被挪到后面了啊。 另外如果是这种情况：
哦豁，这次++怎么没起作用啊，谁都没有++。
pos里面怎么放了一个随机值啊。
来看我们这次insert的时候是不是扩容了啊，初始我们给了4个空间嘛。
但是，我们刚才不是已经处理了扩容时迭代器失效的问题，更新了pos嘛，为什么还有问题。
🆗，我们确实更新了，但我们更新的是不是insert函数里面的pos啊，而且我们是传值，所以并没有影响外面的pos，外面的pos在扩容之后还是野指针。
所以外面的pos还是会失效，我们(*pos)++没有对任何元素产生影响。
所以呢：
刚才上面这两种情况，第一次虽然insert之后pos还能用，好像没失效（因为没扩容），但是可能已经不是我们想要的位置了，就像上面我们find的是3的位置，但后面++的并不是3 了。 第二种情况由于发生了扩容，pos这个位置的迭代器就是一个野指针了，彻底失效了。 但是，这两种情况，我们都认为是迭代器失效。
那上面第二个情况怎么解决啊？
传值不行，传引用吗？
这样外面的pos确实不是野指针了，但是，这样又不行了：
为什么？
这里是传值返回，返回的是拷贝的临时变量，具有常性，不能传给引用。 那怎么办？
我们看到库里面的insert是有返回值的，返回更新后的pos：
接收一下返回值，就可以了。
所以：
insert之后我们就认为迭代器失效了，就不要使用了。 我们可以重新去find，或者根据需要接收一下返回值。
指定位置元素的删除操作–erase
那我们再来实现一下erase：
删除pos位置的元素，那我们就直接挪动后面的元素覆盖就行了，如果后一个的话直接- -_finish就行了。
试一下：
那大家思考一下，erase之后迭代器是否失效？
我们试一下：
erase删除pos位置元素后，pos位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代器不应该会失效，但是：如果pos刚好是最后一个元素，删完之后pos刚好是end的位置，而end位置是没有元素的，那么pos就失效了。因此删除vector中任意位置上元素时，vs就认为该位置迭代器失效了。 并且进行了强制检查。 我们看一下vs 上std中的处理：
我们调式会发现
在这里挂了。 删除vector中任意位置上元素时，vs就认为该位置迭代器失效了 注意⚠：Linux下，g++编译器对迭代器失效的检测并不是非常严格，处理也没有vs下极端。 上面那段代码如果我们在G++环境下面运行会发现结果跟我们自己模拟实现的是一样的，因为我们就是按照SGI版本实现的嘛，G++就是采用的SGI，底层跟我们一样是原生指针。 SGI STL中，erase导致迭代器失效后，程序不一定会崩溃，但运行结果可能是不对的；如果迭代器位置不在begin和end范围内，肯定会崩溃的。
所以：
erase以后，我们也认为迭代器失效了，就不要再使用了，行为结果未定义（不同平台可能不同）。 当然库里面的实现也是有返回值的：
所以我们可以根据需要接收返回值去更新失效的迭代器。
然后大家思考一下，我们之前学的string存在迭代器失效的问题吗？
当然也是存在的，但是我们为什么讲string的时候并没有提迭代器失效的问题呢？ 🆗，因为string的insert和erase是不是提供了下标的版本啊
用下标的版本是不是就不存在迭代器失效的版本啊，但是它也提供了迭代器的版本，那当然如果用迭代器就跟vector一样了，要考虑迭代器失效的问题。
2.5 剩余接口补充
2.5.1 析构
接下来我们来实现一下析构：
vector涉及资源申请，析构函数是需要我们自己实现的：
2.5.2 其它版本的构造
构造函数其实我们一开始就实现了，不过我们只实现了一个默认构造：
那接下来我们再来实现几个其它版本的：
首先看这个，n个val去初始化对象：
首先这里val的缺省值是T()，相信这个不用给大家解释了（调用默认构造函数产生一个匿名对象去作为这个缺省值），我们上面刚刚讲解过，因为这里是模板，要针对所有类型。 那大家看，这里是用产生的这个匿名对象的引用去初始化对象，但是我们之前学了匿名对象的声明周期不是只在当前这一行吗？ 那还怎么拿它去初始化呢？ 🆗，我们在之前讲解匿名对象的时候也提了： 和临时变量一样，如果我们用匿名对象去初始化一个引用的话，它的生命周期就会被延长至该引用被销毁。并且这里肯定都要加const的，因为临时变量和匿名对象都具有常性。
那函数内部具体怎么实现呢？
🆗，我们是不是可以直接push_back() n次啊，那这样的话我们还可以使用reserve直接把空间开够，避免push_back过程中扩容：
来测试一下：
没有问题。
然后我们再来看一下这个构造函数：
用一段迭代器区间去初始化，它的使用我们在上面已经讲解过了，那现在我们来尝试模拟实现一下它： 我们看到它其实是一个函数模板，因为它还支持接收除vector之外其它类型的迭代器，这个我们上面也说过了。 所以说，在一个类模板中，它的成员函数可以是函数模板。
那这里的模板参数我们可以用T，也可以直接用这个InputIterator，因为模板参数的名字我们可以自己起嘛。
那函数体内怎么实现呢？
也很简单，我们直接遍历这个迭代器区间一个个push_back()就行了：
当然这个地方如果大家觉得每个构造函数都要写初始化列表，嫌麻烦的话，我们之前学过C++11不是支持类中的非静态成员变量可以给缺省值嘛，所以我们也可以直接给缺省值，这样就不用写初始化列表了。
🆗，我们接着看：
迭代器区间的这个构造函数我们写好之后呢，会发现一个问题：
我们编译会发现报错了，说非法的间接寻址。 哎？怎么回事啊？
然后我们双击下面这条错误信息发现定位到了这里
把它注释掉就没事了，说明问题与这段代码有关系。
那原因是什么呢？
其实根据错误信息我们也能看出来，yin::vector<int> a(10, 5);这句代码匹配到了迭代器区间的这个构造函数，但是我们本意是不是让他去匹配n个val的构造函数啊。
那这里为什么会匹配到迭代器区间的这个？
🆗，因为函数调用根据参数去匹配的时候，会去找最合适，最匹配的那个，刚才我们没实现迭代器的这个版本的时候，那它只有一个选择，所以就没事，但是现在实现之后，那他就选择了迭代器区间这个，因为这个是一个函数模板，这里10跟5两个int传过来，模板参数InputIterator就自动被推演成int类型了。
但是这个的话：
n是size_t 类型的，int过了还要进行一个类型转换。 所以就匹配到了模板的那个版本。
这里我们加个u就不报错了，加个u它就是无符号整型了嘛。
那这里我们怎么解决这个问题呢？
🆗 ，我们可以看一下源码是怎么做的：
我们看到源码里是不是重载了多个版本来解决参数类型的这个问题啊。 当然我们这里不用考虑那么多情况：
是不是就可以了。
那我们来测试一下迭代器区间的这个构造函数：
当然我们可以自己控制这个区间的大小。
当然我们也可以使用其它类型的迭代器
这个我们再讲使用的时候也演示过，那我们自己写的这个当然也是可以的：
那除此之外，还能这样玩：
甚至可以是数组，我相信原因不用过多解释了：
2.5.3 对vector排序
我们现在相对一个vector进行排序，怎么搞？
那其实算法库里面提供了一个排序的函数sort，我们可以直接用。 我们看到它也是接收一段迭代器区间，演示一下：
就排好了。 当然也可以直接排数组：
当然我们也看出来了它默认是升序。 如果想降序的话这样就行了：
这个大家先简单了解一下，后面还会讲。
2.6 使用memcpy拷贝的问题
我们现在还没有实现拷贝构造：
拷贝构造如果我们不写，编译器会默认生成，但是默认生成的是浅拷贝，而我们的vector涉及资源申请，所以如果用默认生成的一定是会出问题的：
相信原因就不用给大家过多解释了。
所以我们要自己实现一下拷贝构造：
那有了我们之前实现的接口，其实要再来实现这个拷贝构造，也很简单：
怎么做？ 🆗，直接使用reserve把空间开好，然后遍历v的所有元素push_back到当前对象是不是就行了：
试一下：
这下是不是就行了啊。
但是呢：
上面这种写法不够传统，本质是在复用，接下来我们再实现一个更传统一点的，方便我们讲解后面的东西：
大家思考一下，如果不复用push_back的话，开好空间之后我们可以怎么拷贝？
是不是可以用memcpy啊：
🆗，可以完成。
但是，如果是这种场景呢：
刚才vector的元素类型是int，如果是string呢？ 我们来运行程序：
好像挂了呀，调式一下：
确实是挂了。
怎么回事呢？为什么刚才vector<int>就没事，而vector<string>就出现问题了呢？
🆗，原因就在于我们拷贝构造内部使用了memcpy来拷贝数据。 1. memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中 2. 如果拷贝的是自定义类型的元素，memcpy既高效又不会出错
但如果拷贝的是自定义类型元素，并且 自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝
那这样在析构的时候是不是又会出现对同一块空间析构两次的情况啊，所以才会导致程序崩溃。
所以：
vector里面嵌int这些类型的数据（
vector<int>）是没问题的，但如果嵌的是自定义类型并且该自定义类型设计资源申请（需要深拷贝，比如vector<string>，vector<vector>等），就会出错，因为内部memcpy的拷贝实际是浅拷贝。
那我们可以怎么解决这个问题呢？
也好处理，可以这样搞：
大家看这样的话，如果int这样的内置类型就直接赋值，这肯定是没问题的，如果是涉及资源管理的自定义类型，是不是就去调深拷贝的拷贝构造就行了啊。 测试一下：
就可以了。
2.7 对vector<vector>的理解
vector<vector>的使用（OJ练习）
首先我们来看一道题： 题目链接: link
思路讲解
这道题呢是给我们一个行数 numRows，生成「杨辉三角」的前 numRows 行。 那这道题的思路是很简单的，没什么难度： 核心思想：找出杨辉三角的规律，发现每一行头尾都是1，中间第[j]个数等于上一行[j-1]+[j]。 但是，如果我们用C语言去写这道题：
大家看，其实是有点麻烦的，一级指针、二级指针，最终返回的数组还得是malloc的。首先这个参数可能就给我们看懵逼了。 而C++呢？
C++有了vector，就爽很多了。 不过这里需要用到vector<vector>，这是什么东西，🆗，就是一个二维的vector嘛，类似于二维数组，但是如果是二维数组，我们开一个m x n的，它的每行元素是不是相等的啊，而这里杨辉三角是不是每行元素个数不一样啊。 但是用vector，我们是不是就可以很方便的控制每行的size啊。
我们只需要定义一个numRows行的vector<vector>，每行的元素个数是多少？ 是不是i+1啊，i等于0（第0行），就是一个元素；i等于1，两个元素；以此类推。 然后只需把每行第一个和最后一个元素初始化为1 ，中间剩余的元素是不是就是它上一行的元素和上一行的前一个元素相加的和啊。
AC代码
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> vv(numRows);
for(int i=0;i<numRows;i++)
{
vv[i].resize(i+1,0);
vv[i][0]=vv[i][vv[i].size()-1]=1;
}
for(size_t i=0;i<vv.size();++i)
{
for(size_t j=0;j<vv[i].size();++j)
{
if(vv[i][j]==0)
vv[i][j]=vv[i-1][j]+vv[i-1][j-1];
}
}
return vv;
}
};
构造一个vv动态二维数组，vv中总共有n个元素，每个元素都是vector类型的，每行没有包含任何元素，如果n为5时如下所示：
vv中元素填充完成之后，如下图所示：
vector<vector>的拷贝构造
我们上面已经实现了vector的拷贝构造，并且解决了使用memcpy拷贝的内部浅拷贝的问题。
那我们来试一下vector<vector>的拷贝构造：
首先经过我们上面的修改，我们的拷贝构造应该是没问题了，上面我们测试
vector<string>的拷贝构造就没问题了。 我们就来拷贝构造一下上面的那个杨辉三角，用我们自己实现的vector：
哎呀！怎么回事？ 我们的拷贝构造上面不是已经修改好了嘛，为什么又出错了。
问题出在哪里呢？
🆗，除了我们的拷贝构造之前用了memcpy，不过我们已经改了，可是，还有一个地方我们也用了memcpy：
我们的reserve也用了memcpy拷贝数据。
>那这个地方是不是也会出现浅拷贝的问题对于vector<vector>这些类型来说。
把里面的每个小vector浅拷贝到新空间，但是两块空间里面的每个小vector指向同一块空间，然后接着就直接把旧空间释放掉了，然后扩容之后新空间里面的每个vector的_start就全是野指针了。
那要怎么修改？
和拷贝构造一样，我们可以一个一个赋值：
然后我们再来试一下：
哎呀哈？怎么还有问题？ 🆗，那我们通过调式来尝试找一下问题：
我们调式一步步走会发现走到析构的时候崩了。 但是我们的拷贝构造不是应该没问题了嘛，我们来分别观察一下函数返回的ret和main函数中的vv：
我们仔细观察一下能够看出来，ret和vv的地址是不一样的，这当然是正常的表现；但是它们两个里面每个小vector的地址却是一样的，这就有问题了呀！
这说明什么？
内部小vector的拷贝是不是又是浅拷贝啊，欸！可是，我们不是已经修改过拷贝构造了嘛，而且上面vector<string>测试也没问题啊。
请问问题出在哪里？
🆗，我们拷贝构造现在是怎么实现的？
由于memcpy会导致内层浅拷贝的问题，所以我们改成了一个元素一个元素去赋值，内置类型之间赋值没有问题，涉及资源申请的自定义类型赋值会调深拷贝的赋值重载，我们拷贝构造的实现没什么问题。 但是： 问题就在于我们现在使用的vector是我们自己写的，而现在我们并没有进行赋值重载，而默认生成的是浅拷贝，所以： 才导致了内层小vector的赋值是浅拷贝。
所以，我们现在必须实现深拷贝的赋值重载：
怎么搞呢？ 很简单，比如v1=v2，我们可以直接这样：
比如要v2赋值给v1，那赋值重载函数中的参数v是v2的拷贝，然后直接把v交换给v1就行了。当然这里我们再实现一个交换的接口。
那这下我们再来测试一下：
就可以了。
另外：
我们说了，上面实现的那个拷贝构造是比较传统的写法，那现在我们还可以写一个现代的写法：
直接借助迭代器版本的拷贝构造构造出来一个对象，然后把它交换给目标对象。
也是没问题的。
然后再给大家提一个东西就是：
这个地方不加模板参数语法也是支持的，但是建议大家自己写的时候还是加上，给大家说一下的目的是如果我们在别的地方看到这个的写法也不要奇怪，知道这样也可以。
3. 源码展示
vector.h
#pragma once
#include <assert.h>
#include <string.h>
namespace yin
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
vector()
{}
vector(size_t n, const T& val = T())
{
reserve(n);
for (size_t i = 0; i < n; ++i)
{
push_back(val);
}
}
vector(int n, const T& val = T())
{
reserve(n);
for (int i = 0; i < n; ++i)
{
push_back(val);
}
}
template <class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
++first;
}
}
~vector()
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
size_t capacity() const
{
return _end_of_storage - _start;
}
size_t size() const
{
return _finish - _start;
}
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin()const
{
return _start;
}
const_iterator end()const
{
return _finish;
}
void reserve(size_t n)
{
if (n > capacity())
{
size_t sz = size();
T* tmp = new T[n];
if (_start)
{
//memcpy(tmp, _start, size() * sizeof(T));
for (size_t i = 0; i < sz; ++i)
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + sz;
_end_of_storage = _start + n;
}
}
void resize(size_t n, T val = T())
{
if (n < size())
{
_finish = _start + n;
}
else
{
if (n > capacity())
{
reserve(n);
}
//初始化
while (_finish != _start + n)
{
*_finish = val;
++_finish;
}
}
}
/*vector(const vector<T>& v)
{
reserve(v.capacity());
for (auto e : v)
{
push_back(e);
}
}*/
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
vector(const vector<T>& v)
{
vector<T> tmp(v.begin(), v.end());
swap(tmp);
}
//vector(const vector<T>& v)
//{
// _start = new T[v.capacity()];
// //memcpy(_start, v._start, sizeof(T) * v.size());
// for (size_t i = 0; i < v.size(); ++i)
// {
// _start[i] = v._start[i];
// }
// _finish = _start + v.size();
// _end_of_storage = _start + v.capacity();
//}
iterator insert(iterator pos, const T& val)
{
assert(pos >= _start && pos <= _finish);
if (_finish == _end_of_storage)
{
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
//扩容后更新pos，解决pos失效问题
pos = _start + len;
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = val;
++_finish;
return pos;
}
iterator erase(iterator pos)
{
assert(pos >= _start && pos < _finish);
iterator start = pos + 1;
while (start != _finish)
{
*(start - 1) = *start;
++start;
}
--_finish;
return pos;
}
void push_back(const T& x)
{
if (_finish == _end_of_storage)
{
//扩容
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
*_finish = x;
++_finish;
}
void pop_back()
{
assert(!empty());
--_finish;
}
T& operator[](size_t pos)
{
assert(pos < size());
return _start[pos];
}
const T& operator[](size_t pos)const
{
assert(pos < size());
return _start[pos];
}
bool empty()
{
return _start == _finish;
}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
};
}test.cpp
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include "vector.h"
//#include <vector>
//int main()
//{
// vector<int> a;
// a.push_back(1);
// a.push_back(2);
// a.push_back(3);
// a.push_back(4);
// a.push_back(5);
//
// for(size_t i = 0; i < a.size(); ++i)
// {
// cout << a[i] << " ";
// }
// cout << endl;
// for (vector<int>::iterator it = a.begin(); it != a.end(); ++it)
// {
// cout << *it << " ";
// }
// cout << endl;
// for (auto e : a)
// {
// cout << e << " ";
// }
// cout << endl;
// return 0;
//}
//int main()
//{
// vector<int> a;
// a.push_back(1);
// a.push_back(2);
// a.push_back(3);
// a.push_back(4);
// a.push_back(5);
//
// for (vector<int>::iterator it = a.begin(); it != a.end(); ++it)
// {
// cout << *it << " ";
// }
// cout << endl;
//
// for (vector<int>::reverse_iterator rit = a.rbegin(); rit != a.rend(); ++rit)
// {
// cout << *rit << " ";
// }
// cout << endl;
// return 0;
//}
//int main()
//{
// vector<int> a;
// a.push_back(1);
// a.push_back(2);
// a.push_back(3);
// a.push_back(4);
// a.push_back(5);
// for (auto e : a)
// {
// cout << e << " ";
// }
// cout << endl;
// vector<int>::iterator pos = find(a.begin(), a.end(), 3);
// if (pos != a.end())
// {
// a.insert(pos, 30);
// }
// for (auto e : a)
// {
// cout << e << " ";
// }
// cout << endl;
// pos = find(a.begin(), a.end(), 30);
// if (pos != a.end())
// {
// a.erase(pos);
// }
// for (auto e : a)
// {
// cout << e << " ";
// }
// cout << endl;
// a.erase(a.begin());
// for (auto e : a)
// {
// cout << e << " ";
// }
// cout << endl;
// return 0;
//}
//void func(const yin::vector<int>& a)
//{
// for (size_t i = 0; i < a.size(); ++i)
// {
// cout << a[i] << " ";
// }
// cout << endl;
// for (yin::vector<int>::const_iterator it = a.begin(); it != a.end(); ++it)
// {
// cout << *it << " ";
// }
// cout << endl;
//}
//int main()
//{
// yin::vector<int> a;
// a.push_back(1);
// a.push_back(2);
// a.push_back(3);
// a.push_back(4);
// a.push_back(5);
// a.push_back(6);
// func(a);
// for (size_t i = 0; i < a.size(); ++i)
// {
// cout << a[i] << " ";
// }
// cout << endl;
// a.pop_back();
// a.pop_back();
// a.pop_back();
// for (yin::vector<int>::iterator it=a.begin(); it != a.end(); ++it)
// {
// cout << *it << " ";
// }
// cout << endl;
// a.pop_back();
// a.pop_back();
// //a.pop_back();
// //a.pop_back();
// //a.pop_back();
// //a.pop_back();
// //a.pop_back();
// //a.pop_back();
// //a.pop_back();
// //a.pop_back();
// //a.pop_back();
// for (auto e : a)
// cout << e << " ";
// cout << endl;
// return 0;
//}
//#include <vector>
//int main()
//{
// yin::vector<int> a;
// a.push_back(1);
// a.push_back(2);
// a.push_back(3);
// a.push_back(4);
// for (auto e : a)
// cout << e << " ";
// cout << endl;
// auto pos = find(a.begin(), a.end(), 3);
// if (pos != a.end())
// {
// pos = a.erase(pos);
// }
// //(*pos)++;
// for (auto e : a)
// cout << e << " ";
// cout << endl;
// return 0;
//}
//#include <algorithm>
//int main()
//{
// /*int arr[] = { 2,8,9,3,5,6,8,7 };
// yin::vector<int> b(arr, arr + sizeof(arr) / sizeof(arr[0]));
// for (auto e : b)
// cout << e << " ";
// cout << endl;
// sort(b.begin(), b.end());
// for (auto e : b)
// cout << e << " ";
// cout << endl;*/
//
// int arr[] = { 2,8,9,3,5,6,8,7 };
// for (auto e : arr)
// cout << e << " ";
// cout << endl;
// sort(arr, arr + sizeof(arr) / sizeof(arr[0]), greater<int>());
// for (auto e : arr)
// cout << e << " ";
// cout << endl;
//
// return 0;
//}
//int main()
//{
// yin::vector<string> a(5, "hello");
// for (auto e : a)
// cout << e << " ";
// cout << endl;
//
// yin::vector<string> b(a);
// for (auto e : b)
// cout << e << " ";
// cout << endl;
// return 0;
//}
yin::vector<yin::vector<int>> generate(int numRows) {
yin::vector<yin::vector<int>> ret(numRows);
for (int i = 0; i < numRows; i++)
{
ret[i].resize(i + 1, 0);
ret[i][0] = ret[i][ret[i].size() - 1] = 1;
}
for (size_t i = 0; i < ret.size(); ++i)
{
for (size_t j = 0; j < ret[i].size(); ++j)
{
if (ret[i][j] == 0)
ret[i][j] = ret[i - 1][j] + ret[i - 1][j - 1];
}
}
return ret;
}
int main()
{
yin::vector<yin::vector<int>> vv(generate(5));
for (size_t i = 0; i < vv.size(); ++i)
{
for (size_t j = 0; j < vv[i].size(); ++j)
{
cout << vv[i][j] << " ";
}
cout << endl;
}
cout << endl;
return 0;
}🆗，那我们关于vector的讲解就差不多到这里了，欢迎大家指正！！！
腾讯云开发者
