vector使用和实现

vector使用和实现

写在前面

我们string已经学习的差不多了，现在开始学习vector，我们这里会发现，STL的设计很相似，我们学习了一个，这里面就很简单了，我们简单的先看一下vector的使用，今天的重点是迭代器失效的问题和深层次的拷贝问题，这才是我们的难点。

vector 使用

vector可以理解为我们之前的动态的数组,也就是顺序表.它也是一个类模板.我们先看一下简单的使用.它的第一个参数模板是一个要存储的数据类型,第二个是向内存池开辟空间,如果你觉得库里面的内存池不够高效,也可以自己写一个,然后传过去,不过这不是我们要说的.

构造函数

vector里面包含拷贝构造的的话共存在4个构造函数,我们这里一一简绍.

我们这里还是自测试两个比较常用的

int main(){ vector v1; vector v2(10,'a'); return 0;}

size() && capacity()

这个也是我们经常用到的函数,没有什么可以解释的.

int main(){ vector v1(20,15); cout << "size: " << v1.size() << endl; cout << "capacity: " << v1.capacity() << endl; return 0;}

reserve()

这个函数就是开辟空间的,和string那里是一样的,规则还是一样的.

int main(){ vector v1(20,15); v1.reserve(10); cout << "capacity: " << v1.capacity() << endl; v1.reserve(100); cout << "capacity: " << v1.capacity() << endl; return 0;}

resize()

没有什么新意,还是和之前一样.

int main(){ vector v1(20, 15); v1.resize(10, 0); cout << "size: " << v1.size() << endl; v1.resize(100, 0); cout << "size: " << v1.size() << endl; return 0;}

operator[]

这个的底层是一个连续的数组,所以这里我们最好支持下标访问.

int main(){ vector v1(20, 15); for (int i = 0; i < v1.size(); i++) { cout << v1[i] << " "; } cout << endl; return 0;}

迭代器

迭代器这里分为正向迭代器和反向迭代器,而且每种都有const修饰的,这里面我们不做太多的解释,用法和之前一样.

int main(){ vector v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); v1.push_back(5); vector::iterator it = v1.begin(); while (it != v1.end()) { cout << *it << " "; it++; } cout << endl; return 0;}

push_back()

尾插一个数据,在尾部插入一个数据.

int main(){ vector v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); v1.push_back(5); for (int i = 0; i < v1.size(); i++) { cout << v1[i] << " "; } cout << endl; return 0;}

vector 实现

好了,总算是过了上面的认识阶段了,主要是我们没有什么可以说的,它和string几乎一摸一样,这还用说?现在我们要看的是他们的实现,这才是有意思的.

我们先来推一波vector的底层,应该会有一个size和一个capacity记录有效数据和容量,还应该有一个数组,来存放数据.我想这个应该没有什么可以质疑的,我们看看SGI版的的实现,它里面就存放了三个指针(typedef过的),这种方法也是可以的,而且还比我们的简便一些,就用这个来实现吧.

我们画一下它的物理图,这样大家可以好理解一点.

vector

现在我们就可以把框架搭出来了,我们搭个简便的.

