vector的模拟实现-阿里云开发者社区

一、vector类

1、 vector是表示可变大小数组的序列容器。

2、就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。

3、本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。

4、 vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。

上面的图片来自于《STL源码剖析》这本书。从图中我们就可以看出vector实现的基本形式。vector类的成员变量是三个指针。指向起始位置的 _start ，指向最后一个数据的下一个位置的_finish，指向容量的下一个位置的_end_of_storage。

下面的代码就是vector类实现的基本框架

template<class T>
class vector
{
    typedef T* iterator;
  typedef const T* const_iterator;
private:
//三者均为指针
    iterator _start;
  iterator _finish;//最后一个数据的下一个位置
  iterator _end_of_storage;//容量的下一个位置
};

二、构造函数及析构函数

1、构造函数

将三个指针全都置成空。

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

2、析构函数

delete掉 _start的空间，将三者置成nullptr。

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

三、vector的迭代器

vector的迭代器是一个指针。并分为 iterator 和 const_iterator两种类型，非const 对象调用前者，const对象调用后者。

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;
}

四、vector空间增长问题

1、size

获取数据个数

size_t size()const
{
  return _finish - _start;
}

2、capacity

获取容量大小

size_t capacity()const
{
  return _end_of_storage - _start;
}

3、empty

判断是否为空

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

4、resize

void resize(size_t n, const T& val = T())
{
  if (n > capacity())
  {
    reserve(n);
  }
  if (n > size())
  {
    while (_finish < _start + n)
    {
      *_finish = val;
      _finish++;
    }
  }
  else
  {
    _finish = _start + n;
    }
}

5、reserve

void reserve(size_t n)
{
  size_t sz = size();
  if (n > capacity())
  {
    T* tmp = new T[n];
    if (_start)
    {
          //memcpy(tmp, _start, sizeof(T) * sz);
          //如果是vector<vector<int>>类型，那么在拷贝
          //vector中的vector<int>的数据类型时使用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;
  }
}

五、vector的增删查改

1、push_back

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

2、pop_back

void pop_back()
{
  assert(_finish > _start);
  _finish--;
}

六、其他构造函数

1、拷贝构造函数

//拷贝构造函数 v2(v1)
vector(const vector<T>& v)
{
  _start = new T[v.size()];
  memcpy(_start, v._start, sizeof(T) * v.size());
  _finish = _start + v.size();
  _end_of_storage = _start + v.size();
}

vector(const vector<T>& v)
  :_start(nullptr)
  , _finish(nullptr)
  , _end_of_storage(nullptr)
{
  reserve(v.size());
  for (const auto& e : v)
  {
    push_back(e);
  }
}

注：上面的第一种写法其实还有一点bug。举个例子：如果vector里的数据类型是 vector<int>，那么在这memcpy就是一个浅拷贝，虽然vector<vector<int>>有自己的空间，但是里面的数据vector<int>却没有自己的空间，memcpy后，两个对象的vector<int>会指向同一块空间。因此有下面的改进方案

vector(const vector<T>& v)
{
  _start = new T[v.size()];
  for (size_t i = 0; i < v.size(); i++)
  {
    _start[i] = v._start[i];
  }
  _finish = _start + v.size();
  _end_of_storage = _start + v.size();
}

2、构造并初始化

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);
  }
}

3、迭代器进行初始化构造

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

有了迭代器的区间构造，我们就可以写出拷贝构造函数的现代写法

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(const vector<T>& v)
  :_start(nullptr)
  , _finish(nullptr)
  , _end_of_storage(nullptr)
{
  vector<T> tmp(v.begin(), v.end());
  swap(tmp);
}

七、运算符重载

1、下标访问 [ ]

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

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

2、赋值构造

//v1 = v2
vector<T>& operator=(vector<T> v)
{
  swap(v);
  return *this;
}

八、迭代器失效问题（重难点）

1、insert

void insert(iterator pos, const T& x)//返回新插入位置的迭代器 pos
{
  assert(pos >= _start);
  assert(pos <= _finish);
  //满了就扩容:扩容后pos的原位置失效，需要更新pos的位置，
  if (_finish == _end_of_storage)
  {
    reserve(capacity() == 0 ? 4 : capacity() * 2);
  }
  iterator end = _finish - 1;
  while (pos <= end)
  {
    *(end + 1) = *end;
    end--;
  }
  *pos = x;
  _finish++;
}

从上面的图中我们可以看出程序出现了错误，这是为什么呢？这是因为我们在第一次扩容时开辟了4个数据的空间，然后插入了4个数据。这时如果我们再插入数据，那么就会发生扩容，也就是会重新开辟空间，而重新开辟空间后pos的位置就没有指向新空间的pos的位置了，pos成为了一个野指针。因此迭代器就失效了。为了解决这个问题，我们就需要重新找到pos的位置，并返回这个位置。

iterator insert(iterator pos, const T& x)//返回新插入位置的迭代器 pos
{
  assert(pos >= _start);
  assert(pos <= _finish);
  //满了就扩容:扩容后pos的原位置失效，需要更新pos的位置，
  if (_finish == _end_of_storage)
  {
    size_t len = pos - _start;
    reserve(capacity() == 0 ? 4 : capacity() * 2);
    pos = _start + len;
  }
  iterator end = _finish - 1;
  while (pos <= end)
  {
    *(end + 1) = *end;
    end--;
  }
  *pos = x;
  _finish++;
  return pos;
}

