C++番外篇——vector的实现-阿里云开发者社区

1.vector的底层

我们在之前的文章顺序表的实现中了解到：

其底层存在一个指向动态开辟数组的指针、一个表示元素个数的size和一个表示顺序表容量大小的capacity。

而vector使用了一个start、一个finish和一个end_of_storage,虽然二者的表示形式不同，实则都有相同的道理，如图：

现在我们就依据此来实现一下vector。

2.vector构造函数的实现

①构造函数

class vector
{
public:
    vector()
    :_start(nullptr)
    , _finish(nullptr)
    , _endofstorage(nullptr)
    {}
private:
    //全缺省为空
    iterator _start = nullptr;
    iterator _finish = nullptr;
    iterator _endofstorage = nullptr;
}

②拷贝构造

//①传统写法
//vector(const vector<T>& v)
  //{
  //  _start = new T[v.capacity()];//先开空间
  //  memcpy(_start, v._start, v.size() * sizeof(T));
  //  _finish = _start + v.size();
  //  _endofstorage = _start + v.capacity();
  //}
//②现代写法
vector(const vector<T>& v)
  {
    reserve(v.capacity());//首先开一个与旧空间一样的新空间
    for (const auto& e : v)//添加引用&，防止深拷贝
    {
      push_back(e);//复用push_back函数
    }
  }

③析构函数

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

3.访问函数实现

3.1迭代器iterator

①普通迭代器可读可写：

//普通迭代器 可读可写
typedef T* iterator;
iterator begin()
  {
    return _start;
 
  }
  iterator end()
  {
    return _finish;
  }

②const迭代器可读不可写：

//const迭代器 可读不可写
typedef const T* const_iterator;
const_iterator begin() const
  {
    return _start;
  }
  const_iterator end() const
  {
    return _finish;
  }

3.2下标+[]访问

①普通函数，可读可写：

//①可读可写
T& operator[](size_t pos)
  {
    assert(pos < size());//检查是否越界
 
    return _start[pos];//返回pos位置字符的引用，既可读又可写
  }

②const函数，可读不可写：

//②可读不可写
const T& operator[](size_t pos) const 
  {
    assert(pos < size());//检查是否越界
 
    return _start[pos];//返回pos位置字符的引用，既可读又可写
  }

4.析构函数和计算size、capacity、swap简单函数的实现

①析构函数：

//析构函数
~vector()
  {
    if (_start)
    {
      delete[] _start;
      _start = _finish = _endofstorage = nullptr;
    }
  }

②计算size：

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

③计算capacity：

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

④swap函数

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

有了swap函数，我们就可以复用swap函数实现赋值构造函数：

//赋值
vector<T>& operator=(vector<T> v)
//注意这里不能添加&引用，如v3=v1
//无&引用表示v是v1的临时拷贝，v3再拷贝v，出了作用域v就会被销毁，不会改变v1
//而加上&引用则直接表示v1与v3交换了，即可以认为这里实现了swap函数的功能
  {
    swap(v);//复用swap函数
    return *this; 
  }

5. reserve（提前开空间函数实现）

