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的值