一、前言

大家好，在上一文中，我们重点介绍了 STL中的string类，明白了如何去操作字符串。本文我们将要来介绍的是STL中的vector类

二、vector深度剖析及模拟实现【✔】

在介绍完了【vector】的基本接口后，我们就透过源码来深入理解一下

1、源码引入

• 以下我所介绍的都是基于【SGI】版本的STL，对源码有兴趣的同学可以去看看 侯捷老师的《STL源码剖析》

• 然后呢我们就去调出【vector】的一些核心源码，这里我们主要关注的就是这个使用原生指针value_type*所定义出来的迭代器 iterator
• 然后我们又看到了保护成员：[start]、[finish]、[end_of_stroage]。看到它们你是否有想起我们在 模拟string 的时候写到过的 [a]、[size]、[capacity]；没错，它们就存在着一定的对应关系

• 但是呢，只看上面这些成员变量还不够，我们要将其带入到具体的场景中，例如下面有两个接口分别为【尾插】和【扩容】，对于push_back()封装得没有那么厉害，读者结合下面的图应该就能看得懂，分别就是 未满追加的逻辑和已满扩容的逻辑
• 那对于reserve()来说，就是一个扩容的逻辑，【allocate_and_copy】是开辟和拷贝空间，那【deallocate】就是释放空间。在扩完容之后不要忘了去对三个成员变量做更新，这一块的模拟实现我在下面马上就会讲到

• 最后的话我们再来看看 构造函数construct和析构函数destroy，光看代码，不知你是否回忆起了我们曾经在 C/C++内存管理 中有讲到【定位new】这个概念，而且提到了 内存池 这个概念
• 其实我们在调用构造函数的时候，都是通过【空间适配器】在  内存池 中开出空间；那在出了作用域之后这些所开的空间都要销毁了，所以就会去调用析构函数完成释放

💬 对于上面的这些源码呢，读者可以在学习了STL一段时间后，配合侯捷老师的《STL源码剖析》再去展开阅读，因为考虑到读者的基础，就不在继续深入讲解了~

2、模拟实现

然后我们就来模拟实现一下【vector】中的各种接口

• 还是一下，我们先简述一下整体的架构。这个vector类还是包在【bit】这个命名空间中，而对于这个类而言，我要将其定义为一个 模版类，这一块如果还有同学不太熟悉的话可以去看看 C++模版
• 其他部分可以看到迭代器我定义的就是原生指针类型，然后将[_start]、[_finish]、[_end_of_storage]也定义为了三个迭代器类型，并且采用提前声明的形式将它们都初始化为nullptr，这样当我们后面在写 构造函数和析构函数 的时候就不需要再去做初始化了

namespace bit {
  template<class T>
  class vector {
  public:
    typedef T* iterator;
    typedef const T* const_iterator;
  // 主要接口函数
  private:
    iterator _start = nullptr;
    iterator _finish = nullptr;
    iterator _end_of_storage = nullptr;
  };
}

1）迭代器

• 首先的话简单一点，来实现一下迭代器，分为非const版本和const版本

iterator begin()
{
  return _start;
}
iterator end()
{
  return _finish;
}
const_iterator begin()  const
{
  return _start;
}
const_iterator end()  const
{
  return _finish;
}

2）容量

• 然后我们来讲讲容量相关的接口，首先的话就是【size】和【capacity】这两个接口

size_t size()
{
  return _finish - _start;
}
size_t capacity()
{
  return _end_of_storage - _start;
}

• 对于【size】而言指的是当前这个容器中的数据个数，那也就是我们在上面所讲的_start和_finish这两个迭代器之间的距离，我们之前有说到过迭代器它的底层其实就是指针，那要计算出两个指针之间的数据个数的话让它们做一个相减_finish - _start
• 那对于整个容器的容量【capacity】来说，即为_end_of_storage - _start。读者通过下图便可一目了然地看出来

• 然后呢再来说说扩容这一块的接口【reserve】，首先在一进来的时候我们要去做一个判断，只有当所传入的值要比原先的capacity()来得大的时候，我们才去执行一个扩容的逻辑，在内部的扩容逻辑中可以看到我们使用到了前面所定义的模版参数T，这样去写的话就可以根据不同的类型参数开出不同的空间
• 接下去我们所执行的就是拷贝的逻辑，采取到的是内存函数memcpy()，拷贝完后再去释放原空间，接下去把这些成员变量去做一个更新即可