templateclass Vector{public: typedef T* iterator; // 原生指针 typedef const T* const_iterator; Vector() :_start(nullptr) , _finish(nullptr) , _endOfStoage(nullptr) { }private: iterator _start; iterator _finish; iterator _endOfStoage;}

迭代器

vector和string是一样的,它们都是原生指针,所以这里面我们可以直接用.

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

size() && capacity()

这个实现的就更加简单了,我们知道,指针减指针可以得到数据的个数,这里也适用.我们在这就直接用吧。

size_t size() const { return _finish - _start;}// 计算 容量size_t capacity() const { return _endOfStoage - _start;}

operator[]

既然vector的物理地址是连续的,那么我们最好支持operator[]随机访问,这里面是在是太简单了.

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

reserve()

这个是去扩容放热函数,但是这里面可以存在一个很重要的问题,跟深层次的深浅拷贝问题,这是我们今天博客最主要的内容之一,后面我们会一一分享的.

void reserve(size_t n = 0){ size_t oldsize = size(); if(n > capacity()) { // 开一块空间 T* tmp = new T[n]; // 判断 原本空间有没有 数据 if(_start) { memcpy(tmp,_start,size()*sizeof(T)); delete[] _start; } _start = tmp; _finish = tmp + oldsize; _endOfStoage = tmp + n; }}

resize()

这个函数是调整_size的的大小的.我们这里还是只实现一种情况.

void resize(size_t n,const T& val = T()){ // 三种 情况 reserve(n); if(n > size()) { while(size() < n) { // *_finish = val; _finish++; } } else { _finish = _start + n; }}

insert()

这个是在一个地址插入一个元素,我们默认插入在元素的前面,这里面存在迭代器失效的问题.

iterator insert(iterator pos, const T& x){ assert(pos >= _start && pos <= _finish); if(_finish == _endOfStoage) { size_t len = pos - _start; // 记录 防止失效 size_t newCap = _endOfStoage - _start == 0 ? 4 : 2 * capacity(); reserve(newCap); // 更新 pos 解决了一部分迭代器失效问题 pos = _start + len; } // 开始 插入数据 iterator it = _finish; while(it != pos) { *it = *(it - 1); it--; } *pos = x; _finish++; return pos;}

push_back()

复用insert函数就可以了.

void push_back(const T& val){ insert(_finish,val);}

erase()

这个时间复杂度可是达到了O(N),确实有点高,不过也没有办法.

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

pop_back()

尾删的时间复杂度O(1).

void pop_back(){ if(size() != 0) // 这里 最好不要用 空来判断 害怕clear { --_finish; }}

swap

这个函数的主要作用就是为了拷贝构造等地方,我们只需要交换一下三个指针就可以了.

void swap(Vector& v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_endOfStoage, v._endOfStoage); }

迭代器失效

现在我们来谈vector里面最难理解的问题,迭代器失效,我们需要好好的控制使用vector,避免出现错误.vector的迭代器失效大概分为三种,下面我们一一举例.

扩容导致 pos 失效

我们先来看看标准库里面的,这个还是会出现野指针的问题.

#include #include using namespace std;int main(){ vector v(10,1); vector::iterator pos = v.begin(); int i = 0; while (i < 100) { v.insert(pos, 2); i++; } return 0;}

我们先来看看是在哪一步出现问题了,打印一下,这里面我们发现当i等于1的时候出现了

我们需要去看看pos这里面是不是在第一次插入后失效了，VS里面有点严格。

int main(){ vector v(10,1); vector::iterator pos = v.begin(); printf("pos : %p\n", pos); int i = 0; while (i < 100) { if (i == 1) { printf("pos : %p\n", pos); cout << "测试" << endl; } v.insert(pos, 2); i++; } return 0;}

所以这里面我们要去看看Linux环境是如何的,不同的编译器对个的处理机制也是不一样的,这一点我们之前就知道了.

从这里我们就可以看出当我们插入了一些数据后才会发生错误,而且是在i = 10的时候,这个现象我们就可以好好解释一下迭代器失效的原因之一了.我们先来调试一下.

来说一下原因吧,我们插入数据的时候用的是迭代器,准确来说是原生指针,如果饿哦们我们要是原本的指针扩容,那么就会出现现在的事,迭代器指向内容失效了.我们可以通过某种方法来解决一下这个insert问题,可以通过记录pos和_start的相对距离,扩容后在做相应的修改.

iterator insert(iterator pos, const T& x){ assert(pos >= _start && pos <= _finish); if(_finish == _endOfStoage) { size_t len = pos - _start; // 记录 防止失效 size_t newCap = _endOfStoage - _start == 0 ? 4 : 2 * capacity(); reserve(newCap); // 更新 pos 解决了一部分迭代器失效问题 pos = _start + len; } // 开始 插入数据 // ... return pos;}

抱歉,你以为现在你写的就是正确的吗?看一下下面的代码.我们希望在偶数前面添加这个偶数的十倍,看看怎么样?

#include #include "Vector.hpp"using std::cout;using std::cin;using std::endl;int main(){ bit::Vector v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); v.push_back(6); bit::Vector::iterator it = v.begin(); while (it != v.end()) { if (*it % 2 == 0) { int ret = *it * 10; v.insert(it, ret); } it++; } for (int val : v) { cout << val << " "; } return 0;}

好了,又出现问题了,看这里我们就可以发现,又出现了迭代器失效的问题,我们不是更新pos了吗?这里面还是存在些问题,我们传入的是形参,改变形参是不会影响实参的,那么我们是不是可以传入引用,是的可以,但是标准库里面可以不是怎么做的.

我们通过返回值的形式解决这个问题.

iterator insert(iterator pos, const T& x){ assert(pos >= _start && pos <= _finish); // 更新 pos 解决了一部分迭代器失效问题 // 开始 插入数据 // ... return pos;}

为何不用引用这个也是有原因的,要知道,insert支持下面的用法,临时变量具有常性,要用const修饰,那么我们还要如何修改.

返回值导致迭代器失效

如果你要是觉得现在我们的代码就可以正常运行的了,你太过天真了.运行一下你就会发现,还是存在问题的.

#include #include "Vector.hpp"using std::cout;using std::cin;using std::endl;int main(){ bit::Vector v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); v.push_back(6); bit::Vector::iterator it = v.begin(); while (it != v.end()) { if (*it % 2 == 0) { int ret = *it * 10; v.insert(it, ret); } it++; } for (int val : v) { cout << val << " "; } return 0;}

我们现在去用一下标准库里面是不是也存在这个情况.

#include #include using namespace std;int main(){ vector v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); v.push_back(6); vector::iterator it = v.begin(); while (it != v.end()) { if (*it % 2 == 0) { int ret = *it * 10; v.insert(it, ret); } it++; } for (int val : v) { cout << val << " "; } return 0;}

这个也崩了,也就是说我们实现的最起码没有错误,这里面的原因是返回值的事情,我们去瞅瞅.

现在你应该就有些头绪了,我们的返回值可是新插入的迭代器,检验一下.

int main(){ vector v; v.push_back(1); v.push_back(2); v.push_back(3); vector::iterator it = v.begin(); it = v.insert(it, 10); return 0;}

也就是说我们在插入元素后需要需要移动一下迭代器,至于移动到那就是你自己控制的

#include #include using namespace std;int main(){ vector v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); v.push_back(6); vector::iterator it = v.begin(); while (it != v.end()) { if (*it % 2 == 0) { int ret = *it * 10; v.insert(it, ret); it++; } it++; } for (int val : v) { cout << val << " "; } return 0;}

erace 导致迭代器失效

vector还存在第三种迭代器失效的情况,这种请况主要是一个预留的情况,我们现在看看库里面的erase的大致情况,一般情况下,这种情况哦们是遇不到的,因为VS编译器和g++的编译器好象都不缩容,但是这种情况我们是需要知道的.

using namespace std;int main(){ vector v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); v.push_back(6); vector::iterator it = v.begin(); while (it != v.end()) { if (*it % 2 == 0) { it = v.erase(it); // 注意一下 it 接受就可以了 } else { it++; } } for (int val : v) { cout << val << " "; } return 0;}

总结

vector的迭代器的失效主要有两种

由于扩容(insert)或者缩容(erase)导致变成了野指针由于指向的意义变了,类似erase删除元素的下一个位置,insert也是插入元素的下一个,这就导致迭代器自增或者自减的合理使用

编译器对迭代器失效的处理机制

不同的编译器对失效的处理的差异还是很大的，这里面我们重点看看VS的和g++的。这里面VS比较严格，只要插入或者删除了一次，无论是不是扩容还是缩容，当前地址就不能被访问了。

#include #include using namespace std;int main(){ vector v(10,1); vector::iterator it = v.begin(); v.insert(it, 2); cout << v.capacity() << endl; *it; return 0;}

int main(){ vector v(10,1); vector::iterator it = v.begin(); v.erase(it); cout << v.capacity() << endl; *it; return 0;}

但是这里在g++中 据比较佛系了,一般都可以访问,如果碰到了野指针,会单独报错.

#include #include using namespace std;int main(){ vector v(10,1); vector::iterator it = v.begin(); v.insert(it, 2); cout << v.capacity() << endl; *it; return 0;}

int main(){ vector v(10,1); vector::iterator it = v.begin(); v.erase(it); cout << v.capacity() << endl; *it; return 0;}

完善vector

这里我们需要完善一下vector,包括拷贝构造,赋值重载等等,这里都是比较简单的,先来拷贝构造.

拷贝构造

这里我们需要写一下现代的写法,还是比较简单的.

Vector(const Vector& v) //这里建议这样写 当然类内 const Vector& v 这样也可以,只不过不推荐 :_start(nullptr) ,_finish(nullptr) ,_endOfStoage(nullptr) { // 现代写法 Vector vv; for(const T& val : v) { vv.push_back(val); } // 我让你帮我写好,vv这个变量你还要给我析构了. swap(vv); }

赋值重载

这个更加比较简单,可以说是厉害的一批.

Vector& operator=(Vector v){ // 这里我们不传入 引用,这里就编译器自动调用拷贝构造,我们直接可以传入了. swap(v); return *this;}

析构函数

这里把析构函数给写出来,避免内存泄漏.

~Vector(){ if(_start) { delete[] _start; _finish = nullptr; _endOfStoage = nullptr; }}

多值构造

这里我们把这个构造的时候一次初始化多个值的构造函数给写一下.这里还可以复用一下尾插就可以了.

Vector(size_t n, const T& value = T()) :_start(nullptr) ,_finish(nullptr) ,_endOfStoage(nullptr) { Vector vv; for(size_t i=0;i

区间构造

有的时候我们可能会使用区间构造,这里面也存在一个问题,主要就是上面的多值构造有一点问题.等该你调用的是时候就会知道了.

template Vector(InputIterator first, InputIterator last) :_start(nullptr) ,_endOfStoage(nullptr) ,_finish(nullptr) { Vector vv; while(first != last) { vv.push_back(*first); first++; } swap(vv); }

这里面我们先来测试一下,主要看看这个错误的信息

int main(){ // 排除法 vector v1(10, 2); for (auto e : v1) { cout << e << " "; } cout << endl; vector v2(10, 'x'); for (auto e : v2) { cout << e << " "; } cout << endl; return 0;}

我们把第一个排除一下,你就会发现是在第一个第一构造函数那里错了,我们需要分析一下.

int main(){ vector v2(10, 'x'); for (auto e : v2) { cout << e << " "; } cout << endl; return 0;}

我们先来解释一下这个情况,对于编译器而言,我们会自动的推导参数的类型,我们发现它们都是int,所以编译器有理由相信我们调用的是区间构造,因为多值构造的两个参数是不一样的,编译器肯定优先选择区间构造,这就是报错的原因.

源码里面对于这个的解决,是通过把第一个参数了类型改成int.

Vector(int n, const T& value = T()) :_start(nullptr) ,_finish(nullptr) ,_endOfStoage(nullptr) { Vector vv; for(int i=0;i

更深层次的深拷贝

这里vector就剩下最后一个大内容了,这个模块有点困难,需要我们好好的理解,这里我先用个比较简单的例子来举.在标准库里面我们可以vector嵌套vector,向下面一样.

#include #include using namespace std;int main(){ // 排除法 vector> vv; vector v1(10, 1); vector v2(10, 2); vector v3(10, 3); vector v4(10, 4); vector v5(10, 5); vv.push_back(v1); vv.push_back(v2); vv.push_back(v3); vv.push_back(v4); vv.push_back(v5); for (vector& val : vv) { for (int e : val) { cout << e << " "; } cout << endl; } return 0;}

但是对于我们自己写的是无法做到这样的,我们先来运行一下,你就会明白了.

#include #include "Vector.hpp" using namespace std; int main() { bit::Vector> vv; bit::Vector v1(10, 1); bit::Vector v2(10, 2); bit::vector v3(10, 3); bit::vector v4(10, 4); bit::vector v5(10, 5); vv.push_back(v1); vv.push_back(v2); vv.push_back(v3); vv.push_back(v4); vv.push_back(v5); for (bit::Vector& val : vv) { for (int e : val) { cout << e << " "; } cout << endl; } return 0; }

这里面报了段错误,这里我也不让大家思考了,这里的最主要的问题在于insert和reserve两个函数,我们先来解释一下vector嵌套vector的本质.

vector

当vector中的T是自定义类型的数组时,一般会出现浅拷贝的问题,我们这里的实现在于memcpy函数,对于一般的整型数组,它是把数组里面的值拷贝下来,是深拷贝.但是这里的T是自定义类型的数组,也就是我们的vector存储的是地址,那么这时候拷贝的是地址,要知道我们后面还是要delete的,对于自定类型是会调用自己的析构函数的,导致原来的指针变成野指针.我们先来过一遍原来的代码,这样你就会有点了解了,这里的赋值重载是一个深拷贝,没有什么问题.

再不扩容的时候插入数据,步骤是这样的.vector的数组拷贝给了vector数组,对于数组里面的每一个元素都会调用赋值重载,这个可是深拷贝.

插入的时候发生扩容,这里就会出现问题.我们使用了memcpy函数,他把原本数组的的元素都拷贝给tmp,要知道拷贝的是指针,

下面还有最关键的一步,我们把原本的_start给delete,要知道,这里面存储的全是自定义类型数组的指针,编译器会一一的把空间给是释放了.我们的tmp变成了野指针.

解决方案

这个就比较好想了,我们不用memcpy函数,直接一个一个赋值,对于内置类型都一样,对于自定义类型会调用自己的赋值重载,这就没有问题了.

void reserve(size_t n = 0){ size_t oldsize = size(); if (n > capacity()) { // 开一块空间 T* tmp = new T[n]; // 判断 原本空间有没有 数据 if (_start) { // 这里直接 赋值 对于 自定义类型 会自动调用赋值重载 -- 深拷贝 for (int i = 0; i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。