四、容量相关的函数

1.size和capacity

size_t size() const
{
  return _finish - _start;//返回的是容器中有效数据的个数
}
size_t capacity() const
{
  return _end_of_storage - _start;//返回的是容器的实际有效容量
}

2.reserve

reserve增容：

1.当 n > capacity 时，将capacity扩大到n；

2.当 n < capacity 时，不进行任何操作；

void reserve(size_t n)
{
  if (n > capacity())//判断是否需要扩容
  {
    //扩容
    size_t sz = size(); //提前算好增容前的数据个数
    T* tmp = new T[n];  //开辟n个空间
    if (_start)
    {
            //数据拷贝，也不能去使用memcpy函数
      for (size_t i = 0; i < sz; i++)
      {
        tmp[i] = _start[i];
      }
      delete[]_start; //释放旧空间
    }
    _start = tmp; //指向新空间
    _finish = _start + sz;
    _end_of_storage = _start + n;
  }
}

对于reserve，我还需要注意两个问题：

1.对增容前的数据个数进行记录

如果不提前算好增容前的数据个数，而是在增容完后更新_start，对于_finish和_end_of_storage都会出现问题，因为增容完后，就需要释放旧空间。

2.增容前后的数据拷贝不能使用memcpy

如果使用memcpy进行数据的拷贝后，随着_start的释放，tmp作为新的_start后，当进行访问操作时，就存在非法访问

3.resize

当n<size时，是缩容，相应的数据会减少，只需要调整一下_finish的位置

当n>size时，我们还需要判断n是否大于capacity，是否增容

在resize函数中的第二个参数val，采用的是缺省（匿名对象），因为我们并不知道T是什么类型，如果是int/int*给val = 0是可以的，但是T还有可能是vector，我们给到匿名对象作为缺省值的好处在于，对于内置类型它也有自己的默认构造函数

例如:
int i = int();  // i = 0
int j = int(10);// j = 10

当我们不给val传任何参数时，它会去调用自己的默认构造函数给val

void resize(size_t n, const T& val = T())
//T()是匿名对象，它的生命周期本来只是存在于当前行，但是被const修饰以后，可以延长它的生命周期
{
  if (n < size())
  {
    _finish = _start + n;
  }
  else
  {
    if (n > capacity())
    {
      reserve(n);
    }
    while (_finish != _start + n)
    {
      *_finish = val;
      ++_finish;
    }
  }
}

五、增删查改相关的函数

1.push_back

尾插数据时，首先需要判断容器是否已满，若满则去调用reserve

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

2.pop_back

在进行尾删时，需要判断容器是否为空，我们这里并没有实现vector的判空操作，可以利用_finish和_start之间的关系进行判断。

void pop_back(const T& x)
{
  assert(_finish > _start);
  --_finish;
}

3.insert

insert是在某个位置插入数据，插入数据就存在是否扩容，如果不需要扩容，插入数据时不会存在然后的问题；如果需要扩容，但未调整pos，会存在pos失效；

iterator insert(iterator pos, const T& x)
{
  assert(pos >= _start);
  assert(pos <= _finish);
  if (_finish == _end_of_storage)
  {
    //扩容会导致pos失效，需要更新一下pos
    size_t len = pos - _start;
    reserve(capacity() == 0 ? 4 : capacity() * 2);
    pos = _start + len;
  }
  iterator end = _finish - 1;
  while (end >= pos)
  {
    *(end + 1) = *end;
    --end;
  }
  *pos = x;
  ++_finish;
  return pos;
}
void test_vector4()
{
  vector<int> v1;
  v1.push_back(1);
  v1.push_back(2);
  v1.push_back(3);
  v1.push_back(4);
  vector<int>::iterator it = find(v1.begin(), v1.end(), 2);
  if (it != v1.end())
  {
    //如果insert中发生了扩容，那么会导致it指向的空间被释放
    //it本质就是一个野指针，这种问题，我们叫做迭代器失效
    v1.insert(it, 30);
  }
  for (auto e : v1)
  {
    cout << e << " ";
  }
  cout << endl;
}

当插入数据需要扩容时，扩容会将旧空间的数据拷贝到新空间，再释放旧空间，此时pos就指向了一块释放的空间，再对pos位置进行访问时，就属于野指针问题，一般我们还需要加上对pos位置的提前调整，防止迭代器失效。

insert的返回值是iterator：虽然在插入数据的过程中调整了pos，解决了内部的迭代器失效问题，但是外部的迭代器（it）还是失效的，我们需要将更新后的迭代器利用返回值的形式返回，防止需要再次使用这个迭代器时发生失效。

4.erase

erase也会存在迭代器失效的问题

iterator erase(iterator pos)
{
  assert(pos >= _start);
  assert(pos < _finish);
  iterator begin = pos + 1;
  while (begin < _finish)
  {
    *(begin - 1) = *begin;
    ++begin;
  }
  --_finish;
  return pos;
}
void test_vector5()
{
  vector<int> v1;
  v1.push_back(1);
  v1.push_back(2);
  v1.push_back(3);
  v1.push_back(4);
  v1.push_back(5);
  //要求删除v1中所有的偶数
  //         g++下     vs下
  // 1 2 3 4 5 --> 正常    断言报错 vector的迭代器的失效主要是在insert和erase中
  // 1 2 3 4   --> 崩溃    断言报错
  // 1 2 4 5   --> 结果不对  断言报错
    //测试库中的erase --- 存在失效
  vector<int> v2;
  v2.push_back(1);
  v2.push_back(2);
  v2.push_back(3);
  v2.push_back(4);
  v2.push_back(5);
  std::vector<int>::iterator it = v2.begin();
  while (it != v2.end())
  {
    if (*it % 2 == 0)
    { 
      v2.erase(it);
    }
    ++it;
  }
   /*************************************************/
  vector<int>::iterator it = v1.begin();
  while (it != v1.end())
  {
    if (*it % 2 == 0)
    {
      it = v1.erase(it);//每次跟新一下迭代器，不会存在失效了
    }
    else
    {
      ++it;
    }
  }
  for (auto e : v1)
  {
    cout << e << " ";
  }
  cout << endl;
}

