网站建设的优点,江西省住房城乡建设厅网站,河南安阳市地图,网站基础建设和管理暂行办法目录
vector的成员变量
构造函数
reserve
size()
capacity()
push_back 一些小BUG
赋值操作符重载
析构函数 【】操作符重载
resize
pop_back
Insert 迭代器失效
erase
二维数组问题
总结一下 vector#xff0c;翻译软件会告诉你它的意思是向量#xff0c;但其…目录
vector的成员变量
构造函数
reserve
size()
capacity()
push_back 一些小BUG
赋值操作符重载
析构函数 【】操作符重载
resize
pop_back
Insert 迭代器失效
erase
二维数组问题
总结一下 vector翻译软件会告诉你它的意思是向量但其实它就是个顺序表容器与我们刚开始实现的顺序表大差不差但是模板的应用让它变得更加万能接下来我们就尝试去了解学习源码是如何实现vector的。
vector的使用
int main()
{vectorint v;v { 1,2,3,4,5 };for (auto e : v){cout e;}
} 由于模板的使用vector不仅能存放内置类型也可以存放自定义类型比如说用vector套vector 当然vector还有很多的应用型接口在这里不记述有需要的话请移步至这个网站https://cplusplus.com/reference/
看上去vector的使用相当方便也加入了我们的老熟人模板参数那么我们就来模拟实现一下。 vector的成员变量 借助顺序表的前车之鉴我们推断vector的成员变量的实现应该是如下这样的
namespace myvector
{templateclass Tclass vector{public:private:T* _v;size_t _size;size_t _capacity;};
}
但是事与愿违跑去查询STL的源码给了我们当头棒喝 坏了怎么是3个迭代器我们看到迭代器的定义是两个typedef的套娃它的本质依旧是T*Start我们可以理解顺序表结构的头指针但是为什么size和capacity变成了finish和end of storage?
在《SLT源码剖析》中我们得到了答案 那么其实它们的本质没什么太大的分别这样也有助于范式使用。但我这边还是比较喜欢size和capacity就不更改了。 构造函数 我们先实现一个最基本的无参版本
//无参构造函数
vector():_start(nullptr), _size(nullptr), _capacity(nullptr)
{} 然后是传参版本 vector(int n, const T val T()):_start(nullptr), _finish(nullptr), _endofstorge(nullptr){reverse(n);for (int i 0; i n; i){push_back(val);}}reserve 为了能实现一个有基本功能的vector我们先解决一下扩容的问题然后就可以愉快的写push_back了。
由于扩容的前提是不要缩容那么我们就需要得到当前vector的size但是不同于string可以直接得到当前的size我们需要额外写一个函数来获取不过也不算难事毕竟也是比较常用的函数。
两个同类型的指针相减得到的就是它们之间的数据类型个数。
size()
size_t size()
{return _size - _start;
}
capacity()
size_t capacity()
{return _capacity - _start;
}
那么就可以拿来实现reserve了重置空间的逻辑跟string差不太多首先我们检查是否发生了缩容然后借助传入的需要开辟的空间个数来new出来一个新空间接着把旧空间的数据用memcpy拷贝过去然后新空间的size和capacity还需要重置一下因为它们的本体是指针指向的空间已经被销毁了我们就以当前的新头指针上原先的数据个数让其重归正轨。
如下的代码有小BUG我们后面讲
void reserve(const size_t n)
{if (n capacity()){T* tmp new T[n];//如果旧空间就是需要被开辟的也就是_start是个空指针不需要拷贝直接赋值就行//重置空间的话就往下走。if (_start ! nullptr){memcpy(tmp, _start, _size);delete[] _start;}_start tmp;_size _start size();_capacity _start n;}
} push_back 有了空间开辟的函数push_back就没什么难度了。 void push_back(const T val){if (_size _capacity){size_t newcapacity capacity() 0 ? 4 : capacity() * 2;reserve(newcapacity);}*_size val;_size;} 一些小BUG 到这里时一个基本的vector就可以使用了但是还是有一个小问题假如我们直接运行如上代码就会报如下的错误。 怎么回事为什么_size 还是空调试时已经走过了前面的过程那么问题就应该出现在扩容的时候_size 赋值的方法出现了问题。
我们回到reseve函数发现我们想利用size函数来获得当前的数据个数时忽略了此时的_size本身还是指向旧空间的而_start早已更新两个指针相减根本得不出正确答案
那么我们还是需要保存一下旧空间的个数
void reserve(const size_t n){if (n capacity()){T* tmp new T[n];size_t oldsize size();if (_start ! nullptr){memcpy(tmp, _start, sizeof(T)*size());delete[] _start;}_start tmp;_size _start oldsize;_capacity _start n;}
}
再插入5个数据试试看 没有问题。 赋值操作符重载 为了应对赋值的问题编译器默认生成的赋值操作符重载函数是浅拷贝会导致析构两次而崩溃的问题所以我们还是需要实现一下
赋值的情况发生在同类型的情况下所以返回值和参数都应该是vector
然后借用我们之前string的现代写法也就是把一份拷贝与当前的this进行交换我们再实现一个简单的swap函数
void swap(vectorT v)
{std::swap(_start, v._start);std::swap(_size, v._size);std::swap(_capacity, v._capacity);
} 那么为了不影响到赋值操作符左边的值我们不传引用直接传值产生一个拷贝构造然后交换。
vectorT operator (vectorT tmp)
{swap(tmp);return *this;
} 析构函数 //析构函数~vector(){delete[] _start;_start _size _capacity nullptr;} 【】操作符重载 T operator[](size_t n)
{assert(pos size());return *(_startn);
} resize resize函数同string的逻辑没什么太多的区别唯一需要注意的是关于填充缺省值的问题。
当n_capacity的时候需要扩容当nsize的时候需要向多出来的空间填充缺省值当nsize的时候需要重置当前size的位置到n
void resize(const size_t n,T val T())
{if (n capacity()){reserve(n);}if (n size()){while (_size _start n){*_size val;_size;}}else{_size _start n;}
}在这里val为了适应自定义类型采用了匿名构造的方式来为val赋值对于内置类型也是生效的
T val T() pop_back void pop_back(){assert(_size _start);--_size;}Insert 我们先看看描述 传入一个迭代器然后在迭代器位置插入数据。那么我们简单实现一个迭代器
//迭代器
iterator begin()
{return _start;
}iterator end()
{return _size - 1;
} 由于auto的使用原理是自动推导所以当我们实现了某个容器的迭代器的时候就可以正常的使用范围for了auto可以在范围for中成功的推导出来容器的迭代器从而实现遍历。 接下来是insert的主体逻辑 void insert(iterator n, const T val){assert(n _start);//若满扩容if (_size _capacity){size_t newcapacity capacity() 0 ? 4 : capacity() * 2;reserve(newcapacity);}if (n _size){iterator end _size;while (end n){*end *(end - 1);--end;}*n val;_size;}} 坏了怎么崩溃了发生什么事了我们调试看看
通过调试我们发现n的值完全不在当前_start 到 _size 的位置之间这个while循环也走了非常多遍而且这个问题是在扩容时才发生的那么我们就得出了一个最初的结论n所指向的位置在扩容后无法正确生效也就是迭代器失效问题。 迭代器失效
迭代器失效原因如图所示为了更好的理解传入的迭代器n更名为pos 那么为了能成功的修正pos的新位置跟我们处理pushback的方法一样我们保存之前的数据长度然后在新的空间更新pos void insert(iterator n, const T val){assert(n _start);//扩容会引发迭代器失效的问题需要更新迭代器if (_size _capacity){size_t length n - _start;size_t newcapacity capacity() 0 ? 4 : capacity() * 2;reserve(newcapacity);n _start length;}if (n _size){iterator end _size;while (end n){*(end) *(end - 1);end--;}*n val;//整体大小1更新_size_size;}}
那么通过上面的分析我们知晓了迭代器失效的具体原因而迭代器失效指向的真正失效其实是inset之后的迭代器不能再使用了。因为我们是传值调用inset外部的迭代器依然没有更新假如我们想要继续使用很有可能发生越界访问的问题。 erase void erase(iterator n)
{assert(n _start);assert(n _size);if (n _size - 1){pop_back();return;}iterator cur n 1;while (cur _size){*(cur - 1) *cur;cur;}--_size;
} 二维数组问题 vector容器本身服务的对象是各种各样的类型所以当我们希望在vector内部存放其他容器类型的时候它也应该是支持的我们就拿我们自己实现的vector来尝试实现一个二维数组。 没啥问题但是一旦发生扩容会直接崩溃 通过调试我们发现问题发生在析构的时候 但追根溯源析构能发生错误的时候肯定是空间的开辟发生了问题那么罪魁祸首应该就是我们的reserve了 那么为什么创建二维数组的时候才报错还是需要画图来缕一缕。 那么为了避免这种情况我们应该抛弃malloc换成更加深层次的拷贝也就是新开辟一个空间之后把原本的值原封不动的拷贝一份新的也就是内容相同但是地址不同的新拷贝再放入扩容之后的空间。 void reserve(const size_t n){if (n capacity()){T* tmp new T[n];size_t oldsize size();if (_start){for (size_t i 0; i oldsize; i){tmp[i] _start[i];}//释放旧空间防止内存泄漏delete[]_start;}_start tmp;_size tmp oldsize;_capacity _start n;}} 总结一下 根据以上的模拟实现我们基本上了解了vector的基本结构以及接口的使用其本质不同于顺序表为了服务于自定义类型以及泛型变成成员变量是迭代器而迭代器的本身则是类模板参数实现并不算困难但是细节还是需要额外处理。 到此模拟vector的概述就结束了感谢阅读希望对你有点帮助
