网站制作怎样容易,大连地图,网站设计制作哪家服务好,个人 网站建设方案书 备案上次讲了常用的接口#xff1a;C初阶#xff1a;容器#xff08;Containers#xff09;vector常用接口详解 今天就来进行模拟实现啦 文章目录 1.基本结构与文件规划2.空参构造函数#xff08;constructor)4.基本函数#xff08;size(),capacity(),resize(),reserve())4.增…上次讲了常用的接口C初阶容器Containersvector常用接口详解 今天就来进行模拟实现啦 文章目录 1.基本结构与文件规划2.空参构造函数constructor)4.基本函数size(),capacity(),resize(),reserve())4.增删改查(push_back,pop_back,insert,erase)5.在实现Insert和erase时迭代器失效问题6.重载[]7. 完善构造函数7.1vector (size_type n, const value_type val value_type());7.2利用迭代器进行构造7.3拷贝构造 8.重载9.析构函数 1.基本结构与文件规划 vector.h头文件包含类的全部(函数的声明与定义)test.cpp源文件进行调用test函数测试和完善功能 基本结构先看一下源码 namespace MyVector
{template class Tclass vector{public:typedef T* iterator;typedef const T* const_iterator;//先定义好迭代器//各种函数private:iterator _start;iterator _finish;iterator _endOfStorage;};
}_start指向动态数组的起始位置的指针即第一个元素的位置。_finish指向动态数组中最后一个元素之后的位置的指针。在这个实现中_finish 指针始终指向当前元素范围的末尾也就是下一个要插入元素的位置。_endOfStorage指向动态数组分配的内存空间的末尾之后的位置的指针。在这个实现中_endOfStorage 指针指向当前分配的内存空间的末尾当需要扩充容量时会通过比较 _finish 和 _endOfStorage 的位置来判断是否需要重新分配更大的内存空间 2.空参构造函数constructor) vector():_start(nullptr), _finish(nullptr), _endOfStorage(nullptr)//直接使用初始化列表{}都初始化为空指针 #3.迭代器iterator(begin(),end()) iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin()const{return _start;}const_iterator end()const{return _finish;}进行const的重载 4.基本函数size(),capacity(),resize(),reserve()) void reserve(size_t n){if (n capacity()){int old_size size();//保存一下长度方便后续给_finish移到新的位置T* tmp new T[n];if (_start ! nullptr)//vector里存东西了{for (size_t i 0; i size(); i){tmp[i] _start[i];//_start本质是指针}}delete[] _start;_start tmp;_finish _start old_size;_endOfStorage _start n;}}void resize(size_t n, const T x T()){if (n size()){reserve(n);//capacity 的话也没有进行处理while (_finish ! _start n){*_finish x;_finish; }}else{_finish _start n;//小于长度时直接移动finish}}size_t size(){return _finish - _start;}size_t capacity(){return _endOfStorage - _start;} reserve 函数 reserve 函数用于保留至少能容纳 n 个元素的内存空间。如果当前的容量小于 n则会分配新的内存空间并将原来的元素复制到新的内存空间中。首先它会创建一个新的大小为 n 的临时数组 tmp然后将原始数组中的元素复制到临时数组中。接着释放原始数组的内存空间将 _start 指针指向新分配的内存空间同时更新 _finish 和 _endOfStorage 的位置。 resize 函数 resize 函数用于改变数组的大小使其包含 n 个元素并使用值 x 进行初始化。如果 n 大于当前的大小它会调用 reserve 函数以确保数组有足够的容量然后将数组的大小增加到 n并使用值 x 进行初始化。如果 n 小于当前的大小它会直接将 _finish 指针移动到新的位置从而改变数组的大小。 size 函数 size 函数用于返回数组中元素的个数即 _finish 和 _start 之间的距离。 capacity 函数 capacity 函数用于返回数组的容量即 _endOfStorage 和 _start 之间的距离 怎么来理解const T x T()
实现给出各种类型的默认值在这里为了妥协其实内置类型也有构造函数在 C 中。内置类型如 int、float、double 等也有默认构造函数。默认构造函数对于内置类型来说其实就是不带参数的构造函数它会将变量初始化为默认值 T() 表示创建一个类型 T 的临时对象并进行值初始化。这里假设 T 是一个类或者结构体那么这个语句会调用 T 的默认构造函数来创建一个临时对象。const T x 表示创建一个类型为 T 的常量引用 x。这里的引用是 T 类型的引用而且是常量引用意味着 x 引用的对象是不可修改的。const T x T() 将这个临时对象绑定到常量引用 x 上。这样做的好处是可以避免不必要的拷贝同时也可以确保 x 引用的对象是不可修改的。 使用如下来测试 void test1(){vectorint v;for (auto e : v){cout e ;}cout endl;v.resize(10);for (auto e : v){cout e ;}cout endl;v.resize(5);for (auto e : v){cout e ;}cout endl;}4.增删改查(push_back,pop_back,insert,erase) void push_back(const T x){if (_finish _endOfStorage){int newcapacity capacity() 0 ? 2 : 2 * capacity();reserve(newcapacity);}*_finish x;_finish;}void pop_back(){assert(size() 0);--_finish;}iterator insert(iterator pos, const T x)//在pos前插入{assert(pos _finish pos _start);if (_finish _endOfStorage){size_t site pos - _start;int newcapacity capacity() 0 ? 2 : 2 * (capacity());reserve(newcapacity);pos _start site;//pos到新空间的位置上}iterator end _finish - 1;while (end pos)//开始整体向后退{*(end 1) *end;end--;}*pos x;_finish;return pos;}iterator erase(iterator pos)//删pos处{assert(pos _finish pos _start);assert(size() 0);//开始向前移动iterator start pos 1;while (start _finish){*(start - 1) *start;start;}_finish--;return pos;//返回删除的位置}使用test2函数看功能是否正常
void test2(){vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);//尾插3个for (auto e : v){cout e ;}cout endl;v.pop_back();//尾删一个for (auto e : v){cout e ;}cout endl;v.insert(v.begin(), 0);//头插一个0for (auto e : v){cout e ;}cout endl;v.erase(v.begin());//头删for (auto e : v){cout e ;}cout endl;}5.在实现Insert和erase时迭代器失效问题
当使用迭代器遍历容器时如果在遍历的过程中对容器进行了结构性的修改例如插入、删除元素重新分配内存等操作可能会导致迭代器失效。迭代器失效意味着该迭代器不再指向有效的元素或容器的结尾因此继续使用失效的迭代器可能会导致未定义行为。
迭代器失效的原因主要有以下几种
插入操作当在容器中插入元素时可能会导致容器内部的元素发生移动或重新分配内存这会导致原先的迭代器失效。因为插入元素后原先的迭代器可能不再指向正确的位置。删除操作当在容器中删除元素时可能会导致容器内部的元素发生移动也会导致原先的迭代器失效。因为删除元素后原先的迭代器可能指向了一个已经被删除的元素或者指向了不正确的位置。重新分配内存扩容时某些容器在元素数量达到一定阈值时会进行内存的重新分配这会导致原先的迭代器失效。因为重新分配内存后原先的迭代器可能指向了无效的内存地址。容器的清空当对容器进行清空操作时所有的元素都被移除迭代器也会失效。 迭代器失效可以大致分为两类 结构性变化导致的失效这类失效包括扩容时申请了新空间、插入或删除元素导致元素位置改变等情况。在这种情况下原先的迭代器可能会指向已经被移动或者删除的元素或者指向了新分配的内存空间导致迭代器失效。数据变化导致的失效这类失效包括使用了 memmove、std::copy 等函数对容器内部元素进行移动或复制的情况。这些函数可能会导致容器内部的元素发生移动导致原先的迭代器指向的位置发生变化从而导致迭代器失效。 void test3(){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);for (auto e : v){cout e ;}cout endl;//删除偶数vectorint::iterator it v.begin();while (it ! v.end()){if (*it % 2 0){itv.erase(it);//这里不能只是v.erase(it); 删除后}else{it;}}for (auto e : v){cout e ;}cout endl;}在使用 erase 函数删除元素后erase 函数会返回指向被删除元素之后的元素的迭代器而不是原先被删除元素的迭代器。如果使用 v.erase(it);则会导致 it 迭代器失效因为它指向的元素已经被删除而 it 没有更新。因此为了确保迭代器的有效性需要将返回的迭代器赋值给 it以便在下一次循环中继续使用正确的迭代器。 6.重载[] T operator[](size_t i){assert(i size());return _start[i];}const T operator[](size_t i) const{assert(i size());return _start[i];}7. 完善构造函数
7.1vector (size_type n, const value_type val value_type()); vector(size_t n, const T val T()){resize(n, val);}vector(int n, const T val T())//适用于 vectorint v(5,1){resize(n, val);}7.2利用迭代器进行构造 template class InputIteratorvector(InputIterator first, InputIterator last){while (first ! last){push_back(*first);first;}}为什么使用模版 因为可能使用其他类型的迭代器来进行初始化 7.3拷贝构造 vector(const vectorT v):_start(nullptr),_finish(nullptr),_endOfStorage(nullptr)//先利用初始化列表进行初始化{reserve(v.capacity());for (const auto e : v){push_back(e);}}8.重载 void swap(vectorT v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endOfStorage, v._endOfStorage);}vectorT operator(vectorT v){swap(v);return *this;}注意这里的参数不是常量引用而是按值传递的。这是因为在赋值操作符中我们会调用 swap 函数按值传递可以保证传入的参数会被复制一份避免对原对象的修改。在函数体内我们调用了 swap 函数将当前对象和传入的对象进行内容交换然后返回 *this即当前对象的引用。 9.析构函数 ~vector(){delete[] _start;_start _finish _endOfStorage nullptr;}好啦今天就到这里啦感谢大家支持
