vector

1.vector的介绍及使用

1.1vector的介绍

1.2vector的使用

1.2.1vector的定义

1.2.2vector iterrator的使用

1.2.3vector 空间增长问题

1.2.4vector增删改查

1.2.5vector迭代器失效问题。（重点）

【揭秘！】这里有你从未听过的独特见解，快来点赞关注，开启智慧之旅

1.vector的介绍及使用

1.1vector的介绍

vector的文档介绍

1.2vector的使用

学习vector时一定要学会查看文档(上面有文档介绍)，vector在实际中非常重要，在实际中我们熟悉常见的接口就可以，下面列出了常见接口。

1.2.1vector的定义

(constructor)构造函数声明	接口说明
vector()	无参构造
vector(size_type n,const value_type& val = valve_type()))	构造并初始化n个val
vector(const vector& x) （重点）	拷贝构造
vector(InputIterator first,InputIterator last);	使用迭代器进行初始化构造

1.2.2vector iterrator的使用

iterator的使用

接口说明

begin + end

获取第一个数据位置的iterator/const_iterator

获取最后一个数据的下一个位置的iterator/const_iterator

rbegin + rend

获取最后一个数据位置的reverse_iterator

获取第一个数据前一个位置的reverse_iterator

1.2.3vector 空间增长问题

容量空间	接口说明
size	获取数据个数
capacity	获取容量大小
empty	判断是否为空
resize（重点）	改变vector的size
resever（重点）	改变vector的capacity

capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。这个问题经常会考察，不要固化的认为，vector增容都是2倍，具体多少是根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本STL。
reserve只负责开辟空间，如果确定知道需要用多少空间，reverse可以缓解vector增容的代价缺陷问题。
resize在开辟空间的同时还会进行初始化，影响size。

测试vector的默认扩容机制

using namespace std;
void TestVectorExpand()
{size_t sz;vector<int> 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：141

g++运行结果：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()
{vector<int> 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 << endl;}}
}

1.2.4vector增删改查

vector增删查改	接口说明
push_back （重点）	尾插
pop_back （重点）	头插
find	查找。（注意这个是算法模块实现，不是vector的成员接口）
insert	在position之前插入val
erase	删除position位置的数据
swap	交换两个vector的数据空间
operator[] （重点）	像数组一样访问
clear	清除所有数据

注：operator[ ] ：越界就直接断言

at：越界就直接抛异常

data：返回底层指针

1.2.5vector迭代器失效问题。（重点）

迭代器的主要作用就是让算法能够不关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装，比如：vector的迭代器就是原生指针T*。

因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃（即如果继续使用已经失效的迭代器，程序可能会崩溃）。

对于vector可能会导致其迭代器失效的操作有：

1.会引起其底层空间改变的操作，都有可能使迭代器失效，比如：resize、reserve、insert、assign、push_back等。

#include<iostream>
using namespace std;
#include<vector>int mian()
{vector<int> 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;}cout << endl;return 0;
}

2.指定位置元素的删除操作 - erase

#include<iostream>
using namespace std;
#include<vector>int main()
{int a[] = { 1,2,3,4 };vector<int> v(a, a + sizeof(a) / sizeof(int));//使用find查找3所在的位置的iteratorvector<int>::iterator pos = find(v.begin(), v.end(), 3);//删除pos位置的数据，导致pos迭代器失效v.erase(pos);cout << *pos << endl;  //此处会非法访问return 0;
}

earse删除pos位置元素后，pos位置元素会往前移，没有导致底层空间的改变，理论上迭代器应该不会失效，但是：如果pos刚好是最后一个元素，删完之后pos刚好是end的位置，而end位置是没有元素的，那么pos就失效了。因此删除vector中任意位置上的元素时，vs就认为该位置迭代器失效了。

下面的代码功能是删除vector中所有的偶数：

#include<iostream>
using namespace std;
#include<vector>int main()
{vector<int> v{ 1,2,3,4 };auto it = v.begin();while (it != v.end()){if (*it % 2 == 0)v.erase(it);  //这个方法是错的++it;}return 0;
}int mian()
{vector<int> v{ 1,2,3,4 };auto it = v.begin();while (it != v.end()){if (*it % 2 == 0)it = v.erase(it); //这里会更新位置++it;}return 0;
}

3.与vector类似，string在插入+扩容操作+erase之后，迭代器也会失效。

#include<iostream>
#include<string>
using namespace std;
void TestString()
{string s("hello");auto it = s.begin();// 开放之后代码会崩溃，因为resize到20，String会进行扩容// 扩容之后，it会指向旧空间，但是旧空间已经被释放了，该迭代器就失效了// 后续打印时，再访问it指向的空间程序就会崩溃// s.reszie(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;}
}

注：迭代器失效解决方法：在使用前，对迭代器重新赋值即可。

用心呈现，只为遇见更好的你！点赞关注，让我们的博客陪伴你成长！