【C++】：vector容器的底层模拟实现&&迭代器失效&&隐藏的浅拷贝

目录

• 前言
• 一，构造函数
• • 1 . 强制编译器生成默认构造
  • 2 . 拷贝构造
  • 3. 用迭代器区间初始化
  • 4. 用n个val值构造
  • 5. initializer_list 的构造
  • 二，析构函数
  • 三，关于迭代器
  • 四，有关数据个数与容量
  • 五，交换函数swap
  • 六，赋值拷贝
  • 七，[ ]运算符
  • 八，预留空间(扩容)
  • • 8.1 使用memcpy拷贝问题(重点)
    • 九，尾插和尾删数据
    • 十，插入数据 insert
    • 十一，删除数据 erase
    • 十二，insert和erase的迭代器失效问题(重点)
    • • 1. 什么是迭代器失效？
      • 2. insert 的迭代器失效
      • • 2.1 insert 内部pos位置的失效
        • 2.2 insert 以后外部的实参失效
        • 3. erase 以后的迭代器失效

          前言

          点击跳转到文章：vector容器的基本使用

          上篇文章已经介绍了vector容器的基本使用，这篇文章主要选择vector中一些核心的，基本的接口进行模拟实现。

          注意：由于我们模拟实现时使用了类模板，所以不建议进行文件分离，不然会产生链接错误。所以我们把函数都写在.h文件中，在Test.cpp文件中进行测试。

          首先我们先给出vector类：

          #include #include #include using namespace std;templateclass vector{public:// Vector的迭代器是一个原生指针typedef T* iterator;typedef T* const_iterator;//......private:iterator _start = nullptr;//指向开始位置的指针iterator _finish = nullptr;//指向最后一个位置的下一个位置的指针iterator _end_of_storage = nullptr;//指向存储容量的尾};

          一，构造函数

          在vector文档中，构造函数分为好几个类型，下面分别进行介绍：

          1 . 强制编译器生成默认构造

          无参构造

          vector() = default;

          2 . 拷贝构造

          //v2(v1);vector(const vector& v){//提前预开空间，避免边尾插边扩容reserve(v.capacity());for (auto e : v){//this->push_back(e);push_back(e);}}

          3. 用迭代器区间初始化

          (1) 一个类模版的成员函数可以写成函数模版。

          (2) 若使用iterator做迭代器，会导致初始化的迭代器区间[first,last)只能是vector的迭代器，重新声明迭代器，迭代器区间[first,last)可以是任意容器的迭代器。

          template vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}

          4. 用n个val值构造

          vector(size_t n, const T& val = T()){reserve(n);for (size_t i = 0; i  
          具体使用：
           
          //初始化3个空vector v1(3);//初始化为3个xxvector v2(3, "xx");//初始化为3个1vector v3(3, 1);//err 非法的间接寻址.参数匹配问题vector v3(3u, 1);//ok//如果非要这样传参数，就需要再重载一个构造vector v3(3, 1);
           
          (1) 为什么要重载两个类似的构造？
             
          理论上将，提供了vector(size_t n, const T& value = T())之后vector(int n, const T& value = T())就不需要提供了，但是对于：vector v(10, 5);
          编译器在编译时，认为T已经被实例化为int，而10和5编译器会默认其为int类型， 就不会走vector(size_t n, const T& value = T())这个构造方法， 最终选择的是：vector(InputIterator first, InputIterator last)。因为编译器觉得区间构造两个参数类型一致，因此编译器就会InputIterator实例化为int，但是10和5根本不是一个区间，编译时就报错了，故需要增加该构造方法。
            
          (2) T()是什么？
             
          T()是缺省值，注意这里不能给0，因为T可能为自定义类型，当T为内置类型的时候，也ok。因为C++对内置类型进行了升级，也有构造，为了兼容模版。
            
          5. initializer_list 的构造
           
          (1) C++11新增的类模板initializer_list，方便用花括号初始化。
           
          (2) 这里不需要传引用&，因为不涉及拷贝问题，它的内部其实有两个指针，一个指向第一个值的位置，一个指向最后一个值的下一个位置，并且支持迭代器。
           
          vector(initializer_list il){reserve(il.size());for (auto e:il){push_back(e);}}
           
          具体使用：
          支持被花括号括起的任意个数的值给 initializer_list
           
          auto il1 = { 1,3,4,5,6,7 };initializer_list il2 = { 1,2,3 };//这里的隐式类型转换不一样，参数个数不固定vector v4 = { 7,8,9,4,5 };//隐式类型转换vector v5({ 4,5,6 });//直接构造
            
          二，析构函数
           
          ~vector(){if (_start){delete[] _start;_start = _finish = _end_of_storage = nullptr;}}
           
          三，关于迭代器
           
          iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin()const{return _start;}const_iterator end()const{return _finish;}
           
          四，有关数据个数与容量
           
          //计算有效数据个数size_t size()const{return _finish - _start;}//计算当前容量size_t capacity()const{return _end_of_storage - _start;}
           
          五，交换函数swap
           
          与string类类似，依然调用库里的swap函数，进行指针的交换。
           
          void swap(vector& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}
           
          六，赋值拷贝
           
          与string类的现代写法相同。
           
          //赋值拷贝//v3 = v1;vector& operator=(const vector v){swap(v);return *this;}
           
          七，[ ]运算符
           
          //[]运算符T& operator[](size_t pos){//断言，避免下标越界assert(pos  
          八，预留空间(扩容)
           
          void reserve(size_t n){//由于开空间后_start指向改变，所以要提前记录原来的有效数据个数//以便在新空间中更新_finish的位置size_t  old_size = size();if (n > capacity()){T* tmp = new T[n];//开新空间if (_start){//memcpy(tmp, _start, sizeof(T) * old_size);for (size_t i = 0; i  
          8.1 使用memcpy拷贝问题(重点)
           
          假设模拟实现的vector中的reserve接口中，使用memcpy进行的拷贝，以下代码会发生什么问题？
           
          int main(){ bite::vector v; v.push_back("2222"); v.push_back("2222"); v.push_back("2222");  return 0;}
           
          问题分析：
           
          (1) memcpy是内存的二进制格式拷贝，按字节拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中。
           
          (2) 如果拷贝的是自定义类型的元素，memcpy既高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝。
           
          图解如下：
           
          当把原空间里的"2222"拷贝进新空间后，delete会先对原空间的每个对象调用析构函数，再把原空间销毁，但是此时tmp仍指向那块空间，变成野指针了！
            
          复用赋值进行修改后：
           
          此时这里的赋值调用的是string的赋值，肯定是深拷贝
            
          九，尾插和尾删数据
           
          //尾插数据void push_back(const T& x){if (_finish == _end_of_storage){size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);}*_finish = x;++_finish;}//尾删void pop_back(){//断言，确保有数据可删assert(size() > 0);--_finish;}
           
          十，插入数据 insert
           
          //void insert(iterator pos, const T& x)iterator insert(iterator pos, const T& x){//断言，判断下标的有效性assert(pos >= _start && pos size_t len = pos - _start;size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);//insert函数的内部迭代器失效问题：类似于野指针问题//扩容后pos位置失效，需要重新计算pospos = _start + len;}//挪动数据再插入iterator end = _finish - 1;while (end = pos){*(end + 1) = *end;--end;}*(end + 1) = x;++_finish;//返回新插入那个位置的迭代器return pos;}
           
          十一，删除数据 erase
           
          iterator erase(iterator pos){assert(pos >= _start && pos  
          十二，insert和erase的迭代器失效问题(重点)
           
          1. 什么是迭代器失效？
           
          迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装，比如：vector的迭代器就是原生态指针T* 。因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器，程序可能会崩溃)。
           
          2. insert 的迭代器失效
           
          2.1 insert 内部pos位置的失效
           
          当刚好执行了扩容操作这一步时，由于要开辟新空间，拷贝数据，释放空间，改变空间指向。但是此时pos位置还在原空间，这就使pos变成了野指针，如果对该位置进行访问，就会导致程序崩溃。
           
          所以在函数内部，扩容后我们要更新pos迭代器！
            
          2.2 insert 以后外部的实参失效
           
          演示代码如下：
           
          void vector_test2(){vector v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);for (size_t i = 0; i