目录
1.vector的介绍和使用
vector就类似数据结构中的顺序表
- 1. vector是表示可变大小数组的序列容器。
- 2. 就像数组一样,vector也采用的连续存储空间来存储元素。
意味着可以采用下标对vector的元素 进行访问,和数组一样高效。但是又不像数组,它的大小是可以动态改变的,而且它的大小会被容器自 动处理- 3. 本质讲,vector使用动态分配数组来存储它的元素。
当新元素插入时候,这个数组需要被重新分配大小为了增加存储空间。其做法是,分配一个新的数组,然后将全部元素移到这个数组。就时间而言,这是一个相对代价高的任务,因为每当一个新的元素加入到容器的时候,vector并不会每次都重新分配大小- vector分配空间策略:vector会分配一些额外的空间以适应可能的增长,因为存储空间比实际需要的存储空间更大
- vector占用了更多的存储空间,为了获得管理存储空间的能力,并且以一种有效的方式动态增长
- 与其它动态序列容器相比,vector在访问元素的时候更加高效,在末尾添加和删除元素相对高效
对于其它不在末尾的删除和插入操作,效率更低
在C++98里面主要有以下4中构造
1)无参构造一个空的容器
2)构造并初始化 n 个 val 容器
3)拷贝构造某类型容器
4)使用迭代器进行初始化构造
- //1)无参构造一个空的容器
- vector<int> v1; //构造一个int类型的空容器
-
- //2)构造并初始化 n 个 val 容器
- vector<int> v2(3, 6); //构造含有3个6的int类型容器
-
- //3)拷贝构造某类型容器
- vector<int> v3(v2); //拷贝构造int类型的v2容器
-
- //4)使用迭代器进行初始化构造
- vector<int> v4(v2.begin()+1, v2.end()-1); //使用迭代器拷贝构造v2容器的某一段内容
-
- //当然也可以用使用迭代器构造其他类型的容器,
- string s("hello world");
- vector<char> v5(s.begin(), s.end()); //拷贝构造string对象的某一段内容
vector 对 [ ] 运算符进行了重载,所以我们可以直接使用 [ ]+下标 访问或修改对象中的元素
- int main()
- {
- vector<int> v1; // 定义容器v1
-
- // 尾插5个数据
- v1.push_back(1);
- v1.push_back(2);
- v1.push_back(3);
- v1.push_back(4);
- v1.push_back(5);
-
- // 使用下标访问数据
- for (size_t i = 0; i < v1.size(); ++i)
- {
- cout << v1[i] << " ";
- }
- cout << endl;
-
- // 使用下标修改数据
- for (size_t i = 0; i < v1.size(); ++i)
- {
- v1[i] += 3;
- cout << v1[i] << " ";
- }
- cout << endl;
-
- retur
结果:
begin 获取一个字符的迭代器, end获取最后一个字符下一个位置的迭代器
- int main()
- {
- vector<int> v2; // 定义容器v2
-
- // 尾插5个数据
- v2.push_back(1);
- v2.push_back(2);
- v2.push_back(3);
- v2.push_back(4);
- v2.push_back(5);
-
- // 使用迭代器访问数据
- vector<int>::iterator it1 = v2.begin();
- while (it1 != v2.end())
- {
- cout << *it1 << " ";
- it1++;
- }
- cout << endl;
-
- // 使用迭代器修改数据
- vector<int>::iterator it2 = v2.begin();
- while (it2 != v2.end())
- {
- *it2 += 1;
- cout << *it2 << " ";
- it2++;
- }
-
- return 0;
- }
结果如下:
- int main()
- {
- vector<int> v3; // 定义容器v3
-
- // 尾插5个数据
- v3.push_back(1);
- v3.push_back(2);
- v3.push_back(3);
- v3.push_back(4);
- v3.push_back(5);
-
- // 使用范围for访问数据
- for (auto a : v3)
- {
- cout << a << " ";
- }
- cout << endl;
-
- // 使用范围for修改数据
- for (auto& a : v3)
- {
- a += 4;
- cout << a << " ";
- }
-
- return 0;
- }
结果:
正向迭代器:
反向迭代器:
如下图:
通过 begin 函数可以得到容器中第一个元素的正向迭代器
通过 end 函数可以得到容器中最后一个元素的后一个位置的正向迭代器
左闭右开
- 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);
-
- //正向迭代器遍历容器
- vector<int>::iterator it = v.begin();
- //也可以用auto来自动识别:auto it = v.begin();
- while (it != v.end())
- {
- cout << *it << " ";
- it++;
- }
-
- return 0;
- }
通过 rbegin 函数可以得到容器中最后一个元素的反向迭代器
通过 rend 函数可以得到容器中第一个元素的前一个位置的反向迭代器
左开右闭
- 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);
-
- //反向迭代器遍历容器
- vector<int>::reverse_iterator it = v.rbegin();
- //也可以用auto来自动识别:auto it = v.rbegin();
- while (it != v.rend())
- {
- cout << *it << " ";
- it++;
- }
-
- return 0;
- }
官方文本里面的内容:
我们主要学习:
容量空间 | 接口说明 |
size | 获取数据个数 |
capacity | 获取容量大小 |
empty | 判断是否为空 |
resize(重点) | 改变vector的size |
reserve(重点) | 改变vecror的capacity |
size 函数获取当前容器的有效元素个数
- int main()
- {
- vector<int> v(6, 5); //定初始化6个5
-
- cout << v.size() << endl; //获取当前容器中的有效元素个数
-
- return 0;
- }
capacity 函数获取当前容器的最大容量
- int main()
- {
- vector<int> v(6, 5); //定初始化6个5
-
- //获取当前容器中的容量大小
- cout << v.capacity() << endl; // 结果:6
-
- return 0;
- }
可以看下面代码实例:
- int main()
- {
- size_t sz;
-
- vector<int> v;
-
- sz = v.capacity();
-
- cout << "making for 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;
- }
- }
-
- return 0;
- }
结果:
可以看到在VS2022下,capacity 是按照 1.5 倍增长的,
当然,在不同编译环境下,其增长倍数不同,如果在Linux下就是2倍的增长
着是应为VS用的是 PJ版本,Linux的 g++ 用的是 SGI版本
empty 函数用来判断当前容器是否为空。
- int main()
- {
- vector<int> v1(3, 6);
- cout << v1.empty() << endl; // v1非空,输出0
-
- vector<int> v2;
- cout << v2.empty() << endl; // v2为空,输出1
-
- return 0;
- }
reserve函数用来改变vector的最大容量
其有两个注意点,如下:
用法:当我们事先知道要用多大空间时,就提前用reserve开辟好,来减少代码增容时的消耗
- int main()
- {
- vector<int> v;
-
- v.reserve(100); // 提前开好100空间
-
- //......
-
- return 0;
- }
resize 函数改变容器中的有效元素个数。
1)当所给值大于当前的 size 时,将 size 扩大到该值,扩大的元素为第二个所给值,若为给出,则默认为0
2)当所给值小于容器当前的 size 时,只将初始化给的值的数
- int main()
- {
- vector<int> v1(6, 3);
-
- v1.reserve(20);
- cout << v1.capacity() << endl;
- cout << v1.size() << endl << endl;
-
- v1.resize(10);
- cout << v1.capacity() << endl;
- cout << v1.size() << endl;
-
- return 0;
- }
结果:
注意:
C++文档里面的内容:
我们重点学下面这些:
vector增删改查 | 接口说明 |
push back | 尾插 |
pop back | 尾删 |
find | 查找(这个是算法模块,不是vector接口) |
insert | 在position之前插入val |
erase | 删除position位置数据 |
swap | 交换两个vector位置的数据 |
尾插
- int main()
- {
- vector<int> v;
-
- //使用push_back插入5个数据
- v.push_back(1);
- v.push_back(2);
- v.push_back(3);
- v.push_back(4);
- v.push_back(5);
-
- //打印
- for (auto e : v)
- {
- cout << e << " ";
- }
-
- return 0;
- }
尾删:
- int main()
- {
- vector<int> v;
-
- //使用push_back尾插6个数据
- v.push_back(1);
- v.push_back(2);
- v.push_back(3);
- v.push_back(4);
- v.push_back(5);
- v.push_back(6);
-
- //使用pop_back尾删3个数据
- v.pop_back();
- v.pop_back();
- v.pop_back();
- v.pop_back();
-
- //打印
- for (auto e : v)
- {
- cout << e << " ";
- }
-
- return 0;
- }
insert函数可以在所给迭代器位置插入一个或多个元素
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);
-
- //在容器头部插入9
- v.insert(v.begin(), 9);
-
- //在位置2插入6
- v.insert(v.begin()+2, 6);
-
-
- //打印
- for (auto e : v)
- {
- cout << e << " ";
- }
-
- return 0;
- }
结果: 9 1 6 2 3 4 5
2)插入多个值:
- 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);
-
- //在容器头部插入2个4
- v.insert(v.begin(), 2, 4);
-
- //打印
- for (auto e : v)
- {
- cout << e << " ";
- }
-
- return 0;
- }
结果: 4 4 1 2 3 4 5
erase 函数用来删除所给迭代器位置的元素,或者删除所给迭代器区间内的所有函数(左闭右开)
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.erase(v.begin());
-
- //尾删
- v.erase(v.end()-1); //因为是左闭右开区间,所以end-1才能删掉‘5’
-
- //打印
- for (auto e : v)
- {
- cout << e << " "; //结果:2 3 4
- }
-
- return 0;
- }
2)删除一个区间的值
- int main()
- {
- vector<int> v;
-
- v.push_back(0);
- v.push_back(1);
- v.push_back(2);
- v.push_back(3);
- v.push_back(4);
- v.push_back(5);
- v.push_back(6);
- v.push_back(7);
- v.push_back(8);
- v.push_back(9);
-
-
- //删除在该迭代器区间内的元素(左闭右开]
- v.erase(v.begin()+3, v.end() - 3);
-
- //打印
- for (auto e : v)
- {
- cout << e << " ";//结果:0 1 2 7 8 9
- }
-
- return 0;
- }
通过swap函数来交换两个容器的数据空间,实现两个容器的交换
- int main()
- {
- //容器v1
- vector<int> v1;
- v1.push_back(1);
- v1.push_back(1);
- v1.push_back(1);
-
- //容器v2
- vector<int> v2;
- v2.push_back(2);
- v2.push_back(2);
- v2.push_back(2);
-
- //交换v1和v2的数据
- v1.swap(v2);
-
- //打印v1
- cout << "v1:";
- for (auto e1 : v1)
- {
- cout << e1 << " ";
- }
- cout << endl;
-
-
- //打印v2
- cout << "v2:";
- for (auto e2 : v2)
- {
- cout << e2 << " ";
- }
-
- return 0;
- }
由于 vector 没有 find 函数,如果我们要用的话,我们需要去调用算法库里面的一个函数接口:find
使用 std:: find 需要包头文件 #include
可以看到 find 共有三个参数,前两个确定迭代器的区间,第三个参数确定所要寻找的返回值
函数在所给迭代器区间内寻找,
若找到,返回第一个匹配的元素,并返回它的迭代器
若未找到,返回第二个参数
- 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.push_back(6);
-
- // 假设我要3的前面插入600
- //vector
::iterator pos = find(v.begin(), v.end(), 3); - //上面的类型可以直接用auto去推算:
- auto pos = find(v.begin(), v.end(), 3);
- if (pos != v.end())
- {
- cout << "找到" << endl;
- v.insert(pos, 600);
- }
- else
- {
- cout << "未找到" << endl;
- }
-
- for (auto e : v)
- {
- cout << e << " "; //结果: 1 2 600 3 4 5 6
- }
-
- return 0;
- }
sort 函数 和 find 函数 一样,在vector里面没有明确给出,需要用std库里面的:
也需要包头文件
1)默认升序:
- int main()
- {
- vector<int> v;
-
- v.push_back(7);
- v.push_back(1);
- v.push_back(0);
- v.push_back(-1);
- v.push_back(9);
- v.push_back(3);
-
- // 默认排升序
- sort(v.begin(), v.end());
-
- // 打印
- for (auto e : v)
- {
- cout << e << " ";
- }
-
- return 0;
- }
2)降序
排降序需要用到仿函数,就要包仿函数的头文件: #include
- int main()
- {
- vector<int> v;
-
- v.push_back(7);
- v.push_back(1);
- v.push_back(0);
- v.push_back(-1);
- v.push_back(9);
- v.push_back(3);
-
- // 排降序,需要包上仿函数的头文件 #include
- sort(v.begin(), v.end(), greater<int>());
-
- for (auto e : v)
- {
- cout << e << " ";
- }
-
- return 0;
- }
说了这么多的迭代器,那么迭代器到底是个什么东西呢?
其实迭代器的主要作用就是让算法能够不用关心底层数据结构,其底层实际就是一个指针,或者是对指针进行了封装,比如:vector 的迭代器就是原生指针 T*
因此,迭代器失效,就是迭代器底层对应指针所指向的空间别销毁了,而使用一块已经被销毁的空间,则会导致程序崩溃
看下面这段代码:
- 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);
-
- vector<int>::iterator pos = find(v.begin(), v.end(), 3); //获取值为3的元素的迭代器
-
- // 1 2 60 3 4 5
- v.insert(pos, 60); // 在3的位置前插入60
-
- // 删除pos位置的数据,我们会认为pos仍指向3,所以删除后的结果为:1 2 60 4 5
- v.erase(pos);
-
- //但是实际上,会在再次范文pos时出错
-
-
- return 0;
- }
这时VS的assert()的强制检查报错
原因如下:
我们给数组:1 2 3 4 5 中 3 前面插入 60,我们需要先用迭代器来接受 find 找到的值
此时pos的位置如下:我们在用easer删除元素3,此时就会报错
可以看到,我们认为插入后pos应该还指向 ‘ 3 ’ ,但是,实际上pos以及指向了60,这时pos的被改变了,如果我们再进行其他操作,系统检测到pos指向的不是3,那么VS就会强制报错,导致程序崩溃
如果我们需要删除元素3,就需要更新pos的值,解决方法如下:
- 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);
-
- vector<int>::iterator pos = find(v.begin(), v.end(), 3); //获取值为3的元素的迭代器
-
- // 1 2 60 3 4 5
- pos = v.insert(pos, 60); // 在3的位置前插入60,并更新 pos 的值
-
- v.erase(pos+1);
-
- //也可以:pos = find(v.begin(), v.end(), 3); v.erase(pos);
-
- for (auto e : v)
- {
- cout << e << " ";
- }
-
- //结果: 1 2 60 4 5
-
- return 0;
- }
再设计insert、erase这种会改变数组的函数时,制作人考虑到了迭代器会发生改变,所以就给其加了返回值,返回新的迭代器
用 pos = v.insert(pos, 60); 来更新pos,此时pos指向的就应该为60的元素
insert是在其前面插入,所以这时元素3就在pos指向的后面
所以用 v.erase(pos+1); 就能删除元素 ‘3’
也可以再用 pos = find(v.begin(), v.end(), 3); 更新pos的值,使其指向3
然后用 v.erase(pos); 删除pos位置的值
看如下代码:
- int main()
- {
- vector<int> v;
- v.push_back(1);
- v.push_back(2);
- v.push_back(3);
- v.push_back(4);
-
- auto it = v.begin();
-
- v.reserve(10);
-
- //vector
::iterator it = v.begin(); - //用迭代器进行打印
- while (it != v.end())
- {
- cout << *it << " ";
- it++;
- }
-
- return 0;
- }
会报错:
我们通过调试来看:
扩容之前,it指向的空间就是其 v.begin() 的空间,
再扩容之后,it指向的空间不变,但是扩容是异地扩,导致it迭代器失效,所以后面进行打印操作时,会发生报错
这就是扩容导致的迭代器失效
解决方法:再扩容之后更新迭代器:
- int main()
- {
- vector<int> v;
- v.push_back(1);
- v.push_back(2);
- v.push_back(3);
- v.push_back(4);
-
- auto it = v.begin();
-
- v.reserve(10);
-
- //由于扩容,所以需要更新迭代器
- it = v.begin();
-
- //vector
::iterator it = v.begin(); - //用迭代器进行打印
- while (it != v.end())
- {
- cout << *it << " ";
- it++;
- }
-
- return 0;
- }
通过上面的学习我们发现 vector 常用的接口更多是插入和遍历
遍历更喜欢用数组 operator[ i ] 的形式访问,因为这样便捷