免费的行情网站推荐下载安装,园林景观设计公司管理流程,广州天河区酒店,网站建设seo虾哥网络vector的介绍及使用
1.1 vector的介绍
cplusplus.com/reference/vector/vector/
vector是表示可变大小数组的序列容器。就像数组一样#xff0c;vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素
进行访问#xff0c;和数组一样高效。但是…
vector的介绍及使用
1.1 vector的介绍
cplusplus.com/reference/vector/vector/
vector是表示可变大小数组的序列容器。就像数组一样vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素
进行访问和数组一样高效。但是又不像数组它的大小是可以动态改变的而且它的大小会被容器自
动处理。
本质讲vector使用动态分配数组来存储它的元素。当新元素插入时候这个数组需要被重新分配大小
为了增加存储空间。其做法是分配一个新的数组然后将全部元素移到这个数组。就时间而言这是
一个相对代价高的任务因为每当一个新的元素加入到容器的时候vector并不会每次都重新分配大
小。
vector分配空间策略vector会分配一些额外的空间以适应可能的增长因为存储空间比实际需要的存
储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何重新分配都应该是
对数增长的间隔大小以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
因此vector占用了更多的存储空间为了获得管理存储空间的能力并且以一种有效的方式动态增
长。
与其它动态序列容器相比deque, list and forward_list vector在访问元素的时候更加高效在末
尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作效率更低。比起list和forward_list
统一的迭代器和引用更好。
使用STL的三个境界能用明理能扩展 那么下面学习vector我们也是按照这个方法去学习
1.2vector的使用
1.2.1vector的构造函数 **(constructor)**构造函数声明接口说明vector()重点无参构造vectorsize_type n, const value_type val value_type()构造并初始化n个valvector (const vector x); 重点拷贝构造vector (InputIterator first, InputIterator last);使用迭代器进行初始化构造
构造一个vector变量以下情况都是OK的
vectorint v1; vectorint v2(10, 5); // 10个5 vectorint v3(v2.begin(), v2.end()); vectorint v4(v2); 1.2.2析构函数
这里的析构函数一般情况下我们不需要管因为它会自动调用。
拷贝构造和赋值构造vector 的拷贝构造和赋值其实就是深拷贝。
这些我们放在 vector 模拟实现的章节里详细探讨。
1.2.3push_back函数
void push_back (const value_type val);
这实际上会使size增加1当且仅当新的vector大小超过当前vector的capacity时才会自动重新分配分配的存储空间。
vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);1.2.4各种遍历方法
1.for循环遍历 2.迭代器遍历 3.范围for遍历本质也是迭代器
vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);for (size_t i 0; i v.size(); i){cout v[i] ;}cout endl;vectorint::iterator it v.begin();while (it ! v.end()){cout *it ;it;}cout endl;for (auto e: v){cout e ;}cout endl;它不止可以用vector的迭代器只要可以进行类型转换就可以了
string s1(hello world);vectorintv3(s1.begin(), s1.end());for (auto e : v3){cout e ;}cout endl;如果不要第一个和最后一个可以进行和—
string s1(hello world);vectorintv3(s1.begin(), --s1.end());for (auto e : v3){cout e ;}cout endl;反向迭代器 1.2.5 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。
我们对vector默认扩容机制进行测试 void TestVectorExpand()
{size_t sz;vectorint v;sz v.capacity();cout making v grow:\n;for (int i 0; i 100; i){v.push_back(i);if (sz ! v.capacity()){sz v.capacity();cout capacity changed: sz \n;}}
}这里size、capacity和empty我就不做详细介绍了主要介绍一下resize和reserve函数
resize函数void resize (size_type n, value_type val value_type());
如果n小于当前容器的大小内容会缩小到它的前n个元素并删除后面的元素(并销毁它们)。
如果n大于当前容器的大小则在容器末尾插入尽可能多的元素以达到n的大小。如果指定val则新元素被初始化为val的副本否则对它们进行值初始化。
如果n也大于当前容器容量则会自动重新分配已分配的存储空间。
注意这个函数通过插入或删除容器中的元素来改变容器的实际内容。
我们可以用resize直接构造出了作用域他们会自己析构
void test_vector4()
{vectorintv;v.resize(10, 0);vectorintv2(10, 0);
}这两种都可以开空间初始化但是上面这种情况比较好
reserve函数void reserve (size_type n);
1.2.6pop_back 函数
void pop_back();
删除最后一个元素
1.2.7insert 函数 通过在指定位置的元素之前插入新元素可以有效地增加容器的大小。
当且仅当新的向量大小超过当前向量容量时会导致已分配的存储空间自动重新分配。
void test_vector7() {vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);vectorint::iterator ret find(v.begin(), v.end(), 3);if (ret ! v.end()) {cout 找到了 endl;v.insert(ret, 30); // 在ret位置前面插入一个30}for (auto e : v) cout e ; cout endl;
}1.2.8erase函数
iterator erase (iterator position);
iterator erase (iterator first, iterator last);删除position位置的数据
1.2.9swap 函数
交换两个vector的数据空间
void swap (vector x);
1.3find函数 1.4 vector 迭代器失效问题。
迭代器的主要作用就是让算法能够不用关心底层数据结构其底层实际就是一个指针或者是对指针进行了
封装比如vector的迭代器就是原生态指针T 。因此迭代器失效实际就是迭代器底层对应指针所指向的
空间被销毁了而使用一块已经被释放的空间造成的后果是程序崩溃(即如果继续使用已经失效的迭代器
程序可能会崩溃)。
对于vector可能会导致其迭代器失效的操作有
会引起其底层空间改变的操作都有可能是迭代器失效比如resize、reserve、insert、assign、
push_back等。
#include iostream
using namespace std;
#include vector
int main()
{vectorint v{1,2,3,4,5,6};auto it v.begin();// 将有效元素个数增加到100个多出的位置使用8填充操作期间底层会扩容// v.resize(100, 8);// reserve的作用就是改变扩容大小但不改变有效元素个数操作期间可能会引起底层容量改变// v.reserve(100);// 插入元素期间可能会引起扩容而导致原空间被释放// v.insert(v.begin(), 0);// v.push_back(8);// 给vector重新赋值可能会引起底层容量改变v.assign(100, 8);/*出错原因以上操作都有可能会导致vector扩容也就是说vector底层原理旧空间被释放掉
而在打印时it还使用的是释放之间的旧空间在对it迭代器操作时实际操作的是一块已经被释放的
空间而引起代码运行时崩溃。解决方式在以上操作完成之后如果想要继续通过迭代器操作vector中的元素只需给it重新
赋值即可。*/while(it ! v.end()){cout *it ;it;}coutendl;return 0;
}出错原因以上操作都有可能会导致vector扩容也就是说vector底层原理旧空间被释放掉 而在打印时it还使用的是释放之间的旧空间在对it迭代器操作时实际操作的是一块已经被释放的 空间而引起代码运行时崩溃。 解决方式在以上操作完成之后如果想要继续通过迭代器操作vector中的元素只需给it重新 赋值即可。
指定位置元素的删除操作–erase
#include iostream
using namespace std;
#include vector
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就认为该位置迭代器失效了。
注意Linux下g编译器对迭代器失效的检测并不是非常严格处理也没有vs下极端。
// 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;
}
程序输出
1 2 3 4 5
扩容之前vector的容量为: 5
扩容之后vector的容量为: 100
0 2 3 4 5 409 1 2 3 4 5
// 2. 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// 3: erase删除的迭代器如果是最后一个元素删除之后it已经超过end
// 此时迭代器是无效的it导致程序崩溃
int main()
{vectorint v{1,2,3,4,5};// vectorint v{1,2,3,4,5,6};auto it v.begin();while(it ! v.end()){if(*it % 2 0)v.erase(it);it;}for(auto e : v)cout e ;cout endl;return 0;
}// 使用第一组数据时程序可以运行
[slyVM-0-3-centos 20220114]$ g testVector.cpp -stdc11
[slyVM-0-3-centos 20220114]$ ./a.out
1 3 5// 使用第二组数据时程序最终会崩溃
[xiaoluVM-0-3-centos 20220114]$ vim testVector.cpp
[xiaoluVM-0-3-centos 20220114]$ g testVector.cpp -stdc11
[xiaoluVM-0-3-centos 20220114]$ ./a.out
Segmentation fault从上述三个例子中可以看到SGI STL中迭代器失效后代码并不一定会崩溃但是运行结果肯定不
对如果it不在begin和end范围内肯定会崩溃的。
与vector类似string在插入扩容操作erase之后迭代器也会失效
#include string
void 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;}
}迭代器失效解决办法在使用前对迭代器重新赋值即可
