C++ stl中的vector的相关用法 迭代器失效问题

vector的介绍及使用

1、vector是用于表示可变大小数组的序列容器。
2、vector就像数组一样，采用的是连续的空间来存储元素，也意味着可以通过下标对vector的元素进行访问和修改。
3、普通数组的大小不可以动态改变，vector的大小可以动态改变。
4、当vector需要重新分配大小时，其做法是，分配一个新的数组，然后将全部元素移到这个数组当中，并释放原来的数组空间。
5、vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因此存储空间比实际需要的存储空间一般更大。不同的库采用不同的策略权衡空间的使用和重新分配，以至于在末尾插入一个元素的时候是在常数的时间复杂度完成的。
6、由于vector采用连续的空间来存储元素，与其他动态序列容器相比，vector在访问元素的时候更加高效，在其末尾添加和删除元素相对高效，而对于不在其末尾进行的删除和插入操作效率则相对较低。

vector的定义

方式一：
构造一个特定类型的空容器

vector<int> v; //构造int类型的空容器

方式二：
构造一个有n个val元素的特定类型的容器

vector<int> v(5, 2); //构造含有5个2的int类型容器

方式三：
调用拷贝构造方法，拷贝构造特定类型的容器

vector<int> v1(v); // v1为通过拷贝构造int类型的v容器构成

方式四：
使用迭代器拷贝构造某一段内容

vector<int> v1(v.begin(), v.end()); //使用迭代器拷贝构造v容器的某一段内容

这种方式还可以用于拷贝其它容器中的某一段内容
例如：

string s("hello world");
vector<char> v5(s.begin(), s.end()); //拷贝构造string对象的某一段内容

vector的空间相关问题

1.size和capacity
size能够获取当前容器中的有效元素个数，capacity能够获取当前容器的最大容量

例子：

int main()
{vector<int> v(5, 2);cout << v.size() << endl; //获取当前容器中的有效元素个数cout << v.capacity() << endl; //获取当前容器的最大容量return 0;
}

2.resize
能够改变容器中的有效元素个数

resize使用规则：

1、当所给值大于容器当前的size时，将size扩大到该值，扩大的元素为第二个所给值，若未给出，则默认为0。
2、当所给值小于容器当前的size时，将size缩小到该值。

例子：

int main()
{vector<int> v(10, 2);cout << v.size() << endl; //10cout << v.capacity() << endl; //10v.resize(15); //改变容器的size为15 未给出扩大的元素 则用0填充cout << v.size() << endl; //15return 0;
}

3.reserve
能够改变容器的最大容量

reserve使用规则：

1、当所给值大于容器当前的capacity时，将capacity扩大到该值。
2、当所给值小于容器当前的capacity时，什么也不做。

例子：

int main()
{vector<int> v(10, 2);cout << v.size() << endl; //10cout << v.capacity() << endl; //10v.reserve(20); //改变容器的capacity为20，size不变cout << v.size() << endl; //10cout << v.capacity() << endl; //20return 0;
}

4.empty
能够判断当前容器是否为空

int main()
{vector<int> v(10, 2);cout << v.empty() << endl; // 为falsereturn 0;
}

vector的迭代器的使用

迭代器分为正向迭代器和反向迭代器

1.begin和end
begin：容器中指向第一个元素的迭代器
end：容器中指向最后一个元素的后一个位置的迭代器

例子：

int main()
{vector<int> v(10, 2);//正向迭代器遍历容器vector<int>::iterator it = v.begin();while (it != v.end()){cout << *it << " ";it++;}cout << endl; // 2 2 2 2 2 2 2 2 2 2return 0;
}

2.rbegin和rend
rbegin：容器中指向最后一个元素的迭代器
rend：容器中指向第一个元素的前一个位置的迭代器

例子：

int main()
{vector<int> v(10, 2);//反向迭代器遍历容器vector<int>::reverse_iterator rit = v.rbegin();while (rit != v.rend()){cout << *rit << " ";rit++;}// 输出结果虽然相同 但是输出顺序是相反的cout << endl; // 2 2 2 2 2 2 2 2 2 2return 0;
}

vector的增删查改

1.push_back和pop_back
push_back：对容器进行尾部插入元素
pop_back：对容器进行尾部删除元素

例子：

int main()
{vector<int> v;v.push_back(1); //尾插元素1v.push_back(2); //尾插元素2v.push_back(3); //尾插元素3// 此时容器中的元素为 1 2 3v.pop_back(); //尾删元素3v.pop_back(); //尾删元素2v.pop_back(); //尾删元素1return 0;
}

注意： 除了尾插和尾删之外，还有头插push_front和头删pop_front，不过在vector中进行头插和头删的效率较低。

2.insert和erase
insert：能够在所给迭代器的位置插入一个或者多个元素
erase：能够删除所给迭代器的位置的元素，或者删除所给迭代器区间的元素（注意左闭右开）

int main()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.insert(v.begin(), 0); //在容器开头插入0 v.insert(v.begin(), 3, 5); //在容器开头插入3个5v.erase(v.begin()); //删除容器中的第一个元素v.erase(v.begin(), v.begin() + 5); //删除在该迭代器区间内的元素（左闭右开）return 0;
}

