• C++【STL】【vector类的模拟实现】【迭代器失效问题】

    目录

    一、vector容器的基本结构

    二、vector容器的构造函数和析构函数

    三、迭代器

    四、返回容器中的相关参数

    五、交换函数

    六、拷贝构造

    1.拷贝指定范围的数据

    测试代码 

    2.拷贝构造 

    测试代码

    3.使用=拷贝构造

    七、扩容操作

    1.reserve扩容

    2.resize调整大小

    测试代码

    八、让我们的容器支持随机读写

    九、尾插尾删 

    1.尾插push_back

    2.尾删 pop_back

    3.将容器后面追加n个元素，元素为value 

    测试代码 

    十、随机位置插入和删除 

    1.随机位置插入insert

    2.随机位置擦除 

    3.清除函数clear 

    1）写法一：调用erase

    2）写法二：直接将_finish=_start

    测试代码

    ​编辑

    测试代码（clear）

    为什么要返回删除位置的下一个位置的迭代器？ 

    十一、迭代器的失效问题

    问题的解决 

    测试代码

    十二、主程序代码汇总 

    十三、测试程序代码汇总

    调用测试程序

    测试程序

    十四、vector原码

    这里我们先将每一个小模块分别实现，然后最终的汇总代码和测试代码在后面

    一、vector容器的基本结构

    1. #pragma once
    2. #include 
    3. #include 
    4. namespace zhuyuan
    5. {
    6.     template<class T>
    7.     class vector
    8.     {
    9.     public:
    10.        
    11.     private:
    12.         //_start是容器的初始位置
    13.         iterator _start;
    14.         //finish是最后一个数据的下一个位置
    15.         iterator _finish;
    16.         //_end_of_storage是我们整个vector的容量大小
    17.         iterator _end_of_storage;
    18.     };
    19. }

    二、vector容器的构造函数和析构函数

    1.         //空参构造器
    2.         vector()
    3.             :_start(nullptr)
    4.             ,_finish(nullptr)
    5.             ,_end_of_storage(nullptr)
    6.         {
    7.  
    8.         }
    9.         //析构函数
    10.         ~vector()
    11.         {
    12.             //析构的时候只要将整一个空间的首元素的地址传过去就可以了。
    13.             delete[] _start;
    14.             _start=_finish=_end_of_storage= nullptr;
    15.         }

    三、迭代器

    其实连续的空间的迭代器可以用指针来实现

    1.         typedef T* iterator;
    2.         const typedef T* const_iterator;
    3.         iterator begin()
    4.         {
    5.             return _start;
    6.         }
    7.         const iterator begin() const
    8.         {
    9.             return _start;
    10.         }
    11.         iterator end()
    12.         {
    13.             return _finish;
    14.         }
    15.         const iterator end() const
    16.         {
    17.             return _finish;
    18.         }

    四、返回容器中的相关参数

    _end_of_storage表示的是容器中当前开辟的空间的最后位置的迭代器。

    _start表示的是当前的容器的首元素的位置

    _finish表示的当前容器中最后一个元素的下一个位置

    capacity表示的是当前容器的容量大小

    size表示的是当前容器中存储的元素个数

    1.         size_t capacity() const
    2.         {
    3.             return _end_of_storage-_start;
    4.         }
    5.         size_t  size() const
    6.         {
    7.             return _finish-_start;
    8.         }

    五、交换函数

    对我们两个容器中的每一个成员变量都进行交换，交换可以直接调用我们的std中的交换函数。

    1.         void swap(vector& v)
    2.         {
    3.             std::swap(_start, v._start);
    4.             std::swap(_finish, v._finish);
    5.             std::swap(_end_of_storage, v._endOfStorage);
    6.         }

    六、拷贝构造

    1.拷贝指定范围的数据

    1. //将要拷贝的迭代器的范围传入
    2.         vector(iterator first,iterator last)
    3.                 :_start(nullptr)
    4.                 ,_finish(nullptr)
    5.                 ,_end_of_storage(nullptr)
    6.         {
    7.             reserve(last-first+1);
    8.             iterator it=begin();
    9.             for(int i=0;i
    10.             {
    11.                 *it=*(first+i);
    12.                 it++;
    13.             }
    14.             _finish=_start+(last-first);
    15.         }
    16.

    测试代码 

    1. void myvector_test9()
    2.     {
    3.         vector<int> v1;
    4.         v1.push_back(1);
    5.         v1.push_back(2);
    6.         vector<int> v2(v1.begin(),v1.end());
    7.         cout<1]<
    8.     }

    2.拷贝构造 

    1.         vector(const vector& v)
    2.                 : _start(nullptr)
    3.                 , _finish(nullptr)
    4.                 , _end_of_storage(nullptr)
    5.         {
    6.             reserve(v.capacity());
    7.             iterator it = begin();
    8.             const_iterator vit = v.begin();
    9.             while (vit != v.end())
    10.             {
    11.                 *it++ = *vit++;
    12.             }
    13.             _finish = it;
    14.         }

    测试代码

    1. void myvector_test8()
    2.     {
    3.         vector<int> v1;
    4.         v1.push_back(1);
    5.         v1.push_back(2);
    6.         vector<int> v2(v1);
    7.         vector<int>::iterator it=v2.begin();
    8.         while(it!=v2.end())
    9.         {
    10.             cout<<*it<<" ";
    11.             it++;
    12.         }
    13.         cout<
    14.     }

    3.使用=拷贝构造

    这里我们可以采用和之前字符串中一样的老板式的写法

    由于编译器在将v传过来的时候会拷贝构造一个v，将这个v与我们当前的容器中的内容交换一下，我们的当前容器就完成拷贝了

    1.         vector&operator =(vector v)
    2.         {
    3.             swap(v);
    4.             return *this;
    5.         }
    1.  void myvector_test10()
    2.     {
    3.         vector<int> v1;
    4.         v1.push_back(1);
    5.         v1.push_back(2);
    6.         vector<int> v2=v1;
    7.         vector<int>::iterator it1=v1.begin();
    8.         while(it1!=v1.end())
    9.         {
    10.             cout<<*it1<<" ";
    11.             it1++;
    12.         }
    13.         cout<
    14.         vector<int>::iterator it2=v2.begin();
    15.         while(it2!=v2.end())
    16.         {
    17.             cout<<*it2<<" ";
    18.             it2++;
    19.         }
    20.         cout<
    21.     }

     

    七、扩容操作

    1.reserve扩容

    reserve如果传入的数据比当前的空间大小小的话是不会处理的。

    1. //开辟n个空间
    2.         void reserve(size_t n)
    3.         {
    4.             if(n>capacity())
    5.             {
    6.                 size_t  sz=size();
    7.                 T*tmp=new T[n];
    8.                 if(_start)
    9.                 {
    10.                     memcpy(tmp,_start,sizeof(T)*size());
    11.                     delete[] _start;
    12.                 }
    13.                 _start=tmp;
    14.                 _finish=_start+sz;
    15.                 //由于上面的过程中我们将原先的_start给销毁了，新的_start变成了tmp
    16.                 //所以其size可能会发生变化，
    17. //                _finish=_start+size();
    18.                 _end_of_storage=_start+n;
    19.             }
    20.         }

    2.resize调整大小

    1.         //resize第一个参数是要调整到的大小，第二个参数是如果调整出来的大小大于了原来的数据用什么值填充
    2.         void resize(size_t n,const T&value=T())
    3.         {
    4.             //1.如果n小于当前的size，则数据个数缩小到n
    5.             if(n<=size())
    6.             {
    7.                 _finish=_start+n;
    8.                 return;
    9.             }
    10.             //2.空间不够则增容
    11.             if(n>capacity())
    12.             {
    13.                 reserve(n);
    14.             }
    15.             //3.将size扩大到n
    16.             iterator it=_finish;
    17.             _finish=_start+n;
    18.             while(it!=_finish)
    19.             {
    20.                 *it=value;
    21.                 ++it;
    22.             }
    23.  
    24.         }

    测试代码

    1. void myvector_test11()
    2.     {
    3.         vector<int> v1;
    4.         v1.push_back(1);
    5.         v1.push_back(2);
    6.         v1.push_back(3);
    7.         v1.push_back(4);
    8.         vector<int>::iterator it1=v1.begin();
    9.         while(it1!=v1.end())
    10.         {
    11.             cout<<*it1<<" ";
    12.             it1++;
    13.         }
    14.         cout<
    15.         vector<int>v2=v1;
    16.         v1.resize(7,5);
    17.         vector<int>::iterator it2=v1.begin();
    18.         while(it2!=v1.end())
    19.         {
    20.             cout<<*it2<<" ";
    21.             it2++;
    22.         }
    23.         cout<
    24.     }

    八、让我们的容器支持随机读写

    我们分别需要提供const类型的和非const类型的。

    1. const T&operator [](size_t pos) const
    2.         {
    3.             assert(pos<size());
    4.             return _start[pos];
    5.         }
    6.  
    7.         T&operator [](size_t pos)
    8.         {
    9.             assert(pos<size());
    10.             return _start[pos];
    11.         }

    九、尾插尾删 

    1.尾插push_back

    尾插要注意扩容

    1. //使用泛型，输入的是T类型
    2.         void push_back(const T&x)
    3.         {
    4.             if(_finish==_end_of_storage)
    5.             {
    6.  
    7.                 reserve(capacity()==0?4 :capacity()*2);
    8.  
    9.             }
    10.             //finish是最后一个数据的下一个位置
    11.             *_finish=x;
    12.             ++_finish;
    13.         }

    2.尾删 pop_back

    尾删我们需要先判断一下当前的容器还有没有元素

    1.         void pop_back()
    2.         {
    3.             assert(_finish>_start);
    4.             --_finish;
    5.         }

    3.将容器后面追加n个元素，元素为value 

    1.   vector v;
    2. //        如果下面的这个push_back不加const，就会报错，因为拷贝的这个字符串具有隐式类型转换
    3. //        期间会生成一个中间的临时变量，而这个临时变量具有常性。如果不加const会发生权限的扩大。
    4. //        v.push_back("xxxx")
    5.         vector(size_t n, const T& value = T())
    6.                 : _start(nullptr)
    7.                 , _finish(nullptr)
    8.                 , _end_of_storage(nullptr)
    9.         {
    10.             reserve(n);
    11.             while (n--)
    12.             {
    13.                 push_back(value);
    14.             }
    15.         }

    测试代码 

    1. //使用迭代器遍历容器 
    2. void Func(const vector<int>&v)
    3.     {
    4.         vector<int>::const_iterator it=v.begin();
    5.         while(it!=v.end())
    6.         {
    7.             cout<<*it<<" ";
    8.             ++it;
    9.         }
    10.         cout<
    11.     }
    12.     void myvector_test1()
    13.     {
    14.  
    15.         vector<int> v;
    16.         v.push_back(1);
    17.         v.push_back(2);
    18.         v.push_back(3);
    19.         v.push_back(4);
    20.         v.push_back(5);
    21. //使用随机读取的方式遍历
    22.         for(size_t i=0;isize();++i)
    23.         {
    24.             cout<" ";
    25.         }
    26.         cout<
    27.         vector<int>::iterator it=v.begin();
    28.         while(it!=v.end())
    29.         {
    30.             cout<<*it<<" ";
    31.             ++it;
    32.         }
    33.         cout<
    34.  
    35.         //使用范围for的形式遍历容器
    36.         //有了迭代器就支持范围for,也就是调用我们的v.begin()，v.end()来执行相关的操作
    37.         //const的话就走const的迭代器，
    38.         for(auto e:v)
    39.         {
    40.             cout<" ";
    41.         }
    42.         v.pop_back();
    43.         cout<
    44.  
    45.         Func(v);
    46.     }

    十、随机位置插入和删除 

    1.随机位置插入insert

    迭代器失效就是当我们尾插数据的时候，如果发生了扩容，原来的地址空间可能就被转换到了一块更大的空间，所以我们迭代器的指针就失效了。所以我们如果发生了扩容就要及时更新指针。

    1. //        void insert(iterator &pos ,const T& x)
    2.         void insert(iterator pos ,const T& x)
    3.         {
    4.             assert(pos>=_start);
    5.             //等于finish就是尾插
    6.             assert(pos<=_finish);
    7.             if(_finish==_end_of_storage)
    8.             {
    9.                 //如果发生了扩容就要重新调整我们的pos指针的位置，不然就会发生迭代器失效的问题
    10.                 size_t len=pos-_start;
    11.                 reserve(capacity()==0? 4:capacity()*2);
    12.                 //形参是实参的拷贝，并不会真正去改变我们外部的pos
    13.                 //仅仅只能保证我们下面的pos使用是正常的
    14.                 pos=_start+len;
    15.             }
    16.             //挪动数据
    17.             iterator end=_finish -1;
    18.             while(end>=pos)
    19.             {
    20.                 *(end+1)=*end;
    21.                 --end;
    22.             }
    23.             *pos=x;
    24.             ++_finish;
    25.         }

    2.随机位置擦除 

    随机位置擦除的话可以使用缩容来优化我们过大的空间，但是这是一种时间换空间的做法，一般不用做。可以将下面代码中的缩容那部分注释掉。

    1.         //stl规定erase返回删除位置的下一个位置迭代器
    2.         iterator erase(iterator pos)
    3.         {
    4.             assert(pos>=_start);
    5.             assert(pos<_finish);
    6.  
    7.             iterator begin=pos+1;
    8.             //将当前位置不断挪动到前一个位置
    9.             while(begin<_finish)
    10.             {
    11.                 *(begin-1)=*begin;
    12.                 ++begin;
    13.             }
    14.             --_finish;
    15.  
    16.             if(size()<capacity()/2)
    17.             {
    18.                 //缩容，以时间换空间。
    19.                 _end_of_storage=_start+capacity()/2;
    20.             }
    21.             return pos;
    22.         }

    3.清除函数clear 

    1）写法一：调用erase

    1.         void clear()
    2.         {
    3.             while(_finish!=_start)
    4.             {
    5.                 erase(_start);
    6.             }
    7.         }

    2）写法二：直接将_finish=_start

    1.         void clear()
    2.         {
    3.             _finish = _start;
    4.         }

    测试代码

    1. void myvector_test3()
    2.     {
    3.         vector<int> v;
    4.         v.push_back(1);
    5.         v.push_back(2);
    6.         v.push_back(3);
    7.         v.push_back(4);
    8. //    v.push_back(5);
    9.  
    10.         for(size_t i=0;isize();++i)
    11.         {
    12.             cout<" ";
    13.         }
    14.         cout<
    15.  
    16.         v.erase(v.begin());
    17.         for(size_t i=0;isize();++i)
    18.         {
    19.             cout<" ";
    20.         }
    21.         cout<
    22.     }

    测试代码（clear）

    1.  void myvector_test13()
    2.     {
    3.         vector<int> v1;
    4.         v1.push_back(1);
    5.         v1.push_back(2);
    6.         v1.push_back(3);
    7.         vector<int>::iterator it=v1.begin();
    8.         while(it!=v1.end())
    9.         {
    10.             cout<<*it<<" ";
    11.             it++;
    12.         }
    13.         cout<
    14.         v1.clear();
    15.         vector<int>::iterator it2=v1.begin();
    16.         while(it2!=v1.end())
    17.         {
    18.             cout<<*it2<<" ";
    19.             it2++;
    20.         }
    21.         cout<
    22.     }

    为什么要返回删除位置的下一个位置的迭代器？ 

    观察下面几个代码的变化和问题

    1.  void myvector_test4()
    2.     {
    3.         //正常运行
    4.         vector<int> v;
    5.         v.push_back(1);
    6.         v.push_back(2);
    7.         v.push_back(3);
    8.         v.push_back(4);
    9.         v.push_back(5);
    10.  
    11.         //要求删除所有的偶数
    12.         auto it=v.begin();
    13.         while(it!=v.end())
    14.         {
    15.             if(*it%2==0)
    16.             {
    17.                 v.erase(it);
    18.             }
    19.             ++it;
    20.         }
    21.  
    22.         for(size_t i=0;isize();++i)
    23.         {
    24.             cout<" ";
    25.         }
    26.         cout<
    27.     }

    相比于上面 这里我们少push_back了5

    1.  //崩溃
    2.     void myvector_test5()
    3.     {
    4.         vector<int> v;
    5.         v.push_back(1);
    6.         v.push_back(2);
    7.         v.push_back(3);
    8.         v.push_back(4);
    9.  
    10.         //要求删除所有的偶数
    11.         auto it=v.begin();
    12.         while(it!=v.end())
    13.         {
    14.             if(*it%2==0)
    15.             {
    16.                 v.erase(it);
    17.             }
    18.             ++it;
    19.         }
    20.         for(size_t i=0;isize();++i)
    21.         {
    22.             cout<" ";
    23.         }
    24.         cout<
    25.     }

     ​​​​​​​

    1. //4删不掉
    2.     void myvector_test6()
    3.     {
    4.         //正常运行
    5.         vector<int> v;
    6.         v.push_back(1);
    7.         v.push_back(2);
    8.         v.push_back(4);
    9.         v.push_back(3);
    10.         v.push_back(4);
    11.         v.push_back(5);
    12.         v.push_back(5);
    13.         
    14.         //要求删除所有的偶数
    15.         auto it=v.begin();
    16.         while(it!=v.end())
    17.         {
    18.             if(*it%2==0)
    19.             {
    20.                 v.erase(it);
    21.             }
    22.             ++it;
    23.         }
    24.  
    25.         for(size_t i=0;isize();++i)
    26.         {
    27.             cout<" ";
    28.         }
    29.         cout<
    30.     }

    这里的4我们没删掉 

     正确的使用方式是我们在erase的时候就要同步更新我们的pos

    1.  void myvector_test7()
    2.     {
    3.         //正常运行
    4.         vector<int> v;
    5.         v.push_back(1);
    6.         v.push_back(2);
    7.         v.push_back(4);
    8.         v.push_back(3);
    9.         v.push_back(4);
    10.         v.push_back(5);
    11.  
    12.         //要求删除所有的偶数
    13.         auto it=v.begin();
    14.         while(it!=v.end())
    15.         {
    16.             if(*it%2==0)
    17.             {
    18.                 //同步更新我们的it
    19.                 //如果删除了某个数据，it迭代器就不要继续往后走了
    20.                 //因为后面的数据会移动上来，it迭代器当前指向位置并没有检查过
    21.                 it=v.erase(it);
    22.             }
    23.             else
    24.             {
    25.                 ++it;
    26.             }
    27.  
    28.         }
    29.         for(size_t i=0;isize();++i)
    30.         {
    31.             cout<" ";
    32.         }
    33.         cout<
    34.     }
    35.     //结论：insert/erase pos位置，不要直接访问pos。
    36.     // 一定要更新，直接访问，可能会出现各种出乎意料的结果
    37.     //这就是pos所谓的迭代器失效。
    38.     //认为pos失效，不要访问。
    39.     //结果不同的底层实现可能不一样。

    十一、迭代器的失效问题

    迭代器失效就是当我们尾插数据的时候，如果发生了扩容，原来的地址空间可能就被转换到了一块更大的空间，所以我们迭代器的指针就失效了。

    1. //迭代器失效问题
    2.     void myvector_test2()
    3.     {
    4.         vector<int> v;
    5.         v.push_back(1);
    6.         v.push_back(2);
    7.         v.push_back(3);
    8.         v.push_back(4);
    9. //    v.push_back(5);
    10.  
    11.         for(size_t i=0;isize();++i)
    12.         {
    13.             cout<" ";
    14.         }
    15.         cout<
    16.  
    17.         //这里由于我们之前扩容的写法（在上面的push_back中看），是初始开辟四个，然后超出的话空间直接乘以两倍，所以我们在第五个数据插入的时候就会发生扩容
    18.         //在vector发生扩容的时候，我们的迭代器的指针就失效了，就会发生迭代器失效的问题
    19.         auto p=find(v.begin(),v.end(),3);
    20.         if(p!=v.end())
    21.         {
    22.             //在p位置插入数据以后，不要访问p，因为p可能失效
    23.             v.insert(p,30);
    24.             cout<<*p<
    25.             //因为上面的insert30的时候p的指针已经失效了，所以会报错
    26.             v.insert(p,40);
    27.         }
    28.  
    29.         vector<int>::iterator it=v.begin();
    30.         while(it!=v.end())
    31.         {
    32.             cout<<*it<<" ";
    33.             ++it;
    34.         }
    35.         //如果上面的insert加了引用，下面这个代码就会报错。
    36.         //传值返回的都是数据的临时拷贝，这个拷贝具有常性，不能被修改，会报错
    37.         v.insert(v.begin(),1);
    38.     }

    问题的解决 

     我们同样可以仿照erase中的写法，将我们insert函数中当前的扩容之后的对应位置的迭代器返回，然后及时同步迭代器，从而解决这个问题。

    1.         iterator insert(iterator pos ,const T& x)
    2.         {
    3.             assert(pos>=_start);
    4.             //等于finish就是尾插
    5.             assert(pos<=_finish);
    6.             if(_finish==_end_of_storage)
    7.             {
    8.                 //如果发生了扩容就要重新调整我们的pos指针的位置，不然就会发生迭代器失效的问题
    9.                 size_t len=pos-_start;
    10.                 reserve(capacity()==0? 4:capacity()*2);
    11.                 //形参是实参的拷贝，并不会真正去改变pos
    12.                 pos=_start+len;
    13.             }
    14.             //挪动数据
    15.             iterator end=_finish -1;
    16.             while(end>=pos)
    17.             {
    18.                 *(end+1)=*end;
    19.                 --end;
    20.             }
    21.             *pos=x;
    22.             ++_finish;
    23.             return pos;
    24.         }

    测试代码

    1. //迭代器失效问题
    2.     void myvector_test12()
    3.     {
    4.         vector<int> v;
    5.         v.push_back(1);
    6.         v.push_back(2);
    7.         v.push_back(3);
    8.         v.push_back(4);
    9. //    v.push_back(5);
    10.  
    11.         for(size_t i=0;isize();++i)
    12.         {
    13.             cout<" ";
    14.         }
    15.         cout<
    16.  
    17.         //在vector发生扩容的时候，我们的迭代器的指针就失效了，就会发生迭代器失效的问题
    18.         auto p=find(v.begin(),v.end(),3);
    19.         if(p!=v.end())
    20.         {
    21.             //在p位置插入数据以后，及时同步指针
    22.             p=v.insert(p,30);
    23.             for(size_t i=0;isize();++i)
    24.             {
    25.                 cout<" ";
    26.             }
    27.             cout<
    28.             p=v.insert(p,40);
    29.         }
    30.  
    31.         vector<int>::iterator it=v.begin();
    32.         while(it!=v.end())
    33.         {
    34.             cout<<*it<<" ";
    35.             ++it;
    36.         }
    37.     }

    十二、主程序代码汇总 

    1.  
    2. #ifndef VECTORTEST_MYVECTOR_H
    3. #define VECTORTEST_MYVECTOR_H
    4. #pragma once
    5. #include 
    6. #include 
    7. namespace zhuyuan
    8. {
    9.     template<class T>
    10.     class vector
    11.     {
    12.     public:
    13.         typedef T* iterator;
    14.         const typedef T* const_iterator;
    15.         iterator begin()
    16.         {
    17.             return _start;
    18.         }
    19.         const iterator begin() const
    20.         {
    21.             return _start;
    22.         }
    23.         iterator end()
    24.         {
    25.             return _finish;
    26.         }
    27.         const iterator end() const
    28.         {
    29.             return _finish;
    30.         }
    31.         vector()
    32.             :_start(nullptr)
    33.             ,_finish(nullptr)
    34.             ,_end_of_storage(nullptr)
    35.         {
    36.  
    37.         }
    38.  
    39.         ~vector()
    40.         {
    41.             delete[] _start;
    42.             _start=_finish=_end_of_storage= nullptr;
    43.         }
    44.  
    45.         size_t capacity() const
    46.         {
    47.             return _end_of_storage-_start;
    48.         }
    49.         size_t  size() const
    50.         {
    51.             return _finish-_start;
    52.         }
    53. //        vector v;
    54. //        如果下面的这个push_back不加const，就会报错，因为拷贝的这个字符串具有隐式类型转换
    55. //        期间会生成一个中间的临时变量，而这个临时变量具有常性。如果不加const会发生权限的扩大。
    56. //        v.push_back("xxxx")
    57.         vector(size_t n, const T& value = T())
    58.                 : _start(nullptr)
    59.                 , _finish(nullptr)
    60.                 , _end_of_storage(nullptr)
    61.         {
    62.             reserve(n);
    63.             while (n--)
    64.             {
    65.                 push_back(value);
    66.             }
    67.         }
    68.         vector(iterator first,iterator last)
    69.                 :_start(nullptr)
    70.                 ,_finish(nullptr)
    71.                 ,_end_of_storage(nullptr)
    72.         {
    73.             reserve(last-first+1);
    74.             iterator it=begin();
    75.             for(int i=0;i
    76.             {
    77.                 *it=*(first+i);
    78.                 it++;
    79.             }
    80.             _finish=_start+(last-first);
    81.         }
    82.  
    83.         vector(const vector& v)
    84.                 : _start(nullptr)
    85.                 , _finish(nullptr)
    86.                 , _end_of_storage(nullptr)
    87.         {
    88.             reserve(v.capacity());
    89.             iterator it = begin();
    90.             const_iterator vit = v.begin();
    91.             while (vit != v.end())
    92.             {
    93.                 *it++ = *vit++;
    94.             }
    95.             _finish = it;
    96.         }
    97.         vector&operator =(vector v)
    98.         {
    99.             swap(v);
    100.             return *this;
    101.         }
    102.         void swap(vector& v)
    103.         {
    104.             std::swap(_start, v._start);
    105.             std::swap(_finish, v._finish);
    106.             std::swap(_end_of_storage, v._endOfStorage);
    107.         }
    108.         //开辟n个空间
    109.         void reserve(size_t n)
    110.         {
    111.             if(n>capacity())
    112.             {
    113.                 size_t  sz=size();
    114.                 T*tmp=new T[n];
    115.                 if(_start)
    116.                 {
    117.                     memcpy(tmp,_start,sizeof(T)*size());
    118.                     delete[] _start;
    119.                 }
    120.                 _start=tmp;
    121.                 _finish=_start+sz;
    122.                 //由于上面的过程中我们将原先的_start给销毁了，新的_start变成了tmp
    123.                 //所以其size可能会发生变化，
    124. //                _finish=_start+size();
    125.                 _end_of_storage=_start+n;
    126.             }
    127.         }
    128.         //resize第一个参数是要调整到的大小，第二个参数是如果调整出来的大小大于了原来的数据用什么值填充
    129.         void resize(size_t n,const T&value=T())
    130.         {
    131.             //1.如果n小于当前的size，则数据个数缩小到n
    132.             if(n<=size())
    133.             {
    134.                 _finish=_start+n;
    135.                 return;
    136.             }
    137.             //2.空间不够则增容
    138.             if(n>capacity())
    139.             {
    140.                 reserve(n);
    141.             }
    142.             //3.将size扩大到n
    143.             iterator it=_finish;
    144.             _finish=_start+n;
    145.             while(it!=_finish)
    146.             {
    147.                 *it=value;
    148.                 ++it;
    149.             }
    150.  
    151.         }
    152.  
    153.         const T&operator [](size_t pos) const
    154.         {
    155.             assert(pos<size());
    156.             return _start[pos];
    157.         }
    158.  
    159.         T&operator [](size_t pos)
    160.         {
    161.             assert(pos<size());
    162.             return _start[pos];
    163.         }
    164.         //使用泛型，输入的是T类型
    165.         void push_back(const T&x)
    166.         {
    167.             if(_finish==_end_of_storage)
    168.             {
    169.  
    170.                 reserve(capacity()==0?4 :capacity()*2);
    171.  
    172.             }
    173.             //finish是最后一个数据的下一个位置
    174.             *_finish=x;
    175.             ++_finish;
    176.         }
    177.  
    178.         void pop_back()
    179.         {
    180.             assert(_finish>_start);
    181.             --_finish;
    182.         }
    183.  
    184. //        void insert(iterator &pos ,const T& x)
    185.         iterator insert(iterator pos ,const T& x)
    186.         {
    187.             assert(pos>=_start);
    188.             //等于finish就是尾插
    189.             assert(pos<=_finish);
    190.             if(_finish==_end_of_storage)
    191.             {
    192.                 //如果发生了扩容就要重新调整我们的pos指针的位置，不然就会发生迭代器失效的问题
    193.                 size_t len=pos-_start;
    194.                 reserve(capacity()==0? 4:capacity()*2);
    195.                 //形参是实参的拷贝，并不会真正去改变pos
    196.                 pos=_start+len;
    197.             }
    198.             //挪动数据
    199.             iterator end=_finish -1;
    200.             while(end>=pos)
    201.             {
    202.                 *(end+1)=*end;
    203.                 --end;
    204.             }
    205.             *pos=x;
    206.             ++_finish;
    207.             return pos;
    208.         }
    209.         //stl规定erase返回删除位置的下一个位置迭代器
    210.         iterator erase(iterator pos)
    211.         {
    212.             assert(pos>=_start);
    213.             assert(pos<_finish);
    214.  
    215.             iterator begin=pos+1;
    216.             //将当前位置不断挪动到前一个位置
    217.             while(begin<_finish)
    218.             {
    219.                 *(begin-1)=*begin;
    220.                 ++begin;
    221.             }
    222.             --_finish;
    223.  
    224.             if(size()<capacity()/2)
    225.             {
    226.                 //缩容，以时间换空间。
    227.                 _end_of_storage=_start+capacity()/2;
    228.             }
    229.             return pos;
    230.         }
    231.     private:
    232.         iterator _start;
    233.         //finish是最后一个数据的下一个位置
    234.         iterator _finish;
    235.         //_end_of_storage是我们整个vector的容量大小
    236.         iterator _end_of_storage;
    237.     };
    238.  
    239.  
    240. }
    241. #endif //VECTORTEST_MYVECTOR_H

    十三、测试程序代码汇总

    调用测试程序

    1. using namespace std;
    2. #include "myvector.h"
    3.  
    4. int main()
    5. {
    6.     try
    7.     {
    8.         zhuyuan::myvector_test1();
    9.     }
    10.     catch(std::exception&e)
    11.     {
    12.         std::cout<what()<
    13.     }
    14. }

    测试程序

    1.     void Func(const vector<int>&v)
    2.     {
    3.         vector<int>::const_iterator it=v.begin();
    4.         while(it!=v.end())
    5.         {
    6.             cout<<*it<<" ";
    7.             ++it;
    8.         }
    9.         cout<
    10.     }
    11.     void myvector_test1()
    12.     {
    13.  
    14.         vector<int> v;
    15.         v.push_back(1);
    16.         v.push_back(2);
    17.         v.push_back(3);
    18.         v.push_back(4);
    19.         v.push_back(5);
    20.  
    21.         for(size_t i=0;isize();++i)
    22.         {
    23.             cout<" ";
    24.         }
    25.         cout<
    26.         vector<int>::iterator it=v.begin();
    27.         while(it!=v.end())
    28.         {
    29.             cout<<*it<<" ";
    30.             ++it;
    31.         }
    32.         cout<
    33.  
    34.         //有了迭代器就支持范围for,也就是调用我们的v.begin()，v.end()来执行相关的操作
    35.         //const的话就走const的迭代器，
    36.         for(auto e:v)
    37.         {
    38.             cout<" ";
    39.         }
    40.         v.pop_back();
    41.         cout<
    42.  
    43.         Func(v);
    44.     }
    45. //迭代器失效问题
    46.     void myvector_test2()
    47.     {
    48.         vector<int> v;
    49.         v.push_back(1);
    50.         v.push_back(2);
    51.         v.push_back(3);
    52.         v.push_back(4);
    53. //    v.push_back(5);
    54.  
    55.         for(size_t i=0;isize();++i)
    56.         {
    57.             cout<" ";
    58.         }
    59.         cout<
    60.  
    61.         //在vector发生扩容的时候，我们的迭代器的指针就失效了，就会发生迭代器失效的问题
    62.         auto p=find(v.begin(),v.end(),3);
    63.         if(p!=v.end())
    64.         {
    65.             //在p位置插入数据以后，不要访问p，因为p可能失效
    66.             v.insert(p,30);
    67.             cout<<*p<
    68.             v.insert(p,40);
    69.         }
    70.  
    71.         vector<int>::iterator it=v.begin();
    72.         while(it!=v.end())
    73.         {
    74.             cout<<*it<<" ";
    75.             ++it;
    76.         }
    77.         //如果上面的insert加了引用，下面这个代码就会报错。
    78.         //传值返回的都是数据的临时拷贝，这个拷贝具有常性，不能被修改，会报错
    79.         v.insert(v.begin(),1);
    80.     }
    81.     void myvector_test3()
    82.     {
    83.         vector<int> v;
    84.         v.push_back(1);
    85.         v.push_back(2);
    86.         v.push_back(3);
    87.         v.push_back(4);
    88. //    v.push_back(5);
    89.  
    90.         for(size_t i=0;isize();++i)
    91.         {
    92.             cout<" ";
    93.         }
    94.         cout<
    95.  
    96.         v.erase(v.begin());
    97.         for(size_t i=0;isize();++i)
    98.         {
    99.             cout<" ";
    100.         }
    101.         cout<
    102.     }
    103.     void myvector_test4()
    104.     {
    105.         //正常运行
    106.         vector<int> v;
    107.         v.push_back(1);
    108.         v.push_back(2);
    109.         v.push_back(3);
    110.         v.push_back(4);
    111.         v.push_back(5);
    112.  
    113.         //要求删除所有的偶数
    114.         auto it=v.begin();
    115.         while(it!=v.end())
    116.         {
    117.             if(*it%2==0)
    118.             {
    119.                 v.erase(it);
    120.             }
    121.             ++it;
    122.         }
    123.  
    124.         for(size_t i=0;isize();++i)
    125.         {
    126.             cout<" ";
    127.         }
    128.         cout<
    129.     }
    130.  
    131.     //崩溃
    132.     void myvector_test5()
    133.     {
    134.         vector<int> v;
    135.         v.push_back(1);
    136.         v.push_back(2);
    137.         v.push_back(3);
    138.         v.push_back(4);
    139.  
    140.         //要求删除所有的偶数
    141.         auto it=v.begin();
    142.         while(it!=v.end())
    143.         {
    144.             cout<<"it"<<*it<
    145. //            cout<<*it<
    146.             if(*it%2==0)
    147.             {
    148.                 cout<<"end()"<end()-v.begin()<
    149.                 v.erase(it);
    150.             }
    151.             ++it;
    152.         }
    153.         for(size_t i=0;isize();++i)
    154.         {
    155.             cout<" ";
    156.         }
    157.         cout<
    158.     }
    159.     //4删不掉
    160.     void myvector_test6()
    161.     {
    162.         //正常运行
    163.         vector<int> v;
    164.         v.push_back(1);
    165.         v.push_back(2);
    166.         v.push_back(4);
    167.         v.push_back(3);
    168.         v.push_back(4);
    169.         v.push_back(5);
    170.         v.push_back(5);
    171.  
    172.         //要求删除所有的偶数
    173.         auto it=v.begin();
    174.         while(it!=v.end())
    175.         {
    176.             if(*it%2==0)
    177.             {
    178.                 v.erase(it);
    179.             }
    180.             ++it;
    181.         }
    182.  
    183.         for(size_t i=0;isize();++i)
    184.         {
    185.             cout<" ";
    186.         }
    187.         cout<
    188.     }
    189.     void myvector_test7()
    190.     {
    191.         //正常运行
    192.         vector<int> v;
    193.         v.push_back(1);
    194.         v.push_back(2);
    195.         v.push_back(4);
    196.         v.push_back(3);
    197.         v.push_back(4);
    198.         v.push_back(5);
    199.  
    200.         //要求删除所有的偶数
    201.         auto it=v.begin();
    202.         while(it!=v.end())
    203.         {
    204.             if(*it%2==0)
    205.             {
    206.                 it=v.erase(it);
    207.             }
    208.             else
    209.             {
    210.                 ++it;
    211.             }
    212.  
    213.         }
    214.         for(size_t i=0;isize();++i)
    215.         {
    216.             cout<" ";
    217.         }
    218.         cout<
    219.     }
    220.     //结论：insert/erase pos位置，不要直接访问pos。
    221.     // 一定要更新，直接访问，可能会出现各种出乎意料的结果
    222.     //这就是pos所谓的迭代器失效。
    223.     //认为pos失效，不要访问。
    224.     //结果不同的底层实现可能不一样。
    225.     void myvector_test8()
    226.     {
    227.         vector<int> v1;
    228.         v1.push_back(1);
    229.         v1.push_back(2);
    230.         vector<int> v2(v1);
    231.         vector<int>::iterator it=v2.begin();
    232.         while(it!=v2.end())
    233.         {
    234.             cout<<*it<<" ";
    235.             it++;
    236.         }
    237.         cout<
    238.     }
    239.  
    240.     void myvector_test9()
    241.     {
    242.         vector<int> v1;
    243.         v1.push_back(1);
    244.         v1.push_back(2);
    245.         vector<int> v2(v1.begin(),v1.end());
    246.         cout<1]<
    247.     }
    248.     void myvector_test10()
    249.     {
    250.         vector<int> v1;
    251.         v1.push_back(1);
    252.         v1.push_back(2);
    253.         vector<int> v2=v1;
    254.         vector<int>::iterator it1=v1.begin();
    255.         while(it1!=v1.end())
    256.         {
    257.             cout<<*it1<<" ";
    258.             it1++;
    259.         }
    260.         cout<
    261.         vector<int>::iterator it2=v2.begin();
    262.         while(it2!=v2.end())
    263.         {
    264.             cout<<*it2<<" ";
    265.             it2++;
    266.         }
    267.         cout<
    268.     }
    269.     void myvector_test11()
    270.     {
    271.         vector<int> v1;
    272.         v1.push_back(1);
    273.         v1.push_back(2);
    274.         v1.push_back(3);
    275.         v1.push_back(4);
    276.         vector<int>::iterator it1=v1.begin();
    277.         while(it1!=v1.end())
    278.         {
    279.             cout<<*it1<<" ";
    280.             it1++;
    281.         }
    282.         cout<
    283.         vector<int>v2=v1;
    284.         v1.resize(7,5);
    285.         vector<int>::iterator it2=v1.begin();
    286.         while(it2!=v1.end())
    287.         {
    288.             cout<<*it2<<" ";
    289.             it2++;
    290.         }
    291.         cout<
    292.     }
    293.  
    294.  
    295.     //迭代器失效问题
    296.     void myvector_test12()
    297.     {
    298.         vector<int> v;
    299.         v.push_back(1);
    300.         v.push_back(2);
    301.         v.push_back(3);
    302.         v.push_back(4);
    303. //    v.push_back(5);
    304.  
    305.         for(size_t i=0;isize();++i)
    306.         {
    307.             cout<" ";
    308.         }
    309.         cout<
    310.  
    311.         //在vector发生扩容的时候，我们的迭代器的指针就失效了，就会发生迭代器失效的问题
    312.         auto p=find(v.begin(),v.end(),3);
    313.         if(p!=v.end())
    314.         {
    315.             //在p位置插入数据以后，及时同步指针
    316.             p=v.insert(p,30);
    317.             for(size_t i=0;isize();++i)
    318.             {
    319.                 cout<" ";
    320.             }
    321.             cout<
    322.             p=v.insert(p,40);
    323.         }
    324.  
    325.         vector<int>::iterator it=v.begin();
    326.         while(it!=v.end())
    327.         {
    328.             cout<<*it<<" ";
    329.             ++it;
    330.         }
    331.     }

    十四、vector原码

    可以对照原码查看我们上面的模拟实现代码

    1. /*
    2.  *
    3.  * Copyright (c) 1994
    4.  * Hewlett-Packard Company
    5.  *
    6.  * Permission to use, copy, modify, distribute and sell this software
    7.  * and its documentation for any purpose is hereby granted without fee,
    8.  * provided that the above copyright notice appear in all copies and
    9.  * that both that copyright notice and this permission notice appear
    10.  * in supporting documentation.  Hewlett-Packard Company makes no
    11.  * representations about the suitability of this software for any
    12.  * purpose.  It is provided "as is" without express or implied warranty.
    13.  *
    14.  *
    15.  * Copyright (c) 1996
    16.  * Silicon Graphics Computer Systems, Inc.
    17.  *
    18.  * Permission to use, copy, modify, distribute and sell this software
    19.  * and its documentation for any purpose is hereby granted without fee,
    20.  * provided that the above copyright notice appear in all copies and
    21.  * that both that copyright notice and this permission notice appear
    22.  * in supporting documentation.  Silicon Graphics makes no
    23.  * representations about the suitability of this software for any
    24.  * purpose.  It is provided "as is" without express or implied warranty.
    25.  */
    26.  
    27. /* NOTE: This is an internal header file, included by other STL headers.
    28.  *   You should not attempt to use it directly.
    29.  */
    30.  
    31. #ifndef __SGI_STL_INTERNAL_VECTOR_H
    32. #define __SGI_STL_INTERNAL_VECTOR_H
    33.  
    34. __STL_BEGIN_NAMESPACE 
    35.  
    36. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
    37. #pragma set woff 1174
    38. #endif
    39.  
    40. template <class T, class Alloc = alloc>
    41. class vector {
    42. public:
    43.   typedef T value_type;
    44.   typedef value_type* pointer;
    45.   typedef const value_type* const_pointer;
    46.   typedef value_type* iterator;
    47.   typedef const value_type* const_iterator;
    48.   typedef value_type& reference;
    49.   typedef const value_type& const_reference;
    50.   typedef size_t size_type;
    51.   typedef ptrdiff_t difference_type;
    52.  
    53. #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
    54.   typedef reverse_iterator const_reverse_iterator;
    55.   typedef reverse_iterator reverse_iterator;
    56. #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
    57.   typedef reverse_iterator
    58.                            difference_type>  const_reverse_iterator;
    59.   typedef reverse_iterator
    60.           reverse_iterator;
    61. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
    62. protected:
    63.   typedef simple_alloc data_allocator;
    64.   iterator start;
    65.   iterator finish;
    66.   iterator end_of_storage;
    67.   void insert_aux(iterator position, const T& x);
    68.   void deallocate() {
    69.     if (start) data_allocator::deallocate(start, end_of_storage - start);
    70.   }
    71.  
    72.   void fill_initialize(size_type n, const T& value) {
    73.     start = allocate_and_fill(n, value);
    74.     finish = start + n;
    75.     end_of_storage = finish;
    76.   }
    77. public:
    78.   iterator begin() { return start; }
    79.   const_iterator begin() const { return start; }
    80.   iterator end() { return finish; }
    81.   const_iterator end() const { return finish; }
    82.   reverse_iterator rbegin() { return reverse_iterator(end()); }
    83.   const_reverse_iterator rbegin() const { 
    84.     return const_reverse_iterator(end()); 
    85.   }
    86.   reverse_iterator rend() { return reverse_iterator(begin()); }
    87.   const_reverse_iterator rend() const { 
    88.     return const_reverse_iterator(begin()); 
    89.   }
    90.   size_type size() const { return size_type(end() - begin()); }
    91.   size_type max_size() const { return size_type(-1) / sizeof(T); }
    92.   size_type capacity() const { return size_type(end_of_storage - begin()); }
    93.   bool empty() const { return begin() == end(); }
    94.   reference operator[](size_type n) { return *(begin() + n); }
    95.   const_reference operator[](size_type n) const { return *(begin() + n); }
    96.  
    97.   vector() : start(0), finish(0), end_of_storage(0) {}
    98.   vector(size_type n, const T& value) { fill_initialize(n, value); }
    99.   vector(int n, const T& value) { fill_initialize(n, value); }
    100.   vector(long n, const T& value) { fill_initialize(n, value); }
    101.   explicit vector(size_type n) { fill_initialize(n, T()); }
    102.  
    103.   vector(const vector& x) {
    104.     start = allocate_and_copy(x.end() - x.begin(), x.begin(), x.end());
    105.     finish = start + (x.end() - x.begin());
    106.     end_of_storage = finish;
    107.   }
    108. #ifdef __STL_MEMBER_TEMPLATES
    109.   template <class InputIterator>
    110.   vector(InputIterator first, InputIterator last) :
    111.     start(0), finish(0), end_of_storage(0)
    112.   {
    113.     range_initialize(first, last, iterator_category(first));
    114.   }
    115. #else /* __STL_MEMBER_TEMPLATES */
    116.   vector(const_iterator first, const_iterator last) {
    117.     size_type n = 0;
    118.     distance(first, last, n);
    119.     start = allocate_and_copy(n, first, last);
    120.     finish = start + n;
    121.     end_of_storage = finish;
    122.   }
    123. #endif /* __STL_MEMBER_TEMPLATES */
    124.   ~vector() { 
    125.     destroy(start, finish);
    126.     deallocate();
    127.   }
    128.   vector& operator=(const vector& x);
    129.   void reserve(size_type n) {
    130.     if (capacity() < n) {
    131.       const size_type old_size = size();
    132.       iterator tmp = allocate_and_copy(n, start, finish);
    133.       destroy(start, finish);
    134.       deallocate();
    135.       start = tmp;
    136.       finish = tmp + old_size;
    137.       end_of_storage = start + n;
    138.     }
    139.   }
    140.   reference front() { return *begin(); }
    141.   const_reference front() const { return *begin(); }
    142.   reference back() { return *(end() - 1); }
    143.   const_reference back() const { return *(end() - 1); }
    144.   void push_back(const T& x) {
    145.     if (finish != end_of_storage) {
    146.       construct(finish, x);
    147.       ++finish;
    148.     }
    149.     else
    150.       insert_aux(end(), x);
    151.   }
    152.   void swap(vector& x) {
    153.     __STD::swap(start, x.start);
    154.     __STD::swap(finish, x.finish);
    155.     __STD::swap(end_of_storage, x.end_of_storage);
    156.   }
    157.   iterator insert(iterator position, const T& x) {
    158.     size_type n = position - begin();
    159.     if (finish != end_of_storage && position == end()) {
    160.       construct(finish, x);
    161.       ++finish;
    162.     }
    163.     else
    164.       insert_aux(position, x);
    165.     return begin() + n;
    166.   }
    167.   iterator insert(iterator position) { return insert(position, T()); }
    168. #ifdef __STL_MEMBER_TEMPLATES
    169.   template <class InputIterator>
    170.   void insert(iterator position, InputIterator first, InputIterator last) {
    171.     range_insert(position, first, last, iterator_category(first));
    172.   }
    173. #else /* __STL_MEMBER_TEMPLATES */
    174.   void insert(iterator position,
    175.               const_iterator first, const_iterator last);
    176. #endif /* __STL_MEMBER_TEMPLATES */
    177.  
    178.   void insert (iterator pos, size_type n, const T& x);
    179.   void insert (iterator pos, int n, const T& x) {
    180.     insert(pos, (size_type) n, x);
    181.   }
    182.   void insert (iterator pos, long n, const T& x) {
    183.     insert(pos, (size_type) n, x);
    184.   }
    185.  
    186.   void pop_back() {
    187.     --finish;
    188.     destroy(finish);
    189.   }
    190.   iterator erase(iterator position) {
    191.     if (position + 1 != end())
    192.       copy(position + 1, finish, position);
    193.     --finish;
    194.     destroy(finish);
    195.     return position;
    196.   }
    197.   iterator erase(iterator first, iterator last) {
    198.     iterator i = copy(last, finish, first);
    199.     destroy(i, finish);
    200.     finish = finish - (last - first);
    201.     return first;
    202.   }
    203.   void resize(size_type new_size, const T& x) {
    204.     if (new_size < size()) 
    205.       erase(begin() + new_size, end());
    206.     else
    207.       insert(end(), new_size - size(), x);
    208.   }
    209.   void resize(size_type new_size) { resize(new_size, T()); }
    210.   void clear() { erase(begin(), end()); }
    211.  
    212. protected:
    213.   iterator allocate_and_fill(size_type n, const T& x) {
    214.     iterator result = data_allocator::allocate(n);
    215.     __STL_TRY {
    216.       uninitialized_fill_n(result, n, x);
    217.       return result;
    218.     }
    219.     __STL_UNWIND(data_allocator::deallocate(result, n));
    220.   }
    221.  
    222. #ifdef __STL_MEMBER_TEMPLATES
    223.   template <class ForwardIterator>
    224.   iterator allocate_and_copy(size_type n,
    225.                              ForwardIterator first, ForwardIterator last) {
    226.     iterator result = data_allocator::allocate(n);
    227.     __STL_TRY {
    228.       uninitialized_copy(first, last, result);
    229.       return result;
    230.     }
    231.     __STL_UNWIND(data_allocator::deallocate(result, n));
    232.   }
    233. #else /* __STL_MEMBER_TEMPLATES */
    234.   iterator allocate_and_copy(size_type n,
    235.                              const_iterator first, const_iterator last) {
    236.     iterator result = data_allocator::allocate(n);
    237.     __STL_TRY {
    238.       uninitialized_copy(first, last, result);
    239.       return result;
    240.     }
    241.     __STL_UNWIND(data_allocator::deallocate(result, n));
    242.   }
    243. #endif /* __STL_MEMBER_TEMPLATES */
    244.  
    245.  
    246. #ifdef __STL_MEMBER_TEMPLATES
    247.   template <class InputIterator>
    248.   void range_initialize(InputIterator first, InputIterator last,
    249.                         input_iterator_tag) {
    250.     for ( ; first != last; ++first)
    251.       push_back(*first);
    252.   }
    253.  
    254.   // This function is only called by the constructor.  We have to worry
    255.   //  about resource leaks, but not about maintaining invariants.
    256.   template <class ForwardIterator>
    257.   void range_initialize(ForwardIterator first, ForwardIterator last,
    258.                         forward_iterator_tag) {
    259.     size_type n = 0;
    260.     distance(first, last, n);
    261.     start = allocate_and_copy(n, first, last);
    262.     finish = start + n;
    263.     end_of_storage = finish;
    264.   }
    265.  
    266.   template <class InputIterator>
    267.   void range_insert(iterator pos,
    268.                     InputIterator first, InputIterator last,
    269.                     input_iterator_tag);
    270.  
    271.   template <class ForwardIterator>
    272.   void range_insert(iterator pos,
    273.                     ForwardIterator first, ForwardIterator last,
    274.                     forward_iterator_tag);
    275.  
    276. #endif /* __STL_MEMBER_TEMPLATES */
    277. };
    278.  
    279. template <class T, class Alloc>
    280. inline bool operator==(const vector& x, const vector& y) {
    281.   return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
    282. }
    283.  
    284. template <class T, class Alloc>
    285. inline bool operator<(const vector& x, const vector& y) {
    286.   return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
    287. }
    288.  
    289. #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
    290.  
    291. template <class T, class Alloc>
    292. inline void swap(vector& x, vector& y) {
    293.   x.swap(y);
    294. }
    295.  
    296. #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
    297.  
    298. template <class T, class Alloc>
    299. vector& vector::operator=(const vector& x) {
    300.   if (&x != this) {
    301.     if (x.size() > capacity()) {
    302.       iterator tmp = allocate_and_copy(x.end() - x.begin(),
    303.                                        x.begin(), x.end());
    304.       destroy(start, finish);
    305.       deallocate();
    306.       start = tmp;
    307.       end_of_storage = start + (x.end() - x.begin());
    308.     }
    309.     else if (size() >= x.size()) {
    310.       iterator i = copy(x.begin(), x.end(), begin());
    311.       destroy(i, finish);
    312.     }
    313.     else {
    314.       copy(x.begin(), x.begin() + size(), start);
    315.       uninitialized_copy(x.begin() + size(), x.end(), finish);
    316.     }
    317.     finish = start + x.size();
    318.   }
    319.   return *this;
    320. }
    321.  
    322. template <class T, class Alloc>
    323. void vector::insert_aux(iterator position, const T& x) {
    324.   if (finish != end_of_storage) {
    325.     construct(finish, *(finish - 1));
    326.     ++finish;
    327.     T x_copy = x;
    328.     copy_backward(position, finish - 2, finish - 1);
    329.     *position = x_copy;
    330.   }
    331.   else {
    332.     const size_type old_size = size();
    333.     const size_type len = old_size != 0 ? 2 * old_size : 1;
    334.     iterator new_start = data_allocator::allocate(len);
    335.     iterator new_finish = new_start;
    336.     __STL_TRY {
    337.       new_finish = uninitialized_copy(start, position, new_start);
    338.       construct(new_finish, x);
    339.       ++new_finish;
    340.       new_finish = uninitialized_copy(position, finish, new_finish);
    341.     }
    342.  
    343. #       ifdef  __STL_USE_EXCEPTIONS 
    344.     catch(...) {
    345.       destroy(new_start, new_finish); 
    346.       data_allocator::deallocate(new_start, len);
    347.       throw;
    348.     }
    349. #       endif /* __STL_USE_EXCEPTIONS */
    350.     destroy(begin(), end());
    351.     deallocate();
    352.     start = new_start;
    353.     finish = new_finish;
    354.     end_of_storage = new_start + len;
    355.   }
    356. }
    357.  
    358. template <class T, class Alloc>
    359. void vector::insert(iterator position, size_type n, const T& x) {
    360.   if (n != 0) {
    361.     if (size_type(end_of_storage - finish) >= n) {
    362.       T x_copy = x;
    363.       const size_type elems_after = finish - position;
    364.       iterator old_finish = finish;
    365.       if (elems_after > n) {
    366.         uninitialized_copy(finish - n, finish, finish);
    367.         finish += n;
    368.         copy_backward(position, old_finish - n, old_finish);
    369.         fill(position, position + n, x_copy);
    370.       }
    371.       else {
    372.         uninitialized_fill_n(finish, n - elems_after, x_copy);
    373.         finish += n - elems_after;
    374.         uninitialized_copy(position, old_finish, finish);
    375.         finish += elems_after;
    376.         fill(position, old_finish, x_copy);
    377.       }
    378.     }
    379.     else {
    380.       const size_type old_size = size();        
    381.       const size_type len = old_size + max(old_size, n);
    382.       iterator new_start = data_allocator::allocate(len);
    383.       iterator new_finish = new_start;
    384.       __STL_TRY {
    385.         new_finish = uninitialized_copy(start, position, new_start);
    386.         new_finish = uninitialized_fill_n(new_finish, n, x);
    387.         new_finish = uninitialized_copy(position, finish, new_finish);
    388.       }
    389. #         ifdef  __STL_USE_EXCEPTIONS 
    390.       catch(...) {
    391.         destroy(new_start, new_finish);
    392.         data_allocator::deallocate(new_start, len);
    393.         throw;
    394.       }
    395. #         endif /* __STL_USE_EXCEPTIONS */
    396.       destroy(start, finish);
    397.       deallocate();
    398.       start = new_start;
    399.       finish = new_finish;
    400.       end_of_storage = new_start + len;
    401.     }
    402.   }
    403. }
    404.  
    405. #ifdef __STL_MEMBER_TEMPLATES
    406.  
    407. template <class T, class Alloc> template <class InputIterator>
    408. void vector::range_insert(iterator pos,
    409.                                     InputIterator first, InputIterator last,
    410.                                     input_iterator_tag) {
    411.   for ( ; first != last; ++first) {
    412.     pos = insert(pos, *first);
    413.     ++pos;
    414.   }
    415. }
    416.  
    417. template <class T, class Alloc> template <class ForwardIterator>
    418. void vector::range_insert(iterator position,
    419.                                     ForwardIterator first,
    420.                                     ForwardIterator last,
    421.                                     forward_iterator_tag) {
    422.   if (first != last) {
    423.     size_type n = 0;
    424.     distance(first, last, n);
    425.     if (size_type(end_of_storage - finish) >= n) {
    426.       const size_type elems_after = finish - position;
    427.       iterator old_finish = finish;
    428.       if (elems_after > n) {
    429.         uninitialized_copy(finish - n, finish, finish);
    430.         finish += n;
    431.         copy_backward(position, old_finish - n, old_finish);
    432.         copy(first, last, position);
    433.       }
    434.       else {
    435.         ForwardIterator mid = first;
    436.         advance(mid, elems_after);
    437.         uninitialized_copy(mid, last, finish);
    438.         finish += n - elems_after;
    439.         uninitialized_copy(position, old_finish, finish);
    440.         finish += elems_after;
    441.         copy(first, mid, position);
    442.       }
    443.     }
    444.     else {
    445.       const size_type old_size = size();
    446.       const size_type len = old_size + max(old_size, n);
    447.       iterator new_start = data_allocator::allocate(len);
    448.       iterator new_finish = new_start;
    449.       __STL_TRY {
    450.         new_finish = uninitialized_copy(start, position, new_start);
    451.         new_finish = uninitialized_copy(first, last, new_finish);
    452.         new_finish = uninitialized_copy(position, finish, new_finish);
    453.       }
    454. #         ifdef __STL_USE_EXCEPTIONS
    455.       catch(...) {
    456.         destroy(new_start, new_finish);
    457.         data_allocator::deallocate(new_start, len);
    458.         throw;
    459.       }
    460. #         endif /* __STL_USE_EXCEPTIONS */
    461.       destroy(start, finish);
    462.       deallocate();
    463.       start = new_start;
    464.       finish = new_finish;
    465.       end_of_storage = new_start + len;
    466.     }
    467.   }
    468. }
    469.  
    470. #else /* __STL_MEMBER_TEMPLATES */
    471.  
    472. template <class T, class Alloc>
    473. void vector::insert(iterator position, 
    474.                               const_iterator first, 
    475.                               const_iterator last) {
    476.   if (first != last) {
    477.     size_type n = 0;
    478.     distance(first, last, n);
    479.     if (size_type(end_of_storage - finish) >= n) {
    480.       const size_type elems_after = finish - position;
    481.       iterator old_finish = finish;
    482.       if (elems_after > n) {
    483.         uninitialized_copy(finish - n, finish, finish);
    484.         finish += n;
    485.         copy_backward(position, old_finish - n, old_finish);
    486.         copy(first, last, position);
    487.       }
    488.       else {
    489.         uninitialized_copy(first + elems_after, last, finish);
    490.         finish += n - elems_after;
    491.         uninitialized_copy(position, old_finish, finish);
    492.         finish += elems_after;
    493.         copy(first, first + elems_after, position);
    494.       }
    495.     }
    496.     else {
    497.       const size_type old_size = size();
    498.       const size_type len = old_size + max(old_size, n);
    499.       iterator new_start = data_allocator::allocate(len);
    500.       iterator new_finish = new_start;
    501.       __STL_TRY {
    502.         new_finish = uninitialized_copy(start, position, new_start);
    503.         new_finish = uninitialized_copy(first, last, new_finish);
    504.         new_finish = uninitialized_copy(position, finish, new_finish);
    505.       }
    506. #         ifdef __STL_USE_EXCEPTIONS
    507.       catch(...) {
    508.         destroy(new_start, new_finish);
    509.         data_allocator::deallocate(new_start, len);
    510.         throw;
    511.       }
    512. #         endif /* __STL_USE_EXCEPTIONS */
    513.       destroy(start, finish);
    514.       deallocate();
    515.       start = new_start;
    516.       finish = new_finish;
    517.       end_of_storage = new_start + len;
    518.     }
    519.   }
    520. }
    521.  
    522. #endif /* __STL_MEMBER_TEMPLATES */
    523.  
    524. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
    525. #pragma reset woff 1174
    526. #endif
    527.  
    528. __STL_END_NAMESPACE 
    529.  
    530. #endif /* __SGI_STL_INTERNAL_VECTOR_H */
    531.  
    532. // Local Variables:
    533. // mode:C++
    534. // End:

  • 相关阅读:
    4.2冰达机器人：视觉实例-机器人视觉循线、视觉实例-调整循线颜色
    关于 Git 重写历史的一些笔记
    计算机毕业设计 基于SSM的在线预约导游系统的设计与实现 Java实战项目 附源码+文档+视频讲解
    Unity3d-异步加载场景、进度条加载
    基于SSM的智慧城市实验室主页系统的设计与实现
    spring中那些让你爱不释手的代码技巧（续集）
    tcp滑动窗口原理
    信钰证券：碧桂园大涨，石墨烯拉升
    GBase 8c结果集类型
    原子的核型结构及氢原子的波尔理论
  • 原文地址：https://blog.csdn.net/weixin_62684026/article/details/126335773