void reserve(size_t n)
  {
    if (n > capacity())//如果原容量<需要的新空间，就开辟新空间
    {
      T* tmp = new T[n];//开辟新空间
      if (_start)//判断原vector是否为空
      {
        //如果原vector不为空，就将从_start位置开始的n*sizeof(T)个数据拷贝到新空间tmp里
        memcpy(tmp, _start, n * sizeof(T));
        delete[] _start;//释放旧空间
        }
      //再指向新空间
      _start = tmp;
      _finish = _start + size();
      _endofstorage = _start + capacity()；
  }

这样写程序出现了bug：

这是因为

因为size()=_finish - _start;
所以_finish=_start+_finish-_start=_finish
可是这里的_start已经指向了新空间，而_finish指向的还是旧空间
一个空间的末尾 - 另一个空间的开头 ==== 错误！
_endofstorage = _start + capacity();
同样的道理，capacity()还是旧空间，_start是新空间也= 错误！
所以这里正确的做法应该是_endofstorage = _start + n;

正确代码：

void reserve(size_t n)
  {
    if (n > capacity())//如果原容量<需要的新空间，就开辟新空间
    {
      size_t old = size();//在扩容之前将size()先保存一下
      T* tmp = new T[n];//开辟新空间
      if (_start)//判断原vector是否为空
      {
        //如果原vector不为空，就将从_start位置开始的old*sizeof(T)个数据拷贝到新空间tmp里
        memcpy(tmp, _start, old * sizeof(T));
        delete[] _start;//释放旧空间
      }
        //再指向新空间
        _start = tmp;
        _finish = _start + old;
        _endofstorage = _start + n;
    }
  }

完成了reserve函数，我们就可以复用reserve函数实现拷贝构造的现代写法：

//②现代写法
vector(const vector<T>& v)
  {
    reserve(v.capacity());//首先开一个与旧空间一样的新空间
    for (const auto& e : v)//添加引用&，防止深拷贝
    {
      push_back(e);//复用push_back函数
    }
  }

6.resize（提前开空间并初始化函数实现）

使用resize开空间时，我们需要分3种情况：

①要开辟的空间小于原有的有效元素数，即：n<size()，那么这时我们就需要删除数据；

②要开辟的空间大于原有的有效元素数而小于原有的容量，即：size()<n<capacity()，那么这时我们就需要插入数据；

③要开辟的空间大于原有的容量，即:n>capacity()，那么这时我们就需要扩容+插入数据。

void resize(size_t n, T val = T())
    {
    if (n > size())//判断是否需要插入数据
    {
      reserve(n);//无关扩容，先调用reserve扩容
      while (_finish < _start + n)
      {
        *_finish = val;
        ++_finish;
      }
    }
    else//删除数据
      {
              _finish = _start + n;
      }
  }

对于resize()参数的说明：

val不传值时，整个resize函数处于半缺省状态，val默认传缺省值；
如果T是自定义类型，那么就去调用自定义类型的构造函数；
如果T是内置类型，为了兼容C++的模板，int的缺省值就是0，double的缺省值就是0.0，指针的缺省值就是空指针，以此类推。

7.erase函数

//erase函数
void erase(iterator pos)
  {
    assert(pos >= _start && pos < _finish);
 
    iterator it = pos + 1;
    while (it < _finish)
    {
      *(it - 1) = *it;
      ++it;
    }
    _finish--;
  }

8.尾插尾删函数

        //尾插函数
    void push_back(const T& x)
    {
      if (_finish == _endofstorage)//判断vector有没有满
      {
        size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;//如果满了就扩容
        reserve(newcapacity);
      }
      //扩容之后赋值
      *_finish = x;
      ++_finish; 
    }
 
    //尾删函数
    void pop_back()
    {
      assert(size() > 0);
      --_finish;
    }

9.insert指定位置插入实现

void insert(iterator pos, const T& x)//在pos位置之前插入x
  {
    assert(pos <= _finish && pos >= _start);//检查pos是否合法
 
    //检查vector是否充满
    if (_finish == _endofstorage)
    {
      reserve(capacity() == 0 ? 4 : capacity() * 2);//若充满则扩容
    }
    //把从pos位置开始，往后的sizeof(T) * (_finish - pos)个元素复制到pos+1位置
    memmove(pos + 1, pos, sizeof(T) * (_finish - pos));
    *pos = x;//挪动之后再把x放到pos位置
    ++_finish;
  }

这段代码在实际运行时有时会出现错误，这是为什么呢？

原因是：

reserve(capacity() == 0 ? 4 : capacity() * 2);//若充满则扩容
观察reserve函数：不扩容还好，当发生扩容时，reserve会销毁旧空间
此时_start指向新空间，pos仍然指向旧空间，pos在扩容之后失效了
因此这里的解决办法就是计算偏移量，更新一下pos的值

正确代码：

void insert(iterator pos, const T& x)//在pos位置之前插入x
  {
    assert(pos <= _finish && pos >= _start);//检查pos是否合法
 
    //检查vector是否充满
    if (_finish == _endofstorage)
    {
      size_t len = pos - _start;
      reserve(capacity() == 0 ? 4 : capacity() * 2);//若充满则扩容
      pos = _start + len;
    }
    //把从pos位置开始，往后的sizeof(T) * (_finish - pos)个元素复制到pos+1位置
    memmove(pos + 1, pos, sizeof(T) * (_finish - pos));
    *pos = x;//挪动之后再把x放到pos位置
    ++_finish;
  }

10.设计程序验证

void test_vector()
  {
    vector <int> v1;
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    v1.push_back(5);
 
    //迭代器访问
    vector <int>::iterator it = v1.begin();
    while (it != v1.end())
    {
      cout << *it << " ";
      ++it;
    }
    cout << endl;
    //范围for访问
    for (auto e : v1)
    {
      cout << e << " ";
    }
    cout << endl;
    //下标+[]访问
    for (size_t i = 0; i < v1.size(); i++)
    {
      cout << v1[i] << " ";
    }
    cout << endl;
  }

源代码（vector.h）

#pragma once
 
#include <iostream>
#include <assert.h>
 
using namespace std;
 
 
namespace xxk
{
  template<class T>
  class vector
  {
  public:
    typedef T* iterator;//普通迭代器 可读可写
    typedef const T* const_iterator;//const迭代器 可读不可写
 
    //构造函数
    vector()
      :_start(nullptr)
      , _finish(nullptr)
      , _endofstorage(nullptr)
    {}
 
    //拷贝构造
    //①传统写法
    //vector(const vector<T>& v)
    //{
    //  _start = new T[v.capacity()];//先开空间
    //  memcpy(_start, v._start, v.size() * sizeof(T));
    //  _finish = _start + v.size();
    //  _endofstorage = _start + v.capacity();
    //}
    //②现代写法
    vector(const vector<T>& v)
    {
      reserve(v.capacity());//首先开一个与旧空间一样的新空间
      for (const auto& e : v)//添加引用&，防止深拷贝
      {
        push_back(e);//复用push_back函数
      }
    }
 
    //赋值
    vector<T>& operator=(vector<T> v)
    //注意这里不能添加&引用，如v3=v1
    //无&引用表示v是v1的临时拷贝，v3再拷贝v，出了作用域v就会被销毁，不会改变v1
    //而加上&引用则直接表示v1与v3交换了，即可以认为这里实现了swap函数的功能
    {
      swap(v);//复用swap函数
      return *this; 
    }
 
    //析构函数
    ~vector()
    {
      if (_start)
      {
        delete[] _start;
        _start = _finish = _endofstorage = nullptr;
      }
    }
 
    //迭代器begin()和end()实现
    //普通迭代器 可读可写
    iterator begin()
    {
      return _start;
 
    }
    iterator end()
    {
      return _finish;
    }
    //const迭代器 可读不可写
    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 _endofstorage - _start;
    }
 
    //下标+[]访问函数的实现
    //①可读可写
    T& operator[](size_t pos)
    {
      assert(pos < size());//检查是否越界
 
      return _start[pos];//返回pos位置字符的引用，既可读又可写
    }
    //②可读不可写
    const T& operator[](size_t pos) const 
    {
      assert(pos < size());//检查是否越界
 
      return _start[pos];//返回pos位置字符的引用，既可读又可写
    }
 
    //reserve扩容函数
    //error：
    //void reserve(size_t n)
    //{
    //  if (n > capacity())//如果原容量<需要的新空间，就开辟新空间
    //  {
    //    T* tmp = new T[n];//开辟新空间
    //    if (_start)//判断原vector是否为空
    //    {
    如果原vector不为空，就将从_start位置开始的n*sizeof(T)个数据拷贝到新空间tmp里
    //      memcpy(tmp, _start, n * sizeof(T));
    //      delete[] _start;//释放旧空间
    //    }
    //    //再指向新空间
    //    _start = tmp;
    //    _finish = _start + size();
    //    //因为size()=_finish - _start;
    //    //所以_finish=_start+_finish-_start=_finish
    //    //可是这里的_start已经指向了新空间，而_finish指向的还是旧空间
    //    //一个空间的末尾 - 另一个空间的开头 ==== 错误！
    //    _endofstorage = _start + capacity();
    //    //同样的道理，capacity()还是旧空间，_start是新空间 也= 错误！
    //    //所以这里正确的做法应该是_endofstorage = _start + n;
    //  }
    //}
 
    void reserve(size_t n)
    {
      if (n > capacity())//如果原容量<需要的新空间，就开辟新空间
      {
        size_t old = size();//在扩容之前将size()先保存一下
        T* tmp = new T[n];//开辟新空间
        if (_start)//判断原vector是否为空
        {
      //如果原vector不为空，就将从_start位置开始的old*sizeof(T)个数据拷贝到新空间tmp里
          memcpy(tmp, _start, old * sizeof(T));
          delete[] _start;//释放旧空间
        }
          //再指向新空间
          _start = tmp;
          _finish = _start + old;
          _endofstorage = _start + n;
      }
    }
 
    //resize函数
    void resize(size_t n, T val = T())
      //val不传值时，整个resize函数处于半缺省状态，val默认传缺省值。
      //如果T是自定义类型，那么就去调用自定义类型的构造函数；
      //如果T是内置类型，为了兼容C++的模板，int的缺省值就是0，double的缺省值就是0.0，指针的缺省值就是空指针，以此类推
    {
      if (n > size())//判断是否需要插入数据
      {
        reserve(n);//无关扩容，先调用reserve扩容
        while (_finish < _start + n)
        {
          *_finish = val;
          ++_finish;
        }
      }
      else//删除数据
      {
        _finish = _start + n;
      }
    }
 
        //erase函数
    void erase(iterator pos)
    {
      assert(pos >= _start && pos < _finish);
 
      iterator it = pos + 1;
      while (it < _finish)
      {
        *(it - 1) = *it;
        ++it;
      }
      _finish--;
    }
 
    //尾插函数
    void push_back(const T& x)
    {
      if (_finish == _endofstorage)//判断vector有没有满
      {
        size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;//如果满了就扩容
        reserve(newcapacity);
      }
      //扩容之后赋值
      *_finish = x;
      ++_finish; 
    }
 
    //尾删函数
    void pop_back()
    {
      assert(size() > 0);
      --_finish;
    }
 
    //指定位置插入（insert）函数
    //error:
    //void insert(iterator pos, const T& x)//在pos位置之前插入x
    //{
    //  assert(pos <= _finish && pos >= _start);//检查pos是否合法
 
    //  //检查vector是否充满
    //  if (_finish == _endofstorage)
    //  {
        //reserve(capacity() == 0 ? 4 : capacity() * 2);//若充满则扩容
        观察reserve函数：不扩容还好，当发生扩容时，reserve会销毁旧空间
        此时_start指向新空间，pos仍然指向旧空间，pos在扩容之后失效了
        因此这里的解决办法就是计算偏移量，更新一下pos的值
    //  }
    //  //把从pos位置开始，往后的sizeof(T) * (_finish - pos)个元素复制到pos+1位置
    //  memmove(pos + 1, pos, sizeof(T) * (_finish - pos));
    //  *pos = x;//挪动之后再把x放到pos位置
    //  ++_finish;
    //}
 
    void insert(iterator pos, const T& x)//在pos位置之前插入x
    {
      assert(pos <= _finish && pos >= _start);//检查pos是否合法
 
      //检查vector是否充满
      if (_finish == _endofstorage)
      {
        size_t len = pos - _start;
        reserve(capacity() == 0 ? 4 : capacity() * 2);//若充满则扩容
        pos = _start + len;
      }
      //把从pos位置开始，往后的sizeof(T) * (_finish - pos)个元素复制到pos+1位置
      memmove(pos + 1, pos, sizeof(T) * (_finish - pos));
      *pos = x;//挪动之后再把x放到pos位置
      ++_finish;
    }
 
    //swap函数
    void swap(vector<T>& v)
    {
      std::swap(_start, v._start);
      std::swap(_finish, v._finish);
      std::swap(_endofstorage, v._endofstorage);
    }
 
  private:
    //全缺省为空
    iterator _start = nullptr;
    iterator _finish = nullptr;
    iterator _endofstorage = nullptr;
  };
  
}

C++番外篇——vector的实现

1.vector的底层

2.vector构造函数的实现

①构造函数

②拷贝构造

③析构函数

3.访问函数实现

3.1迭代器iterator

3.2下标+[]访问

4.析构函数和计算size、capacity、swap简单函数的实现

①析构函数：

②计算size：

③计算capacity：

④swap函数

5. reserve（提前开空间函数实现）

6.resize（提前开空间并初始化函数实现）

7.erase函数

8.尾插尾删函数

9.insert指定位置插入实现

10.设计程序验证

源代码（vector.h）

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

C++番外篇——vector的实现

1.vector的底层

2.vector构造函数的实现

①构造函数

②拷贝构造

③析构函数

3.访问函数实现

3.1迭代器iterator

3.2下标+[]访问

4.析构函数和计算size、capacity、swap简单函数的实现

①析构函数：

②计算size：

③计算capacity：

④swap函数

5. reserve（提前开空间函数实现）

6.resize（提前开空间并初始化函数实现）

7.erase函数

8.尾插尾删函数

9.insert指定位置插入实现

10.设计程序验证

源代码（vector.h）

热门文章

最新文章

相关课程

相关电子书