5.swap

void swap(vector<T>& v)
{
  std::swap(_start, v._start);
  std::swap(_finish, v._finish);
  std::swap(_end_of_storage, v._end_of_storage);
}

六、完成代码

#pragma once
namespace vec
{
  template<class T>
  class vector
  {
    //typedef T* iterator;//typedef也受访问限定符的限制，放在这里默认是私有的
  public:
    typedef T* iterator;
    typedef const T* const_iterator;
    iterator begin()
    {
      return _start;
    }
    iterator end()
    {
      return _finish;
    }
    const_iterator begin() const
    {
      return _start;
    }
    const_iterator end() const
    {
      return _finish;
    }
    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()
      :_start(nullptr)
      , _finish(nullptr)
      , _end_of_storage(nullptr)
    {}
    //v2(v1)
    //传统写法
    /*
        vector(const vector<T>& v)
    {
      _start = new T[v.capacity()];
      _finish = _start + v.size();
      _end_of_storage = _start + v.capacity();
      memcpy(_start, v._start, v.size() * sizeof(T));//存在浅拷贝
    }
    vector(const vector<T>& v)
    {
      _start = new T[v.capacity()]; //让v2开辟一块和v一样大小的空间
      for (size_t i = 0; i < v.size(); i++)
      {
        _start[i] = v[i];//通过循环进行赋值
      }
      //最后调整_finish和_end_of_storage的大小
      _finish = _start + v.size();
      _end_of_storage = _start + v.capacity();
    }
        */
    //v2(v1)
    //现代写法
    //一个类模板的成员函数，又可以是一个函数模板
    template <class InputIterator>
    vector(InputIterator first, InputIterator last)
      :_start(nullptr)
      , _finish(nullptr)
      , _end_of_storage(nullptr)
    {
      while (first != last)
      {
        push_back(*first);
        ++first;
      }
    }
    vector(const vector<T>& v)//也支持vector(const vector& v)
      :_start(nullptr)
      , _finish(nullptr)
      , _end_of_storage(nullptr)
    {
      vector<T> tmp(v.begin(), v.end());
      swap(tmp);
      //this->swap(tmp);
    }
    //v1 = v2
    //vector<T>& operator=(const vector<T>& v) //传统写法
    //vector& operator=(vector v)语法上也支持这样写
    vector<T>& operator=(vector<T> v)//推荐写
    {
      swap(v);
      return *this;
    }
    ~vector()
    {
      if (_start)
      {
        delete[] _start;
        _start = _finish = _end_of_storage = nullptr;
      }
    }
    const T& operator[](size_t i) const
    {
      assert(i < size());
      return _start[i];
    }
    T& operator[](size_t i)
    {
      assert(i < size());
      return _start[i];
    }
    size_t size() const
    {
      return _finish - _start;
    }
    size_t capacity() const
    {
      return _end_of_storage - _start;
    }
    void reserve(size_t n)
    {
      if (n > capacity())
      {
        //扩容
        size_t sz = size();
        T* tmp = new T[n];
        if (_start)
        {
          //memcpy(tmp, _start, sizeof(T) * size());存在浅拷贝
          for (size_t i = 0; i < sz; i++)
          {
            //T是int，一个一个拷贝没问题
            //T是自定义类型，一个个拷贝调用的是深拷贝赋值，也没问题
            tmp[i] = _start[i];
          }
          delete[]_start;
        }
        _start = tmp;
        _finish = _start + sz;
        _end_of_storage = _start + n;
      }
    }
    void resize(size_t n, const T& val = T())
        //T()是匿名对象，它的生命周期本来只是存在于当前行，但是被const修饰以后，可以延长它的生命周期
    {
      if (n < size())
      {
        _finish = _start + n;
      }
      else
      {
        if (n > capacity())
        {
          reserve(n);
        }
        while (_finish != _start + n)
        {
          *_finish = val;
          ++_finish;
        }
      }
    }
    iterator insert(iterator pos, const T& x)
    {
      assert(pos >= _start);
      assert(pos <= _finish);
      if (_finish == _end_of_storage)
      {
        //扩容会导致pos失效，需要更新一下pos
        size_t len = pos - _start;
        reserve(capacity() == 0 ? 4 : capacity() * 2);
        pos = _start + len;
      }
      iterator end = _finish - 1;
      while (end >= pos)
      {
        *(end + 1) = *end;
        --end;
      }
      *pos = x;
      ++_finish;
      return pos;
    }
    iterator erase(iterator pos)
    {
      assert(pos >= _start);
      assert(pos < _finish);
      iterator begin = pos + 1;
      while (begin < _finish)
      {
        *(begin - 1) = *begin;
        ++begin;
      }
      --_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(const T& x)
    {
      assert(_finish > _start);
      --_finish;
    }
  private:
    iterator _start;
    iterator _finish;
    iterator _end_of_storage;
  };
}

【C++】STL——vector模拟实现（2）