vector的模拟实现

vector的模拟实现

vector 结构定义

vector要实现成模板的形式, 使vector中可以存储任意类型的数据; 成员变量不再像string给一些具体的数据类型, 而是采用指针模拟的迭代器来实现， 这里使用C+11语法给成员变量缺省值， 在构造和拷贝构造时不用去初始化列表中初始化, 直接用缺省值

template<class T>
class vector
{
public:typedef T* iterator;typedef const T* const_iterator;private:iterator _start=nullptr;             //指向首元素 iterator _finish=nullptr;            //sizeiterator _end_of_storage=nullptr;    //capacity
}

1. vector的迭代器的实现

vector的迭代器有两种, 一种迭代器可读指向内容可以修改, 一种是const类型的迭代器,只读不可修改指向内容。用指针实现即可。

template<class T>
class vector
{
public:typedef T* iterator;typedef const T* const_iterator;iterator begin(){return _start;}iterator end(){return _finish;          }//指向内容不能修改, 只能读不能写const_iterator begin()const{return _start;}const_iterator end()const{return _finish;}
}

2. vector四个默认成员函数

2.1 构造函数

按照库中的构造函数, 我们提供3个版本的

2.1.1 无参

vector()          //给缺省值  --- 初始化列表使用
{}

2.1.2 n个val初始化

直接向数组中尾插数据，用reserve提前扩容, 提高效率

注意点: 这里传参的第二个参数使用匿名对象，const T& val = T() 这种写法会调用默认构造(可以是任意类型)，我们前面讲内置类型是没有默认构造函数的, 理论而言是没有的, 但是调用模板之后必须要支持默认构造

补充匿名对象

vector(size_t n, const T& val = T())    //匿名对象
{reserve(n);     //提前扩容, 提高效率for (int i = 0; i < n; ++i){push_back(val);}
}

2.1.3 迭代器初始化

这里又要使用模板实现， 要实现一个任意类型的迭代器允许任意类型的数据使用，直接用迭代器遍历数组, 尾插数据即可

//任意类型的迭代器   --- 允许类的成员函数再设函数模板
//[first, last)
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{while (first != last){push_back(*first);++first;}
}

2.2 析构函数

直接将start指向的空间释放, 并且将三个指针置空即可

~vector()
{delete[] _start;_start = _finish = _end_of_storage = nullptr;
}

2.3 拷贝构造函数

2.3.1 传统写法

开辟新的空间，使即将被赋值的对象 _start指向新空间，后赋值(深拷贝)将原空间内容拷贝到新空间, 改变新空间的 _finish和 _end_of_storage

一定要使用赋值的方法深拷贝, memcpy是浅拷贝

vector(const vector<T>& v)            
{_start = new T[v.capacity()];//memcpy(_start, v._start, sizeof(T) * v.size());//深拷贝for (size_t i = 0; i < v.size(); ++i){_start[i] = v._start[i];      //赋值就是深拷贝}_finish = _start + v.size();_end_of_storage = _start + v.capacity();
}

2.3.2 现代写法

直接用迭代区间初始化去构造临时对象 tmp ，然后交换tmp 和原对象即可

vector(const vector<T>& v)           
{vector<T> tmp(v.begin(), v.end());swap(tmp);
}

2.4 赋值重载运算符

这里要实现深拷贝, v1=v2其实是v2去拷贝构造v，然后交换v1和v，便可对v1赋值

//v1 = v2
vector<T>& operator=(vector<T>  v)     //v2拷贝构造v, 交换v1和v
{swap(v);return *this;
}

3. 管理数组相关接口

3.1 reserve

在n>capacity时再去扩容, 这种做法是防止缩容

1. 提前记录好原数组大小, 防止扩容拷贝数据后数组大小改变；开辟n个空间大小的tmp数组
2. 遍历将原数组中元素拷贝到新数组中, 一定要使用赋值的方法深拷贝，不能使用memcpy(memcpy是浅拷贝)
3. 释放原数组，改变3个指针的指向

