【STL模版库】模拟实现vector类模版

一、核心结构

template<class T>
class Myvector{
    typedef T *iterator; //[1]
    typedef const T *const_iterator;
  private:
    iterator _start; //指向存存储空间的开头 //[2]
    iterator _finish; //指向实际存储元素的下一个位置
    iterator _end_of_storage; //指向存储空间结尾的下一个位置

  public:   
    size_t size()const{
      return _finish-_start;
    }
    size_t capacity()const{
      return _end_of_storage-_start;
    }
};

解释：

• [1] 对于顺序表迭代器就是指向其内部元素的指针。
• [2] 下面是其结构示意图：
  

二、遍历访问

2.1 迭代器

	iterator begin(){
      return _start;
    }

    iterator end(){
      return _finish;
    }

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

2.2 operator[ ]

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

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

三、默认成员函数

3.1 构造

    Myvector()
      :_start(nullptr), //[1]
      _finish(nullptr),
      _end_of_storage(nullptr)
    {}

    Myvector(size_t n, const T &val = T()) //[2]
      :_start(nullptr),
      _finish(nullptr),
      _end_of_storage(nullptr)
    {
      resize(n, val);
    }
 	//上一个函数的重载函数
    Myvector(int n, const T &val = T()) //[3]
      :_start(nullptr),
      _finish(nullptr),
      _end_of_storage(nullptr)
    {
      resize(n, val);
    }

 

解释：

• [1] 构造函数必须要先将3个迭代器置空，否则在reserve开空间时会出现访问野指针的问题。
• [2] 第二个参数用T类型的匿名对象做缺省值，相当于去调默认构造。生成的匿名对象具有常性需用const引用。
• [2] 由此可以看出，我们自己定义的类是一定要提供默认构造的，否则会出现一些问题。
• [2] 由于模版的出现，C++对内置类型进行了升级，内置类型也具有默认构造。内置类型的默认构造会将其初始化为0
• [3] 重载该函数的目的是为了解决和函数Myvector(input_iterator first, input_iterator last);的调用冲突问题。
• [3] 例如：Myvector v1(10, 5);如果没有该重载函数，由于10(int)与size_t(unsigned int)类型不匹配，需要进行类型转换。所以编译器会优先匹配Myvector(input_iterator first, input_iterator last);，将10和5解释成迭代器，从而访问非法空间造成程序崩溃。

3.2 拷贝构造

//迭代器区间拷贝构造：
    template<class input_iterator> //[1]
     Myvector(input_iterator first, input_iterator last)
        :_start(nullptr),
        _finish(nullptr),
        _end_of_storage(nullptr)
      {
        reserve(last-first);
        while(first!=last)
        {
          *_finish = *first;
          ++_finish;
          ++first;
        }
      }

// 传统写法：
    Myvector(const Myvector<T> &v)
        :_start(nullptr),
        _finish(nullptr),
        _end_of_storage(nullptr)
    {
      reserve(v.size());
      for(size_t i = 0; i<v.size(); ++i)
      {
        _start[i] = v._start[i];
      }
      _finish = _start + v.size();
    }

// 复用写法：
    Myvector(const Myvector<T> &v)
        :_start(nullptr), //[3]
        _finish(nullptr),
        _end_of_storage(nullptr)
    {
      Myvector tmp(v.begin(), v.end()); //[2]
      swap(tmp); 
    }
    
//交换函数：
    void swap(Myvector<T> &v){
      std::swap(_start,v._start);
      std::swap(_finish,v._finish);
      std::swap(_end_of_storage, v._end_of_storage);
    }

解释：

• [1] 将此函数写成模版，是为了兼容各种容器的迭代器。使vector可以拷贝构造各种容器的数据。
• [2] 复用迭代器区间拷贝构造，先构造出临时对象tmp，再与构造对象交换数据（浅交换）
• [2] 之后tmp析构，而构造对象也得到了拷贝数据。
• [3] 注意：交换前要先将构造对象的三个迭代器置空，否则析构tmp时会因释放野指针而崩溃。

