鞍山市城乡建设局网站,新媒体营销包括什么,如何做2级网站,读经典做临床报名网站本期主题#xff1a;vector的讲解和模拟实现博客主页#xff1a;小峰同学分享小编的在Linux中学习到的知识和遇到的问题小编的能力有限#xff0c;出现错误希望大家不吝赐vector的介绍及使用1.1vector的介绍vector其实就是一个数组的模板 #xff0c;存放的数据可以改变而已…本期主题vector的讲解和模拟实现博客主页小峰同学分享小编的在Linux中学习到的知识和遇到的问题小编的能力有限出现错误希望大家不吝赐vector的介绍及使用1.1vector的介绍vector其实就是一个数组的模板 存放的数据可以改变而已。使用vector存放的数据类型 类名称vector是表示可变大小数组的序列容器。 就像数组一样vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素 进行访问和数组一样高效。但是又不像数组它的大小是可以动态改变的而且它的大小会被容器自 动处理。 与其它动态序列容器相比deque, list and forward_list vector在访问元素的时候更加高效在末 尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作效率更低。比起list和forward_list 统一的迭代器和引用更好。 1.2vector的使用1.2.1. 成员函数1.2.2. 迭代器这里和string几乎相同就不一一介绍了。1.2.3.容量相关capacity的代码在vs和g下分别运行会发现vs下capacity是按1.5倍增长的g是按2倍增长的。 这个问题经常会考察不要固化的认为vector增容都是2倍具体增长多少是根据具体的需求定义 的。vs是PJ版本STLg是SGI版本STL。 reserve只负责开辟空间如果确定知道需要用多少空间reserve可以缓解vector增容的代价缺陷问 题。 resize在开空间的同时还会进行初始化影响size。 1.2.4.元素访问注意at和[ ]的区别at发生越界会抛异常[ ]发生越界直接断言检查断言检查只在debug版本下才会起作用。relesae版本不起作用。1.2.5.元素修改assign赋值前会先把元数据清空 vector的模拟实现2.1.常见错误2.1.1. vector 迭代器失效问题迭代器的主要作用就是让算法能够不用关心底层数据结构其底层实际就是一个指针或者是对指针进行了 封装比如vector的迭代器就是原生态指针T* 。因此迭代器失效实际就是迭代器底层对应指针所指向的 空间被销毁了而使用一块已经被释放的空间造成的后果是程序崩溃(即如果继续使用经失效的迭代器 程序可能会崩溃)。 #include iostream
using namespace std;
#include vector
int main()
{vectorint v{1,2,3,4,5,6};auto it v.begin();// 将有效元素个数增加到100个多出的位置使用8填充操作期间底层会扩容// v.resize(100, 8);// reserve的作用就是改变扩容大小但不改变有效元素个数操作期间可能会引起底层容量改变// v.reserve(100);// 插入元素期间可能会引起扩容而导致原空间被释放// v.insert(v.begin(), 0);// v.push_back(8);// 给vector重新赋值可能会引起底层容量改变v.assign(100, 8);/*出错原因以上操作都有可能会导致vector扩容也就是说vector底层原理旧空间被释放掉
而在打印时it还使用的是释放之间的旧空间在对it迭代器操作时实际操作的是一块已经被释放的
空间而引起代码运行时崩溃。解决方式在以上操作完成之后如果想要继续通过迭代器操作vector中的元素只需给it重新
赋值即可。*/while(it ! v.end()){cout *it ;it;}coutendl;return 0;
}
2.1.2. insert传进去的迭代器出了函数还能用吗
int main()
{vectorint 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);vectorint::iterator it find(v.begin(), v.end(), 4);v.insert(it, 100);cout *it endl;return 0;
}大家觉得这个代码 有问题吗在vs2019上运行起来会报出访问异常的问题这就是insert迭代器失效的问题。但是在LInux下不会出现问题因为底层的模拟实现是的g做不到这样的检查。但是有时候g有时候也会出问题所以统一认为迭代器失效了。2.1.3. erase删除偶数的问题先看代码
int main()
{zxf::vectorint 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);zxf::vectorint::iterator it v.begin();while (it ! v.end()){if (*it % 2 0){v.erase(it);}else{it;}}for (auto i : v) {cout i endl;}return 0;
}这个程序在vs2019下绝对报错但是在Linux下一般只要控制得好不会报错。注意erase有一个返回值返回欲删除元素的下一个元素的迭代器。所以一般要给it重新赋值。一般不使用删除位置的迭代器要想使用就要更新it。2.1.4. 用n个m去初始化的时候vectorint会出问题。先看我们实现的代码:其中的两个构造函数。vector(size_t n ,const T val T()):_start(nullptr),_finish(nullptr),_end_of_storagr(nullptr)
{reserve(n);while(n--){push_back(val);}
}template class InputIterator
vector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{while (first ! last){push_back(*first);first;}
}假如我们现在是一个vectorint的数组初始化的时候 vectorint v(5,6) 。5 6是会被识别成int类型。本意是想用5个6进行初始化的但是我们发现它把他识别成为了迭代器初始化。就会出现报错非法访问的问题。库里面的改进方法可以看到LInux中的gSGI版本的stl使用的是重载多个vector但是最后都调用同一个函数。这样就避免了走模板的困扰就很好的解决了这个问题。2.1.5.深层次的拷贝问题。观察代码void reserve(size_t n){if (n capacity()){size_t oldsize size();iterator tmp new T[n];if (_start){memmove(tmp, _start, sizeof(T) * oldsize);delete[] _start;}_finish tmp oldsize;_start tmp;//注意这里的顺序或者提前记录 oldsize的值。_end_of_storage tmp n;}}分析是不是发现没有什么问题但是这个代码是不对的为什么呢reserve是扩容的意思但是假设T是一个自定义类型。比如T vectorint ,这个时候tmp开好空间直接把原空间的值指向vetorint指针)拷贝给tmp数组vectovectorint,然后在delete原来的vectorvectorint,这个时候vector里面放的是一个自定义类型vectorint)就会调用自定义类型的析构函数释放掉原空间以及原空间内容指向的空间这个时候tmp的内容指向的空间就被释放了tmp里面的元素指向的空间被释放了他就是存了一系列的野指针。就会出问题。改进void reserve(size_t n){if (n capacity()){size_t oldsize size();iterator tmp new T[n];if (_start){
1· //memmove(tmp, _start, sizeof(T) * oldsize);for (size_t i 0; i oldsize; i){tmp[i] _start[i];}delete[] _start;}_finish tmp oldsize;_start tmp;//注意这里的顺序或者提前记录 oldsize的值。_end_of_storage tmp n;}}这样的话直接调用赋值重载就不会涉及到浅拷贝的问题。这样tmp里面元素vectorint指向的空间就不同了就很好的解决了这个问题虽然这样写效率不高但是现在的水平只能这样写。2.2.源码直接上源码vector.h#pragma once#includeassert.h
#includeiostreamusing namespace std;namespace zxf
{templateclass Tclass vector{public:typedef T* iterator;typedef const T* const_iterator;const_iterator begin()const{return _start;} iterator begin(){return _start;}iterator end(){return _finish;} const_iterator end()const{return _finish;}size_t size()const{//return (_finish - _start) / sizeof(T);return (_finish - _start);//注意这里对指针的正确理解}size_t capacity()const{return _end_of_storage - _start;}T operator[](size_t pos){//记住断言检查assert(pos size());return _start[pos];}const T operator[](size_t pos)const{assert(pos size());return _start[pos];}vector():_start(nullptr), _finish(nullptr), _end_of_storage(nullptr) {}~vector(){delete[] _start;_start nullptr;_finish nullptr;_end_of_storage nullptr;}templateclass Intputvector(Intput frist, Intput last):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){while (frist last){push_back(*frist);frist;}}//拷贝构造vector(const vectorT v):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){reserve(v.capacity());for (const auto a : v)//注意这里要加引用{push_back(a);}//想一想为何要加引用。//}vector(const vectorT v):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){vectorT tmp(v.begin(), v.end());swap(tmp);}vectorT operator(vectorT v)//这种写法简单//如果v1 v1 不太好//但是也不会出错{swap(v);return *this;}//vectorT operator(const vectorT v)//{// vectorT tmp(v.begin(),v.end())// swap(tmp);// return *this;//}void reserve(size_t n){if (n capacity()){size_t oldsize size();iterator tmp new T[n];if (_start){//memmove(tmp, _start, sizeof(T) * oldsize);for (size_t i 0; i oldsize; i){tmp[i] _start[i];}delete[] _start;}_finish tmp oldsize;_start tmp;//注意这里的顺序或者提前记录 oldsize的值。_end_of_storage tmp n;}}void push_back(const T value){if (_end_of_storage _finish){size_t newcapacity _start nullptr ? 4 : capacity() * 2;reserve(newcapacity);}*_finish value;_finish;}bool empty(){return _start _finish;}void pop_back(){//注意判断是否为空不能一直减assert(!empty());--_finish;}void resize(size_t n, T value T()){if (n capacity()){reserve(n);}if (n size()){_finish _start n;}else{while (size() ! n){*_finish value;_finish;}}}iterator insert(iterator pos, const T value){assert(pos _finish);assert(pos _start);size_t p pos - _start;//注意这里迭代器失效的问题if (_finish _end_of_storage){size_t newcapacity _start nullptr ? 4 : capacity() * 2;reserve(newcapacity);}pos _start p;for (iterator i _finish; i pos; i--){*(i 1) *i;}*pos value;_finish;return _start;}void insert(iterator pos, size_t n, const T val){assert(pos _finish);assert(pos _start);size_t p pos - _start;//注意也有迭代器失效问题if (_finish n _end_of_storage){size_t newcapacity capacity() n2;reserve(newcapacity);}pos _start p;for (iterator i _finish; i pos; i--){*(i n) *i;}int i n;while (i--){*pos val;pos;} _finish n;}iterator erase(iterator pos){assert(pos _finish);assert(pos _start);if (_start ! nullptr){for (iterator i pos; i _finish -1; i){*i *(i 1);}}--_finish;return pos;//这里是为了个库里面保持一致}void swap(vector v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}void clear(){_finish _start;}private:iterator _start;iterator _finish;iterator _end_of_storage;};}
