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的模拟实现

一、vector类

二、构造函数及析构函数

1、构造函数

2、析构函数

三、vector的迭代器

四、vector空间增长问题

1、size

2、capacity

3、empty

4、resize

5、reserve

五、vector的增删查改

1、push_back

2、pop_back

六、其他构造函数

1、拷贝构造函数

2、构造并初始化

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

七、运算符重载

1、下标访问 [ ]

2、赋值构造

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

1、insert

2、erase

九、总代码

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

vector的模拟实现

一、vector类

二、构造函数及析构函数

1、构造函数

2、析构函数

三、vector的迭代器

四、vector空间增长问题

1、size

2、capacity

3、empty

4、resize

5、reserve

五、vector的增删查改

1、push_back

2、pop_back

六、其他构造函数

1、拷贝构造函数

2、构造并初始化

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

七、运算符重载

1、下标访问 [ ]

2、赋值构造

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

1、insert

2、erase

九、总代码

热门文章

最新文章

相关电子书