新郑网站建设公司,公司网站服务器维护,免费空白ppt模板下载,c 精品课程建设网站源程序目录 #x1f4a1;前言一#xff0c;构造函数1 . 强制编译器生成默认构造2 . 拷贝构造3. 用迭代器区间初始化4. 用n个val值构造5. initializer_list 的构造 二#xff0c;析构函数三#xff0c;关于迭代器四#xff0c;有关数据个数与容量五#xff0c;交换函数swap六前言一构造函数1 . 强制编译器生成默认构造2 . 拷贝构造3. 用迭代器区间初始化4. 用n个val值构造5. initializer_list 的构造 二析构函数三关于迭代器四有关数据个数与容量五交换函数swap六赋值拷贝七[ ]运算符八预留空间(扩容)8.1 使用memcpy拷贝问题(重点) 九尾插和尾删数据十插入数据 insert十一删除数据 erase十二insert和erase的迭代器失效问题(重点)1. 什么是迭代器失效2. insert 的迭代器失效2.1 insert 内部pos位置的失效2.2 insert 以后外部的实参失效 3. erase 以后的迭代器失效 前言
上篇文章已经介绍了vector容器的基本使用vector容器的基本使用这篇文章主要选择vector中一些核心的基本的接口进行模拟实现。 注意由于我们模拟实现时使用了类模板所以不建议进行文件分离不然会产生链接错误。所以我们把函数都写在.h文件中在Test.cpp文件中进行测试。 首先我们先给出vector类
#include assert.h
#include vector
#include iostream
using namespace std;templateclass T
class vector
{
public:// Vector的迭代器是一个原生指针typedef T* iterator;typedef T* const_iterator;//......private:iterator _start nullptr;//指向开始位置的指针iterator _finish nullptr;//指向最后一个位置的下一个位置的指针iterator _end_of_storage nullptr;//指向存储容量的尾
};一构造函数
在vector文档中构造函数分为好几个类型下面分别进行介绍
1 . 强制编译器生成默认构造
无参构造
vector() default;2 . 拷贝构造
//v2(v1);
vector(const vectorT v)
{//提前预开空间避免边尾插边扩容reserve(v.capacity());for (auto e : v){//this-push_back(e);push_back(e);}
}3. 用迭代器区间初始化
3.1 一个类模版的成员函数可以写成函数模版。 3.2 若使用iterator做迭代器会导致初始化的迭代器区间[first,last)只能是vector的迭代器重新声明迭代器迭代器区间[first,last)可以是任意容器的迭代器。
template class InputIterator
vector(InputIterator first, InputIterator last)
{while (first ! last){push_back(*first);first;}
}4. 用n个val值构造
vector(size_t n, const T val T())
{reserve(n);for (size_t i 0; i n; i){push_back(val);}
}vector(int n, const T val T())
{reserve(n);for (size_t i 0; i n; i){push_back(val);}
}具体使用
//初始化3个空
vectorstring v1(3);//初始化为3个xx
vectorstring v2(3, xx);//初始化为3个1
vectorint v3(3, 1);//err 非法的间接寻址.参数匹配问题
vectorint v3(3u, 1);//ok//如果非要这样传参数就需要再重载一个构造
vectorint v3(3, 1);4.1 为什么要重载两个类似的构造 理论上将提供了vector(size_t n, const T value T())之后vector(int n, const T value T())就不需要提供了但是对于vector int v(10, 5); 编译器在编译时认为T已经被实例化为int而10和5编译器会默认其为int类型 就不会走vector(size_t n, const T value T())这个构造方法 最终选择的是vector(InputIterator first, InputIterator last)。因为编译器觉得区间构造两个参数类型一致因此编译器就会InputIterator实例化为int但是10和5根本不是一个区间编译时就报错了故需要增加该构造方法。 4.2 T()是什么 T()是缺省值注意这里不能给0因为T可能为自定义类型当T为内置类型的时候也ok。因为C对内置类型进行了升级也有构造为了兼容模版。 5. initializer_list 的构造
5.1. C11新增的类模板initializer_list方便初始化。 5.2. 它的内部其实有两个指针一个指向第一个值的位置一个指向最后一个值的下一个位置并且支持迭代器。
vector(initializer_listT il)
{reserve(il.size());for (auto e:il){push_back(e);}
}具体使用 支持被花括号括起的任意个数的值给 initializer_list
auto il1 { 1,3,4,5,6,7 };
initializer_listint il2 { 1,2,3 };//这里的隐式类型转换不一样参数个数不固定
vectorint v4 { 7,8,9,4,5 };//隐式类型转换
vectorint v5({ 4,5,6 });//直接构造二析构函数
~vector()
{if (_start){delete[] _start;_start _finish _end_of_storage nullptr;}
}三关于迭代器
iterator begin()
{return _start;
}iterator end()
{return _finish;
}const_iterator begin()const
{return _start;
}const_iterator end()const
{return _finish;
}四有关数据个数与容量
//计算有效数据个数
size_t size()const
{return _finish - _start;
}//计算当前容量
size_t capacity()const
{return _end_of_storage - _start;
}五交换函数swap
与string类类似依然调用库里的swap函数进行指针的交换。
void swap(vectorT v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);
}六赋值拷贝
与string类的现代写法相同。
//赋值拷贝
//v3 v1;
vectorT operator(const vectorT v)
{swap(v);return *this;
}七[ ]运算符
//[]运算符
T operator[](size_t pos)
{//断言避免下标越界assert(pos size());return _start[pos];
}八预留空间(扩容)
void reserve(size_t n)
{//由于开空间后_start指向改变所以要提前记录原来的有效数据个数//以便在新空间中更新_finish的位置size_t old_size size();if (n capacity()){T* tmp new T[n];//开新空间if (_start){//memcpy(tmp, _start, sizeof(T) * old_size);for (size_t i 0; i old_size; i){//此时这里的赋值调用的是string的赋值肯定是深拷贝tmp[i] _start[i];}delete[] _start;//释放旧空间}_start tmp;//改变指向指向新空间//在新空间里更新_finish_end_of_storage的位置_finish _start old_size;_end_of_storage _start n;}
}8.1 使用memcpy拷贝问题(重点)
假设模拟实现的vector中的reserve接口中使用memcpy进行的拷贝以下代码会发生什么问题
int main()
{bite::vectorbite::string v;v.push_back(2222);v.push_back(2222);v.push_back(2222);return 0;
}问题分析 (1) memcpy是内存的二进制格式拷贝按字节拷贝将一段内存空间中内容原封不动的拷贝到另外一段内存空间中。 (2) 如果拷贝的是自定义类型的元素memcpy既高效又不会出错但如果拷贝的是自定义类型元素并且自定义类型元素中涉及到资源管理时就会出错因为memcpy的拷贝实际是浅拷贝。
图解如下
当把原空间里的2222拷贝进新空间后delete会先对原空间的每个对象调用析构函数再把原空间销毁但是此时tmp仍指向那块空间变成野指针了 复用赋值进行修改后
此时这里的赋值调用的是string的赋值肯定是深拷贝 九尾插和尾删数据
//尾插数据
void push_back(const T x)
{if (_finish _end_of_storage){size_t newcapacity capacity() 0 ? 4 : capacity() * 2;reserve(newcapacity);}*_finish x;_finish;
}//尾删
void pop_back()
{//断言确保有数据可删assert(size() 0);--_finish;
}十插入数据 insert
//void insert(iterator pos, const T x)
iterator insert(iterator pos, const T x)
{//断言判断下标的有效性assert(pos _start pos _finish);//判断是否扩容if (_finish _end_of_storage){size_t len pos - _start;size_t newcapacity capacity() 0 ? 4 : capacity() * 2;reserve(newcapacity);//insert函数的内部迭代器失效问题类似于野指针问题//扩容后pos位置失效需要重新计算pospos _start len;}//挪动数据再插入iterator end _finish - 1;while (end pos){*(end 1) *end;--end;}*(end 1) x;_finish;//返回新插入那个位置的迭代器return pos;
}十一删除数据 erase
iterator erase(iterator pos)
{assert(pos _start pos _finish);iterator end pos 1;while (end ! _finish){*(end - 1) *end;end;}--_finish;//返回删除位置的下一个位置的迭代器return pos;
}十二insert和erase的迭代器失效问题(重点)
1. 什么是迭代器失效
迭代器的主要作用就是让算法能够不用关心底层数据结构其底层实际就是一个指针或者是对指针进行了封装比如vector的迭代器就是原生态指针T* 。因此迭代器失效实际就是迭代器底层对应指针所指向的空间被销毁了而使用一块已经被释放的空间造成的后果是程序崩溃(即如果继续使用已经失效的迭代器程序可能会崩溃)。
2. insert 的迭代器失效
2.1 insert 内部pos位置的失效
当刚好执行了扩容操作这一步时由于要开辟新空间拷贝数据释放空间改变空间指向。但是此时pos位置还在原空间这就使pos变成了野指针如果对该位置进行访问就会导致程序崩溃。
所以在函数内部扩容后我们要更新pos迭代器 2.2 insert 以后外部的实参失效
演示代码如下
void vector_test2()
{vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);for (size_t i 0; i v1.size(); i){cout v1[i] ;}cout endl;//输入x查找是否存在如果存在在该位置前插入10int x;cin x;vectorint::iterator it find(v1.begin(), v1.end(), x);//用返回值接收it v1.insert(it, 10);//建议失效后的迭代器不要访问除非使用返回值。cout *it endl;for (size_t i 0; i v1.size(); i){cout v1[i] ;}cout endl;
}insert以后it这个实参会不会失效呢答案是会的。 在扩容的时候一定会导致迭代器失效。因为虽然在insert内部形参修正了但是形参的改变不影响实参。 迭代器失效的建议是不要使用失效的迭代器
如果非要访问此时插入的那个位置必须使用 insert 的返回值返回的是新插入那个位置的迭代器。
3. erase 以后的迭代器失效
erase 以后的迭代器失效问题比较复杂它与平台相关。
代码演示如下
int main()
{int a[] { 1, 2, 3, 4 };vectorint v(a, a sizeof(a) / sizeof(int));// 使用find查找3所在位置的iteratorvectorint::iterator it find(v.begin(), v.end(), 3);// 删除it位置的数据导致it迭代器失效。//v.erase(it); // errit v.erase(it); // okcout *it endl; // 此处会导致非法访问return 0;
}erase 以后it这个实参会不会失效呢答案是会的。
erase删除pos位置元素后it位置之后的元素会往前搬移没有导致底层空间的改变理论上讲迭代器不应该会失效但是如果it刚好是最后一个元素删完之后it刚好是end的位置而end位置是没有元素的那么it就失效了。或者说某个编译器有这样的机制当删除到一定的数量时会进行缩容处理此时it也就相当于野指针了。因此删除vector中任意位置上元素时vs就认为该位置迭代器失效了。
如果非要访问这个位置也需要用返回值重新赋值
以下代码的功能是删除vector中所有的偶数
int main()
{vectorint v{ 1, 2, 3, 4 };auto it v.begin();while (it ! v.end()){if (*it % 2 0)//v.erase(it); // errit v.erase(it); // okit;}return 0;
}这个代码在VS平台下一定会运行崩溃因为删除后it位置已经失效了此时再对it进行访问(操作或是解引用操作都是)会程序报错。
但是在Linux下g编译器对迭代器失效的检测并不是非常严格处理也没有vs下极端所以正常运行。 注意 与vector类似string在插入扩容操作erase之后迭代器也会失效但是string的插入一般由下标控制虽然也重载了迭代器版本但是并不常用。 综上所述迭代器失效解决办法在使用前对迭代器重新赋值即可。
