网站建设公司swot分析,注册公司需要什么条件?,有用织梦做的大网站吗,建一个网站需要什么条件前言 本文将模拟实现vector的常用功能#xff0c;目的在于更深入理解vector。 一、前置知识
在模拟之前先对vector的结构和常用接口学习#xff0c;有一个大致了解。看源码#xff0c;本文参考的源码是SGI版本的stl3.0。 技巧#xff1a; 看源码不要一行一行的看#xff…前言 本文将模拟实现vector的常用功能目的在于更深入理解vector。 一、前置知识
在模拟之前先对vector的结构和常用接口学习有一个大致了解。看源码本文参考的源码是SGI版本的stl3.0。 技巧 看源码不要一行一行的看要先看框架了解整体框架看源码要学会猜根据单词的意思去猜它想表达什么。规范的代码每一个名字都有它的含义。总结一看框架二去猜带着猜想去验证。 看框架的步骤 先看成员变量再看成员函数 参考vector的源码 vector的成员变量是三个原生指针变量设为原生指针类型有什么好处在模拟时讲解vector的成员函数vector的常用接口讲解链接 STL中的容器因为需要频繁的申请和释放空间所以STL中提供了内存池allocator类模板内存池的本质是先在堆区中申请一定的空间留作备用当有新的内存需求时就从内存池中分出一块内存块若内存块不够再继续申请新的内存这样可以提高内存分配的效率。现阶段我们只是简单模拟vector所以我们这没有使用内存池而是直接在堆区申请空间后期会讲解内存池的。
二、vector常用接口的模拟
1、vector的成员变量 vector的成员变量是三个原生指针T* _start开始位置即指向第一个元素的位置_finish结束位置即指向最后一个元素的下一个位置_end_of_storage存储结束位置 虽然vector使用的是三个原生指针但是可以通过指针运算得到size和capacity。 代码示例
//为了避免与库中的vector冲突将其封装在wjs的命名空间中
namespace wjs
{//类模板的实现和定义不分离后续学到模板进阶会讲解templateclass Tclass vector{public:typedef T* iterator;//获取容器中的元素个数size_t size()const//内部不改变成员变量建议加上const——普通对象和const对象都可以调用{//指针-指针两者之间的元素个数return _finish - _start;}//获取为当前容器分配的存储空间size_t capacity()const//内部不改变成员变量建议加上const——普通对象和const对象都可以调用{//指针-指针两者之间的元素个数return _end_of_storage - _start;}private:iterator _start;//开始位置指向第一个元素iterator _finish;//结束位置指向最后一个元素的下一个位置iterator _end_of_storage;//指向存储结束位置};
}tip
使用命名空间将我们模拟实现的vector封装避免命名冲突。类模板的定义与实现不分离后续在模板进阶讲解。size和capacity可以通过指针-指针得到注意指针-指针运算有一个前提是物理存储空间是连续的。const成员 const修饰的是*this即const成员函数的内部不能修改成员变量建议只要成员函数内部不修改成员变量都应该加const这样普通对象和const对象都可以调用
2、vector的默认成员函数 构造函数 构造函数创建类对象时编译器自动调用给成员变量赋初值类的成员变量建议在初始化列表初始化成员变量为内置类型需要我们手动初始化不然为随机值成员变量为自定义类型不初始化会去调用它的默认构造建议每个类都要有一个默认构造vector的常用构造函数 默认构造函数一般使用最多构造一个空的vector即将每个成员初始化为空构造并初始化n个val先初始化成员变量再复用reserve开n的空间最后再通过尾插将val插入容器使用迭代器初始化构造先初始化成员变量再将迭代器区间的数据尾插入容器 析构函数 析构函数对象销毁时编译器自动调用完成对象中资源的清理编译器生成的析构函数对内置类型不做处理自定义类型会去调用它的析构函数当类涉及动态资源的申请时就需要显式实现析构释放资源。 赋值重载函数 赋值重载函数已经存在的两个对象复制拷贝当类涉及资源管理时就需要自己显示实现完成深拷贝编译器默认生成的赋值重载函数只能完成浅拷贝赋值重载深拷贝的现代写法让形参去调用拷贝构造去帮我们开空间拷贝数据之后与形参交换函数结束后形参销毁也顺便帮我们把旧空间释放了现代写法无法避免自己给自己赋值的情况当现实中也很少会出现 拷贝构造函数 拷贝构造函数用一个已经存在的对象初始化另一个对象注意拷贝构造只有一个参数并且必须是本类型的引用使用传值会引发无限递归编译器默认生成的拷贝构造也是只能完成浅拷贝所以当类涉及资源管理时就需要自己显式实现完成深拷贝拷贝构造深拷贝的现代写法自己开空间自己拷贝数据 总结当类涉及资源管理时拷贝构造、赋值重载、析构都需要显式实现。 //为了避免与库中的vector冲突将其封装在wjs的命名空间中
namespace wjs
{//类模板的实现和定义不分离后续学到模板进阶会讲解templateclass Tclass vector{public://默认构造函数vector()//初始化列表成员变量定义的地方建议在初始化列表初始化成员变量//成员变量为内置类型不初始化为随机值:_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){}//构造并初始化n个valvector(size_t n, const T val T())//T()调用构造函数//初始化成员变量:_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){//复用reserve开空间reserve(n);//复用push_back尾插n个valfor (size_t i 0; i n; i){push_back(val);}}//使用迭代器区间初始化//类模板的成员函数也可以是函数模板templateclass InputIteratorvector(InputIterator first, InputIterator last)//初始化成员变量:_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){//复用push_back将迭代器区间[firstlast)的数据尾插进容器while (first ! last){push_back(*first);first;}}//当wjs::vectorint v(10, 1);报错——》 error C2100: 非法的间接寻址//函数重载调用时会走最匹配的wjs::vectorint v(10, 1)两个参数类型都是int所以他走使用迭代器构造//重载一个vector(int n, const T val T())他就会走构造n个val//构造并初始化n个valvector(int n, const T val T())//T()调用构造函数//初始化成员变量:_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){//复用reserve开空间reserve(n);//复用push_back尾插n个valfor (int i 0; i n; i){push_back(val);}}//交换两个vector对象void swap(vectorT v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}//赋值重载——现代写法叫别人帮我们开空间拷贝数据之后交换vectorT operator(vectorT v)//形参v直接就去调用拷贝构造帮我们开空间可拷贝数据了{//与v交换swap(v);return *this;}//拷贝构造函数vector(const vectorT v){//传统写法自己开空间自己拷贝_start new T[v.capacity()];//注意不能使用memcpy它只能完成浅拷贝for (size_t i 0; i v.size(); i){//当T为自定义类型时会去调用的它的赋值重载完成深拷贝_start[i] v._start[i];}_finish _start v.size();_end_of_storage _start v.capacity();}//析构函数~vector(){if (_start){delete[] _start;_start _finish _end_of_storage nullptr;}}};
}tip
重载函数在调用时会走匹配的。T()T是一个模板参数所以T()是一个任意类型的匿名对象。如果T是定义类型会去调用它的默认构造从这点建议每个类都需要有一个默认构造如果是内置类型也去调用内置类型的默认构造。理论上内置类型是没有构造函数的但是有了模板之后C对此做了特殊处理对内置类型做了升级也提供了构造。结论如果对象中涉及到资源管理时千万不能使用memcpy进行对象之间的拷贝因为memcpy是浅拷贝可能会引起内存泄漏甚至程序崩溃。
3、vector的遍历 迭代器 begin返回指向容器的第一个元素的位置的迭代器end返回指向容器最后一个元素的下一个位置的迭代器begin和end一般会实现两个版本普通版本和const版本有了迭代器就可以使用范围for因为范围for的底层就是替换为begin和end operator[] operator []越界是断言处理断言只在debug下会生效release下不生效operator[]一般也会实现两个版本一个返回普通引用一个返回常引用 //为了避免与库中的vector冲突将其封装在wjs的命名空间中
namespace wjs
{//类模板的实现和定义不分离后续学到模板进阶会讲解templateclass Tclass vector{public:typedef T* iterator;typedef const T* const_iterator;//普通版本迭代器——迭代器可读可写iterator begin(){//返回指向第一个元素的位置的迭代器return _start;}iterator end(){//返回指向最后一个元素的下一位置的迭代器return _finish;}//const版本迭代器——迭代器只可读const_iterator begin()const{//返回指向第一个元素的位置的const迭代器return _start;}const_iterator end()const{//返回指向最后一个元素的下一位置的const迭代器return _finish;}//operator[]//普通版本——返回普通引用可读可写T operator[](size_t pos){//operator[]越界断言assert(pos 0 pos size());//返回pos位置元素的引用return _start[pos];}//cosnt版本——返回const引用只可读const T operator[](size_t pos)const{//operator[]越界断言assert(pos 0 pos size());//返回pos位置元素的常引用return _start[pos];}};
}4、vector的reserve和resize resize resize将容器大小调整为n 如果n小于当前容器大小则内容将减少到其前n个元素删除超出的部分如果n大于当前容器大小则通过在末尾插入所需数量的元素来扩展内容以达到n的大小。如果指定了val则新元素将初始化为val的副本否则它们将进行值初始化注意如果n也大于当前容器容量则会自动重新分配存储空间 reserve reserve请求改变容器的capacity只有当n当前容量时reserve才会重新分配空间将其容量增加到n或更大 namespace wjs
{//类模板的实现和定义不分离后续学到模板进阶会讲解templateclass Tclass vector{public://调整容器的sizevoid resize(size_t n, const T val T()){//如果nsizeif (n size()){//如果ncapacity一次扩容避免多次扩容reserve(n);//尾插val使sizenwhile (_finish _start n){push_back(val);//_finish;尾插之后finish会1所以这里不能再重复1了}}else{//nsize使sizen调整_finish的位置即可_finish _start n;}}//调整容器容量void reserve(const size_t n){//只有ncapacity时才会重新开空间将其capacity增加到nif (n capacity()){size_t old_size size();iterator tmp new T[n];//判断if (_start){//memcpy是浅拷贝所以当拷贝的自定义类型且涉及资源管理时就会报错//memcpy(tmp, _start, sizeof(T) * old_size);for (size_t i 0; i old_size; i){//当T为自定义类型时会去调用它的赋值重载,完成深拷贝tmp[i] _start[i];}delete[] _start;}_start tmp;//_start的改变会影响size所以需要在前面将旧size保存_finish _start old_size;_end_of_storage _start n;}}};
}tip
memcpy是内存的二进制格式拷贝将一段内存空间中的内容原封不动的拷贝到另一段内存空间中即memcpy是浅拷贝当memcpy拷贝的内容不涉及资源管理时memcpy即高效又不会出错但当memcpy拷贝的是自定义类型且涉及资源管理时就会出错因为memcpy不能完成深拷贝结论如果对象中涉及到资源管理时千万不能使用memcpy进行对象之间的拷贝因为memcpy是浅拷贝可能会引起内存泄漏甚至程序崩溃。
5、vector的插入 push_back 尾插在vector的末尾插入x尾插需要注意①尾插之前需要检查是否扩容②尾插之后size1即_finish namespace wjs
{//类模板的实现和定义不分离后续学到模板进阶会讲解templateclass Tclass vector{public://尾插void push_back(const T x){//插入之前判断是否需要扩容if (_finish _end_of_storage){//扩容size_t new_capacity capacity() 0 ? 4 : 2 * capacity();reserve(new_capacity);}//尾插*_finish x;_finish;}};
}insert 在pos位置的元素之前插入xinsert需要注意①断言pos位置是否合理②插入之前检查是否需要扩容③插入之后需要更新size namespace wjs
{//类模板的实现和定义不分离后续学到模板进阶会讲解templateclass Tclass vector{public://pos位置的元素之前插入void insert(iterator pos, const T x){//断言pos位置是否合理assert(pos _start pos _finish);//插入之前判断是否需要扩容if (_finish _end_of_storage){//扩容size_t new_capacity capacity() 0 ? 4 : 2 * capacity();reserve(new_capacity);}//[pos, _finish - 1]的数据向后挪动将pos位置空出iterator end _finish - 1;while (end pos){*(end 1) *end;--end;}//pos位置插入x*pos x;_finish;}};
}tip
insert在pos位置的元素之前插入x需要向后挪动数据在模拟实现string的时候我们使用的是下标当是头插的时候结束条件我们不好控制因为size_t不会小于0我们当时使用了npos现在vector使用iterator就不会出现这种情况了。
测试代码
//测试insert
void test_vector04()
{wjs::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);v.push_back(7);v.push_back(8);for (auto e : v){cout e ;}cout endl;
}运行结果 分析 修改1
namespace wjs
{//类模板的实现和定义不分离后续学到模板进阶会讲解templateclass Tclass vector{public://pos位置的元素之前插入void insert(iterator pos, const T x){//断言pos位置是否合理assert(pos _start pos _finish);//插入之前判断是否需要扩容//注意扩容之后需要更新pos否则pos指向释放的旧空间会造成迭代器失效if (_finish _end_of_storage){//计算pos与_start的相对距离size_t len pos - _start;//扩容size_t new_capacity capacity() 0 ? 4 : 2 * capacity();reserve(new_capacity);//更新pospos _start len;}//[pos, _finish - 1]的数据向后挪动将pos位置空出iterator end _finish - 1;while (end pos){*(end 1) *end;--end;}//pos位置插入x*pos x;_finish;}};
}测试代码
//测试insert
void test_vector04()
{wjs::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);v.push_back(7);v.push_back(8);for (auto e : v){cout e ;}cout endl;//头插100auto pos v.begin();v.insert(pos, 100);//插入之后修改pos位置的元素*pos 10;cout *pos endl;for (auto e : v){cout e ;}cout endl;
}运行结果 分析
扩容之后在insert中更新pos只解决了内部迭代器失效的问题外面的pos并没有解决它仍指向一块已经释放的空间。思考那我们可以将pos参数设为引用内部的改变也影响外面吗答案是不可以因为引用的权限可以平移或缩小但是不可以放大。当外面传的pos迭代器为一个const迭代器时引用权限被放大这是错误的那将参数也设为常引用呢这也不可以因为常引用就不可以修改pos了。insert解决外部pos迭代器失效的方法是插入之后返回修改的pos迭代器即指向新插入的第一个元素的迭代器。
修改2
namespace wjs
{//类模板的实现和定义不分离后续学到模板进阶会讲解templateclass Tclass vector{public://pos位置的元素之前插入iterator insert(iterator pos, const T x){//断言pos位置是否合理assert(pos _start pos _finish);//插入之前判断是否需要扩容//注意扩容之后需要更新pos否则pos指向释放的旧空间会造成迭代器失效if (_finish _end_of_storage){//计算pos与_start的相对距离size_t len pos - _start;//扩容size_t new_capacity capacity() 0 ? 4 : 2 * capacity();reserve(new_capacity);//扩容之后更新pos解决内部pos失效问题pos _start len;}//[pos, _finish - 1]的数据向后挪动将pos位置空出iterator end _finish - 1;while (end pos){*(end 1) *end;--end;}//pos位置插入x*pos x;_finish;//返回形参pos解决外部pos失效问题return pos;}};
}测试代码
void test_vector04()
{wjs::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);v.push_back(7);v.push_back(8);for (auto e : v){cout e ;}cout endl;//头插100auto pos v.begin();//insert之后pos迭代器可能会失效(扩容)//记住insert之后就不要使用这个pos迭代器因为它可能失效了//使用这个pos迭代器是一个高危行为//如果非要使用这个pos这个位置的迭代器可以接收insert的返回值//insert的返回值就是指向pos这个位置的迭代器auto ret v.insert(pos, 100);*ret 10;cout *ret endl;for (auto e : v){cout e ;}cout endl;
}tip
insert之后pos迭代器可能会失效(扩容)记住insert之后就不要使用这个pos迭代器因为它可能失效了使用这个pos迭代器是一个高危行为
push_back可以复用insert
namespace wjs
{//类模板的实现和定义不分离后续学到模板进阶会讲解templateclass Tclass vector{public://尾插void push_back(const T x){插入之前判断是否需要扩容//if (_finish _end_of_storage)//{// //扩容// size_t new_capacity capacity() 0 ? 4 : 2 * capacity();// reserve(new_capacity);//}尾插//*_finish x;//_finish;//复用insertinsert(_finish, x);}};
}6、vector的删除 erase 删除pos位置的元素erase需要注意①断言pos位置是否合理即有没有数据②删除之后更新size即_finish。 思考 erase存在迭代器失效吗 erase删除pos位置元素后迭代器的意义变了指向删除的最后一个元素之后的元素的新位置理论上迭代器并没有失效因为删除并没有改变底层空间注意如果pos是最后一个元素删除之后pos刚好是_finish的位置而_finish位置是没有元素的所以pos迭代器失效VS系列下检测比较严格删除vector任意位置上的元素都认为该位置迭代器失效了Linux下g编译器对迭代器失效的检测就相对佛系处理没有VS下极端只有删除vector最后一个元素才认为迭代器失效了在实际场景中迭代器的意义变了也容易出现各种问题总结vector 迭代器对象在erase或insert后不能再访问这个迭代器我们都认为它失效了访问结果是未定义的。erase通过返回一个指向删除的最后一个元素之后的元素的新位置迭代器解决迭代器失效问题。 namespace wjs
{//类模板的实现和定义不分离后续学到模板进阶会讲解templateclass Tclass vector{public://删除pos位置的元素iterator erase(iterator pos){//断言pos是否合理assert(pos _start pos _finish);//删除pos位置元素即将[pos1, _finish - 1]的元素向前挪动iterator begin pos 1;while (begin _finish){*(begin - 1) *begin;begin;}--_finish;//erase通过返回一个指向删除的最后一个元素之后的元素的新位置迭代器解决迭代器失效问题即pos迭代器return pos;}};
}测试代码
void test_vector05()
{wjs::vectorint v2;v2.push_back(1);v2.push_back(2);v2.push_back(2);v2.push_back(3);v2.push_back(4);v2.push_back(5);v2.push_back(6);for (auto e : v2){cout e ;}cout endl;//删除所有偶数auto it2 v2.begin();while (it2 ! v2.end()){if (*it2 % 2 0){//erase之后迭代器失效//解决方案it2需要接收erase的返回值it2 v2.erase(it2);}else{it2;}}for (auto e : v2){cout e ;}cout endl;
}tip
insert和erase之后的迭代器失效是通过接收返回值解决的 pop_back 尾删删除vector中的最后一个元素尾删之后size-1这里直接复用erase即可 namespace wjs
{//类模板的实现和定义不分离后续学到模板进阶会讲解templateclass Tclass vector{public:void pop_back(){//复用eraseerase(_finish - 1);}};
}
