【C++标准模版库】模拟实现vector+迭代器失效问题

模拟实现vector

一.vector成员变量

成员变量：

1. iterator _start：指向vector的起始位置。
2. iterator _finish：指向vector的最后一个有效数据的下一个位置。
3. iterator _end_of_storage：指向vector可容纳最大数据个数的下一个位置。

大体结构如下：

namespace xzy
{//有模版不能分离到.h与.cpp文件，否则报链接错误template<classT>classvector{public:typedef T* iterator;private:
        iterator _start =nullptr;
        iterator _finish =nullptr;
        iterator _end_of_storage =nullptr;};}

二.构造函数

1.无参（默认）构造

类内函数拷贝构造，系统就不再提供默认构造，无法

vector<int> v;

需要自己提供默认构造，C++11中

vector() = default;

强制生成默认构造。

//C++11 强制生成默认构造//vector() = default;vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){}

2.有参构造

1. 迭代器区间构造：例如用list对象的迭代器区间构造vector对象。作用：例如由于list对象排序性能较低，利用vector的迭代器区间初始化list对象中相同的数据进行排序，可以提高性能。

//类模版的成员函数可以是函数模版template<classInputIterator>vector(InputIterator first, InputIterator last){while(first != last){push_back(*first);++first;}}intmain(){
    list<int>l1(10,1);//数据类型要求匹配，例如：都是int
    vector<int>v1(l1.begin(), l1.end());}

1. n个值为val初始化：

vector(size_t n,const T& val =T()){reserve(n);for(size_t i =0; i < n; i++){push_back(val);}}

解决办法：

3.拷贝构造

1.传统写法

vector(const vector<T>& v){
    _start =new T[v.capacity()];//memmove(_start, v._start, v.size() * sizeof(T));for(size_t i =0; i < v.size(); i++){
        _start[i]= v._start[i];}
    _finish = _start + v.size();
    _end_of_storage = _start + v.capacity();}

更好的写法：遍历vector进行尾插。

vector(const vector<T>& v){reserve(v.size());for(auto& e : v){push_back(e);}}

2.现代写法

voidswap(vector<T>& v){
    std::swap(_start, v._start);
    std::swap(_finish, v._finish);
    std::swap(_end_of_storage, v._end_of_storage);}vector(const vector<T>& v){
    vector<T>tmp(v.begin(), v.end());swap(tmp);}

三.vector对象的容量操作

1.size

size_t size()const{return _finish - _start;}

2.capacity

size_t capacity()const{return _end_of_storage - _start;}

3.clear

voidclear(){
    _finish = _start;}

4.empty

boolempty()const{return _start == _finish;}

5.reserve

扩容时：先开辟新空间，再将旧空间拷贝到空间，释放旧空间，最后修改数据。

但是这里存在一个坑，如下：

初始_start 和 _finish 为缺省值 nullptr。
_finish = _start + size() = _start + _finish - _start = _finish = nullptr——>程序崩溃。

正确代码如下：

voidreserve(size_t n){//第一种解决方法//if (n > capacity())//{//    T* tmp = new T[n];//    memmove(tmp, _start, sizeof(T) * size());//    delete[] _start;//    _finish = tmp + size();//    _start = tmp;//    _end_of_storage = _start + n;//}//第二种解决方法//if (n > capacity())//{//    size_t old_size = size();//    T* tmp = new T[n];//    memmove(tmp, _start, sizeof(T) * size());//    delete[] _start;//    _start = tmp;//    _finish = _start + old_size;//    _end_of_storage = _start + n;//}//第三种解决方法if(n >capacity()){//先保存有效数据个数
        size_t old_size =size();//开空间
        T* tmp =new T[n];//拷贝数据for(size_t i =0; i < old_size; i++){
            tmp[i]= _start[i];}//释放旧空间delete[] _start;//更新数据
        _start = tmp;
        _finish = _start + old_size;
        _end_of_storage = _start + n;}}

但是第一种与第二种方法在某些vector容器数据为自定义类型时存在浅拷贝问题如下图：

同理：拷贝构造使用的memmove也存在此问题。

6.resize

修改有效数据的个数时：若传入的参数小于有效数据的个数：删除数据即修改_finish即可；若传入的参数大于有效数据的个数：插入数据前考虑是否扩容。

voidresize(size_t n,const T& val =T()){if(n <size()){
        _finish = _start + n;}else{reserve(n);while(_finish < _start + n){*_finish = val;++_finish;}}}

四.vector对象的访问及遍历操作