==看着逻辑很清晰，但是呢下面的代码存在着非常多的漏洞==

void reserve(size_t n)
{
  if (n > capacity())
  {
    T* tmp = new T[n];    // 开一块新空间
    if (_start)
    {
      memcpy(tmp, _start, sizeof(T) * size());
      delete[] _start;
    }
    _start = tmp;
    _finish = _start + size();
    _end_of_storage = _start + n;
  }
}

• 我们这里再写一个push_back的接口（后面讲），让代码先跑起来

void push_back(const T& x)
{
  if (_finish == _end_of_storage)
  {
    size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
    reserve(newCapacity);
  }
  *_finish = x;
  _finish++;
}

💻第一轮测试 — 空指针异常

下面是测试的代码

void test_vector1()
{
  bit::vector<int> v;
  v.push_back(1);
  v.push_back(2);
  v.push_back(3);
  v.push_back(4);
  for (auto e : v)
  {
    cout << e << " ";
  }
  cout << endl;
}

• 但是呢在运行起来后却发现程序出现了崩溃，这是为什么呢？

• 按下【F5】以调试的方式运行起来就可以发现有地方出现了 空指针异常

• 进一步，我们通过【调试窗口】再来看看，很明显得就看到这个_finish的值为【0x00000000】

• 知道了问题所在，接下去我们就通过调试一步步地来看。虽然这个代码是崩在191，但是呢其实真正的问题还是出在【reserve】这个扩容的逻辑中，随着我们一步一步地去看，可以看到_start和_end_of_storage这两个都没什么问题，但是_finish就是没有什么变化，所以呢我们可以锁定到下面这句话

_finish = _start + size();

• 此时就需要去看看这个【size】了，之前我们使用的是_finish - _start来计算的 size()，在执行这句话时_start已经发生了改变，因为我们去开出了一块新的空间，但是这时_finish的值还是一开始的【nullptr】，那么这个 size() 最后计算出来的大小即为 -_start，此时再和_start去做一个结合的话即为 0

💬 所以，上述就是为什么这个_finish的值为【0x00000000】原因，那我们要如何去修改呢？

• 首先第一种解决方案，就是先去更新这个_finish，用开出空间的 tmp 去做一个更新，然后再用 tmp 去更新_start，这样就不会出现问题了

_finish = tmp + size();
_start = tmp;
_end_of_storage = _start + n;

• 通过调试来观察看看就发现确实不为空了

💬 但是呢上面这种方案的话可能你的徒弟在维护你的代码的时候就会觉得很奇怪，又给改回去了，导致原先的问题再度发生，所以我们可以采取下面这种策略

• 我们可以在每次没开始扩容之前我们都可以去事先保存一下这个 size()，后面的更新顺序就不需要发生变动了，在加的时候加上sz即可

if (n > capacity())
{
  // 先保存一下原先的size()
  size_t sz = size();
  T* tmp = new T[n];    // 开一块新空间
  if (_start)
  {
    memcpy(tmp, _start, sizeof(T) * size());
    delete[] _start;
  }
  _start = tmp;
  _finish = _start + sz;
  _end_of_storage = _start + n;
}

• 通过调试再来看到确实也可以起到同样的效果

👉 但是呢这还没完，【reserve】接口还是存在问题

💻第二轮测试 — memcpy的拷贝问题

• 下面是我们要进行第二轮测试的代码，内部类型使用的是 string类

void test_vector2()
{
  bit::vector<string> v;
  v.push_back("11111");
  v.push_back("22222");
  v.push_back("33333");
  v.push_back("44444");
  for (auto e : v)
  {
    cout << e << " ";
  }
  cout << endl;
}

• 运行起来看并没有什么问题

• 但是呢当我再去push_back("55555")的时候程序却出现了问题

💬 那此时有的同学脑子转得很快，感觉到一定是【reserve】扩容的地方出现了问题

• 于是经过我们的排查，先定位到了这一句，有同学就觉得是不是因为每次sizeof(T)的对象大小不一样了?

memcpy(tmp, _start, sizeof(T) * size());

我觉得上述这个老铁提出来的问题非常好，我们一起来看看。请读者思考一下下面的结果是多少