2、erase

void erase(iterator pos)
{
  assert(pos >= _start);
  assert(pos < _finish);
  iterator begin = pos + 1;
  while (begin < _finish)
  {
    *(begin - 1) = *begin;
    begin++;
  }
  _finish--;
}

erase也有失效的情况。

void test()
{
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    //删除所有偶数
    auto it = v.begin();
    while(it != v.end())
    {
        if(*it % 2 == 0)
        {
            v.erase(*it);
        }
        it++;
    }
    for(auto e : v)
    {
        cout << e << " ";
    }
}

push_back下面的数及对应结果。

1 2 3 4 5 正常运行

1 2 3 4 崩溃

1 2 4 3 4 5 结果不对

为什么会这样呢？看下图

第二种情况是it和end()已经错过了，且it已经越界了，永远不会相等了。

所以正确的代码如下：

//指向擦除的最后一个元素之后的元素的新位置。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 test()
{
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    //删除所有偶数
    auto it = v.begin();
    while(it != v.end())
    {
        if(*it % 2 == 0)
        {
            it = v.erase(*it);
        }
        else
        {
            it++;
        }
    }
    for(auto e : v)
    {
        cout << e << " ";
    }
}

九、总代码

using namespace std;
namespace zdl
{
  template<class T>
  class vector
  {
  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;
    }
    vector()
      :_start(nullptr)
      , _finish(nullptr)
      , _end_of_storage(nullptr)
    {}
    //拷贝构造函数 v2(v1)
    vector(const vector<T>& v)
    {
      _start = new T[v.size()];
      //memcpy(_start, v._start, sizeof(T) * v.size());
      /*如果是vector<vector<int>>类型，那么在拷贝
        vector中的vector<int>的数据类型时使用memcpy是浅拷贝
      会被析构两次*/
      for (size_t i = 0; i < v.size(); i++)
      {
        _start[i] = v._start[i];
      }
      _finish = _start + v.size();
      _end_of_storage = _start + v.size();
    }
    /*vector(const vector<T>& v)
      :_start(nullptr)
      , _finish(nullptr)
      , _end_of_storage(nullptr)
    {
      reserve(v.size());
      for (const auto& e : v)
      {
        push_back(e);
      }
    }*/
    //现代写法
    /*vector(const vector<T>& v)
      :_start(nullptr)
      , _finish(nullptr)
      , _end_of_storage(nullptr)
    {
      vector<T> tmp(v.begin(), v.end());
      swap(tmp);
    }*/
    //eg : 10个1构造
    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);
      }
    }
    //迭代器区间构造
    template<class InputIterator>
    vector(InputIterator first, InputIterator last)
      :_start(nullptr)
      , _finish(nullptr)
      , _end_of_storage(nullptr)
    {
      while (first != last)
      {
        push_back(*first);
        first++;
      }
    }
    void swap(vector<T> v)
    {
      std::swap(_start, v._start);
      std::swap(_finish, v._finish);
      std::swap(_end_of_storage, v._end_of_storage);
    }
    //v1 = v2
    vector<T>& operator=(vector<T> v)
    {
      swap(v);
      return *this;
    }
    ~vector()
    {
      delete[] _start;
      _start = _finish = _end_of_storage = nullptr;
    }
    size_t size()const
    {
      return _finish - _start;
    }
    size_t capacity()const
    {
      return _end_of_storage - _start;
    }
    void reserve(size_t n)
    {
      size_t sz = size();
      if (n > capacity())
      {
        T* tmp = new T[n];
        if (_start)
        {
          //memcpy(tmp, _start, sizeof(T) * sz);
          //如果是vector<vector<int>>类型，那么在拷贝
          //vector中的vector<int>的数据类型时使用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;
      }
    }
    void push_back(const T& x)
    {
      if (_finish == _end_of_storage)
      {
        reserve(capacity() == 0 ? 4 : capacity() * 2);
      }
      *_finish = x;
      _finish++;
    }
    void pop_back()
    {
      assert(_finish > _start);
      _finish--;
    }
    iterator insert(iterator pos, const T& x)//返回新插入位置的迭代器 pos
    {
      assert(pos >= _start);
      assert(pos <= _finish);
      //满了就扩容:扩容后pos的原位置失效，需要更新pos的位置，
      if (_finish == _end_of_storage)
      {
        size_t len = pos - _start;
        reserve(capacity() == 0 ? 4 : capacity() * 2);
        pos = _start + len;
      }
      iterator end = _finish - 1;
      while (pos <= end)
      {
        *(end + 1) = *end;
        end--;
      }
      *pos = x;
      _finish++;
      return pos;
    }
    //指向擦除的最后一个元素之后的元素的新位置。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;
    }
    T& operator[](size_t pos)
    {
      assert(pos < size());
      return _start[pos];
    }
    const T& operator[](size_t pos)const
    {
      assert(pos < size());
      return _start[pos];
    }
    void resize(size_t n, const T& val = T())
    {
      if (n > capacity())
      {
        reserve(n);
      }
      if (n > size())
      {
        while (_finish < _start + n)
        {
          *_finish = val;
          _finish++;
        }
      }
      else
      {
        _finish = _start + n;
      }
    }
  private:
    //三者均为指针
    iterator _start;
    iterator _finish;//最后一个数据的下一个位置
    iterator _end_of_storage;//容量的下一个位置
  };
}

vector的模拟实现