1 类的成员变量

namespace grm
{
  template<class T>
  class vector
  {
  public:
    typedef T* iterator;
    typedef const T* const_iterator;
    private:
    iterator _start;
    iterator _finish;
    iterator _endofstorage;
  };
}

这里面与之前我们实现的顺序表有所不同的是里面的成员变量全是指针，_start是开始数据的地址，_finish是有效数据下一位的地址，_endofstorage是数据最大容量的下一位地址。

2 常用成员函数和迭代器

        size_t size()const
    {
      return _finish - _start;
    }
    size_t capacity()const
    {
      return _endofstorage - _start;
    }
    iterator begin()
    {
      return _start;
    }
    iterator end()
    {
      return _finish;
    }
    const_iterator begin()const
    {
      return _start;
    }
    const_iterator end()const
    {
      return _finish;
    }
    const T& operator[](size_t i)
    {
      return _finish[i];
    }
    T& operator[](size_t i)const
    {
      return _finish[i];
    }

这些都很简单，就不在多说了。

3 增删查改

3.1 reverse

大家看看下面这种写法有没有问题？

        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();
        _endofstorage = _start + n;
      }
    }

大家回顾一下size()我们是用_finish - _start实现的，这样的话使用size()的时候_finish还没有更新，而_start已经被更新了，那不就g了吗，正确的处理方式有两种，一种是先更新_start,另外一种是先保存size()。

方法1：

        void reserve(size_t n)
    {
      if (n > capacity())
      {
        T* tmp = new T[n];
        if (_start)
        {
          memcpy(tmp, _start, sizeof(T) * size());
          delete[] _start;
        }
        //写法1：
        _finish = tmp + size();
        _start = tmp;
        _endofstorage = _start + n;
      }
    }

写法2：

        void reserve(size_t n)
    {
      if (n > capacity())
      {
        T* tmp = new T[n];
        size_t sz = size();//先保存size()
        if (_start)
        {
          memcpy(tmp, _start, sizeof(T) * sz);
          delete[] _start;
        }
        //写法2：
        _start = tmp;
        _finish = tmp + sz;
        _endofstorage = _start + n;
      }
    }

这样无论先更新还是后更新都可。

大家仔细看看上面这种写法还有没有问题？

顺便问一句，这里能够用memcpy吗？

如果T是内置类型的话那还好没啥问题，那如果T是一个自定义类型就会出大问题，因为memcpy进行的是浅拷贝，那析构的话就又会将同一块空间析构两次而出错。

正确的做法是一个一个赋值拷贝：

        void reserve(size_t n)
    {
      if (n > capacity())
      {
        T* tmp = new T[n];
        size_t sz = size();
        if (_start)
        {
          //memcpy(tmp, _start, sizeof(T) * sz);//浅拷贝，如果是自定义类型就会发生重复析构
          for (int i = 0; i < sz; i++)
          {
            tmp[i] = _start[i];
          }
          delete[] _start;
        }
        //错误写法
        /*_start = tmp;
        _finish = _start + size();//使用size()时_finish还没有更新
        _endofstorage = _start + n;*/
        //写法1：
        _finish = tmp + size();
        _start = tmp;
        _endofstorage = _start + n;
        //写法2：
        /*_start = tmp;
        _finish = tmp + sz;
        _endofstorage = _start + n;*/
      }
    }

结论：如果对象中涉及到资源管理时，千万不能使用 memcpy 进行对象之间的拷贝，因为 memcpy 是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃。

3.2 push_back

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

3.3 resize

        void resize(size_t n, const T& x = T())//用T类型创造出来的匿名对象
    {
      if (n > capacity())
      {
        reserve(n);
      }
      while (_finish != _endofstorage)
      {
        *_finish = x;
        _finish++;
      }
    }

3.4 insert && erase

        //iterator insert(iterator& pos, const T& val)
    iterator insert(iterator pos, const T& val)
    {
      assert(pos >= _start);
      assert(pos <= _finish);
      if (_finish >= _endofstorage)
      {
        //扩容了要更新pos
        size_t gap = pos - _start;
        reserve(capacity() == 0 ? 4 : capacity() * 2);
        pos = _start + gap;
      }
      iterator end = _finish ;
      while (pos < end)
      {
        *end = *(end - 1);
        --end;
      }
      *pos = val;
      ++_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;
    }

大家想想为啥扩容了要更新pos？假如不更新pos，当扩容了后pos的值肯定会发生改变，那么我们就不能够使用原先的pos来访问数据了，否则就非法越界了。这也是迭代器失效的问题。大家想想string会迭代器失效吗？答案也是会的，不过由于string我们常用的是下标访问所以一般来说不会失效。