void reserve(size_t n)
{if (n > capacity())      //防止缩容{size_t sz = size();  //提前记录好原数组大小, 防止扩容拷贝数据后数组大小改变T* tmp = new T[n];if (_start){//memcpy(tmp, _start, sizeof(T) * size());   //错误写法,memcpy浅拷贝for (size_t i = 0; i <sz; ++i){tmp[i] = _start[i];      //赋值就是深拷贝}delete[] _start;}_start = tmp;_finish = _start+sz;_end_of_storage = _start + n;}
}

3.2 resize

1. n < size() 就是删除数据，直接改变 _finish的指向即可
2. n > size()调用reserve函数扩容， 后遍历给数组赋值

void resize(size_t n, T val=T())       // T val=T()  调用默认构造(可以是任意类型)
{if (n < size())       //删除数据{_finish = _start + n;}else if (n > size()){if (n > capacity())reserve(n);//初始化while (_finish != _start + n){*_finish = val;++_finish;}}
}

3.3 push_back

1. 检查容量, 容量不够时需要扩容
2. 直接向 _finsh指向位置插入元素, 后改变 _finish的指向

void push_back(const T& x)
{if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;++_finish;
}

3.3 pop_back

直接finish指向前移, – _finsh即可

注意: 数组为空无法删除

void pop_back()
{assert(!empty());--_finish;
}

3.4 empty

直接判断 _start是否等于 _finish

bool empty()
{return _start == _finish;
}

3.5 insert

1. 检查容量，观察是否需要扩容, 扩容前计算出pos与start之间，pos与start之间相对距离不变，扩容后更新pos位置(这里存在迭代器失效的问题)
2. 遍历挪动数据
3. 将val插入pos位置

注意: 检查pos位置的合法性

iterator insert(iterator pos, const T&val)
{assert(pos >= _start   &&  pos<=_finish);//1. 检查容量if (_finish == _end_of_storage){size_t len = pos - _start;      //pos与start之间相对距离不变reserve(capacity() == 0 ? 4 : capacity() * 2);//扩容后更新pos, 解决pos失效的问题pos = _start + len;}//2. 挪动数据iterator end = _finish - 1;while (end>=pos){*(end + 1) = *end;--end;}*pos = val;++_finish;return pos;
}

3.6 erase

1. 遍历挪动数据
2. 改变 _ finish的指向

注意: 检查pos位置的合法性

iterator erase(iterator pos)
{assert(pos >= _start && pos < _finish);//挪动数据iterator start = pos + 1;while (start != _finish){*(start - 1) = *start;++start;}--_finish;return pos;        //返回被删除元素的下一个元素, 对迭代器进行更新
}

3.7 size

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

3.8 capacity

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

3.9 swap

void swap(vector<T>& v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);
}

4. 运算符重载

4.1 []

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

5. 迭代器失效问题

迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装，比如：vector的迭代器就是原生态指针T* 。因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器，程序可能会崩溃)。

对于vector可能会导致其迭代器失效的操作有：

1. 指定位置前插入元素操作 — insert

如下代码, 错误演示:

void insert(iterator pos, const T&val)
{assert(pos >= _start   &&  pos<=_finish);//1. 检查容量if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}//2. 挪动数据iterator end = _finish - 1;while (end>=pos){*(end + 1) = *end;--end;}*pos = val;++_finish;
}

此代码存在两个大问题:

1. 迭代器失效的问题，插入元素扩容时, 可能存在异地扩容, 扩容后pos的指向没有更新， 就可能会出现如下图扩容后pos处指向随机值，扩容后无法找到pos指向的元素**。所以我们利用pos和 _start之间的相对距离不变的特点, 在扩容前先算出pos和 _start之间的距离，扩容后更新pos指向即可**
2. 函数形参pos是实参的临时拷贝, 形参的改变不会影响外部的实参。有两种结局方式: 1. 引用传参, iterator begin() 迭代器实现是传值返回， 会返回临时对象， 临时对象具有常性， 这里相当于权限放大 2. 按照库里的实现方式给返回值。这里只能使用给返回值的方式更新pos

