目录
vector的介绍
vector的使用
vector的定义方式
vector的空间增长问题
size和capacity
reserve和resize
empty
vector的迭代器使用
begin和end
rbegin和rend
vector的增删查改
push_back和pop_back
insert和erase
swap
元素访问
vector迭代器失效问题
迭代器失效问题举例
迭代器失效解决方法
vector的介绍
动态数组容器:vector
是一种序列容器,它能够存储可变数量的元素,类似于数组,但更加灵活。
连续存储:vector
采用连续内存空间来存储其元素,这使得通过索引访问元素变得可能,就像操作普通数组一样方便。
动态大小:与静态数组不同,vector
的容量可以根据需要自动调整,无需手动重新分配内存。
内存重新分配:当vector
需要扩展其容量时,它会创建一个更大的新内存块,将现有元素复制到新位置,然后释放旧内存空间。
空间分配策略:vector
通常会预留一些额外的存储空间,以便容纳未来可能增加的元素。这种策略有助于减少重新分配内存的频率,从而提高性能。不同的实现可能会采用不同的预留策略,以平衡空间使用和性能。
性能特点:由于vector
的元素存储在连续的内存中,它在随机访问和在容器末尾添加或删除元素时表现出较高的效率。然而,如果在非末尾位置进行插入或删除操作,由于可能需要移动多个元素,其效率可能会降低。
vector的使用
vector
是C++标准模板库(STL)中的一个动态数组类,它在内存中以连续的方式存储元素,提供类似数组的功能但又具有动态大小和安全性。vector
的主要优势在于它的灵活性和效率,能够自动处理内存分配和释放,使得程序员可以更专注于算法设计而不是底层内存管理。
vector的定义方式
方式一: 构造一个某类型的空容器。
vector<int> v1; //构造int类型的空容器
方式二: 构造一个含有n个val的某类型容器。
vector<int> v2(10, 2); //构造含有10个2的int类型容器
方式三: 拷贝构造某类型容器的复制品。
vector<int> v3(v2); //拷贝构造int类型的v2容器的复制品
方式四: 使用迭代器拷贝构造某一段内容。
vector<int> v4(v2.begin(), v2.end()); //使用迭代器拷贝构造v2容器的某一段内容
注意:该方式也可用于拷贝其他容器的某一段内容。
string s("hello world");vector<char> v5(s.begin(), s.end()); //拷贝构造string对象的某一段内容
vector的空间增长问题
size和capacity
查询元素数量:使用size()
函数可以快速得知容器中实际存储的元素数量。了解容器容量:通过调用capacity()
函数,我们可以了解容器当前能够容纳的最大元素数,即容器的总容量。 #include <iostream>#include <vector>using namespace std;int main(){vector<int> v(10, 2);cout << v.size() << endl; //获取当前容器中的有效元素个数cout << v.capacity() << endl; //获取当前容器的最大容量return 0;}
reserve和resize
调整容器容量:reserve
函数用于设定容器的最大容量。
如果指定的值超过当前容量,容器会扩展以适应新的容量需求;
如果指定的值小于或等于当前容量,则容器保持不变。
改变元素数量:resize
函数允许我们改变容器中实际存储的元素数量。
如果新指定的数量大于当前元素个数,容器会添加新元素,其值可以指定,若未指定则使用默认值;
如果新指定的数量小于当前元素个数,容器将缩减至该数量。
#include <iostream>#include <vector>using namespace std;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; //20v.resize(15); //改变容器的size为15cout << v.size() << endl; //15cout << v.capacity() << endl; //20return 0;}
empty
调用empty()
函数可以迅速判断容器内是否含有元素。若容器为空,函数返回一个布尔值true
;若容器内有元素,则返回false
。
#include <iostream>#include <vector>using namespace std;int main(){vector<int> v(10, 2);cout << v.empty() << endl;return 0;}
vector的迭代器使用
begin和end
获取容器起始点:begin()
函数返回一个迭代器,指向容器中的第一个元素,允许用户从容器的起点开始遍历。
定位容器末尾位置:end()
函数提供了一个迭代器,它位于容器最后一个元素之后的位置,标志着容器的结束,但不指向任何实际元素。
#include <iostream>#include <vector>using namespace std;int main(){vector<int> v(10, 2);//正向迭代器遍历容器vector<int>::iterator it = v.begin();while (it != v.end()){cout << *it << " ";it++;}cout << endl;return 0;}
rbegin和rend
反向遍历的起点:rbegin()
函数提供了一个反向迭代器,它指向容器中的最后一个元素,允许从容器的末尾开始反向遍历。
反向遍历的终点:rend()
函数返回一个反向迭代器,它位于容器第一个元素之前的位置,标志着反向遍历的结束。
#include <iostream>#include <vector>using namespace std;int main(){vector<int> v(10, 2);//反向迭代器遍历容器vector<int>::reverse_iterator rit = v.rbegin();while (rit != v.rend()){cout << *rit << " ";rit++;}cout << endl;return 0;}
vector的增删查改
push_back和pop_back
尾部插入操作:push_back()
函数用于在容器的末尾添加一个新元素,实现动态增长。
尾部删除操作:pop_back()
函数用于移除容器末尾的元素,实现动态缩减。
#include <iostream>#include <vector>using namespace std;int main(){vector<int> v;v.push_back(1); //尾插元素1v.push_back(2); //尾插元素2v.push_back(3); //尾插元素3v.push_back(4); //尾插元素4v.pop_back(); //尾删元素v.pop_back(); //尾删元素v.pop_back(); //尾删元素v.pop_back(); //尾删元素return 0;}
insert和erase
元素插入:insert()
函数允许我们在指定的迭代器位置插入单个或多个元素,从而在容器的特定位置扩展内容。
元素删除:erase()
函数提供了删除指定迭代器位置的单个元素或删除迭代器定义的区间内所有元素的功能,遵循左闭右开的原则。
#include <iostream>#include <vector>using namespace std;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); //在容器开头插入0v.insert(v.begin(), 5, -1); //在容器开头插入5个-1v.erase(v.begin()); //删除容器中的第一个元素v.erase(v.begin(), v.begin() + 5); //删除在该迭代器区间内的元素(左闭右开)return 0;}
swap
swap()
函数提供了一种简便的方法来交换两个容器的数据内容,使得两个容器的数据空间可以快速互换。 #include <iostream>#include <vector>using namespace std;int main(){vector<int> v1(10, 1);vector<int> v2(10, 2);v1.swap(v2); //交换v1,v2的数据空间return 0;}
元素访问
在vector
中,通过重载的[ ]
操作符,我们可以使用下标方式直接访问容器中的元素,这提供了一种直观且方便的方法。
#include <iostream>#include <vector>using namespace std;int main(){vector<int> v(10, 1);//使用“下标+[]”的方式遍历容器for (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;return 0;}
由于vector
支持迭代器,我们可以采用范围for循环来遍历容器中的所有元素。编译器在编译过程中会自动将范围for循环转换为迭代器的使用形式。
#include <iostream>#include <vector>using namespace std;int main(){vector<int> v(10, 1);//范围forfor (auto e : v){cout << e << " ";}cout << endl;return 0;}
vector迭代器失效问题
迭代器的抽象作用:迭代器的核心功能是为容器提供一种抽象机制,使用户在操作容器时无需了解其底层数据结构的复杂性。对于vector
,迭代器本质上是指向容器存储空间的指针。
迭代器失效的情况:当迭代器所关联的内存空间被释放或重新分配时,迭代器就会失效。这意味着迭代器指向的内存区域不再有效,如果继续使用这样的迭代器,可能会导致程序运行出错甚至崩溃
迭代器失效问题举例
示例一:
#include <iostream>#include <algorithm>#include <vector>using namespace std;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;}
在我们的代码示例中,原本的计划是利用指向序列中特定位置(索引2)的迭代器,首先在该位置插入一个值10,随后删除原位置的元素2。
但实际操作中,我们忽略了迭代器在插入操作后会指向新插入的元素10。因此,当我们执行删除操作时,实际上删除的是新插入的元素10,而非原计划要删除的元素2。
示例二:
#include <iostream>#include <vector>using namespace std;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、3、5元素进行判断。
迭代器失效解决方法
在进行容器操作时,应养成在每次使用迭代器之前进行重新赋值的习惯。这有助于维持迭代器的准确性和避免因迭代器失效而导致的问题。
示例一解决方法:
#include <iostream>#include <algorithm>#include <vector>using namespace std;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;}
我们在使用迭代器删除元素2时对其进行重新赋值便可以解决。
示例二解决方法:
#include <iostream>#include <vector>using namespace std;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;}
我们可以接收erase函数的返回值(erase函数返回删除元素的后一个元素的新位置),并且控制代码的逻辑:当元素被删除后继续判断该位置的元素(因为该位置的元素已经更新,需要再次判断)。