插入可以用返回值接受，为啥不用引用呢？

有些场景下可能不适用：

        //有些场景下不适用，像下面这里：
    v.insert(v.begin(), -1);//这里v.begin()是用一个具有常属性的临时变量保存的，不能够修改，与形参类型矛盾了。
    for (auto e : v)
    {
      cout << e << " ";
    }

大家再思考一下下面这段程序：

    void test5()
  {
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(2);
    v.push_back(5);
    //删除所有为2的数字
    vector<int>::iterator it = find(v.begin(), v.end(), 2);
    while (it != v.end())
    {
      //vector<int>::iterator ret = find(it, v.end(), 2);
      auto ret = find(it, v.end(), 2);
      if (ret != v.end())
      {
        it =ret;
        v.erase(it);
      }
      ++it;
    }
    for (auto& e : v)    cout << e << " ";
    }

这种使用方法肯定是错误的，因为it在不断的往下面走可能会失效，正确应该修改为：

            if (ret != v.end())
      {
        it =ret;
        v.erase(it);
      }
      else
      {
        ++it;
      }

4 默认成员函数

4.1 构造函数

           vector()
      :_start(nullptr)
      , _finish(nullptr)
      , _endofstorage(nullptr)
    {}

4.2 拷贝构造

传统写法：

        vector(const vector<T>& v)
    {
      _start = new T[v.capacity()];
      memcpy(_start, v._start, sizeof(T) * v.size());
      _finish = _start + v.size();
      _endofstorage = _start + v.capacity();
    }

这里也是一样，正确的做法是一个一个赋值拷贝：

//传统写法
    vector(const vector<T>& v)
    {
      _start = new T[v.capacity()];
      //memcpy(_start, v._start, sizeof(T) * v.size());//这里也是浅拷贝
      for (int i = 0; i < v.size(); i++)
        _start[i] = v._start[i];
      _finish = _start + v.size();
      _endofstorage = _start + v.capacity();
    }

我们知道现代写法就是不用我们自己造轮子，通过构造函数来帮助我们实现，但是我们又发现是无法用我们刚才实现的构造函数来完成tmp对象的创建的，所以我们又得重新再写一个构造函数：

        template <class InputIterator>
    vector(InputIterator first, InputIterator last)
      : _start(nullptr)
      , _finish(nullptr)
      , _endofstorage(nullptr)
    {
      while (first != last)
      {
        push_back(*first);
        first++;
      }
    }

这里的InputIterator取名C++是有默认规定的，迭代器分类：

input_iterator(只写） output_iterator(只读)

没有实际对应的类型

forward_iterator(单向)

<forward_list> <unordered_map> <unordered_set>

bidirectional_iterator(双向)

randomaccess_iterator(随机)

有了这个构造函数后就能够用现代写法了：

        //现代写法
    //void swap(vector& v)//可以这么写，但不推荐，可读性不高
    void swap(vector<T>& v)
    {
      std::swap(_start, v._start);
      std::swap(_finish, v._finish);
      std::swap(_endofstorage, v._endofstorage);
    }
    vector(const vector<T>& v)
      : _start(nullptr)
      , _finish(nullptr)
      , _endofstorage(nullptr)
    {
      vector<T> tmp(v.begin(),v.end());
      swap(tmp);
    }

4.3 赋值运算符重载

传统写法：

        //传统写法
    vector<T>& operator=(const vector<T>& v)
    {
      if (this != &v)
      {
        T* tmp = new T[v.capacity()];
        //memcpy(tmp, v._start, sizeof(T) * v.size());浅拷贝
        for (int i = 0; i < v.size(); i++)
          tmp[i] = v._start[i];
        delete[] _start;
        _start = tmp;
        _finish = _start + v.size();
        _endofstorage = _start + v.capacity();
      }
      return *this;
    }

现代写法：

        //现代写法1：
    vector<T>& operator=(const vector<T>& v)
    {
      vector<T> tmp(v);
      swap(tmp);
      return *this;
    }
    //现代写法2：
    vector<T>& operator=(vector<T> v)
    {
      swap(v);
      return *this;
    }

这里与之前string的类似。

4.4 析构函数

        ~vector()
    {
      delete[] _start;
      _start = _finish = _endofstorage = nullptr;
    }

有需要的老铁可以在博主的码云中获取源码：

https://gitee.com/monday-sky/text_cpp/commit/6521a7399bdf5ebccf028e5fa130cccbd57d4dcc

【vector的模拟实现】