3.3 赋值重载 & 析构

    Myvector<T>& operator=(const Myvector<T> &v){
      Myvector tmp(v); //[1]
      swap(tmp);
    }

    ~Myvector(){
      delete[] _start;
    }

• [1] 复用拷贝构造实现赋值重载。

四、容量操作

4.1 reserve

    void reserve(size_t n){
      if(n > capacity())
      {
        iterator tmp = new T[n];
        size_t sz = size();
        if(_start!=nullptr)
        {
          //memcpy(tmp, _start, sz * sizeof(T)); //[1]
          for(size_t i = 0; i< sz; ++i)
          {
            tmp[i] = _start[i];
          }
          delete[] _start;
        }
        _start = tmp;
        _finish = _start + sz; //[2]
        _end_of_storage = _start + n;
      }
    }

解释：

• [1] 此处不能使用memcpy拷贝数据，当模版类型T是自定义类型且涉及动态内存申请时（如string或list），memcpy只能进行浅拷贝。
• [1] 应该逐元素调用赋值重载，以实现多层深拷贝。下文有二维动态数组的深拷贝问题的详解。
• [2] 扩容后开辟新空间，释放旧空间。_finish和_end_of_storage也要根据长度计算新地址，否则就成了野指针。

4.2 resize

    void resize(size_t n, const T &val = T()){
      if(n > size())
      {
        reserve(n);
        for(size_t i = size(); i<n; ++i)
        {
          _start[i] = val; //[1]
        }
      }
      _finish = _start + n; //[2]
    }

解释：

• [1] 对于自定义类型元素此处调用赋值重载。
• [2] 当n > size()，_finish向后移动；当n<=size()，_finish向前移动；

五、增删查改

5.1 push_back & pop_back

    void push_back(const T &val){
      if(_finish == _end_of_storage)
      {
        size_t n = capacity() == 0? 5:capacity()*2;
        reserve(n);
      }
      *_finish = val;
      ++_finish;
    }
    
    void pop_back(){
      assert(_finish != _start);
      --_finish;
    }

5.2 insert

    iterator insert(iterator pos, const T &val){
      assert(pos >= _start);
      assert(pos <= _finish); //[1]
      if(_finish == _end_of_storage)
      {
        size_t n = capacity() == 0? 5:capacity()*2;
        size_t len = pos-_start;
        reserve(n);
        pos = _start+len; //[2]
      }
      iterator end = _finish - 1;
      while(end >= pos)
      {
        *(end+1) = *end;
        --end;
      }
      *pos = val;
      ++_finish;
      return pos; //[3]
    }

解释：

• [1] 当pos == _finish时，表示尾插数据。
• [2] 扩容重开空间后，pos仍指向旧空间的地址成了野指针（迭代器失效）。因此需要根据长度重新计算位置。
• [3] insert插入数据pos迭代器可能失效，因此要返回重新计算后的pos迭代器（指向新插入的数据），并在函数调用处接收返回值，才可继续进行插入操作。

5.3 erase

    iterator erase(iterator pos){
      assert(pos >= _start);
      assert(pos < _finish);
      iterator tmp = pos+1; //[1]
      while(tmp < _finish){
        *(tmp-1) = *tmp;
        ++tmp;
      }
      --_finish;
	
	  //if(size() < capacity()/2) //[2]
	  //{
	  	//......
	  	//缩容--以时间换空间
	  //}

      return pos; //[3]
    }

解释：

• [1] 这个过程是在向前挪动数据覆盖要删除的数据。
• [2] 不排除个别版本的erase会进行缩容操作，此处重新开辟内存空间，pos迭代器也有可能失效，因此同样需要重新计算。
• [3] 返回被删除元素的后一个元素。

六、关于vector的两个问题

6.1 迭代器失效问题

在所有偶数前插入此数的10倍 ：

