绵阳微网站制作,软件产品设计方案,asp个人网站源码,科技公司怎么取名字文章目录 vector介绍和使用1.vector的介绍2.vector的使用2.1 vector的定义2.2 vector iterator的使用2.3 vector空间增长问题2.4 vector增删查改2.5 vector迭代器失效问题 3.vector 在OJ中的使用 vector介绍和使用
1.vector的介绍 vector是表示 可变大小数组的 序列容器。 就… 文章目录 vector介绍和使用1.vector的介绍2.vector的使用2.1 vector的定义2.2 vector iterator的使用2.3 vector空间增长问题2.4 vector增删查改2.5 vector迭代器失效问题 3.vector 在OJ中的使用 vector介绍和使用
1.vector的介绍 vector是表示 可变大小数组的 序列容器。 就像数组一样vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问和数组一样高效。但是又不像数组它的大小是可以动态改变的而且它的大小会被容器自动处理。 本质讲vector使用动态分配数组来存储它的元素。当新元素插入时候这个数组需要被重新分配大小。为了增加存储空间其做法是分配一个新的数组然后将全部元素移到这个数组。就时间而言这是一个相对代价高的任务因为每当一个新的元素加入到容器的时候vector并不会每次都重新分配大小。 vector分配空间策略vector会分配一些额外的空间以适应可能的增长因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何重新分配都应该是对数增长的间隔大小以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。 因此vector占用了更多的存储空间为了获得管理存储空间的能力并且以一种有效的方式动态增长。 与其它动态序列容器相比deque, list and forward_list vector在访问元素的时候更加高效在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作效率更低。比起list和forward_list统一的迭代器和引用更好
2.vector的使用
vector学习时一定要学会查看文档vector文档介绍vector在实际中非常的重要在实际中我们熟悉常
见的接口就可以下面列出了哪些接口是要重点掌握的。 2.1 vector的定义
constructor接口说明vector()重点无参构造vectorsize_type n, const value_type val value_type()构造并初始化n个valvector (const vector x); 重点拷贝构造vector (InputIterator first, InputIterator last);使用迭代器进行初始化构造
2.2 vector iterator的使用
iterator的使用接口说明begin end重点获取第一个数据位置的iterator/const_iterator 获取最后一个数据的下一个位置的iterator/const_iteratorrbegin rend获取最后一个数据位置的reverse_iterator获取第一个数据前一个位置的reverse_iterator
2.3 vector空间增长问题
容量空间接口说明size获取数据个数capacity获取容量大小empty判断是否为空resize重点改变vector的sizereserve重点改变vector的capacity
capacity的代码在vs和g下分别运行会发现vs下capacity是按1.5倍增长的g是按2倍增长的。这个问题经常会考察不要固化的认为vector增容都是2倍具体增长多少是根据具体的需求定义的。vs是PJ版本STLg是SGI版本STL。reserve只负责开辟空间如果确定知道需要用多少空间reserve可以缓解vector增容的代价缺陷问题。resize在开空间的同时还会进行初始化影响size。
2.4 vector增删查改
vector****增删查改接口说明push_back重点尾插pop_back(重点尾删find查找。注意这个是算法模块实现不是vector的成员接口insert在position之前插入valerase删除position位置的数据swap交换两个vector的数据空间operator[]像数组一样访问重点
2.5 vector迭代器失效问题
迭代器的主要作用就是让算法能够不用关心底层数据结构其底层实际就是一个指针或者是对指针进行了封装比如vector的迭代器就是原生态指针T 。因此迭代器失效实际就是迭代器底层对应指针所指向的空间被销毁了而使用一块已经被释放的空间造成的后果是程序崩溃(即如果继续使用已经失效的迭代器程序可能会崩溃)。
对于vector可能会导致其迭代器失效的操作有
会引起其底层空间改变的操作都有可能是迭代器失效比如resize、reserve、insert、assign、push_back等。
#include iostream
using namespace std;
#include vectorint main()
{vectorint v{ 1,2,3,4,5,6 };auto it v.begin();v.resize(100, 8); // 将有效元素个数增加到100个多出的位置使用8填充操作期间底层会扩容v.reserve(100); // reserve的作用就是改变扩容大小但不改变有效元素个数操作期间可能会引起底层容量改变v.insert(v.begin(), 0); // 插入元素期间可能会引起扩容而导致原空间被释放v.push_back(8);v.assign(100, 8); // 给vector重新赋值可能会引起底层容量改变return 0;
}以上操作都有可能会导致vector扩容也就是说vector底层原理旧空间被释放掉而在打印时it还使用的是释放之间的旧空间在对it迭代器操作时实际操作的是一块已经被释放的空间而引起代码运行时崩溃。
解决方式在以上操作完成之后如果想要继续通过迭代器操作vector中的元素只需给it重新赋值即可。
#include iostream
using namespace std;
#include vectorint main()
{vectorint v{ 1,2,3,4,5,6 };auto it v.begin();/*v.resize(100, 8);v.reserve(100);v.insert(v.begin(), 0); v.push_back(8);v.assign(100, 8); */while (it ! v.end()){cout *it ;it;}cout endl;return 0;
}指定位置元素的删除操作 – erase
#include iostream
using namespace std;
#include vectorint main()
{int a[] { 1, 2, 3, 4 };vectorint v(a, a sizeof(a) / sizeof(int));vectorint::iterator pos find(v.begin(), v.end(), 3); // 使用find查找3所在位置的iteratorv.erase(pos); // 删除pos位置的数据导致pos迭代器失效。cout *pos endl; // 此处会导致非法访问return 0;
}erase删除pos位置元素后pos位置之后的元素会往前搬移没有导致底层空间的改变理论上讲迭代器不应该会失效.
但是如果pos刚好是最后一个元素删完之后pos刚好是end的位置而end位置是没有元素的那么pos就失效了。
因此删除vector中任意位置上元素时vs就认为该位置迭代器失效了。
实例删除vector中所有的偶数
#include iostream
using namespace std;
#include vectorint main()
{vectorint v{ 1, 2, 3, 4 };auto it v.begin();while (it ! v.end()){if (*it % 2 0)it v.erase(it);elseit;}return 0;
}注意Linux下g编译器对迭代器失效的检测并不是非常严格处理也没有vs下极端。
#include iostream
using namespace std;
#include vector// 1. 扩容之后迭代器已经失效了程序虽然可以运行但是运行结果已经不对了
int main()
{vectorint v{ 1,2,3,4,5 };for (size_t i 0; i v.size(); i)cout v[i] ;cout endl;auto it v.begin();cout 扩容之前vector的容量为: v.capacity() endl;// 通过reserve将底层空间设置为100目的是为了让vector的迭代器失效 v.reserve(100);cout 扩容之后vector的容量为: v.capacity() endl;// 经过上述reserve之后it迭代器肯定会失效在vs下程序就直接崩溃了但是linux下不会// 虽然可能运行但是输出的结果是不对的while (it ! v.end()){cout *it ;it;}cout endl;return 0;
}vs下 linux下 但是在linux中 erase删除任意位置代码后linux下迭代器并没有失效
因为空间还是原来的空间后序元素往前搬移了it的位置还是有效的。
#include vector
#include algorithm
int main()
{vectorint v{ 1,2,3,4,5 };vectorint::iterator it find(v.begin(), v.end(), 3);v.erase(it);cout *it endl;while (it ! v.end()){cout *it ;it;}cout endl;return 0;
}/*程序可以正常运行并打印
4
4 5 */与vector类似string在插入扩容操作erase之后迭代器也会失效
#define _CRT_SECURE_NO_WARNINGS
#include iostream
using namespace std;
#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;}
}
int main()
{TestString();return 0;
}迭代器失效解决办法在使用前对迭代器重新赋值即可
3.vector 在OJ中的使用
只出现一次的数字i
class Solution {
public:int singleNumber(vectorint nums) {int value 0;for (auto e : v) { value ^ e; }return value;}
};杨辉三角OJ
// 涉及resize / operator[]
// 核心思想找出杨辉三角的规律发现每一行头尾都是1中间第[j]个数等于上一行[j-1][j]
class Solution {
public:vectorvectorint generate(int numRows) {vectorvectorint vv(numRows);for (int i 0; i numRows; i){vv[i].resize(i 1, 1);}for (int i 2; i numRows; i){for (int j 1; j i; j){vv[i][j] vv[i - 1][j] vv[i - 1][j - 1];}}return vv;}
};总结通过上面的oj题目我们发现vector常用的接口更多是插入和遍历。遍历更喜欢用数组operator[i]的形式访问因为这样便捷。 删除排序数组中的重复项 OJ 只出现一次的数ii OJ 只出现一次的数iii OJ 数组中出现次数超过一半的数字 OJ 电话号码字母组合OJ
