• STL好难(3):vector的使用


    目录

    1.vector的介绍和使用

    2.vector的常见构造:

    3.vector的遍历方式

    🍉[ ] + 下标

    🍉通过迭代器进行访问:

    🍉范围for:

    4.vector的迭代器

    🍉begin 和 end

    🍉rbegin 和 rend

    5.vector空间扩容:

    🍉size

    🍉capacity

    🍉capacity的增容:

    🍉empty

    🍉reserve

    🍉resize

    6.vector 的增删改查

    🍉push back

    🍉pop back

    🍉insert

    🍉erase

    🍉swap

    🍉find

    🍉sort

    7.vector的迭代器失效问题

    🍉情况1:迭代器指向的位置意义改变

    🍉情况2:扩容、缩容,导致迭代器的野指针,使其失效

    8.总结:


    1.vector的介绍和使用

    vector就类似数据结构中的顺序表

    • 1. vector是表示可变大小数组的序列容器。
    • 2. 就像数组一样,vector也采用的连续存储空间来存储元素。
      意味着可以采用下标对vector的元素 进行访问,和数组一样高效。但是又不像数组,它的大小是可以动态改变的,而且它的大小会被容器自 动处理
    • 3. 本质讲,vector使用动态分配数组来存储它的元素。
      当新元素插入时候,这个数组需要被重新分配大小为了增加存储空间。其做法是,分配一个新的数组,然后将全部元素移到这个数组。就时间而言,这是一个相对代价高的任务,因为每当一个新的元素加入到容器的时候,vector并不会每次都重新分配大小
    • vector分配空间策略:vector会分配一些额外的空间以适应可能的增长,因为存储空间比实际需要的存储空间更大
    • vector占用了更多的存储空间,为了获得管理存储空间的能力,并且以一种有效的方式动态增长
    • 与其它动态序列容器相比,vector在访问元素的时候更加高效,在末尾添加和删除元素相对高效
      对于其它不在末尾的删除和插入操作,效率更低

    2.vector的常见构造:

    在C++98里面主要有以下4中构造

    1)无参构造一个空的容器

    2)构造并初始化 n 个 val 容器 

    3)拷贝构造某类型容器

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

    1. //1)无参构造一个空的容器
    2. vector<int> v1; //构造一个int类型的空容器
    3. //2)构造并初始化 n 个 val 容器 
    4. vector<int> v2(3, 6); //构造含有3个6的int类型容器
    5. //3)拷贝构造某类型容器
    6. vector<int> v3(v2); //拷贝构造int类型的v2容器
    7. //4)使用迭代器进行初始化构造
    8. vector<int> v4(v2.begin()+1, v2.end()-1); //使用迭代器拷贝构造v2容器的某一段内容
    9. //当然也可以用使用迭代器构造其他类型的容器,
    10. string s("hello world");
    11. vector<char> v5(s.begin(), s.end()); //拷贝构造string对象的某一段内容

    3.vector的遍历方式

    🍉[ ] + 下标

    vector 对 [ ] 运算符进行了重载,所以我们可以直接使用 [ ]+下标 访问或修改对象中的元素

    1. int main()
    2. {
    3. vector<int> v1; // 定义容器v1
    4. // 尾插5个数据
    5. v1.push_back(1);
    6. v1.push_back(2);
    7. v1.push_back(3);
    8. v1.push_back(4);
    9. v1.push_back(5);
    10. // 使用下标访问数据
    11. for (size_t i = 0; i < v1.size(); ++i)
    12. {
    13. cout << v1[i] << " ";
    14. }
    15. cout << endl;
    16. // 使用下标修改数据
    17. for (size_t i = 0; i < v1.size(); ++i)
    18. {
    19. v1[i] += 3;
    20. cout << v1[i] << " ";
    21. }
    22. cout << endl;
    23. retur

    结果: 

    🍉通过迭代器进行访问:

    begin 获取一个字符的迭代器, end获取最后一个字符下一个位置的迭代器

    1. int main()
    2. {
    3. vector<int> v2; // 定义容器v2
    4. // 尾插5个数据
    5. v2.push_back(1);
    6. v2.push_back(2);
    7. v2.push_back(3);
    8. v2.push_back(4);
    9. v2.push_back(5);
    10. // 使用迭代器访问数据
    11. vector<int>::iterator it1 = v2.begin();
    12. while (it1 != v2.end())
    13. {
    14. cout << *it1 << " ";
    15. it1++;
    16. }
    17. cout << endl;
    18. // 使用迭代器修改数据
    19. vector<int>::iterator it2 = v2.begin();
    20. while (it2 != v2.end())
    21. {
    22. *it2 += 1;
    23. cout << *it2 << " ";
    24. it2++;
    25. }
    26. return 0;
    27. }

    结果如下: 

    🍉范围for:

    1. int main()
    2. {
    3. vector<int> v3; // 定义容器v3
    4. // 尾插5个数据
    5. v3.push_back(1);
    6. v3.push_back(2);
    7. v3.push_back(3);
    8. v3.push_back(4);
    9. v3.push_back(5);
    10. // 使用范围for访问数据
    11. for (auto a : v3)
    12. {
    13. cout << a << " ";
    14. }
    15. cout << endl;
    16. // 使用范围for修改数据
    17. for (auto& a : v3)
    18. {
    19. a += 4;
    20. cout << a << " ";
    21. }
    22. return 0;
    23. }

    结果:

    4.vector的迭代器

    正向迭代器:

     

    反向迭代器:

    如下图:

    🍉begin 和 end

    通过 begin 函数可以得到容器中第一个元素的正向迭代器

    通过 end 函数可以得到容器中最后一个元素的后一个位置的正向迭代器

    左闭右开

    1. int main()
    2. {
    3. vector<int> v;
    4. v.push_back(1);
    5. v.push_back(2);
    6. v.push_back(3);
    7. v.push_back(4);
    8. v.push_back(5);
    9. //正向迭代器遍历容器
    10. vector<int>::iterator it = v.begin();
    11. //也可以用auto来自动识别:auto it = v.begin();
    12. while (it != v.end())
    13. {
    14. cout << *it << " ";
    15. it++;
    16. }
    17. return 0;
    18. }

      

    🍉rbegin 和 rend

    通过 rbegin 函数可以得到容器中最后一个元素的反向迭代器

    通过 rend 函数可以得到容器中第一个元素的前一个位置的反向迭代器

    左开右闭

    1. int main()
    2. {
    3. vector<int> v;
    4. v.push_back(1);
    5. v.push_back(2);
    6. v.push_back(3);
    7. v.push_back(4);
    8. v.push_back(5);
    9. //反向迭代器遍历容器
    10. vector<int>::reverse_iterator it = v.rbegin();
    11. //也可以用auto来自动识别:auto it = v.rbegin();
    12. while (it != v.rend())
    13. {
    14. cout << *it << " ";
    15. it++;
    16. }
    17. return 0;
    18. }

     

    5.vector空间扩容:

    官方文本里面的内容:

     我们主要学习:

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

    点击这里查看文档

    🍉size

    size 函数获取当前容器的有效元素个数

    1. int main()
    2. {
    3. vector<int> v(6, 5); //定初始化6个5
    4. cout << v.size() << endl; //获取当前容器中的有效元素个数
    5. return 0;
    6. }

    🍉capacity

    capacity 函数获取当前容器的最大容量

    1. int main()
    2. {
    3. vector<int> v(6, 5); //定初始化6个5
    4. //获取当前容器中的容量大小
    5. cout << v.capacity() << endl; // 结果:6
    6. return 0;
    7. }

    🍉capacity的增容:

    可以看下面代码实例:

    1. int main()
    2. {
    3. size_t sz;
    4. vector<int> v;
    5. sz = v.capacity();
    6. cout << "making for grow:\n";
    7. for (int i = 0; i < 100; ++i)
    8. {
    9. v.push_back(i);
    10. if (sz != v.capacity())
    11. {
    12. sz = v.capacity();
    13. cout << "capacity changed: " << sz << endl;
    14. }
    15. }
    16. return 0;
    17. }

    结果:

    可以看到在VS2022下,capacity 是按照 1.5 倍增长的,

    当然,在不同编译环境下,其增长倍数不同,如果在Linux下就是2倍的增长

    着是应为VS用的是 PJ版本,Linux的 g++ 用的是 SGI版本

    🍉empty

    empty 函数用来判断当前容器是否为空。

    • 如果为空,输出1,否则,输出0
    1. int main()
    2. {
    3. vector<int> v1(3, 6);
    4. cout << v1.empty() << endl; // v1非空,输出0
    5. vector<int> v2;
    6. cout << v2.empty() << endl; // v2为空,输出1
    7. return 0;
    8. }

    🍉reserve

    reserve函数用来改变vector的最大容量

    其有两个注意点,如下:

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

    用法:当我们事先知道要用多大空间时,就提前用reserve开辟好,来减少代码增容时的消耗

    1. int main()
    2. {
    3. vector<int> v;
    4. v.reserve(100); // 提前开好100空间
    5. //......
    6. return 0;
    7. }

    🍉resize

    resize 函数改变容器中的有效元素个数。

    1)当所给值大于当前的 size 时,将 size 扩大到该值,扩大的元素为第二个所给值,若为给出,则默认为0

    2)当所给值小于容器当前的 size 时,只将初始化给的值的数

    1. int main()
    2. {
    3. vector<int> v1(6, 3);
    4. v1.reserve(20);
    5. cout << v1.capacity() << endl;
    6. cout << v1.size() << endl << endl;
    7. v1.resize(10);
    8. cout << v1.capacity() << endl;
    9. cout << v1.size() << endl;
    10. return 0;
    11. }

    结果:

     注意:

    • reserve 只负责开辟空间,如果确定知道需要用多少空间,可以用 reserve 缓解 vector 扩容代价,reserve不会影响size
    • resize 在开空间的同时还会进行初始化,会影响 size。

    6.vector 的增删改查

    C++文档里面的内容:

    我们重点学下面这些:

    vector增删改查接口说明
    push back尾插
    pop back尾删
    find查找(这个是算法模块,不是vector接口)
    insert在position之前插入val
    erase删除position位置数据
    swap交换两个vector位置的数据

     点击这里查看文档

    🍉push back

    尾插

    1. int main()
    2. {
    3. vector<int> v;
    4. //使用push_back插入5个数据
    5. v.push_back(1);
    6. v.push_back(2);
    7. v.push_back(3);
    8. v.push_back(4);
    9. v.push_back(5);
    10. //打印
    11. for (auto e : v)
    12. {
    13. cout << e << " ";
    14. }
    15. return 0;
    16. }

    🍉pop back

    尾删:

    1. int main()
    2. {
    3. vector<int> v;
    4. //使用push_back尾插6个数据
    5. v.push_back(1);
    6. v.push_back(2);
    7. v.push_back(3);
    8. v.push_back(4);
    9. v.push_back(5);
    10. v.push_back(6);
    11. //使用pop_back尾删3个数据
    12. v.pop_back();
    13. v.pop_back();
    14. v.pop_back();
    15. v.pop_back();
    16. //打印
    17. for (auto e : v)
    18. {
    19. cout << e << " ";
    20. }
    21. return 0;
    22. }

    🍉insert

    insert函数可以在所给迭代器位置插入一个或多个元素

    1)插入一个值:

    1. int main()
    2. {
    3. vector<int> v;
    4. v.push_back(1);
    5. v.push_back(2);
    6. v.push_back(3);
    7. v.push_back(4);
    8. v.push_back(5);
    9. //在容器头部插入9
    10. v.insert(v.begin(), 9);
    11. //在位置2插入6
    12. v.insert(v.begin()+2, 6);
    13. //打印
    14. for (auto e : v)
    15. {
    16. cout << e << " ";
    17. }
    18. return 0;
    19. }

    结果:         9 1 6 2 3 4 5

    2)插入多个值:

    1. int main()
    2. {
    3. vector<int> v;
    4. v.push_back(1);
    5. v.push_back(2);
    6. v.push_back(3);
    7. v.push_back(4);
    8. v.push_back(5);
    9. //在容器头部插入2个4
    10. v.insert(v.begin(), 2, 4);
    11. //打印
    12. for (auto e : v)
    13. {
    14. cout << e << " ";
    15. }
    16. return 0;
    17. }

    结果:         4 4 1 2 3 4 5

    🍉erase

    erase 函数用来删除所给迭代器位置的元素,或者删除所给迭代器区间内的所有函数(左闭右开)

    1)删除一个值

    1. int main()
    2. {
    3. vector<int> v;
    4. v.push_back(1);
    5. v.push_back(2);
    6. v.push_back(3);
    7. v.push_back(4);
    8. v.push_back(5);
    9. //头删
    10. v.erase(v.begin());
    11. //尾删
    12. v.erase(v.end()-1); //因为是左闭右开区间,所以end-1才能删掉‘5’
    13. //打印
    14. for (auto e : v)
    15. {
    16. cout << e << " "; //结果:2 3 4
    17. }
    18. return 0;
    19. }

    2)删除一个区间的值

    1. int main()
    2. {
    3. vector<int> v;
    4. v.push_back(0);
    5. v.push_back(1);
    6. v.push_back(2);
    7. v.push_back(3);
    8. v.push_back(4);
    9. v.push_back(5);
    10. v.push_back(6);
    11. v.push_back(7);
    12. v.push_back(8);
    13. v.push_back(9);
    14. //删除在该迭代器区间内的元素(左闭右开]
    15. v.erase(v.begin()+3, v.end() - 3);
    16. //打印
    17. for (auto e : v)
    18. {
    19. cout << e << " ";//结果:0 1 2 7 8 9
    20. }
    21. return 0;
    22. }

    🍉swap

    通过swap函数来交换两个容器的数据空间,实现两个容器的交换

    1. int main()
    2. {
    3. //容器v1
    4. vector<int> v1;
    5. v1.push_back(1);
    6. v1.push_back(1);
    7. v1.push_back(1);
    8. //容器v2
    9. vector<int> v2;
    10. v2.push_back(2);
    11. v2.push_back(2);
    12. v2.push_back(2);
    13. //交换v1和v2的数据
    14. v1.swap(v2);
    15. //打印v1
    16. cout << "v1:";
    17. for (auto e1 : v1)
    18. {
    19. cout << e1 << " ";
    20. }
    21. cout << endl;
    22. //打印v2
    23. cout << "v2:";
    24. for (auto e2 : v2)
    25. {
    26. cout << e2 << " ";
    27. }
    28. return 0;
    29. }

    🍉find

    由于 vector 没有 find 函数,如果我们要用的话,我们需要去调用算法库里面的一个函数接口:find

    使用 std:: find 需要包头文件 #include

    可以看到 find 共有三个参数,前两个确定迭代器的区间,第三个参数确定所要寻找的返回值

    函数在所给迭代器区间内寻找,
    若找到,返回第一个匹配的元素,并返回它的迭代器
    若未找到,返回第二个参数

    1. int main()
    2. {
    3. vector<int> v;
    4. v.push_back(1);
    5. v.push_back(2);
    6. v.push_back(3);
    7. v.push_back(4);
    8. v.push_back(5);
    9. v.push_back(6);
    10. // 假设我要3的前面插入600
    11. //vector::iterator pos = find(v.begin(), v.end(), 3);
    12. //上面的类型可以直接用auto去推算:
    13. auto pos = find(v.begin(), v.end(), 3);
    14. if (pos != v.end())
    15. {
    16. cout << "找到" << endl;
    17. v.insert(pos, 600);
    18. }
    19. else
    20. {
    21. cout << "未找到" << endl;
    22. }
    23. for (auto e : v)
    24. {
    25. cout << e << " "; //结果: 1 2 600 3 4 5 6
    26. }
    27. return 0;
    28. }

    🍉sort

    sort 函数  和  find 函数  一样,在vector里面没有明确给出,需要用std库里面的:

    也需要包头文件

    1)默认升序:

    1. int main()
    2. {
    3. vector<int> v;
    4. v.push_back(7);
    5. v.push_back(1);
    6. v.push_back(0);
    7. v.push_back(-1);
    8. v.push_back(9);
    9. v.push_back(3);
    10. // 默认排升序
    11. sort(v.begin(), v.end());
    12. // 打印
    13. for (auto e : v)
    14. {
    15. cout << e << " ";
    16. }
    17. return 0;
    18. }

    2)降序

    排降序需要用到仿函数,就要包仿函数的头文件: #include  

    1. int main()
    2. {
    3. vector<int> v;
    4. v.push_back(7);
    5. v.push_back(1);
    6. v.push_back(0);
    7. v.push_back(-1);
    8. v.push_back(9);
    9. v.push_back(3);
    10. // 排降序,需要包上仿函数的头文件 #include
    11. sort(v.begin(), v.end(), greater<int>());
    12. for (auto e : v)
    13. {
    14. cout << e << " ";
    15. }
    16. return 0;
    17. }

    7.vector的迭代器失效问题

    说了这么多的迭代器,那么迭代器到底是个什么东西呢?

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

    因此,迭代器失效,就是迭代器底层对应指针所指向的空间别销毁了,而使用一块已经被销毁的空间,则会导致程序崩溃

    🍉情况1:迭代器指向的位置意义改变

    看下面这段代码:

    1. int main()
    2. {
    3. vector<int> v;
    4. v.push_back(1);
    5. v.push_back(2);
    6. v.push_back(3);
    7. v.push_back(4);
    8. v.push_back(5);
    9. vector<int>::iterator pos = find(v.begin(), v.end(), 3); //获取值为3的元素的迭代器
    10. // 1 2 60 3 4 5
    11. v.insert(pos, 60); // 在3的位置前插入60
    12. // 删除pos位置的数据,我们会认为pos仍指向3,所以删除后的结果为:1 2 60 4 5
    13. v.erase(pos);
    14. //但是实际上,会在再次范文pos时出错
    15. return 0;
    16. }

     这时VS的assert()的强制检查报错

    原因如下:

    我们给数组:1 2 3 4 5 中 3 前面插入 60,我们需要先用迭代器来接受 find 找到的值
    此时pos的位置如下:

    我们在用easer删除元素3,此时就会报错

     

    可以看到,我们认为插入后pos应该还指向 ‘ 3 ’ ,但是,实际上pos以及指向了60,这时pos的被改变了如果我们再进行其他操作,系统检测到pos指向的不是3那么VS就会强制报错,导致程序崩溃

    如果我们需要删除元素3,就需要更新pos的值,解决方法如下:

    1. int main()
    2. {
    3. vector<int> v;
    4. v.push_back(1);
    5. v.push_back(2);
    6. v.push_back(3);
    7. v.push_back(4);
    8. v.push_back(5);
    9. vector<int>::iterator pos = find(v.begin(), v.end(), 3); //获取值为3的元素的迭代器
    10. // 1 2 60 3 4 5
    11. pos = v.insert(pos, 60); // 在3的位置前插入60,并更新 pos 的值
    12. v.erase(pos+1);
    13. //也可以:pos = find(v.begin(), v.end(), 3); v.erase(pos);
    14. for (auto e : v)
    15. {
    16. cout << e << " ";
    17. }
    18. //结果: 1 2 60 4 5
    19. return 0;
    20. }

    再设计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位置的值

     

    🍉情况2:扩容、缩容,导致迭代器的野指针,使其失效

    看如下代码:

    1. int main()
    2. {
    3. vector<int> v;
    4. v.push_back(1);
    5. v.push_back(2);
    6. v.push_back(3);
    7. v.push_back(4);
    8. auto it = v.begin();
    9. v.reserve(10);
    10. //vector::iterator it = v.begin();
    11. //用迭代器进行打印
    12. while (it != v.end())
    13. {
    14. cout << *it << " ";
    15. it++;
    16. }
    17. return 0;
    18. }

    会报错:

     

    我们通过调试来看:

    扩容之前,it指向的空间就是其 v.begin() 的空间,

    再扩容之后,it指向的空间不变,但是扩容是异地扩,导致it迭代器失效,所以后面进行打印操作时,会发生报错

    这就是扩容导致的迭代器失效

    解决方法:再扩容之后更新迭代器:

    1. int main()
    2. {
    3. vector<int> v;
    4. v.push_back(1);
    5. v.push_back(2);
    6. v.push_back(3);
    7. v.push_back(4);
    8. auto it = v.begin();
    9. v.reserve(10);
    10. //由于扩容,所以需要更新迭代器
    11. it = v.begin();
    12. //vector::iterator it = v.begin();
    13. //用迭代器进行打印
    14. while (it != v.end())
    15. {
    16. cout << *it << " ";
    17. it++;
    18. }
    19. return 0;
    20. }

    8.总结:

    通过上面的学习我们发现 vector 常用的接口更多是插入和遍历

    遍历更喜欢用数组 operator[ i ] 的形式访问,因为这样便捷

  • 相关阅读:
    分布式事务 —— SpringCloud Alibaba Seata
    单片机通用Bootloader框架-优化
    PCB 各层定义
    数据结构与算法之美 复杂度分析(下)
    通过 chatgpt 协助完成网站数据破解
    包含漏洞-读写文件以及执行命令
    smartmontools-5.43交叉编译Smartctl
    ES 数据库
    Conmi的正确答案——Ubuntu修改国内源(阿里云 aliyun)
    二进制安装Kubernetes(k8s)v1.30.1
  • 原文地址:https://blog.csdn.net/weixin_60630270/article/details/130905392