1.operator[]

T&operator[](size_t i){assert(i >=0&& i <size());return _start[i];}const T&operator[](size_t i)const{assert(i >=0&& i <size());return _start[i];}

2.实现迭代器：begin+end

typedef T* iterator;typedefconst T* const_iterator;

iterator begin(){return _start;}
iterator end(){return _finish;}

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

五.vector对象的增删查改操作

1.operator

1.传统写法

vector<T>&operator=(const vector<T>& v){if(this!=&v){delete[] _start;
        
        _start =new T[v.capacity()];//memcpy(_start, v._start, v.size() * sizeof(T)); //当vector<string>时存在问题for(size_t i =0; i < v.size(); i++){
            _start[i]= v._start[i];}
        _finish = _start + v.size();
        _end_of_storage = _start + v.capacity();}return*this;}

更好的写法：遍历vector进行尾插。

vector<T>&operator=(const vector<T>& v){if(this!=&v){clear();reserve(v.size());for(auto& e : v){push_back(e);}}return*this;}

2.现代写法

voidswap(vector<T>& v){
    std::swap(_start, v._start);
    std::swap(_finish, v._finish);
    std::swap(_end_of_storage, v._end_of_storage);}//类内可以用类名替代类型：vector& operator=(vector tmp)
vector<T>&operator=(vector<T> tmp){swap(tmp);return*this;}

2.push_back

尾插时：先检查容量，再进行尾插。

voidpush_back(const T& x){//容量满了——>扩容if(_finish == _end_of_storage){reserve(capacity()==0?4:2*capacity());}//尾插*_finish = x;++_finish;}

3.pop_back

尾删时：先检查是否有有效数据，再进行尾删。

voidpop_back(){assert(!empty());--_finish;}

4.insert

插入时：先检查容量，再整体右移一位，最后插入。

迭代器失效：类似野指针

实现插入操作有一个坑造成迭代器失效问题，如下图：

修改后的代码能解决上面的问题，但是又存在另一个迭代器失效的问题，如下图：

迭代器失效：位置意义改变

由于不知道insert函数内是否存在扩容，不能确保pos是否为野指针，解决方法：可以在insert函数中返回pos用于接受。代码如下：

iterator insert(iterator pos,const T& x){assert(pos >= _start);assert(pos <= _finish);//容量满了——>扩容if(_finish == _end_of_storage){//记录pos的相对位置防止迭代器失效
        size_t len = pos - _start;reserve(capacity()==0?4:2*capacity());
        pos = _start + len;}//整体后移一位
    iterator end = _finish -1;while(end >= pos){*(end +1)=*end;--end;}//插入数据*pos = x;++_finish;return pos;}

5.erase

同理erase也会遇到的迭代器失效：位置意义改变，在vs2022中的vector（SLT）不接收erase的返回值强行访问，程序崩溃。接收erase的返回值访问，程序正常运行。

iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);
    
    iterator it = pos +1;while(it !=end()){*(it -1)=*it;++it;}--_finish;return pos;}

实现删除vector中的偶数：

intmain(){
    std::vector<int> v1;
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);auto it = v1.begin();while(it != v1.end()){if(*it %2==0){
            it = v1.erase(it);}else{
            it++;}}return0;}

六.源代码

1.vector.h

