做网站最便宜,网站是什么意思例如,基础建站如何提升和优化,淘宝网网页版登录入口在哪里目录
一.vector的介绍及使用
1.1.vector的介绍
1.2.vector的使用
1.2.1.vector的定义
1.2.2.vector iterator的使用
1.2.3.vector的空间增长问题
1.2.4.vector的增删查改
1.3.vector在OJ中的使用
题一#xff1a;只出现一次的数字
题二#xff1a;杨辉三角
题三只出现一次的数字
题二杨辉三角
题三电话号码的字母组合
1.4.vector迭代器失效问题
在VS环境下
在Linux环境下
string迭代器失效问题
二.vector深度剖析及模拟实现
2.1.原码剖析
2.2.模拟实现
2.2.1.迭代器相关
2.2.2.容量相关
2.2.3.元素访问相关
2.2.4.修改操作相关
2.2.5.成员函数相关
2.3.vector类的完整实现
vector.h
test.c 一.vector的介绍及使用
1.1.vector的介绍
1.vector是表示可变大小数组的序列容器。 2.就像数组一样vector也采用连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问和数组一样高效。但是又不像数组它的大小是可以动态改变的而且它的大小会被容器自动处理。 3.本质讲vector使用动态分配数组来存储它的元素。当新元素插入时候这个数组需要被重新分配大小为了增加存储空间。其做法是分配一个新的数组然后将全部元素移到这个数组。就时间而言这是一个相对代价高的任务因为每当一个新的元素加入到容器的时候vector并不会每次都重新分配大小。 4.vector分配空间策略vector会分配一些额外的空间以适应可能的增长因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何重新分配都应该是对数增长的间隔大小以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。 5.因此vector占用了更多的存储空间为了获得管理存储空间的能力并且以一种有效的方式动态增长。 6.与其它动态序列容器相比deque, list and forward_listvector在访问元素的时候更加高效在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作效率更低。比起list和forward_list统一的迭代器和引用更好。
注意
1.在向向量容器中插入元素时如果插入操作引起了向量容量的扩展那么执行插入之前所获得的一切迭代器指针引用都会失效因为空间被重新分配了元素的内存地址发生了变化如果插入操作没有引起向量容量的扩展那么只有处于插入位置之后的迭代器指针引用失效因为插入位置后面的元素被移动了对插入之前的元素不会有影响。
2.在删除向量容器中的元素时被删除元素后面的元素会顺序向前移动将被删除元素留下的空位补上而后面闲置的空间并不会被释放。删除操作的效率和插入类似被删除元素越靠前删除操作所需的时间就越多删除操作不会引起向量容器容量的改变因此被删除之前的迭代器指针引用都能够继续使用而删除元素之后的迭代器指针引用都会失效。
1.2.vector的使用
vector是STL中一种自定义数据类型包含在头文件vector中其定义如下所示
templateclass T,class AllocatorallocatorT
class vector;
vector是将元素置于一个动态数组中加以管理的容器是最简单的序列式容器。它支持随机存取元素。在程序开发过程中使用vector作为动态数组是非常方便的尤其是在末端添加或删除元素时速度非常快。
1.2.1.vector的定义 (constructor)构造函数声明 接口说明 vector()重点 无参构造 vector(size_type n, const value_type val value_type()) 构造并初始化n个val vector(const vector x)重点 拷贝构造 vector(InputIterator first, InputIterator last) 使用迭代器进行初始化构造
详解 说明
迭代器是STL中最基本的一部分内容它将容器与算法联系起来起着粘合剂的作用几乎STL提供的所有算法都是通过迭代器存取元素来实现的。它有些类似于指针当参数化类型是C内部类型时迭代器就是指针。
注意
vectorchar v和string s是不同的虽然二者存放的都是字符char。对于前者来说它是一个存放字符的数组末尾是不存在\0的需要我们自己手动添加对于后者来说它是一个字符串而字符串的末尾默认存在\0不需要我们自己手动添加。
案例
void test_vector()
{//方式一无参构造//vector对象可以初始化状态为空不指定大小也不指定初始值vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);//for循环for (size_t i 0; i v1.size(); i){cout v1[i] ;}cout endl;//迭代器vectorint::iterator it v1.begin();while (it ! v1.end()){cout *it ;it;}cout endl;//范围forfor (auto e : v1){cout e ;}cout endl;//方式二拷贝构造//用一个vector对象初始化另一个或相互赋值时两个vector对象的元素类型必须相同//其实它调用的是vector的拷贝构造函数vectorint copy(v1);for (auto e : copy){cout e ;}cout endl;vectorint v v1;for (auto e : v){cout e ;}cout endl;//方式三构造并初始化n个val//用vector对象的大小和统一初始值来定义容器vectorint v2(10, 1);for (auto e : v2){cout e ;}cout endl;//方式四使用迭代器进行初始化构造//迭代器有些类似于指针当参数化类型是C内部类型时迭代器就是指针vectorint v3(v2.begin(), v2.end());for (auto e : v3){cout e ;}cout endl;//既然有了vector为什么还需要string呢//虽然它和string底层都是存储字符char但还是有所不同的。//相比T是char的vector它自身默认是不存在\0的需要我们自己手动添加但是对于s来说它是一个字符串而字符串本身就是以\0结尾的。//所以说T是char的vector不能去替代string。string s1(hello world);vectorchar v4(s1.begin(), s1.end());//可以设置部分区间v3(s1.begin(), --s1.end())for (auto e : v4){cout e ;}cout endl;
}
运行结果 1.2.2.vector iterator的使用 iterator的使用 接口说明begin end重点获取第一个数据位置的iterator/const_iterator 获取最后一个数据的下一个位置的iterator/const_iterator rbegin rend获取最后一个数据位置的reverse_iterator获取第一个数据前一个位置的reverse_iterator
详解 迭代器主要有两种形式一种是可读可写的迭代器一种是只读的常量迭代器
正向迭代器容器类名::iterator 迭代器名常量正向迭代器容器类名::const_iterator 迭代器名反向迭代器容器类名::reverse_iterator 迭代器名常量反向迭代器容器类名::const_reverse_iterator 迭代器名
STL中的容器提供了begin()与end()函数返回一个随机访问迭代器来访问元素除此之外各容器还提供了rbegin()与rend()这样一对函数用于返回一个逆向迭代器。rbegin()返回的是逆向遍历的第一个元素即倒数第一个元素rend()返回的是逆向遍历的末尾元素的后一个位置即第一个元素的上一个位置其实这个位置已经不在容器中了。 案例
void test_vector()
{vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);//迭代器vectorint::iterator it v.begin();while (it ! v.end()){cout *it ;it;}cout endl;//反向迭代器vectorint::reverse_iterator rit v.rbegin();//auto ritv.rbegin();while (rit ! v.rend()){cout *rit ;rit;}cout endl;cout v.max_size() endl;
}
运行结果 1.2.3.vector的空间增长问题 容量空间 接口说明 size 获取数据个数 capacity 获取容量大小 empty 判断是否为空 resize重点 改变vector的size reserve重点 改变vector的capacity
详解 向量容器的容量与容器大小并不一定相同vector提供了两个函数capacity()和size()分别获取容器容量和容器大小。
reserve改变vector的capacity
案例一
#includetime.hvoid test_vector()
{//vs下capacity是按1.5倍增长的g下是按2倍增长的size_t sz;vectorint v;const size_t n 10000;size_t begin clock();sz v.capacity();cout making v grow:\n;for (int i 0; i n; i){v.push_back(i);if (sz ! v.capacity()){sz v.capacity();cout capacity changed: sz \n;}}size_t end clock();cout 消耗时间 end - begin endl;
}
运行结果 如果已经确定vector中要存储元素大概个数可以提前将空间设置足够这样就可以避免边插入边扩容导致效率低下的问题了。
案例二
#includetime.hvoid test_vector()
{//vs下capacity是按1.5倍增长的g下是按2倍增长的size_t sz;vectorint v;const size_t n 10000;size_t begin clock();sz v.capacity();//如果已经确定vector中要存储元素大概个数可以提前将空间设置足够//这样就可以避免边插入边扩容导致效率低下的问题了v.reserve(n);//提前将容量设置好可以避免一边插入一边扩容cout making v grow:\n;for (int i 0; i n; i){v.push_back(i);if (sz ! v.capacity()){sz v.capacity();cout capacity changed: sz \n;}}size_t end clock();cout 消耗时间 end - begin endl;
}运行结果 resize改变vector的size
案例一
void test_vector()
{//vectorint v1;//v1.resize(10, 0);//vectorint v2(10, 0);//reisze(size_t n, const T data T())//将有效元素个数设置为n个如果增多时增多的元素使用data进行填充//注意resize在增多元素个数时可能会扩容vectorint v;for (int i 1; i 10; i){v.push_back(i);}v.resize(5);v.resize(8, 100);v.resize(12);cout v contains: endl;for (size_t i 0; i v.size(); i){cout v[i] ;}cout endl;
}运行结果 案例二
void test_vector()
{vectorint v;v.reserve(10);cout capacity: v.capacity() endl;cout size: v.size() endl;for (size_t i 0; i 10; i){v[i] i;}cout v contains: endl;for (size_t i 0; i v.size(); i){cout v[i] ;}cout endl;
}
运行结果 分析
可以发现程序运行出错因为对于reserve而言它只是改变capacity而不会改变size所以此时的size依旧为0容器中没有存取任何元素。当我们通过关系运算符operator[]去访问容器中元素时程序就会发生异常显示下标越界。此时我们可以使用push_back()对程序进行修改它在插入元素的同时也会对size进行修改并且也会进行一定的扩容。
改进 小结
capacity的代码在vs和g下分别运行可以发现vs下capacity是按1.5倍增长的g下capacity是按2倍增长的。这个问题经常会考察不要固化的认为vector增容都是2倍具体增长多少是根据具体的需求定义的。vs是PJ版本STLg是SGI版本STLreserve只负责开辟空间如果确定知道需要用多少空间reserve可以缓解vector增容的代价缺陷问题resize在开空间的同时还会进行初始化影响size。
1.2.4.vector的增删查改 vector增删查改 接口说明 push_back重点 尾插 pop_back重点 尾删 find 查找注意这个是算法模块实现不是vector的成员接口 insert 在position之前插入val erase 删除position位置的数据 swap 交换两个vector的数据空间 operator[] 像数组一样访问
详解 push_back和pop_back从尾部插入和删除元素
push_back()函数是向vector容器末尾添加元素。先创建一个空的vector对象再调用push_back()函数向其中添加元素。而pop_back()用于弹出vector容器末尾的一个元素。
案例
void test_vector()
{vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);auto it v.begin();while (it ! v.end()){cout *it ;it;}cout endl;v.pop_back();v.pop_back();it v.begin();while (it ! v.end()){cout *it ;it;}cout endl;
}
运行结果 insert和erase插入和删除元素
vector提供了一对向容器中随机插入和删除元素的函数insert()与erase()函数其中insert()函数用于向容器中插入元素erase()函数用于移除容器中的元素。注意insert()函数与erase()函数中的位置只能由begin()或end()返回的迭代器来指示而不能用纯粹的数字作为参数。
案例
void test_vector()
{//find查找注意这个是算法模块实现不是vector的成员接口vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);for (auto e : v){cout e ;}cout endl;//1.先使用find查找2所在位置//注意vector没有提供find方法如果要查找只能使用STL提供的全局findvectorint::iterator pos find(v.begin(), v.end(), 2);if (pos ! v.end()){//2.在pos位置之前插入30v.insert(pos, 20);}for (auto e : v){cout e ;}cout endl;//v.erase(pos);//err不能直接用因为迭代器失效了若想要删除原来pos位置上的元素要对迭代器重新赋值pos find(v.begin(), v.end(), 2);if (pos ! v.end()){v.erase(pos);}for (auto e : v){cout e ;}cout endl;v.erase(v.begin());//可以直接进行头删for (auto e : v){cout e ;}cout endl;
}
运行结果 swap和operator[ ]
swap()函数主要用于交换两个vector对象的数据空间而operator[ ]主要用于对容器中元素进行访问与修改。
案例
void test_vector()
{vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);//通过operator[]读写第0个位置v[0] 10;cout v[0] endl;//使用for[]方式遍历for (size_t i 0; i v.size(); i){cout v[i] ;}cout endl;vectorint swapv;swapv.swap(v);cout v data: endl;for (size_t i 0; i v.size(); i){cout v[i] ;}cout endl;//使用迭代器遍历cout swapv data: endl;auto it swapv.begin();while (it ! swapv.end()){cout *it ;it;}//使用范围for遍历for (auto x : v){cout x ;}cout endl;
}
运行结果 1.3.vector在OJ中的使用
题一只出现一次的数字
题目描述
给你一个非空整数数组nums除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法来解决此问题且该算法只使用常量额外空间。
示例 1
输入nums [2,2,1]
输出1示例 2
输入nums [4,1,2,1,2]
输出4示例 3
输入nums [1]
输出1分析 使用异或操作符^相同为0相异为1。
实现
class Solution
{
public:int singleNumber(vectorint nums){int ret 0;for (auto e : nums)ret ^ e;return ret;}
};
题二杨辉三角
题目描述
给定一个非负整数numRows生成「杨辉三角」的前numRows行。在「杨辉三角」中每个数是它左上方和右上方的数的和。
示例 1:
输入: numRows 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]示例 2:
输入: numRows 1
输出: [[1]]分析 找出杨辉三角的规律发现每一行头尾都是1中间第[j]个数等于上一行[j-1][j]。
实现
class Solution
{
public:vectorvectorint generate(int numRows)//vectorvectorint vv;vv[i]对应vectorintvv[i][j]对应int{vectorvectorint vv;vv.resize(numRows, vectorint());//采用匿名对象对每一行进行初始化//初始化for (size_t i 0; i vv.size(); i){vv[i].resize(i 1, 0);vv[i][0] vv[i][vv[i].size() - 1] 1;//将每行的第一个和最后一个元素置为1}//遍历for (size_t i 0; i vv.size(); i){for (size_t j 0; j vv[i].size(); j){if (vv[i][j] 0){vv[i][j] vv[i - 1][j] vv[i - 1][j - 1];}}}return vv;}
};
扩展
vectorbit::vectorint vv(n)构造一个vv动态二维数组vv中总共有n个元素每个元素都是vector类型的每行没有包含任何元素如果n为5时如下所示 vv中元素填充完成之后如下图所示 使用标准库中vector构建动态二维数组时与上图实际是一致的。
题三电话号码的字母组合
题目描述
给定一个仅包含数字2-9的字符串返回所有它能表示的字母组合。答案可以按任意顺序返回。给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。 示例 1
输入digits 23
输出[ad,ae,af,bd,be,bf,cd,ce,cf]示例 2
输入digits
输出[]示例 3
输入digits 2
输出[a,b,c]实现
class Solution
{string _numToStr[10] { , ,abc,def,ghi,jkl,mno,pqrs,tuv,wxyz };
public:void Combinations(const string digits, size_t di, string combineStr, vectorstring strV){if (di digits.size()){strV.push_back(combineStr);return;}int num digits[di] - 0;string str _numToStr[num];for (auto ch : str){Combinations(digits, di 1, combineStr ch, strV);}}vectorstring letterCmobinations(string digits){vectorstring strV;if (digits.size() 0){return strV;}Combinations(digits, 0, , strV);return strV;}
};
1.4.vector迭代器失效问题
迭代器的主要作用就是让算法能够不用关心底层数据结构其底层实际就是一个指针或者是对指针进行了封装比如vector的迭代器就是原生态指针T* 。因此迭代器失效实际就是迭代器底层对应指针所指向的空间被销毁了而使用一块已经被释放的空间造成的后果是程序崩溃(即如果继续使用已经失效的迭代器程序可能会崩溃)。
情况分类 如果容器扩容并在其他地方重新开辟了一块空间那么原来容器底层的空间上所保存的迭代器全部失效 当容器调用insert()方法后当前位置到容器末尾元素的所有迭代器全部失效 当容器调用erase()方法后当前位置到容器末尾元素的所有迭代器全部失效。
在VS环境下
案例一
void test1()
{vectorint v{ 1,2,3,4,5 };auto it v.begin();//将有效元素个数增加到10个多出的位置使用8填充操作期间底层会扩容v.resize(10, 8);while (it ! v.end()){cout *it ;it;}cout endl;
}void test2()
{vectorint v{ 1,2,3,4,5 };auto it v.begin();//reserve的作用就是改变扩容大小但不改变有效元素个数操作期间可能会引起底层容量改变v.reserve(10);while (it ! v.end()){cout *it ;it;}cout endl;
}void test3()
{vectorint v{ 1,2,3,4,5 };auto it v.begin();//插入元素期间可能会引起扩容而导致原空间被释放v.insert(v.begin(), 0);v.push_back(6);while (it ! v.end()){cout *it ;it;}cout endl;
}void test4()
{vectorint v{ 1,2,3,4,5 };auto it v.begin();//给vector重新赋值可能会引起底层容量改变v.assign(10, 8);while (it ! v.end()){cout *it ;it;}cout endl;
}int main()
{test1();return 0;
}
运行结果 分析
会引起底层空间改变的操作都有可能导致迭代器失效比如resize、reserve、insert、assign、push_back等。
出错原因以上操作都有可能导致vector扩容也就是说vector底层原有的旧空间被释放掉而在打印时it还使用的是释放之间的旧空间在对it迭代器操作时实际操作的是一块已经被释放的旧空间从而引起代码运行时崩溃。解决方式在以上操作完成之后如果想要继续通过迭代器操作vector中的元素只需给it重新赋值即可。
案例二
int main()
{int a[] { 1, 2, 3, 4 };vectorint v(a, a sizeof(a) / sizeof(int));//使用find查找3所在位置的iteratorvectorint::iterator pos find(v.begin(), v.end(), 3);//删除pos位置的数据导致pos迭代器失效v.erase(pos);cout *pos endl; //此处会导致非法访问return 0;
}运行结果 分析
erase删除pos位置元素后pos位置之后的元素会往前搬移没有导致底层空间的改变理论上讲迭代器不应该会失效但是如果pos刚好是最后一个元素删完之后pos刚好是end的位置而end位置是没有元素的那么pos就失效了。因此删除vector中任意位置上元素时vs就认为该位置迭代器失效了。
案例三
int main()
{vectorint v{ 1, 2, 3, 4 };auto it v.begin();while (it ! v.end()){if (*it % 2 0){v.erase(it);//it v.erase(it);}else{it;}}for (auto e : v){cout e ;}cout endl;return 0;
}
运行结果 分析
该代码的功能是删除vector中所有的偶数在使用erase进行删除时出现迭代器失效问题。
出错原因因为vetor使用连续分配的内存erase删除一个元素导致后面所有的元素都会向前移动一个位置这些元素的地址发生了变化所以当前位置到容器末尾元素的所有迭代器全部失效。解决方式利用erase方法可以返回下一个有效的iterator即it v.erase(it)。
在Linux环境下
注意在Linux下g编译器对迭代器失效的检测并不是非常严格处理也没有vs下极端。
案例一 运行结果 分析
扩容之后迭代器已经失效程序虽然可以运行但是运行结果已经不对了。经过reserve之后it迭代器肯定会失效在vs下程序直接崩溃但是在Linux下不会虽然程序可以运行但是输出的结果是不对的。
案例二 运行结果 分析
erase删除任意位置代码后Linux下迭代器并没有失效。因为空间还是原来的空间后序元素往前搬移了it的位置还是有效的。
案例三 运行结果 分析
erase删除的迭代器如果是最后一个元素删除之后it已经超过end。此时迭代器是无效的it导致程序崩溃。
从上述三个例子中可以看到SGI STL中迭代器失效后代码并不一定会崩溃但是运行结果肯定不对如果it不在begin和end范围内肯定会崩溃的。
string迭代器失效问题
与vector类似string在插入扩容操作erase之后迭代器也会失效。
#include stringvoid TestString()
{string s(hello);auto it s.begin();//放开之后代码会崩溃因为resize到20会string会进行扩容//扩容之后it指向之前旧空间已经被释放了该迭代器就失效了//后序打印时再访问it指向的空间程序就会崩溃//s.resize(20, !);while (it ! s.end()){cout *it;it;}cout endl;it s.begin();while (it ! s.end()){it s.erase(it);//按照下面方式写运行时程序会崩溃因为erase(it)之后//it位置的迭代器就失效了//s.erase(it);it;}
}
小结
迭代器失效解决办法在使用前对迭代器重新赋值即可。
在向向量容器中插入元素时如果插入操作引起了向量容量的扩展那么执行插入之前所获得的一切迭代器,指针,引用都会失效因为空间被重新分配了元素的内存地址发生了变化如果插入操作没有引起向量容量的扩展那么只有处于插入位置之后的迭代器,指针,引用失效因为插入位置后面的元素被移动了对插入之前的元素不会有影响。
在删除向量容器中的元素时被删除元素后面的元素会顺序向前移动将被删除元素留下的空位补上而后面闲置的空间并不会被释放。删除操作的效率和插入类似被删除元素越靠前删除操作所需的时间就越多删除操作不会引起向量容器容量的改变因此被删除之前的迭代器,指针,引用都能够继续使用而删除元素之后的迭代器,指针,引用都会失效。
二.vector深度剖析及模拟实现
2.1.原码剖析
迭代器 成员变量 图解 2.2.模拟实现
前提为了避免和vector类发生冲突我们采用命名空间的方式来隔离冲突域。如下所示
namespace bite
{templateclass Tclass vector {public:typedef T* iterator;typedef const T* const_iterator;//主要接口函数private:iterator _start nullptr;iterator _finish nullptr;iterator _end_of_storage nullptr;};
}
2.2.1.迭代器相关
常用的迭代器分为正向迭代器与常量正向迭代器。正向迭代器可以改变对象中指定元素的值而常量正向迭代器不可以改变对象中指定元素的值。
//非const迭代器
iterator begin()
{return _start;
}iterator end()
{return _finish;
}//const迭代器
const_iterator begin() const
{return _start;
}const_iterator end() const
{return _finish;
}
2.2.2.容量相关
size用于获取容器大小
size_t size() const
{return _finish - _start;
}
capacity用于获取容器容量
size_t capacity() const
{return _end_of_storage - _start;
}
empty用于判断某个容器是否为空
bool empty()
{return _start _finish;
}
reserve用于改变vector的capacity
在进行reserve之前我们要判断所传入的值 n 是否大于capacity()若ncapacity()则先调用new来开辟一块新的空间然后调用memcpy函数来将旧空间的内容拷贝到新空间接着再调用delete将旧空间进行释放最后再更新_start_finish以及_end_of_storage。
void reserve(size_t n)
{if (n capacity()){//开辟新空间T* tmp new T[n];if (_start){//拷贝数据memcpy(tmp, _start, sizeof(T) * size());//删除旧空间delete[] _start;}_start tmp;_finish _start size();_end_of_storage _start n;}
}调试分析 可以发现_start和_end_of_storage的值在程序执行过程中均已发生改变而_finish的值却没有发生任何变化。因为当我们在开辟新空间tmp时_start的值已经发生了改变(指向tmp)而此时的_finish依旧是初始值nullptr。当我们在计算_finish_startsize()时结合size()_finish - _start此时的_finish_start_finish-_start_finishnullptr。所以最终_finish的值为0x00000000。
那么该如何进行修改才能使_finish的值进行更新呢
法一先更新_finish再更新_start。不推荐
_finish tmp size();
_start tmp;
_end_of_storage _start n;调试分析 通过调试可以发现此时的_finish的确发生了变化。但是该方法一般推荐因为不利于代码的后期维护。
法二先保存size()的值sz然后再按顺序更新_start和_finish。推荐
void reserve(size_t n)
{if (n capacity()){size_t sz size();//开辟新空间T* tmp new T[n];if (_start){//拷贝旧数据memcpy(tmp, _start, sizeof(T) * size());//释放旧空间delete[] _start;}_start tmp;//_finish _start size();//err因为size()_finish-_start所以_start_finish-_start_finishnullptr。又因为_start已经发生变化变成新空间的_start了而_finish还是旧空间的_finish,,所以_finish-_start就是一个负值,再加_start就是0_finish _start sz;_end_of_storage _start n;}
}
调试分析 通过调试可以发现finish的确发生了变化此时_finish为空的问题得到了有效解决。
之前vector中的内置类型均为int当我们将其置为string类型时案例如下
void test_vector()
{vectorstring v;v.push_back(111111111111111111111);v.push_back(222222222222222222222);v.push_back(333333333333333333333);v.push_back(444444444444444444444);for (auto e : v){cout e ;}cout endl;v.push_back(555555555555555555555);
}
调试分析 通过调试可以发现当我们在调用析构函数对旧空间进行释放时程序运行出错。结合前面所学内容应该是出现了深浅拷贝问题。 当第五次push_back时需要调用reserve函数进行增容开好空间后memcpy将旧空间的内容拷贝至新空间。由上述调试可知memcpy完成的是浅拷贝同时它把_start里_str所指向的空间的内容也进行了拷贝。待拷贝完成之后将delete[] _start而数组里存放的是string对象它会先去调用string对象的析构函数将堆上的空间进行释放然后再把_start所指向的空间进行释放最后再更新_start,_finish和_end_of_storage。当程序的生命周期结束之时vector会调用析构函数对空间进行释放但是tmp中string对象所指向的堆空间已经被释放此时的_str由于空间被释放已经变成一个野指针所以vector调用析构函数时会对这个野指针进行二次释放进而会导致程序崩溃。 小结
memcpy是内存的二进制格式拷贝将一段内存空间中内容原封不动的拷贝到另外一段内存空间中如果拷贝的是自定义类型的元素memcpy既高效又不会出错但如果拷贝的是自定义类型元素并且自定义类型元素中涉及到资源管理时就会出错因为memcpy的拷贝实际是浅拷贝。
结论
如果对象中涉及到资源管理时千万不能使用memcpy进行对象之间的拷贝因为memcpy是 浅拷贝否则可能会引起内存泄漏甚至程序崩溃。
为了避免该问题发生我们可以调用赋值运算符重载进行逐一拷贝以此来完成深拷贝。reserve函数的完整实现如下所示
void reserve(size_t n)
{if (n capacity()){size_t sz size();//开辟新空间T* tmp new T[n];if (_start){//拷贝旧数据//memcpy(tmp, _start, sizeof(T) * size());for (size_t i 0; i sz; i){tmp[i] _start[i];//赋值运算符重载}//释放旧空间delete[] _start;}_start tmp;//_finish _start size();//err因为size()_finish-_start所以_start_finish-_start_finishnullptr。又因为_start已经发生变化变成新空间的_start了而_finish还是旧空间的_finish,,所以_finish-_start就是一个负值,再加_start就是0_finish _start sz;_end_of_storage _start n;}
}
resize改变vector的size
resize主要用于改变vector的size大小。分三种情况进行讨论
n _finish_finish n _end_of_storagen _end_of_storage
//T()采用匿名对象的方式生成一个默认缺省值
//val不能置为0因为T不一定为int类型
void resize(size_t n, T val T())
{if (n size()){//删除数据_finish _start n;}else{if (n capacity()){reserve(n);}while (_finish ! _start n){*_finish val;_finish;}}
}
2.2.3.元素访问相关
operator[ ]主要通过下标的方式对元素进行访问。分为const版和非const版。
//非const operator[]
T operator[](size_t pos)
{assert(pos size());return _start[pos];
}//const operator[]
const T operator[](size_t pos) const
{assert(pos size());return _start[pos];
}
2.2.4.修改操作相关
push_back尾插
void push_back(const T x)
{if (_finish _end_of_storage){//扩容reserve(capacity() 0 ? 4 : capacity() * 2);}*_finish x;_finish;
}
pop_back尾删
void pop_back()
{assert(!empty());--_finish;
}
insert在pos之前插入val
在插入之前首先要对插入位置的合法性进行判断然后判断空间是否已满若空间已满则进行扩容在扩完容之后要及时更新pos否则会发生迭代器失效问题最后再从后向前移动元素并进行插入。
iterator insert(iterator pos, const T val)
{assert(pos _start);assert(pos _finish);//检查容量if (_finish _end_of_storage){size_t len pos - _start;reserve(capacity() 0 ? 4 : capacity() * 2);pos _start len;//扩容后要更新pos解决pos失效问题}iterator end _finish - 1;while (end pos){*(end 1) *end;--end;}*pos val;_finish;return pos;
}
erase删除pos位置的数据
在删除之前首先要对删除位置的合法性进行判断然后再从前向后移动元素并进行删除。
//返回值是一个迭代器并且是被删除元素的下一个位置的迭代器
iterator erase(iterator pos)
{assert(pos _start);assert(pos _finish);iterator start pos 1;while (start ! _finish){*(start - 1) *start;start;}--_finish;return pos;
}
swap交换两个vector的数据空间
通过调用std库中的模板函数swap来实现两个vector中的数据空间交换。
void swap(vectorT v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);
}
2.2.5.成员函数相关
构造
无参构造
vector()
{}
有参构造
版本一区间构造
//若使用iterator做迭代器会导致初始化的迭代器区间[first,last)只能是vector的迭代器
//重新声明迭代器迭代器区间[first,last)可以是任意容器的迭代器
//[first,end)
templateclass InputIterator
vector(InputIterator first, InputIterator last)
{while (first ! last){push_back(*first);first;}
}
版本二
vector(size_t n, const T val T())//const T val T():调用T的默认构造生成一个匿名对象同时使用const引用可以延长匿名对象的生命周期到引用对象域结束
{reserve(n);for (size_t i 0; i n; i){push_back(val);}
}
版本三
vector(int n, const T val T())//const T val T():调用T的默认构造生成一个匿名对象同时使用const引用可以延长匿名对象的生命周期到引用对象域结束
{reserve(n);for (int i 0; i n; i){push_back(val);}
}
说明
理论上将提供了vector(size_t n, const T value T())之后vector(int n, const T value T())就不需要再提供了但是对于vectorint 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根本不是一个区间编译时就报错了故需要增加该构造方法。
为了去调用vector(size_t n, const T value T())我们可以在传递第一个参数时加上一个u即可那么编译器在编译时就会将其识别成无符号整数。
拷贝构造
在写拷贝构造时要避免浅拷贝问题的发生。如果对象中涉及到资源管理千万不要使用函数memcpy进行对象之间的拷贝因为memcpy是浅拷贝否则可能会引起内存泄漏甚至程序崩溃。
版本一
vector(const vectorT v)
{reserve(v.capacity());for (auto e : v){push_back(e);}
}
版本二
vector(const vectorT v)
{//reserve(v.capacity());_start new T[v.capacity()];//如果对象中涉及到资源管理时千万不能使用memcpy进行对象之间的拷贝因为memcpy是浅拷贝否则可能会引起内存泄漏甚至程序崩溃//memcpy(_start, v._start, sizeof(T) * v.size());//用赋值完成深拷贝for (size_t i 0; i v.size(); i){_start[i] v._start[i];}_finish _start v.size();_end_of_storage _start v.capacity();
}
版本三
//vector(const vector v)//可以不加模板参数
vector(const vectorT v)
{//借助区间构造迭代器去完成vector(InputIterator first, InputIterator last)vectorT tmp(v.begin(), v.end());swap(tmp);
}
赋值运算符重载
//vector operator(vector v)//可以不加模板参数
vectorT operator(vectorT v)
{swap(v);return *this;
}
析构
~vector()
{delete[] _start;_start _finish _end_of_storage;
}
2.3.vector类的完整实现
vector.h
#pragma once
#includeassert.hnamespace bite
{templateclass Tclass vector{public:typedef T* iterator;typedef const T* const_iterator;//构造vector(){}//vectorint v(10,5);vector(size_t n, const T val T())//const T val T():调用T的默认构造生成一个匿名对象同时使用const引用可以延长匿名对象的生命周期到引用对象域结束{reserve(n);for (size_t i 0; i n; i){push_back(val);}}/*理论上将提供了vector(size_t n, const T value T())之后vector(int n, const T value T())就不需要提供了但是对于vectorint 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根本不是一个区间编译时就报错了故需要增加该构造方法*/vector(int n, const T val T())//const T val T():调用T的默认构造生成一个匿名对象同时使用const引用可以延长匿名对象的生命周期到引用对象域结束{reserve(n);for (int i 0; i n; i){push_back(val);}}//若使用iterator做迭代器会导致初始化的迭代器区间[first,last)只能是vector的迭代器//重新声明迭代器迭代器区间[first,last)可以是任意容器的迭代器//[first,end)templateclass InputIteratorvector(InputIterator first, InputIterator last){while (first ! last){push_back(*first);first;}}//交换void swap(vectorT v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}//赋值运算符重载//vector operator(vector v)//可以不加模板参数vectorT operator(vectorT v){swap(v);return *this;}//拷贝构造/*vector(const vectorT v){reserve(v.capacity());for (auto e : v){push_back(e);}}*///拷贝构造传统写法//vector(const vectorT v)//{// //reserve(v.capacity());// _start new T[v.capacity()];// //如果对象中涉及到资源管理时千万不能使用memcpy进行对象之间的拷贝因为memcpy是浅拷贝否则可能会引起内存泄漏甚至程序崩溃// //memcpy(_start, v._start, sizeof(T) * v.size());// //用赋值完成深拷贝// for (size_t i 0; i v.size(); i)// {// _start[i] v._start[i];// }// _finish _start v.size();// _end_of_storage _start v.capacity();//}//拷贝构造现代写法//vector(const vector v)//可以不加模板参数vector(const vectorT v){//借助区间构造迭代器去完成vector(InputIterator first, InputIterator last)vectorT tmp(v.begin(), v.end());swap(tmp);}//析构~vector(){delete[] _start;_start _finish _end_of_storage;}//非const迭代器iterator begin(){return _start;}iterator end(){return _finish;}//const迭代器const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}//重置size//T()采用匿名对象的方式生成一个默认缺省值//val不能置为0因为T不一定为int类型void resize(size_t n, T val T()){if (n size()){//删除数据_finish _start n;}else{if (n capacity()){reserve(n);}while (_finish ! _start n){*_finish val;_finish;}}}//err//void reserve(size_t n)//{// if (n capacity())// {// T* tmp new T[n];// if (_start)// {// memcpy(tmp, _start, sizeof(T) * size());// delete[] _start;// }// _start tmp;// _finish _start size();// _end_of_storage _start n;// }//}//不推荐不利于代码维护/*void reserve(size_t n){if (n capacity()){T* tmp new T[n];if (_start){memcpy(tmp, _start, sizeof(T) * size());delete[] _start;}_finish tmp size();_start tmp;_end_of_storage _start n;}}*///扩容void reserve(size_t n){if (n capacity()){size_t sz size();//开辟新空间T* tmp new T[n];if (_start){//拷贝旧数据//memcpy(tmp, _start, sizeof(T) * size());for (size_t i 0; i sz; i){tmp[i] _start[i];//赋值运算符重载}//释放旧空间delete[] _start;}_start tmp;//_finish _start size();//err因为size()_finish-_start所以_start_finish-_start_finishnullptr。又因为_start已经发生变化变成新空间的_start了而_finish还是旧空间的_finish,,所以_finish-_start就是一个负值,再加_start就是0_finish _start sz;_end_of_storage _start n;}}//尾插void push_back(const T x){if (_finish _end_of_storage){//扩容reserve(capacity() 0 ? 4 : capacity() * 2);}*_finish x;_finish;}//尾删void pop_back(){assert(!empty());--_finish;}//插入//迭代器失效扩容引起野指针问题iterator insert(iterator pos, const T val){assert(pos _start);assert(pos _finish);//检查容量if (_finish _end_of_storage){size_t len pos - _start;reserve(capacity() 0 ? 4 : capacity() * 2);pos _start len;//扩容后要更新pos解决pos失效问题}//挪动数据iterator end _finish - 1;while (end pos){*(end 1) *end;--end;}*pos val;_finish;return pos;}//删除//返回值是一个迭代器并且是被删除元素的下一个位置的迭代器iterator erase(iterator pos){assert(pos _start);assert(pos _finish);iterator start pos 1;while (start ! _finish){*(start - 1) *start;start;}--_finish;return pos;}//非const operator[]T operator[](size_t pos){assert(pos size());return _start[pos];}//const operator[]const T operator[](size_t pos) const{assert(pos size());return _start[pos];}//大小size_t size() const{return _finish - _start;}//容量size_t capacity() const{return _end_of_storage - _start;}//判空bool empty(){return _start _finish;}private:iterator _start nullptr;iterator _finish nullptr;iterator _end_of_storage nullptr;};//const对象的访问void func(const vectorint v){//for循环for (size_t i 0; i v.size(); i){cout v[i] ;}cout endl;//迭代器vectorint::const_iterator it v.begin();while (it ! v.end()){cout *it ;it;}cout endl;}void test_vector1(){vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);//const对象的访问func(v1);//for循环for (size_t i 0; i v1.size(); i){cout v1[i] ;}cout endl;//迭代器vectorint::iterator it v1.begin();while (it ! v1.end()){cout *it ;it;}cout endl;v1.pop_back();v1.pop_back();v1.pop_back();//范围forfor (auto e : v1){cout e ;}cout endl;}//templateclass T//void f()//{// T x T();// cout x endl;//}////void test_vector2()//{// //内置类型有没有构造函数// int i int();//调用默认构造// int j int(1);// //int* pi int* ();//err// fint();// fint*();// fdouble();//}void test_vector2(){vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);//for循环for (size_t i 0; i v1.size(); i){cout v1[i] ;}cout endl;cout v1.size() endl;cout v1.capacity() endl;v1.resize(10);cout v1.size() endl;cout v1.capacity() endl;//for循环for (size_t i 0; i v1.size(); i){cout v1[i] ;}cout endl;v1.resize(3);cout v1.size() endl;cout v1.capacity() endl;//for循环for (size_t i 0; i v1.size(); i){cout v1[i] ;}cout endl;}//迭代器的主要作用就是让算法能够不用关心底层数据结构其底层实际就是一个指针或者是对指针进行了//封装比如vector的迭代器就是原生态指针T* 。因此迭代器失效实际就是迭代器底层对应指针所指向的//空间被销毁了而使用一块已经被释放的空间造成的后果是程序崩溃(即如果继续使用已经失效的迭代器程序可能会崩溃)//g没有强制检查具体问题具体分析结果未定义void test_vector3(){vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);//迭代器失效要更新posv1.insert(v1.begin(), 0);func(v1);auto pos find(v1.begin(), v1.end(), 3);if (pos ! v1.end()){v1.insert(pos, 30);//pos v1.insert(pos, 30);}func(v1);//insert以后我们认为pos失效不能再使用用pos接收可以解决这个问题//(*pos);func(v1);}void test_vector4(){vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);for (auto e : v1){cout e ;}cout endl;auto pos find(v1.begin(), v1.end(), 3);if (pos ! v1.end()){v1.erase(pos);}//erase以后pos是否失效答案是失效了最好不要访问因为行为结果未定义跟具体编译器实现有关(*pos);for (auto e : v1){cout e ;}cout endl;}void test_vector5(){bite::vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);for (auto e : v1){cout e ;}cout endl;//要求删除所有的偶数bite::vectorint::iterator it v1.begin();while (it ! v1.end()){if (*it % 2 0){//v1.erase(it);//errit v1.erase(it);//返回的是删除数据的下一个位置的迭代器}else{it;}}for (auto e : v1){cout e ;}cout endl;}void test_vector6(){vectorint v1(10, 5);for (auto e : v1){cout e ;}cout endl;vectorint v2(v1.begin() 1, v1.end() - 1);for (auto e : v2){cout e ;}cout endl;std::string s1(hello);vectorint v3(s1.begin(), s1.end());for (auto e : v3){cout e ;}cout endl;int a[] { 10,1,5,20,30,40,50 };vectorint v4(a, a 3);for (auto e : v4){cout e ;}cout endl;v1.insert(v1.begin(), 10);for (auto e : v1){cout e ;}cout endl;sort(v1.begin(), v1.end());for (auto e : v1){cout e ;}cout endl;//sort(a, a sizeof(a) / sizeof(a[0]));//升序//greaterint g;//sort(a, a sizeof(a) / sizeof(a[0]), g);//降序sort(a, a sizeof(a) / sizeof(a[0]), greaterint());for (auto e : a){cout e ;}cout endl;}class Solution{public:vectorvectorint generate(int numRows)//vectorvectorint vv;vv[i]对应vectorintvv[i][j]对应int{vectorvectorint vv;vv.resize(numRows, vectorint());//采用匿名对象对每一行进行初始化//初始化for (size_t i 0; i vv.size(); i){vv[i].resize(i 1, 0);vv[i][0] vv[i][vv[i].size() - 1] 1;//将每行的第一个和最后一个元素置为1}//遍历for (size_t i 0; i vv.size(); i){for (size_t j 0; j vv[i].size(); j){if (vv[i][j] 0){vv[i][j] vv[i - 1][j] vv[i - 1][j - 1];}}}return vv;}};void test_vector7(){vectorint v1(10, 5);for (auto e : v1){cout e ;}cout endl;vectorint v2(v1);for (auto e : v2){cout e ;}cout endl;vectorstd::string v3(3, 111111111111111111111);for (auto e : v3){cout e ;}cout endl;vectorstd::string v4(v3);for (auto e : v4){cout e ;}cout endl;v4.push_back(2222222222222222222222);v4.push_back(2222222222222222222222);v4.push_back(2222222222222222222222);for (auto e : v4){cout e ;}cout endl;//二维数组vectorvectorintret Solution().generate(5);for (size_t i 0; i ret.size(); i){for (size_t j 0; j ret[i].size(); j){cout ret[i][j] ;}cout endl;}cout endl;}void test_vector(){vectorstring v;v.push_back(111111111111111111111);v.push_back(222222222222222222222);v.push_back(333333333333333333333);v.push_back(444444444444444444444);for (auto e : v){cout e ;}cout endl;v.push_back(555555555555555555555);}
}
test.c
#includeiostream
#includealgorithm
#includefunctional
#includestring
#includevector
using namespace std;#includevector.hint main()
{//vectorint::iterator it;//cout typeid(it).name() endl;bite::test_vector();return 0;
}
