【C++】STL之vector类模拟-2

3）元素访问

• 对于元素访问的话我们最常用的就是下标 + []的形式，这里给出两种，一个是const版本和非const版本

T& operator[](size_t pos)
{
  assert(pos < size());
  return _start[pos];
}
T& operator[](size_t pos) const
{
  assert(pos < size());
  return _start[pos];
}

4）修改操作

接下去的话我们来讲讲有关修改操作的一些接口

• 首先第一个的话就是push_back，这个我在上面讲【reserve】的时候给出过，现在仔细地再来讲一讲：首先的话我们要考虑的就是扩容的逻辑，上面我们有讲到在VS下是呈现 1.5倍 的增长趋势，但是在g++下呈现的则是 2倍 的扩容逻辑，这里的扩容的话我们就交给【reserve】来实现

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

然后的话我们来实现一下【insert】这个接口

void insert(iterator pos, const T& x)

这一块的话我们已经讲过很多遍了，要在某一个位置插入数据的话就需要先去挪动部分的数据，这里我们从后往前挪，防止造成覆盖的情况，当数据挪动完毕后，再在pos这个位置插入指定的数据即可

• 在一进入函数的时候大家可以去做一个断言的操作，不过很多同学可能会好奇这边的pos >= _start，为什么可以位于首部

assert(pos >= _start && pos <= _finish);

💬 在讲解 string类 的时候我们确实讲到了这种写法的缺陷，但是读者要看清楚了，这里pos的类型是 iterator，为一个迭代器。而我们在 string类  中所讲到的这个pos呢是一个无符号整数

• 位于首部的迭代器pos不可能是0，因为它是一段空间的地址，有效空间的地址不可能是0，

string& insert (size_t pos, const string& str);

• 不过呢，既然是插入数据的话就一定会存在容量不足的情况，此时就需要一个扩容逻辑，这里我们直接用上面在push_back()接口中所写的即可

// 1.首先考虑扩容逻辑
if (_finish == _end_of_storage)
{
  size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
  reserve(newCapacity);
}

以下是整体的代码

void insert(iterator pos, const T& x)
{
  assert(pos >= _start && pos <= _finish);
  // 1.首先考虑扩容逻辑
  if (_finish == _end_of_storage)
  {
    size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
    reserve(newCapacity);
  }
  // 2.挪动数据
  iterator end = _finish - 1;
  while (end >= pos)
  {
    *(end + 1) = *end;
    --end;
  }
  *pos = x;
  ++_finish;
}

• 那么对于push_back()这个接口我们就可以去复用一下【insert】这个接口了

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

💻第三轮测试 — 迭代器失效问题

• 好，在写完【insert】接口后，我们再来做一个测试。可以发现程序崩溃了

马上，我们通过调试来观察一下

• 此时我们已经往【v】中插入了4个数据，马上使用insert(v.begin(), 100)去做一个头插，那么一进到函数中我们就可以知道这个当前对象的_start和pos所处的迭代器位置是相同的，也就是同一段空间的地址

• 那此时我们知道容器中的空间已经满了，所以会去走一个扩容的逻辑，此时可以看到当前对象this的_start已经发生了改变

• 可以看到，在扩完容之后，当前对象的_start和待插入位置的pos已经发生了变化，那么在此时我们再去挪动数据进行插入的时候就会出现问题了

💬 我们可以通过下面的图示来看看到底这个扩完容之后是怎样的

• 可以看到_start确实发生了一个变化，但是呢pos还是指向原来的那个地方。那读者可以自己去想象一下子在遍历挪动数据的时候究竟何时才是个头呢？

• 我们可以通过调试再来观察一下挪动数据这段逻辑，可以看到在挪动完几次数据后就出现了随机值，并且出现了死循环的问题

https://p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/9faf5f27479747aba8c13e6efd75a752~tplv-k3u1fbpfcp-jj-mark:3024:0:0:0:q75.awebp#?w=1434&h=386&s=443201&e=gif&f=285&b=cfe9d5🔰 ==以上所出现的这个问题就被称作是 【迭代器失效的问题】==

那我们要如何去解决呢？

💬 有同学说，内部外部无法一起修改的话参数部分加个引用不就行了

void insert(iterator& pos, const T& x)

• 这其实是不对的，因为有些时候我们所传递的迭代器位置是v.begin() + 3，在这中间会去产生一个临时对象，我们知道临时对象是具有常性的，那么传递进去的时候就会造成【权限放大】的问题

v.insert(v.begin() + 3, 6);

💬 那有同学又说，那防止一下权限放大不就好了，加个const

• 这肯定是不可以的，看到程序依旧会出现问题

• 首先大家要明白的一个点是出错的根本原因在于：_start的位置改变了但是pos的位置没有发生改变。
• 所以我们所要做的一个点就是：让pos的位置随着_start的变动而一起变动，这样就不会出现问题了。以下我们需要改进的代码部分，在进行扩容之前，我们可以先去计算一下从【_start】到【pos】的位置有多远；
• 然后呢我们在执行完扩容的逻辑之后，就要去更新一下这个【pos】迭代器的位置所在，就使用刚才计算出来的这段距离即可

// 1.首先考虑扩容逻辑
if (_finish == _end_of_storage)
{
  // 首先保存一下从_start到pos的距离
  size_t len = pos - _start;
  size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
  reserve(newCapacity);
  // 再扩完容之后更新一下pos, 解决迭代器失效问题
  pos = _start + len;
}

那代码做了更新之后迭代器失效的问题真的解决了呢，我们通过调试一起来看看

• 可以看到，通过我们的骚操作😛【pos】位置就随着【start】的变化而随着变化

• 但是呢就上面这样还不够，我们只解决了内部迭代器失效的问题，而外部迭代器失效的问题并没有很好地解决。
• 外部迭代器，那是什么东西？ 我们来看下这段代码

bit::vector<int>::iterator it = v.begin();
v.insert(it, 33);
bit::print(v);
cout << *it << endl;
bit::print(v);

可以看到，在使用完这个这个迭代器之后再去访问就出现了问题

如果直接其换成库里面的【vector】的话，就直接崩溃了

👉 所以，对于迭代器这一块我们在使用的时候一定要慎重，在使用完之后不要去轻易地修改它

it = v.insert(it, 33);

• 如何执意要进行修改的话也不是没有办法，我们只需要在【insert】之后去接受一下当前所操作的这个迭代器的位置即可，记住这个位置，下次在访问的时候也就不会出问题

具体代码如下：

iterator insert(iterator pos, const T& x)
{
  assert(pos >= _start && pos <= _finish);
  // 1.首先考虑扩容逻辑
  if (_finish == _end_of_storage)
  {
    // 首先保存一下从_start到pos的距离
    size_t len = pos - _start;
    size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
    reserve(newCapacity);
    // 再扩完容之后更新一下pos, 解决迭代器失效问题
    pos = _start + len;
  }
  // 2.挪动数据
  iterator end = _finish - 1;
  while (end >= pos)
  {
    *(end + 1) = *end;
    --end;
  }
  *pos = x;
  ++_finish;
  return pos;
}