//#pragma once#ifndef__VECTOR_H__#define__VECTOR_H__#include<iostream>#include<assert.h>usingnamespace std;namespace xzy
{//有模版不能分离到.h与.cpp文件，否则报链接错误template<classT>classvector{public:typedef T* iterator;typedefconst T* const_iterator;//C++11 强制生成默认构造//vector() = default;vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){}vector(const vector<T>& v){
            _start =new T[v.capacity()];//memmove(_start, v._start, v.size() * sizeof(T)); //当vector<string>时存在问题for(size_t i =0; i < v.size(); i++){
                _start[i]= v._start[i];}
            _finish = _start + v.size();
            _end_of_storage = _start + v.capacity();}/*vector(const vector<T>& v)
        {
            reserve(v.size());
            for (auto& e : v)
            {
                push_back(e);
            }
        }*///类模版的成员函数可以是函数模版template<classInputIterator>vector(InputIterator first, InputIterator last){while(first != last){push_back(*first);++first;}}vector(size_t n,const T& val =T()){reserve(n);for(size_t i =0; i < n; i++){push_back(val);}}voidclear(){
            _finish = _start;}//vector<T>& operator=(const vector<T>& v)//{//    if (this != &v)//    {//        delete[] _start;//        _start = new T[v.capacity()];//        //memcpy(_start, v._start, v.size() * sizeof(T));//当vector<string>时存在问题//      for(size_t i = 0; i < v.size(); i++)//        {//              _start[i] = v._start[i];//        }//        _finish = _start + v.size();//        _end_of_storage = _start + v.capacity();//    }//    return *this;//}//vector<T>& operator=(const vector<T>& v)//{//    if (this != &v)//    {//        clear();//        reserve(v.size());//        for (auto& e : v)//        {//            push_back(e);//        }//    }//    return *this;//}voidswap(vector<int>& v){
            std::swap(_start, v._start);
            std::swap(_finish, v._finish);
            std::swap(_end_of_storage, v._end_of_storage);}类内可以用类名替代类型：vector& operator=(vector tmp)
        vector<T>&operator=(vector<T> tmp){swap(tmp);return*this;}~vector(){if(_start !=nullptr){delete[] _start;}
            _start = _finish = _end_of_storage;}

        iterator begin(){return _start;}

        iterator end(){return _finish;}

        const_iterator begin()const{return _start;}

        const_iterator end()const{return _finish;}//以下有一个坑//void reserve(size_t n)//{//    if (n > capacity())//    {//        //开空间//        T* tmp = new T[n];//        //拷贝数据//        memmove(tmp, _start, sizeof(T) * size());//        //释放旧空间//        delete[] _start;//        //更新数据//        _start = tmp;//        _finish = _start + size(); 注意：size()已经不再是有效数据个数了，可以通过调试观察//        _end_of_storage = _start + n;//    }//}voidreserve(size_t n){//第一种解决方法：依旧存在错误//if (n > capacity())//{//    T* tmp = new T[n];//    memmove(tmp, _start, sizeof(T) * size());//    delete[] _start;//    _finish = tmp + size();//    _start = tmp;//    _end_of_storage = _start + n;//}//第二种解决方法：依旧存在错误/*if (n > capacity())
            {
                size_t old_size = size();
                T* tmp = new T[n];
                memmove(tmp, _start, sizeof(T) * size());
                delete[] _start;
                _start = tmp;
                _finish = _start + old_size;
                _end_of_storage = _start + n;
            }*///第三种解决方法if(n >capacity()){//先保存有效数据个数
                size_t old_size =size();//开空间
                T* tmp =new T[n];//拷贝数据for(size_t i =0; i < old_size; i++){
                    tmp[i]= _start[i];}//释放旧空间delete[] _start;//更新数据
                _start = tmp;
                _finish = _start + old_size;
                _end_of_storage = _start + n;}}voidresize(size_t n,const T& val =T()){if(n <size()){
                _finish = _start + n;}else{reserve(n);while(_finish < _start + n){*_finish = val;++_finish;}}}

        size_t size()const{return _finish - _start;}

        size_t capacity()const{return _end_of_storage - _start;}voidpush_back(const T& x){//容量满了——>扩容if(_finish == _end_of_storage){reserve(capacity()==0?4:2*capacity());}//尾插*_finish = x;++_finish;}boolempty(){return _start == _finish;}voidpop_back(){assert(!empty());--_finish;}//void insert(iterator pos, const T& x)//{//    //容量满了——>扩容//    if (_finish == _end_of_storage)//    {//        reserve(capacity() == 0 ? 4 : 2 * capacity());//    }//    //整体后移一位//    iterator end = _finish;//    while (end > pos)//    {//        *end = *(end - 1);//        --end;//    }//    //插入数据//    *pos = x; //pos为野指针，迭代器失效//    ++_finish;//}

        iterator insert(iterator pos,const T& x){//容量满了——>扩容if(_finish == _end_of_storage){//记录pos的相对位置防止迭代器失效
                size_t len = pos - _start;reserve(capacity()==0?4:2*capacity());
                pos = _start + len;}//整体后移一位
            iterator end = _finish -1;while(end >= pos){*(end +1)=*end;--end;}//插入数据*pos = x;++_finish;return pos;}

        iterator erase(iterator pos){
            iterator it = pos +1;while(it !=end()){*(it -1)=*it;++it;}--_finish;return pos;}

        T&operator[](size_t i){assert(i >=0&& i <size());return _start[i];}const T&operator[](size_t i)const{assert(i >=0&& i <size());return _start[i];}private:
        iterator _start =nullptr;
        iterator _finish =nullptr;
        iterator _end_of_storage =nullptr;};}#endif