C++:vector增删查改模拟实现

C++:vector增删查改模拟实现

• 前言
• 一、迭代器
• • 1.1 非const迭代器：begin()、end()
  • 1.2 const迭代器：begin()、end()
  • 二、构造函数、拷贝构造函数、赋值重载、析构函数模拟实现
  • • 2.1 构造函数
    • • 2.1.1 无参构造
      • 2.1.2 迭代器区间构造
      • 2.1.3 n个值构造
      • 2.2 拷贝构造
      • 2.3 赋值重载
      • 3 析构函数
      • 三、容量相关：capacity()、size()、reserve()、resize()
      • • 3.1 capacity()
        • 3.2 size()
        • 3.3 reserve()
        • 3.4 resize()
        • 四、operator[ ]重载
        • 五、元素相关：insert、erase、push_back、pop_back
        • • 5.1 insert()
          • 5.2 erase()
          • • 5.2.1 erase迭代器失效
            • 5.3 push_bach()
            • 5.4 pop_back()
            • ��、所有代码

              ---

              前言

              提前在这说明下，vector增删查改模拟实现的成员变量博主采用SGI版本。下面给出其库中成员变量是哪些，后续的模拟实现都基于此。

              我们发现库中定义了3个T*的变量。同时3个成员变量的意义如下：

              一、迭代器

              1.1 非const迭代器：begin()、end()

              typedef T* iterator;iterator begin(){return _start;}iterator end(){return _finish;}

              1.2 const迭代器：begin()、end()

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

              二、构造函数、拷贝构造函数、赋值重载、析构函数模拟实现

              2.1 构造函数

              我们先来看看vector库中的构造类型如下：

              我们知道有三种构造方式，下面给出各种的实现方式。

              2.1.1 无参构造

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

              2.1.2 迭代器区间构造

              template//使用模板是为了，当数据类型匹配时就可以使用vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);first++;}}

              2.1.3 n个值构造

              vector(size_t  n, const T& value = T()){reserve(n);for (size_t i = 0; i  
              2.2 拷贝构造
               
              拷贝构造我们先调用开好一块空间，在依次插入数据即可。
               
              //vector(const vector& x) //库中实现模式, 直接使用类名。但C++，类型不是类名。//这里各位读者了解下这里直接类名做类型也正确即可，但不建议各位这样做。vector(const vector& v){reserve(v.capacity());//后面会给出实现for (auto& e : v){push_back(e);}}
               
              2.3 赋值重载
               
              赋值重载这里我们不要传引用，而是直接传参即可。编译器调用拷贝构造生成形参后，在调用swap()函数依次交换形参和this即可。
               
              //赋值重载void swap(vector& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v_endofstorage);}vector& operator= (vector tmp){swap(tmp);return *this;}
               
              3 析构函数
               
              ~vector(){delete[] _start;_start = _finish = _endofstorage = nullptr;}
               
              三、容量相关：capacity()、size()、reserve()、resize()
               
              3.1 capacity()
               
              size_t capacity()const{return _endofstorage - _start;}
               
              3.2 size()
               
              size_t size()const{return _finish - _start;}
               
              3.3 reserve()
               
              由于stl中我们一般不缩容，所以先判断reserve的空间大小是否比当前空间容量大。
              如果reserve的空间更大，所以我们需要先开好目标大小的空间，在将原数据拷贝过去，最后析构原来空间即可。
              但下面这两种实现方式对吗？
               
              第一种：
               
              void reserve(size_t n){if (n > capacity()){T* tmp = new T[n];if (_start)//如果原来空间有数据，拷贝到新空间{memcpy(tmp, _start, sizeof(T) * size());delete[] _start;}//更新_start、_finish、_endofstorage。指向新空间中相应位置_start = tmp;_finish = _start + size();_endofstorage = _start + n;}}
               
              先说结论：上诉这段代码是错的。
              在我们调试后会发现_finish的值没有更新。（这里大家自行验证下接口）
               
              原因：(win11画图一直很模糊，博主也很无奈，各位将就看吧)
               
              第二种：
              为了解决上诉问题，我们可以先记录_finish和_start的偏移量，用来代替size()函数。
              所以初学者很容易写出以下代码：
               
              void reserve(size_t n){if (n > capacity()){size_t sz = size();//记录_finish 和 _start 的偏移量T* tmp = new T[n];if (_start){//memcpy(tmp, _start, sizeof(T) * sz);delete[] _start;}_start = tmp;_finish = _start + sz;//不能用size()代替sz，否则会导致迭代器失效_endofstorage = _start + n;}}
               
              那这是否正确呢？答案是否定的。
              我们来看看下面这种场景：
               
              实际上对于这种情况，可以自己循环依次赋值即可。内置类型直接拷贝数据；内置类型调用赋值重载，是一种深拷贝。
               
              最终代码如下：
               
              void reserve(size_t n){if (n > capacity()){size_t sz = size();//记录_finish 和 _start 的偏移量T* tmp = new T[n];if (_start){//memcpy(tmp, _start, sizeof(T) * sz);for (size_t i = 0; i  
              3.4 resize()
               
              resize逻辑还是很简单的。
              首先判断resize()的目标大小n和有效数据个数size()谁大。如果有效个数size()更大，只需更改_finish即可；否则要先进行扩容（reserve会将原有数据拷贝到新空间），然后从_finish开始向扩充的空间插入新的值。
               
              代码如下：
               
              //const会延长匿名对象的生命周期, 匿名对象具有常性//模板出来后，对类进行了升级，内置类型也有构造函数//void resize(size_t n, T val = T())void resize(size_t n, const T& val = T()){if (n  
              四、operator[ ]重载
               
              T& operator[](size_t pos){assert(pos  
              五、元素相关：insert、erase、push_back、pop_back
               
              5.1 insert()
               
              任意位置插入数据，首先需判断是否需要扩容。然后将插入位置pos开始往后的数据向后移动，最后将新数据插入到pos处即可。
              tips：
               

              • 如果发生扩容，需要先记录pos和_start之间的偏移量。在将pos位置跟新，指向新空间中对应位置。否则会导致迭代器失效

                void insert(iterator pos, const T& x){assert(pos >= _start);assert(pos size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}//挪动数据iterator end = _finish - 1;while (end = pos){*(end + 1) = *end;end--;}//插入数据*pos = x;_finish++;}

                5.2 erase()

                任意位置删除数据，只需要从pos+1开始，将后续数据全部依次向前移动覆盖，最后更新_finish即可。

                iterator erase(iterator pos){assert(pos >= _start);assert(pos  
                5.2.1 erase迭代器失效
                 
                void testvector4(){vector v;v.push_back(1);v.push_back(2);v.push_back(2);v.push_back(4);v.push_back(5);v.push_back(6);auto it = v.begin();while (it