0000000000000000000000000000000000000000000000000000000.png

文章导读

本章我们将参照STL源码来模拟实现vector，这要求我们具备数据结构的基础且了解vector的基本使用。模式实现vector，将锻炼我们的代码能力，加深对类和对象的认识，同时能使我们对vector的使用更加游刃有余。

正文

定义vector类

为了区别于标准库中的vector，我们可以使用自己的命名空间，在自己的命名空间中模拟实现vector。我们已经了解过库中vector的基本使用，知道vector是一个可以存储任何类型的容器，为了实现各种类型都可以匹配，我们可以利用模板来实现。

STL源码中，vector包含三个基本成员：

iterator _start：指向首元素的迭代器；
iterator _finish：指向尾元素下一位的迭代器；
iterator _end_of_storage：指向最大容量的下一位的迭代器；

我们可以把迭代器理解为像指针一样的东西。

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

各成员函数的实现

构造函数

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

迭代器

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

size与capacity——求大小与容量

  size_t size() const
  {
    return _finish - _start; //指针相减即为个数
  }
  size_t capacity() const
  {
    return _end_of_storage - _start;
  }

reserve——扩容

  void reserve(size_t n)
  {
    if (n > capacity())
    {
      size_t sz = size();
      //使用中间变量，防止new失败
      iterator tmp = new T[n];
      if (_start)
      {
        //转移数据
        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中的深浅拷贝问题

在reserve的实现中，我们不能使用memcpy来拷贝数据，否则会发生浅拷贝的问题，导致在析构报错。对于简单的内置类型或自定义类型，memcpy是一个不错的选择，既高效又实用。但是一旦元素涉及到资源申请，memcpy只是简单的将一个元素的值拷贝给另一个元素，并不会将该元素指向的空间的内容全部拷贝给另一个元素。所以，我们必须手动实现深拷贝。

🍁错误示例

  void reserve(size_t n)
  {
    if (n > capacity())
    {
      size_t sz = size();
      //使用中间变量，防止new失败
      iterator tmp = new T[n];
      if (_start)
      {
        //浅拷贝
        memcpy(tmp, _start, sizeof(T)*size());
        delete[] _start;
      }
      //指向新空间
      _start = tmp;
      _finish = _start + sz;
      _end_of_storage = _start + n;
    }
  }

resize——扩容并初始化

  void resize(size_t n, T val = T())
  {
    //n<size()，删除数据
    if (n < size())
    {
      _finish = _start + n;
    }
    else
    {
      if (n > capacity)
        reserve(n); //扩容
      while (_finish != _start + n)
      {
        //初始化
        *_finish = val;
        ++_finish;
      }
    }
  }

push_back——尾插

  void push_back(const T& val)
  {
    //扩容
    if (_finish == _end_of_storage)
    {
      reserve(capacity() == 0 ? 4 : capacity() * 2);
    }
    //插入元素
    *_finish = val;
    ++_finish;
  }

pop_back——尾删

  void pop_back()
  {
    assert(!empty());
    --_finish;
  }

insert——插入

  iterator insert(iterator pos,T val=T()) //使用匿名构造
  {
    assert(pos >= _start);
    assert(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;
  }

erase——删除

  iterator erase(iterator pos)
  {
    assert(pos >= _start);
    assert(pos < _finish);
    //挪动数据
    iterator end = pos + 1;
    while (end != _finish)
    {
      *(end - 1) = *end;
      ++end;
    }
    --_finish;
    return pos;
  }

empty——判空

  bool empty()
  {
    return size() == 0;
  }

[]重载——访问元素

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

传值构造

  vector<int> v1(10, 5); //用10个5来构造

  vector(size_t n, const T& val = T())
    :_start(nullptr),
    _finish(nullptr),
    _end_of_storage(nullptr)
  {
    //扩容
    reserve(n);
    //尾插
    for (size_t i = 0; i < n; i++)
    {
      push_back(val);
    }
  }
  //重载版本，防止调用时与迭代器区间构造混淆
  vector(int n, const T& val = T())
    :_start(nullptr),
    _finish(nullptr),
    _end_of_storage(nullptr)
  {
    reserve(n);
    for (size_t i = 0; i < n; i++)
    {
      push_back(val);
    }
  }

迭代器区间构造

  vector<int> v1(10, 5); 
  vector<string> v2(v1.begin(), v1.end()); //迭代器区间构造

  template<class InputIterator>
  vector(InputIterator begin, InputIterator end)
  {
    //扩容
    reserve(end - begin);
    while (begin != end)
    {
      push_back(*begin);
      ++begin;
    }
  }

赋值重载

  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)
  {
    //写法1
    //_start = new T[v.capacity()];
    //for (size_t i = 0; i < v.size(); i++)
    //{
    //  _start[i] = v._start[i];
    //}
    //_finish = _start + v.size();
    //_end_of_storage = _start + v.capacity();
    //写法2
    vector<T> tmp(v.begin(), v.end());
    swap(tmp);
  }

拷贝构造中的深浅拷贝问题

在写法1中，如果使用memcpy，同样会发生浅拷贝的问题。