正确代码，就是上面单独实现的insert

2. 指定位置元素的删除操作–erase

如下代码

void test_vector4()
{std::vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);//auto pos = find(v1.begin(), v1.end(), 2);      //程序可能不会崩溃auto pos = find(v1.begin(), v1.end(), 4);        //一定会崩溃if (pos != v1.end()){v1.erase(pos);}(*pos)++;for (auto e : v1){cout << e << " ";}cout << endl;
}

1. 对于删除元素2来说, 删除2后, 去更改*pos位置的值，VS下程序会崩溃, Linux下不会

2. 对于删除元素4来说, 删除4后, 去更改*pos位置的值，VS和Linux下都会崩溃, 删除pos位置后, 该位置已不再数组的范围中了, 再去更改访问就是野指针的问题了，程序一定会崩溃

分析:

erase删除pos位置元素后，pos位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代器不应该会失效，但是：如果pos刚好是最后一个元素，删完之后pos刚好是end的位置，而end位置是没有元素的，那么pos就失效了

结论: erase之后, pos是否失效? 失效，不要访问，行为结果未定义

删除元素后, 要对迭代器指向位置进行更新, 防止迭代器失效

如下代码， 删除数组中的偶数元素, 删除后要对it进行更新，所以erase删除元素后返回的是删除元素的下一个位置

void test_vector5()
{vector<int> v1;v1.push_back(10);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);v1.push_back(50);vector<int>::iterator it = v1.begin();while (it != v1.end()){if (*it % 2 == 0)//v1.erase(it);it = v1.erase(it);    //每次删完后更新itelseit++;}for (auto e : v1){cout << e << " ";}cout << endl;
}

6. 深浅拷贝问题

6.1 简单介绍深浅拷贝

浅拷贝

浅拷贝：也称位拷贝，编译器只是将对象中的值拷贝过来。如果对象中管理资源，最后就会导致多个对象共享同一份资源，当一个对象销毁时就会将该资源释放掉，而此时另一些对象不知道该资源已经被释放，以为还有效，所以当继续对资源进项操作时，就会发生发生了访问违规。

深拷贝

深拷贝: 给每个对象独立分配资源, 保证多个对象之间不会因资源而造成多次释放，造成程序崩溃问题

6.2 vector中深浅拷贝的几种情况

情况1: 不写拷贝构造函数， 直接使用默认的拷贝构造函数

代码如下， 实现将v1拷贝到v2, 不写拷贝构造函数使用默认的拷贝构造函数时，默认的拷贝构造会对内置类型完成浅拷贝, 会使v1,v2指向同一块空间, 并且析构时会析构两次, 程序会崩溃。

情况2: 写了拷贝构造函数， 拷贝构造函数中使用memcpy和reserve中的memcpy

1. memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中
2. 如果拷贝的是自定义类型的元素，memcpy既高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝。

代码如下, 将字符串拷贝到一个字符串数组中, 使用memcpy实现了外层深拷贝，内层浅拷贝, 程序会崩溃

在使用memcpy函数前, 实现了外层的深拷贝

使用memcpy函数后, 实现了内层的浅拷贝

我们要实现的是外层深拷贝，内层深拷贝, 直接 使用赋值的方法实现深拷贝

情况3: 拷贝构造函数中使用赋值深拷贝，不写赋值重载运算符, 使用默认生成的

代码如下, 实现打印杨辉三角，运行此代码程序会崩溃

调试发现实现的是外层深拷贝，内层浅拷贝

在拷贝构造时外层的vv和ret实现了深拷贝后， 内层的 vector< int > 调用默认的赋值重载, 实现的是浅拷贝, 而我们的内层需要实现深拷贝，写赋值重载函数，内层用交换来实现深拷贝