3.find
上面的例子中是按照位置进行插入或者删除，如果配合find函数使用时，则可以根据某个特定的值的位置进行插入或删除。即先使用find找到该位置，再在该位置进行插入或者删除

find函数有3个参数，前两个参数确定一个寻找的范围，为迭代器的区间（左闭右开），第三个参数为需要寻找的值
find函数会在所给迭代器区间寻找第一个匹配的元素，找到则返回它的迭代器，如果没找到，则返回所给的第二个参数

例子：

int main()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);vector<int>::iterator pos = find(v.begin(), v.end(), 3); //获取值为3的元素的迭代器v.insert(pos, 5); //在3的位置插入5pos = find(v.begin(), v.end(), 2); //获取值为3的元素的迭代器v.erase(pos); //删除2return 0;
}

注意： find函数是在算法库中实现的，不是vector中的成员函数，使用时需要包含头文件 < algorithm >

4.swap
能够交换两个容器的数据空间，将两个容器进行交换

int main()
{vector<int> v1(5, 1);vector<int> v2(5, 2);v1.swap(v2); //交换v1,v2的数据空间return 0;
}

5.[ ]进行元素访问
vector当中重载了[ ]操作符，所以我们可以通过下标+[ ]的方式对容器中的元素进行访问和修改

例子：

int main()
{vector<int> v(5, 2);//使用“下标+[]”的方式遍历容器for (int i = 0; i < v.size(); i++){cout << v[i] << " "; // 0下标开始}cout << endl;return 0;
}

vector支持迭代器，既然有迭代器，那么我们就可以使用范围for对vector容器进行遍历

int main()
{vector<int> v(5, 2);//范围forfor (auto e : v){cout << e << " ";}cout << endl;return 0;
}

vector迭代器失效问题

迭代器的主要作用是让我们使用容器时不用关心其底层的数据结构，vector的迭代器在底层实际上是一个指针。
迭代器失效就是指迭代器底层对应的指针所指向的空间被销毁，而指向一块已经被释放了的空间，继续使用失效的迭代器则可能使程序崩溃

示例1：

int main()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);//v: 1 2 3 4 5vector<int>::iterator pos = find(v.begin(), v.end(), 2); //获取值为2的元素的迭代器v.insert(pos, 10); //在值为2的元素的位置插入10//v: 1 10 2 3 4 5v.erase(pos); //删除元素2 ？？？error（迭代器失效）//v: 1 2 3 4 5return 0;
}

说明：

在代码中，我们希望通过find找到元素为2的迭代器，然后在该位置插入一个元素10，再将元素2进行删除。但是实际上我们获取的是指向2位置的指针，当我们在2的位置上插入10之后，那么从2开始的元素都向后移动一位，此时原本指向2的指针现在指向了10，所以我们原本希望删除2，实际删除的是10

示例2：

int main()
{vector<int> v;for (size_t i = 1; i <= 6; i++){v.push_back(i);}vector<int>::iterator it = v.begin();while (it != v.end()){if (*it % 2 == 0) //删除容器当中的全部偶数{v.erase(it);}it++;}return 0;
}

说明：

在该代码中，我们希望删除的是容器中的全部偶数，我们已知容器中的元素有{1,2,3,4,5,6}；代码中使用迭代器it遍历容器中的元素，遇到偶数就删除，看起来好像没问题，但其实最终结果是错误的，因为将元素删除之后，后面的元素都会往前挪动一位，例如我们遇到1,1不是偶数，所以指向下一位，遇到2时，此时将2删除，2后面的元素都往前挪动一位，3往前挪动一位，就代替了2的位置，此时it++，那么it就直接指向元素4了，即迭代器it没有对3这个元素进行判断，因为原本3这个位置是2的，而2判断并且删除之后it就直接++了，所以如果这个3是偶数时，那结果就出错了。除此之外，当我们删除元素6时，元素6之后的迭代器v.end()也要向前移动，那么v.end()就指向了刚被删除的元素6的位置，此时it++，那么it就与v.end()错开了，访问了不属于容器的内存空间，导致程序崩溃

迭代器失效解决方法：
注意使用迭代器时，每次使用之前，对迭代器进行重新赋值

示例1解决方法：

int main()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);//v: 1 2 3 4 5vector<int>::iterator pos = find(v.begin(), v.end(), 2); //获取值为2的元素的迭代器v.insert(pos, 10); //在值为2的元素的位置插入10//v: 1 10 2 3 4 5pos = find(v.begin(), v.end(), 2); //重新获取值为2的元素的迭代器v.erase(pos); //删除元素2//v: 1 10 3 4 5return 0;
}

示例1中，在值为2的位置插入10之后，重新获取值为2的元素的迭代器，那么此时就可以对元素2进行删除了

示例2解决方法：

int main()
{vector<int> v;for (size_t i = 1; i <= 6; i++){v.push_back(i);}vector<int>::iterator it = v.begin();while (it != v.end()){if (*it % 2 == 0) //删除容器当中的全部偶数{it = v.erase(it); //删除后获取下一个元素的迭代器}else{it++; //是奇数则it++}}return 0;
}

示例2中，我们接收erase函数的返回值（erase函数返回删除元素的后一个元素的新位置），并且只有当前位置元素为奇数时才it++，对于偶数，则删除当前元素之后继续判断该位置的元素（因为该位置元素被更新，所以需要再次判断）