邯郸wap网站建设公司,徐州网站简介,网站建设与管理实验,内容管理系统WordPress吃不了自律的苦#xff0c;又接受不了平庸的罪。想让自己变好#xff0c;但又想舒服些。 你啊你……要么就不要去想#xff0c;想了又不去做#xff0c;犹犹豫豫#xff0c;徘徊不前#xff0c;患得患失… 文章目录一、四种构造函数1.vector的框架和无参构造2.构造函数调…吃不了自律的苦又接受不了平庸的罪。想让自己变好但又想舒服些。 你啊你……要么就不要去想想了又不去做犹犹豫豫徘徊不前患得患失… 文章目录一、四种构造函数1.vector的框架和无参构造2.构造函数调用不明确调用函数时的匹配优先度所造成的问题二、vector的拷贝构造和赋值重载三、迭代器失效异地扩容引起的野指针问题1.insert异地扩容导致的迭代器失效2.vs和g对于erase后迭代器是否失效的处理手段一个极端一个温和四、vector的更深层次的拷贝1.memcpy逐字节拷贝造成的浅拷贝问题2.其他方便使用的小接口一、四种构造函数
1.vector的框架和无参构造
1. 下面是vector的框架其中成员变量分别为指向当前使用空间首部分的_start指针和最后一个元素的下一个位置的_finish指针以及指向可用空间末尾的下一个位置的_end_of_storage指针并且对于vector来说由于它的底层是由顺序表实现的所以它的迭代器就是原生态指针T*我们定义了const和非const的迭代器便于const和非const对象的迭代器的调用。
下面是SGI版本的stl_vector.h的源码实现我们模拟实现的就是SGI版本的源码。 namespace wyn
{templateclass Tclass vector{public:typedef T* iterator;typedef const T* const_iterator;…………private:iterator _start;iterator _finish;iterator _end_of_storage;};
}2. 无参的构造函数我们利用初始化列表来进行初始化。用nullptr初始化比较好因为nullptr的free或delete都不会出错。
vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr)
{}2.构造函数调用不明确调用函数时的匹配优先度所造成的问题
1. 除无参构造外常用的构造还有迭代器区间作为参数的构造函数。这里的迭代器需要用函数模板来实现因为构造vector所用的迭代器不一定只是vector类型的还有可能是string类型所以这里的迭代器形参需用模板来实现。 templateclass InputIterator
vector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{while (first last){push_back(*first);first;}
}2. 另一种构造是用n个value值来进行构造value既有可能是内置类型也有可能是自定义类型所以如果用引用作参数的话需要用const引用也就是常引用来作参数否则无法接收内置类型的实参。 3. 在实现完n个value构造的构造函数之后如果我们此时用10个int类型的数字1来构造对象v1实际会报错报错的原因其实是由于函数的匹配优先级所导致的实参无法正确匹配相应的构造函数。而使用10个char类型的字符A却不会报错这其实也是由于函数的匹配优先级决定的。
4. 对于size_t和常引用作为参数的构造来说它的匹配优先级对于10个1实际不是最高的因为常引用需要进行类模板参数T类型的推导而10又是整型intint到size_t还需要进行隐式类型转换代价有点大。 而对于迭代器区间作为参数的构造来讲函数模板参数InputIterator只需要进行一次类型推导即可完成匹配所以用10个1来构造时实际匹配的构造函数是迭代器区间作为参数的构造函数而在匹配的构造函数中对迭代器区间进行了解引用那就是对常量10进行了解引用则发生非法的间接寻址。
5. 对于这种问题的解决可以将size_t换成int类型或者将10强转为size_t类型但stl源码的解决方式并非是这样的而是利用了函数重载来解决了这个问题多重载了一个类型为int的构造函数。 //vectorint v1(10, 1);
//1.两个都是int则v1优先匹配的是两个参数均为同类型的模板class InputIterator不会是下面的构造因为10需要进行隐式类型转换
//1也需要进行类模板的显示实例化优先级并没有同类型参数的函数模板高函数模板只需要一次推导参数类型即可匹配成功。
//2.但是如果匹配了函数模板则解引用int类型就会发生错误非法的间接寻址。
//
//vectorchar v1(10, A);一个是int一个是char没有选择只能选择下面的构造函数进行v1的构造。//所以可以将构造函数的第一个参数类型改为int但库在实现的时候默认用的就是size_t我们改成int就不太好。
//那该怎么办呢答案就是看源代码。利用重载构造解决问题。
vector(size_t n, const T val T())//引用和指针在赋值时有可能出现权限问题。这里需要用常量引用否则无法接收常量值。:_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{reserve(n);while (n--){push_back(val);}
}
vector(int n, const T val T())//引用和指针在赋值时有可能出现权限问题。这里需要用常量引用否则无法接收常量值。:_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{reserve(n);while (n--){push_back(val);}
}
void test_vector8()
{std::string s(hello world);vectorint v(s.begin(), s.end());for (auto e : v){cout e ;}cout endl;//vectorint v1(10, 1);//报错非法的间接寻址vectorchar v1(10, A);//这样的情况都不会出现问题但是这样的情况构造函数第二个参数需要加const修饰以免权限放大for (auto e : v1){cout e ;}cout endl;//编译错误注释代码排除寻找出现问题的代码部分//运行错误进行调试
}二、vector的拷贝构造和赋值重载
1. 对于拷贝构造的实现和string一样还是有传统写法和利用打工人的现代写法利用打工人的本质实际就是代码重构。传统写法还分为两种一种是自己new一个空间然后利用memcpy对数据进行拷贝另一种就是提前用reserve预留好空间然后push_back将数据尾插到提前预留的空间当中但前一种的传统写法实际存在潜在的隐患如果拷贝的数据类型是自定义类型那就是浅拷贝因为memcpy拷贝设计资源申请的类型时会逐字节进行浅拷贝。所以还是使用现代写法吧。
2. 无论是从代码可读性还是实用性的角度来讲现代写法都更胜一筹这里利用形参对象v的迭代器来构造临时对象tmp然后将对象tmp和* this进行交换为了防止对象tmp离开函数栈帧销毁时造成野指针的访问问题所以在调用构造函数时采用了初始化列表的方式将* this的三个成员都初始化为nullptr。
3. 在实现拷贝构造后实现赋值重载就比较简单了利用传值拷贝构造的临时对象即可然后调用swap类成员函数即可完成自定义类型的赋值工作。为了符合连续赋值含义我们利用引用来作为返回值。
4.利用现代写法的拷贝构造和赋值重载无论是vectorvector int 这样的类型还是更为复杂的vector类型都可以完成深层次的拷贝问题
下面是我陷入的坑然后想了想又自己跳出来了。 vector swap(vectorT v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);return *this;
}
// v2(v1)---v1拷贝构造v2
vector(vectorT v):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{//1.普通的传统写法就是开空间和拷贝数据//_start new T[v.capacity()];//2.进阶的传统写法reserve(v.capacity());for (auto e : v)//遍历v将遍历所得的迭代器里面的值依次赋值给e如果T是自定义类型这里会发生多次的拷贝构造所以最好加引用。{push_back(e);}
}
vector(const vectorT v)//打工人依旧是带参数的构造函数:_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{//string时候的拷贝构造调用的是带参的构造函数依次来创建出tmp构造函数就是打工人vectorT tmp(v.begin(), v.end());swap(tmp);//交换的时候就可以体现出拷贝构造函数初始化列表的好处了。
}// v1 v2;
// v1 v1;//极少数情况才会出现自己给自己赋值况且自己给自己赋值也不报错所以我们容忍这种情况的出现。
vectorT operator(vectorT v)//返回引用符合连续赋值的含义
{swap(v);return *this;
}三、迭代器失效异地扩容引起的野指针问题
1.insert异地扩容导致的迭代器失效
1. 迭代器就是粘合容器和算法的粘合剂它可以让算法不用关心底层数据结构的实现其底层实际就是一个指针或是对指针进行封装的产物。 vector的迭代器是一个原生指针的typedef所以迭代器失效的本质就是指针失效换句话说就是野指针访问对指针指向的无效空间进行访问所导致的问题。
2. 在使用insert时我们需要传某个位置的迭代器如果在insert中不发生扩容则这个迭代器在insert之后还是有效的但只要在insert中发生扩容则迭代器就会失效因为reserve进行的是异地扩容所以原有的迭代器就不能使用因为原有迭代器指向的是已经释放的旧空间的某个位置所以如果继续使用则势必会发生野指针的访问这正是我们所说的迭代器失效。 3. 如果要解决方式也很简单,使用insert的返回值即可它的返回值是指向第一个新插入元素的迭代器。利用insert的返回值就不会发生迭代器失效的问题了。 //迭代器失效野指针问题
void insert(iterator pos, const T val)
{assert(pos _start);assert(pos _finish);if (_finish _end_of_storage){size_t len pos - _start;//记录一下原空间pos和_start的相对位置。size_t new_capacity capacity() 0 ? 4 : 2 * capacity();//扩容导致了迭代器pos失效因为进行了异地扩容pos位置指向的是已释放空间的迭代器reserve(new_capacity);pos _start len;//所以如果发生扩容则需要更新pos的位置}//挪动数据对于vector来说就不存在pos等于0时的越界问题但没有下标的问题又会产生指针的问题iterator end _finish - 1;while (end pos){*(end 1) *end;--end;}*pos val;_finish;
}
void test_vector4()//测试迭代器失效
{string s;vectorint v;//v.reserve(10);//如果提前开辟好空间就不会产生迭代器失效的问题。实际就是因为异地扩容导致的迭代器失效v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);vectorint::iterator it find(v.begin(), v.end(), 3);if (it ! v.end()){v.insert(it, 30);}//insert以后it不能继续使用因为迭代器可能失效野指针虽然在insert内解决了迭代器失效的问题但那只是修改了内部的pos//it是外部的依旧不可以使用传值传递外部的问题依旧没有被解决。(*it);//这里一定是一个野指针因为发生了异地扩容it指向的是旧空间的位置但野指针的访问并没有被编译器报错这很危险。//所以一定要小心对于野指针的使用如果it指向的旧空间被分配给某些十分关键的金融数据则野指针访问会修改这些关键数据非常危险//如果野指针的使用影响到其他的进程就完蛋了公司里出现这样的问题直接废球了。//1.为什么不用传引用来解决这里的问题呢因为对于地址这样的常量不能作为变量进行传递无法从int*转换为int*//2.所以在insert之后不要继续使用it因为他很有可能失效就算在vs上不失效但你能保证在其他平台下也不失效吗比如g呢for (auto e : v){cout e ;}cout endl;
}2.vs和g对于erase后迭代器是否失效的处理手段一个极端一个温和
1. 对于vs编译器来说他是认为erase后迭代器是失效的在2013的版本下会直接报断言错误在2022版本下会越界访问而g对迭代器失效的检测并不是非常严格处理也没有vs下极端。 2. erase删除任意位置代码后linux下迭代器并没有失效因为空间还是原来的空间后序元素往前搬移了it的位置还是有效的但是在vs下就会直接报错所以对于erase之后迭代器是否失效的这一讨论为了保证程序良好的移植性我们统一认为erase之后迭代器失效如果要使用则需要利用erase的返回值来对迭代器重新赋值。 iterator erase(iterator pos)
{assert(pos _start);assert(pos _finish);iterator begin pos 1;while (begin _finish){*(begin - 1) *(begin);begin;}--_finish;return pos;
}
void test_vector5()//测试迭代器失效
{std::vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);// it是失效还是不失效呢std::vectorint::iterator it find(v.begin(), v.end(), 3);if (it ! v.end()){v.erase(it);}//读cout *it endl;//PJ版实现的非常复杂相对于SGI版本。能够检查出来越界访问//写//(*it);for (auto e : v){cout e ;}cout endl;
}3. 这里在多说一句在应用场景要求删除所有的偶数情况下这样的情况稍加更加复杂如果条件控制不得当一不小心连g都有可能会报错在条件控制这里我们主要说一下while循环中if和if else的区别如果是if条件判断则后面的it无论什么情况都会一下无论是偶数还是奇数it都会这样的控制条件就比较容易出问题。而如果利用if和else来解决的话则只有在奇数情况下it才会偶数情况下it不会。这就是if和if else在用法上的区别。 平常在使用时要根据具体场景恰当选择这两个分支语句中的哪一个之前我不知道两者区别的时候就因为使用的场景不恰当导致出现了很多的bug。
void test_vector6()//这里我们用自己实现的erase来更新失效之后的迭代器
{// 要求删除所有的偶数vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(4);v.push_back(9);vectorint::iterator it v.begin();while (it ! v.end()){if (*it % 2 0){it v.erase(it);//所以正确的使用方式就是利用erase的返回值进行迭代器的使用这样不管你怎么用迭代器都不会失效。//因为在erase之后我们统一认为迭代器it失效了所以需要erase的返回值来更新迭代器代码在VS和g下面都可以跑。}//it;//更新迭代器之后不要继续it了因为erase的返回值已经帮你把it挪到下一个元素的位置了所以你就不要再了else{it;}//vs结果还是一样的erase之后itvs认为迭代器失效。所以不要尝试使用erase之后的迭代器。//统一认为erase之后的迭代器失效。}for (auto e : v){cout e ;}cout endl;
}
//insert扩容迭代器失效和erase后统一认为迭代器失效。如果想用那就不要去直接访问迭代器而是利用返回值更新一下迭代器。四、vector的更深层次的拷贝
1.memcpy逐字节拷贝造成的浅拷贝问题
1. 在测试接口部分我们创建了一个vectorvector int 类型的数组数组每个元素是vector int 类型由10个数字1组成的vector int 在push_back四次之前程序都不会报错在第五次的时候程序就会崩溃。 2. 其实是因为在第五次的时候要调用reserve接口reserve会进行开空间和数据拷贝的工作而数据拷贝利用的是memcpy逐字节拷贝的函数所以一旦拷贝的数据类型是自定义类型那就是指针的浅拷贝在临时对象离开函数栈帧销毁tmp对象时会调用析构函数将指针所指空间销毁这样一来*this对应的数组里面的每个vector int 对象的所有指针就都会变为野指针此时push_back就会对野指针进行访问自然程序会报错。 3. 所以如果想要解决那就不仅仅需要进行vectorvector int 类型的数组的深拷贝数组的元素也需要进行深拷贝所以就需要深层次的深拷贝继续利用memcpy当然是不行的但其实我们可以利用赋值重载来进行解决赋值重载间接调用拷贝构造拷贝构造又间接调用迭代器区间作为参数的构造函数用它当作打工人来帮我们构造一个和拷贝对象一样的对象最后将被拷贝对象成功创建出来赋值重载内部只需进行交换二维数组内部的一维数组的三个指针即可。 所以代码重构的思想是非常优雅的毫不费力地帮我们解决了深层次的深拷贝问题。 ~vector()
{delete[] _start;_start _end_of_storage _finish nullptr;
}
void reserve(size_t n)
{if (n capacity())//只进行扩容{size_t oldsize size();T* tmp new T[n];//不需要检查new失败因为Cnew失败直接抛异常if (_start)//空对象扩容时_start是nullptr没必要拷贝数据{//memcpy(tmp, _start, sizeof(T) * size());//如果是自定义类型则浅拷贝后的同一空间释放两次势必会造成野指针使用问题的出现//仅仅只发生vectorint对象数组的深拷贝是不行的还需要进行其中每个对象的深拷贝则需要深层次的深拷贝。for (size_t i 0; i oldsize; i){tmp[i] _start[i];//这里直接调用赋值重载赋值重载会帮助我们进行对象数组元素的深拷贝}delete[]_start;}/*_start tmp;_finish _start size();*///如果是空对象则_finish没改变为空而start变为tmp的首元素地址了。_start tmp;_finish tmp oldsize;_end_of_storage _start n;}
}
void resize(size_t n,T val T())//如果是自定义类型则将自定义类型的对象先进行初始化然后在插到vector里面。
{if (n capacity()){reserve(n);while (_finish _start n)//要小心这里的条件控制_finish不能等于_startn否则发生越界访问。{*_finish val;//如果T是自定义类型则这里发生赋值重载_finish;}}else{_finish _start n;}
}
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;
}
void test_vector9()//这里涉及很深的深拷贝问题。
{vectorvectorint vv;vectorint v(10, 1);vv.push_back(v);//第一次是开空间然后存放数据并不存在拷贝数据的情况。vv.push_back(v);vv.push_back(v);vv.push_back(v);vv.push_back(v);//这个地方会挂挂在扩容问题出在拷贝数据上面。for (size_t i 0; i vv.size(); i){for (size_t j 0; j vv[i].size(); j){cout vv[i][j] ;}cout endl;}cout endl;vectorvectorint vvret Solution().generate(5);//非静态成员函数的调用必须与某个特定对象相对。1.搞成静态就可以解决了。2.或者利用匿名对象调用非静态成员函数//这里出现问题的原因还是因为reserve里的memcpy浅拷贝因为拷贝构造利用的打工人是迭代器区间为参的构造函数依旧绕不开//push_back和reserve那么一旦出现对象数组的拷贝构造时reserve里面的memcpy就会造成野指针问题。for (size_t i 0; i vvret.size(); i){for (size_t j 0; j vvret[i].size(); j){cout vvret[i][j] ;}cout endl;}cout endl;
}2.其他方便使用的小接口
iterator begin()
{return _start;
}
iterator end()
{return _finish;
}
const_iterator begin()const
{return _start;
}
const_iterator end()const
{return _finish;
}
T operator[](size_t pos)
{assert(pos size());return _start[pos];//把_start当成数组玩就行。解引用比较麻烦
}
const T operator[](size_t pos)const
{assert(pos size());return _start[pos];//把_start当成数组玩就行。解引用比较麻烦
}
size_t size()const//const和非const对象都能调
{return _finish - _start;//左闭右开的差正好就是这个区间内的元素个数[0,10)是正好10个元素左闭右闭算的是间隔数如果算元素个数还得1
}
size_t capacity()const
{return _end_of_storage - _start;
}
bool empty()const
{return _start _finish;
}
void pop_back()
{assert(!empty());//判断为假就报错。--_finish;
}