//错误写法： 
void Test1(){    
  int arr[] = {1,2,3,4,5};    
  Myvector<int> v1(arr, arr+sizeof(arr)/sizeof(arr[0]));    
  Myvector<int>::iterator it = v1.begin();    
  while(it != v1.end())    
  {    
    if(*it % 2 == 0)    
    {    
      v1.insert(it, (*it) * 10); //返回值指向新插入的数据                                                                                                                                     
    }  
    ++it;
  }    
    
  for(int e : v1)    
  {    
    cout << e << " ";    
  }    
  cout << endl;    
}  

此时可能出现以下两种迭代器失效的情况，从而引起程序崩溃：

//正确写法：    
void Test1(){    
  int arr[] = {1,2,3,4,5};    
  Myvector<int> v1(arr, arr+sizeof(arr)/sizeof(arr[0]));    
  Myvector<int>::iterator it = v1.begin();    
  while(it != v1.end())    
  {    
    if(*it % 2 == 0)    
    {    
      it = v1.insert(it, (*it) * 10); //接收返回值，解决情况1                                                                                                                                
      it+=2; //从偶数的下一个数据开始重新判断，解决情况2    
    }  
    else
    {  
    	++it;
    }    
  }    
  //......   
}  

删除数列中所有的偶数：

//错误写法：                                                                                                                                                  
void Test2(){    
  int arr[] = {1,2,3,4,5};    
  Myvector<int> v1(arr, arr+sizeof(arr)/sizeof(arr[0]));    
  Myvector<int>::iterator it = v1.begin();    
  while(it != v1.end())
  {
    if(*it % 2 == 0)
    {
      v1.erase(it); //返回值指向被删除元素的后一个元素
    }
      ++it; 
  }

  for(int e : v1)
  {
    cout << e << " ";
  }
  cout << endl;  
}

运行结果：

解释SGI版结果：

1. 第一种情况看似正常运行，实则是因为数据排列的偶然性。
2. 第二种情况程序崩溃。是因为最后一个数是偶数，删除之后又++it错过了_finish，最终导致越界访问程序崩溃。
3. 第三种情况程序可以运行但结果不对。是因为删除第一个2之后++it错过了第二个2。

//正确写法：                                                                                                                                                  
void Test2(){    
  int arr[] = {1,2,2,3,4,4,4};    
  Myvector<int> v1(arr, arr+sizeof(arr)/sizeof(arr[0]));    
  Myvector<int>::iterator it = v1.begin();    
  while(it != v1.end())
  {
    if(*it % 2 == 0)
    {
      it = v1.erase(it); //返回值指向被删除元素的后一个元素
    }
    else{
      ++it;
    }
  }
  //......  
}

结论：

1. 使用insert/erase插入或删除pos位置数据之后。一定要接收返回值更新pos位置，如果直接访问可能因扩容而遇到野指针问题。
2. 要明确insert/erase返回值指向的位置，并对返回更新后的pos进行适当调整以继续插入或删除操作。

6.2 二维动态数组的深拷贝问题

以上一节提到的题目杨辉三角（【STL模版库】vector的介绍及使用3.2）为例，如果我们要拷贝其计算得到的结果：

 void Test1(){
  Myvector<Myvector<int>> ret = Solution().generate(5); //拷贝构造    
  for(size_t i = 0; i<ret.size(); ++i)    
  {    
    for(size_t j = 0; j<ret[i].size(); ++j)    
    {    
      cout << ret[i][j] << " ";    
    }    
    cout << endl;    
  }
}

ret是Myvector<Myvector>类型的二维数组，那么多层深拷贝是如何进行的呢？

运行结果：

深拷贝问题的解决方案：
将所有设计数据拷贝的过程都改为逐个赋值拷贝。对于内置类型直接赋值即可；对于自定义类型，调用其赋值重载函数，开辟新空间并向下继续调用其元素的赋值重载。以此实现容器整体的深拷贝。文章来源地址https://www.toymoban.com/news/detail-455427.html

到了这里，关于【STL模版库】模拟实现vector类模版的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！