void test_vector3()
{
  string s1("11111");
  string s2;
  string s3("222222222222222222");
  cout << sizeof(s1) << endl;
  cout << sizeof(s2) << endl;
  cout << sizeof(s3) << endl;
}

• 如果有阅读过 深入浅出STL之string类 的同学一定可以知道在VS下对于每个string对象的大小都是固定死的，均为 28B，即使是通过不同的构造形式构造出来的对象也是一样的

接下去呢，就带读者好好地通过调试观察一下:computer:

v.push_back("1111111111111111");
v.push_back("2222222222222222");
v.push_back("3333333333333333");
v.push_back("4444444444444444");
v.push_back("5555555555555555");

• 如果对深浅拷贝这一块比较了解的同学一定可以知晓这里很明显地发生了一个 浅拷贝 的问题，所以导致在delete[] _start的时候发生了一个 ==并发修改== 的问题

• 这就导致了我们在释放原本的这块空间时导致拷贝后的这块空间也造成了另一块空间的问题

可能有的读者还是不太理解这其中的原理，我们通过画图再来看看

• 可以看到，在扩容的时候我们去开出了一块新的空间，然后使用memcpy()将数据原封不动地拷贝到了另一块空间中，再去做了一个扩容，那在上面我们也看到过了，就是因为这个memcpy()原封不动拷贝的问题，就使得新空间和旧空间虽然是两块独立的空间，但是呢每个对象中的_str都和另一个对象指向了那一块同样的空间

• 那么在接下去在执行这句代码的时候就会先去调用当前对象的析构函数将每一块空间中的内容先清理掉，然后再去调用delete释放掉整块空间。==因为每两个对象所指向的空间都是同一块的，所以在释放的时候就会造成同时修改的问题==

delete[] _start;

【总结一下】：

vector是深拷贝，但是vector空间上存的对象是string的数组，使用memcpy()导致string对象的浅拷贝

那我们要如何去避免这一种问题呢？

• 很简单，我们去换一下这个拷贝的逻辑就可以了，不要使用memcpy()去进行浅拷贝，而是使用下面这种形式去进行拷贝
• 对于tmp[i] = _start[i]如果对代码比较敏感的同学应该可以很快地看出这会去调用 string类 的赋值重载，然后去做一个深拷贝，此时就不会造成两个_str指向同一块空间了

for (size_t i = 0; i < size(); i++)
{
  tmp[i] = _start[i];
}

• 最后通过调试再来观察一下👀

以下就是【reserve】这个接口的最终完整版实现逻辑

void reserve(size_t n)
{
  if (n > capacity())
  {
    // 先保存一下原先的size()
    size_t sz = size();
    T* tmp = new T[n];    // 开一块新空间
    if (_start)
    {
      //memcpy(tmp, _start, sizeof(T) * size());
      for (size_t i = 0; i < size(); i++)
      {
        tmp[i] = _start[i];
      }
      delete[] _start;
    }
    _start = tmp;
    _finish = _start + sz;
    _end_of_storage = _start + n;
  }
}

接下去的话我们再来看看【resize】这个接口该如何去实现

• 还是一样分为三类来进行讨论：

• 一个是n < _finish的情况；
• 第二个是n > _finish && n <= _end_of_storage的情况；
• 第三个是n >_end_of_storage的情况；

• 对于后两种情况我们可以做一个合并，使用上面【reserve】去做一个容量的检查

• 我们来看一下具体的代码，首先是第一种，直接让_finish = _start + n即可；如果是另一种情况的话，就先使用【reserve】去检查一下是否需要扩容，然后再去通过循环追加对应的数据即可

void resize(size_t n, const T& val = T())
{
  if (n < size())
  {
    _finish = _start + n;
  }
  else
  {
    // 先使用reserve()去检查一下是否需要扩容
    reserve(n);
    while (_finish != _start + n)
    {
      *_finish = val;
      _finish++;
    }
  }
}

• 可能有同学比较好奇这个T()是干嘛的，还记我们在 C++缺省参数 中所讲到的知识点吗。没错，这个T()就是给到的默认缺省参数，因为当前的形参【val】的类型使用的就是模版参数类型，采取自动推导的形式去进行自动识别
• 而T()就是我们在 类和对象小知识 中所学习过的【匿名对象】，切记这里不可以给0，因为当前的数据类型不一定就是 整型，我们就可以根据这个匿名对象去生成不同的默认值

const T& val = T()

简单地来测试一下