C++ vector

前言：

vector的部分源码：

（做过删除，留下关键信息）

 

vector的使用
 

构造函数：

1 无参构造
 

vector<int> v1;

 2 构造并初始化n个val

	vector<int> v2(5,1);

3 拷贝构造

 

	vector<int> v3(v2);

4 使用迭代器进行初始化构造 

迭代器可以是任意容器的迭代器

	vector<int> v3(v2.begin(), v2.end());

    string s("hello");vector<int> v3(s.begin(), s.end());

 

vector的 iterator 的使用
 

1 begin+end （顺序）

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

 

    string s("hello");vector<int> v2(s.begin(),s.end());vector<int>::iterator it = v2.begin();//auto it = v2.begin();while (it != v2.end()){cout << *it << " ";it++;}cout << endl;

 有迭代器，就可以使用范围for遍历数组

    for (auto e : v2){cout << e << " ";}cout << endl;

const对象使用const迭代器进行遍历打印：

    const vector<int> v(5,3);vector<int>::const_iterator it = v.begin();while (it != v.end()){cout << *it << " ";it++;}cout << endl;

 

 

2 rbegin+rend（逆序） 

获取最后一个数据位置的reverse_iterator/const_reverse_iterator，获取第一个数据前一个位置的
reverse_iterator/const_reverse_iterator

 

	string s("hello");vector<int> v2(s.begin(),s.end());vector<int>::reverse_iterator rit = v2.rbegin();//auto rit = v2.rbegin();while (rit != v2.rend()){cout << *rit << " ";rit++;}cout << endl;

 vector的容量空间

size：获取数据个数

capacity：获取容量大小

empty：判断是否为空

1 resize

改变vector的size

reisze(size_t n, const T& data = T())

n<size 删除作用

size<n<capacitty 插入作用

n>capacity 扩容+插入 

传参给val，就用传过来的值，若没有传参，则用缺省值：匿名对象（先调用构造完成初始化）拷贝构造val 

 可完成开空间+初始化

    vector<int> v;v.resize(4);

2 reserve 

改变vector的capacity

reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题
 

     vector<int> v;//v.reserve(100);size_t sz = v.capacity();for (size_t i = 0; i < 100; i++){v.push_back(i);if (sz != v.capacity()){sz = v.capacity();cout << "扩容:" << sz << endl;}}

使用reserve，没有发生扩容

    vector<int> v;v.reserve(100);size_t sz = v.capacity();for (size_t i = 0; i < 100; i++){v.push_back(i);if (sz != v.capacity()){sz = v.capacity();cout << "扩容:" << sz << endl;}}

 

 如果已经确定vector中要存储元素大概个数，可以提前将空间设置足够，就可以避免边插入边扩容导致效率低下的问题了

vector 增删查改

1 push_back（尾插）

2 pop_back（尾删）

    vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);vector<int>::iterator 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;

3 find

 find不是vector自身提供的方法，是STL提供的算法，是算法模块实现，不是vector的成员接口

 4 insert

 在指定位置前插入值为val的元素，比如：3之前插入30,如果没有则不插入

5 erase 

 

    vector<int> v{ 1,2,3 ,4};// 使用列表方式初始化，C++11新语法vector<int>::iterator pos= find(v.begin(), v.end(), 3);//1. 先使用find查找3所在位置if (pos != v.end()){v.insert(pos, 20);// 2. 在pos位置之前插入30}auto it = v.begin();while (it != v.end()){cout << *it << " ";it++;}cout << endl;pos = find(v.begin(), v.end(), 3);v.erase(pos);it = v.begin();while (it != v.end()){cout << *it << " ";it++;}cout << endl;

insert和erase以后迭代器都失效了，不能在访问，所以以上代码中的迭代器pos在insert以后失效，重新赋值后，才可以使用

vector 迭代器失效问题

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

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

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

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

1. 会引起其底层空间改变的操作，都有可能使迭代器失效
 

比如：resize、reserve、insert、assign、push_back等

    vector<int> 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(0);//扩容了//v.assign(100, 8);//扩容了while (it != v.end())//操作的是已经释放掉的旧空间，程序崩溃{cout << *it << " ";it++;}cout << endl;

程序崩溃原因：以上操作，都有可能会导致vector扩容，一旦扩容，vector底层原理旧空间被释放掉，而在打印时，it使用的是已经释放掉的旧空间，在对it迭代器操作时，实际操作的是一块已经被释放的空间，而引起代码运行时崩溃

解决方案：给it重新赋值即可
 

    vector<int> v{ 1,2,3,4,5,6 };auto it = v.begin();v.resize(100, 8);it = v.begin();//重新赋值while (it != v.end()){cout << *it << " ";it++;}cout << endl;

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

    vector<int> v{ 1,2,3,4,5,6 };auto pos = find(v.begin(), v.end(), 5);v.erase(pos); 删除pos位置的数据，导致pos迭代器失效cout << *pos << endl;//非法访问

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

下面来看实例：

删除vector中所有的偶数

错误代码：

   vector<int> v{ 1, 2, 3, 4 };auto it = v.begin();while (it != v.end()){if (*it % 2 == 0)v.erase(it);//erase以后，it迭代器失效++it;//报错}

正确代码：

	vector<int> v{ 1, 2, 3, 4 };auto it = v.begin();while (it != v.end()){if (*it % 2 == 0){it = v.erase(it);//it失效，重新赋值，it成为下一个要判断的数据的迭代器}else{it++;}}for (auto e : v){cout << e << " ";}cout << endl;

3 注意

Linux下，g++编译器对迭代器失效的检测并不是非常严格，处理也没有vs下极端

1. 扩容之后，迭代器已经失效了，程序虽然可以运行，但是运行结果已经不对了
2. erase删除任意位置代码后，linux下迭代器并没有失效，因为空间还是原来的空间，it的位置还是有效的

3 erase删除的迭代器如果是最后一个元素，it已经等于end，失效了，++it导致程序崩溃
4 与vector类似，string在插入+扩容操作+erase之后，迭代器也会失效
 

vector的遍历

1 operator[]

    vector<int> v{ 1,2,3,4 };for (size_t i = 0; i < v.size(); i++){v[i] *= 10;//写cout << v[i]<<" ";//读}

 2 迭代器遍历

    vector<int> v{ 1,2,3,4 };vector<int>::iterator it = v.begin();//auto it = v.begin();while (it != v.end()){cout << *it << " ";it++;}cout << endl;

 

3 范围for遍历 

    for (auto e : v){cout << e << " ";}cout << endl;