平原做网站,国外最开放的浏览器有什么优势,宇说建筑网站,如何选择一家好的网站建设公司目录 前言vector的介绍及使用1. vector的使用1.1 vector的定义1.2 iterator的使用1.3 vector空间增长问题1.4 vector增删查改 2. vector迭代器失效问题(重点) 总结 前言
本文介绍了C中的vector数据结构及其使用方法。
更多好文, 持续关注 ~ 酷酷学!!! 正文开始
vector的介绍… 目录 前言vector的介绍及使用1. vector的使用1.1 vector的定义1.2 iterator的使用1.3 vector空间增长问题1.4 vector增删查改 2. vector迭代器失效问题(重点) 总结 前言
本文介绍了C中的vector数据结构及其使用方法。
更多好文, 持续关注 ~ 酷酷学!!! 正文开始
vector的介绍及使用
vector是表示可变大小数组的序列容器.就像数组一样, vector也采用的连续存储空间来存储元素. 也就是意味着可以采用下标对vector的元素进行访问, 和数组一样高效. 但是又不像数组, 它的大小是可以动态改变的, 而且它的大小会被容器自动处理.本质讲, vector使用动态分配数组来存储它的元素. 当新元素插入的时候, 这个数组需要被重新分配大小为了增加存储空间, 其做法是, 分配一个新的数组, 然后讲全部元素移动到这个数组, 就时间而言, 这是一个相对代价高的任务, 因为每当一个新的元素加入到容器的时候, vector并不会每次都重新分配大小.vector分配空间策略: vector会分配一些额外的空间以适应可能的增长, 因为存储空间比实际比实际需要的存储空间更大. 不同的库采用不同的策略权衡空间的使用和重新分配, 但是无论如何, 重新分配都应该是对数增长的间隔大小, 以至于在末尾插入一个元素的时候是在常数时间复杂度完成的.因此,vector占用了更多的存储空间, 为了获得管理存储空间的能力, 并且以一种有效的方式动态增长与其它动态序列容器相比(deque,list and forward_list) , vector在访问元素的时候更加高效, 在末尾添加和删除元素相对高效, 对于其他不在末尾的删除和插入操作, 效率更低, 比起list和forward_list 统一的迭代器和引用更好
使用STL的三个三个境界: 能用, 明理, 能拓展, 下面讲详细介绍STL – vector 1. vector的使用
我们先来查看vector的文档介绍, vector在实际中非常重要, 在实际中我们熟悉常见的接口就可以.
成员函数
1.1 vector的定义 代码演示:
int TestVector1()
{// constructors used in the same order as described above:vectorint first; // empty vector of intsvectorint second(4, 100); // four ints with value 100vectorint third(second.begin(), second.end()); // iterating through secondvectorint fourth(third); // a copy of third// 下面涉及迭代器初始化的部分我们学习完迭代器再来看这部分// the iterator constructor can also be used to construct from arrays:int myints[] { 16,2,77,29 };vectorint fifth(myints, myints sizeof(myints) / sizeof(int));cout The contents of fifth are:;for (vectorint::iterator it fifth.begin(); it ! fifth.end(); it)cout *it;cout \n;return 0;
}1.2 iterator的使用 代码演示:
void PrintVector(const vectorint v)
{// const对象使用const迭代器进行遍历打印vectorint::const_iterator it v.begin();while (it ! v.end()){cout *it ;it;}cout endl;
}void TestVector2()
{// 使用push_back插入4个数据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;// 使用迭代器进行修改it v.begin();while (it ! v.end()){*it * 2;it;}// 使用反向迭代器进行遍历再打印// vectorint::reverse_iterator rit v.rbegin();auto rit v.rbegin();while (rit ! v.rend()){cout *rit ;rit;}cout endl;PrintVector(v);
}1.3 vector空间增长问题 capacity的代码在vs和g下分别运行会发现, vs下capacity是按照1.5倍增长的, g是按2倍进行增长的, 这个问题经常会考察, 不要固化的认为, vector增容都是2倍, 具体增长多少是根据具体的需求定义的, vs是PJ版本STL, g是SGI版本STL.reserve只负责开辟空间, 如果确定知道需要用多少空间, reverse可以缓解vector增容的代价缺陷问题resize在开空间的同时还会进行初始化, 影响size.
可以执行下面代码在VS和g编译器分别进行测试vector的扩容机制
// 测试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;}}
}vs运行结果vs下使用的STL基本是按照1.5倍方式扩容
making foo grow :
capacity changed : 1
capacity changed : 2
capacity changed : 3
capacity changed : 4
capacity changed : 6
capacity changed : 9
capacity changed : 13
capacity changed : 19
capacity changed : 28
capacity changed : 42
capacity changed : 63
capacity changed : 94
capacity changed : 141g运行结果linux下使用的STL基本是按照2倍方式扩容
making foo grow :
capacity changed : 1
capacity changed : 2
capacity changed : 4
capacity changed : 8
capacity changed : 16
capacity changed : 32
capacity changed : 64
capacity changed : 128如果已经确定好vector中要存储元素的大概个数, 可以提前将空间设置足够,就可以避免边插入边扩容导致效率低下的问题了
举个例子: void TestVectorExpandOP()
{vectorint v;size_t sz v.capacity();v.reserve(100); // 提前将容量设置好可以避免一遍插入一遍扩容cout making bar 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;}}
}1.4 vector增删查改 代码演示: 尾插和尾删: push_back和pop_back
void TestVector4()
{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, 以及查找find 注意: find不是vector自身提供的方法, 是STL提供的算法模块, 使用时需要包含 algorithm 头文件
void TestVector5()
{// 使用列表方式初始化C11新语法vectorint v{ 1, 2, 3, 4 };// 在指定位置前插入值为val的元素比如3之前插入30,如果没有则不插入// 1. 先使用find查找3所在位置// 注意vector没有提供find方法如果要查找只能使用STL提供的全局findauto pos find(v.begin(), v.end(), 3);if (pos ! v.end()){// 2. 在pos位置之前插入30v.insert(pos, 30);}vectorint::iterator it v.begin();while (it ! v.end()) {cout *it ;it;}cout endl;pos find(v.begin(), v.end(), 3);// 删除pos位置的数据v.erase(pos);it v.begin();while (it ! v.end()) {cout *it ;it;}cout endl;
}operator[]index 和 C11中vector的新式forauto的遍历 vector使用这两种遍历方式是比较便捷的
void TestVector6()
{vectorint v{ 1, 2, 3, 4 };// 通过[]读写第0个位置。v[0] 10;cout v[0] endl;// 1. 使用for[]小标方式遍历for (size_t i 0; i v.size(); i)cout v[i] ;cout endl;vectorint swapv;swapv.swap(v);cout v data:;for (size_t i 0; i v.size(); i)cout v[i] ;cout endl;// 2. 使用迭代器遍历cout swapv data:;auto it swapv.begin();while (it ! swapv.end()){cout *it ;it;}// 3. 使用范围for遍历for (auto x : v)cout x ;cout endl;
}2. vector迭代器失效问题(重点)
迭代器的主要作用就是让算法能够不用关心底层的数据结构, 其底层实际就是一个指针, 或者是对指针进行了封装, 比如: vector的迭代器就是原生态指针T* , 因此迭代器失效, 实际就是迭代器底层对应指针所指向的空间被销毁了, 而使用的一块已经被释放的空间, 造成的后果是程序崩溃, 即如果继续使用已经失效的迭代器, 程序可能会崩溃.
对于vector可能会导致其迭代器失效的操作有:
会引起其底层空间改变的操作, 都有可能是迭代器失效, 如: resize, reserve, insert, assign, push_back等.
出错原因: 以下操作, 都有可能会导致vector扩容, 也就是说vector底层原理旧空间被释放掉, 而在打印的时候, it还使用的是释放之前的就空间, 在对it迭代器操作时, 实际操作的是一块被释放的空间, 而引起代码运行时崩溃.
int main()
{vectorint v{ 1,2,3,4,5,6 };auto it v.begin();v.resize(100, 8);//将有效元素个数增加到100个,多出的位置使用8填充,操作期间底层会扩容,其it不可以在使用v.reserve(100);//reserve的作用就是改变扩容大小但不改变有效元素个数,操作期间会引起底层容量改变,其it不可以在使用v.insert(v.begin(), 0);v.push_back(8);//插入元素期间,可能会引起扩容, 而导致原空间被释放,it不可以在使用v.assign(100, 8);//给vector重新赋值,可能会引起底层容量改变, 其it不可在使用while (it ! v.end()){cout *it ;it;}cout endl;return 0;
}解决方式: 在以上操作完成之后, 如果想要继续通过迭代器操作vector中的元素, 只需给it重新赋值即可.
可以看到insert这里返回值为一个迭代器, 迭代器的位置位插入元素之后的下一个新位置, 我们可以用来接受新的迭代器 指定位置元素的删除操作 – erase
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就认为该位置迭代器失效了. 当然, vs也给出了解决方案, 如果还想访问it则编译器会将新的it作为函数返回值 一个指向函数调用后最后被删除元素的下一个位置的迭代器。如果操作删除了序列中的最后一个元素那么就是容器的末尾。
错误写法
int main()
{vectorint v{ 1,2,3,4 };auto it v.begin();while (it ! v.end()){if (*it % 2 0){v.erase(it);}it;}return 0;
}正确写法:
int main()
{vectorint v{ 1,2,3,4 };auto it v.begin();while (it ! v.end()){if (*it % 2 0){it v.erase(it);}it;}return 0;
}注意: Linux下,g编译器对迭代器失效的检测并不是非常严格, 处理也没有vs下极端.
下面来看看Linux下的迭代器
扩容之后, 迭代器已经失效了, 程序虽然可以运行, 但是运行结果已经不对了
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 5erase删除任意位置代码后, linux下迭代器并没有失效, 因为空间还是原来的空间, 后序元素往前搬移了, it的位置还是有效的
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但是, 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)}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 // 使用第二组数据时程序最终会崩溃
[slyVM-0-3-centos 20220114]$ vim testVector.cpp
[slyVM-0-3-centos 20220114]$ g testVector.cpp -stdc11
[slyVM-0-3-centos 20220114]$ ./a.out
Segmentation fault从上述三个例子中可以看到: SGI STL中, 迭代器失效后, 代码并不一定会崩溃, 但是运行结果肯定不对, 如果it不在begin和end范围内, 肯定会崩溃的. 与vector类似, string在插入扩容操作erase之后, 迭代器也会失效
这里代码放开后会崩溃, 因为resize到20, string会进行扩容, 扩容之后, it指向之前的旧空间就已经被释放了, 该迭代器就失效了, 后续打印时, 在访问it指向的空间程序就会崩溃.
int main()
{string s(hello);auto it s.begin();//s.resize(20, !);while (it ! s.end()){cout *it;it;}cout endl;return 0;
}erase也是如此
int main()
{string s(hello);auto it s.begin();while (it ! s.end()){s.erase(it);//错误写法it s.erase(it);//it;}return 0;
}总结一下: 迭代器的解决办法, 在使用之前, 对迭代器重新赋值即可.
总结
vector是可变大小的数组能够动态调整其存储容量。 通过下标访问vector中元素的效率与数组相同但其大小由容器自动管理。 在扩容时vector会分配额外的空间从而提高末尾插入元素的效率。 vector支持通过迭代器高效访问元素但在增删操作中迭代器可能失效。 调用reserve可以提前分配空间减少扩容的性能损失。 vector中的元素可以通过多种方式插入和删除包括在中间位置插入以及尾部的增删。 在操作vector时若要继续使用迭代器需重新赋值以避免失效。 完
