三.vector的实现原理

发布时间:2023-12-29 15:00

文章目录

      • 一.vector的实现原理
        • 1.vector 基类介绍
        • 2.vector从最后面插入元素时发生了什么
          • 2.1对空vector插入一个元素
          • 2.2 vector当前内存用完时插入
        • 3.vector在中间插入一个元素会发生什么
        • 4.vector删除元素内存会被释放吗
          • 4.1从容器最后删除
          • 4.2从容器中间删除
        • 5.vector如何修改某个位置的元素值
        • 6.vector读取与插入元素的时间复杂度
        • 7.vector基本算法
        • 8.vector底层实现总结
      • 二.vector的注意事项
        • 1. 在不确定的情况下使用at而不是operator[]
        • 2. 什么类型不可以作为vector的模板类型
        • 3. vector的迭代器会失效的原因
        • 4. vector怎么迅速的释放内存
          • 4.1 通过swap函数
          • 4.2 使用shrink_to_fit函数

温习提示:为了阅读大家方便,源代码我没有加上去,想要深入了解的话,可以看侯捷老师的STL源码剖析。这是针对看过这本书的同学总结的,直接背就可以。

一.vector的实现原理

1.vector 基类介绍

  • vector就是一个模板类,其基类什么也没干vector v;这样的声明,只不过是调用了基类的无参构造,它什么也没干。也没有动态分配内存。

  • 如果vector在构造的时候指定容器大小,那么声明时就会申请动态内存,但如果构造是默认构造,并不会申请动态内存。

  • 基类的作用:

  1. 保存容器开始位置、结束位置以及所申请内存空间的的下一个位置;
  2. 申请动态内存空间。

2.vector从最后面插入元素时发生了什么

  • 2.1对空vector插入一个元素
  1. 分配一个元素为1的空间,将这个元素插入进去,如果后面超出容器所申请的空间,则重新分配一块新的内存空间(其大小为原空间大小的2倍)。

  2. 将原内存的元素按着所在顺序全部拷贝到新内存,并把要插入的元素插入到最后一个元素的下一个位置。

  3. 调用原内存中的析构函数,销毁原内存。

  • 2.2 vector当前内存用完时插入

    同上

3.vector在中间插入一个元素会发生什么

  • 其实就是把当前要插入元素的位置后面的元素向后移动,然后把待插入元素插入到相应的位置。

4.vector删除元素内存会被释放吗

  • 4.1从容器最后删除
  1. 从容器最后删除是调用pop_back(),将迭代器向前移动一位,然后把最后一个元素销毁。
  • 4.2从容器中间删除
  1. 从容器中间删除调用的是erase(作用是删除当前位置的元素,将删除元素的后面元素依次向前移动一位,并返回指向当前位置的迭代器)。所以从中间删除元素不会释放已经申请的动态内存

5.vector如何修改某个位置的元素值

  • vector可以通过迭代器和下标的方式来修改所指当前元素的值。

6.vector读取与插入元素的时间复杂度

  • vector读取一个元素,可以采取at,以及[]来直接访问元素,所以读取元素的时间复杂度是O(1),而插入和删除元素需要移动元素,时间时间复杂度为O(n)。在末尾插入和删除元素的时间复杂度为O(1).

7.vector基本算法

  • 因为vector具有operator *,operator ++,operator --,operator +=,operator -=,operator -,operator +,opeator->,所以vector的迭代器是随机访问迭代器。

    pop_back(), push_back() 尾删,尾插

    erase 指定位置删除

    clear 全部删除

    insert 指定位置插入

    [] , at[] 访问,修改元素

8.vector底层实现总结

  • vector是一个动态数组,用于维护一段连续的动态控件,内部有三个成员函数,用来储存起始位置,已使用位置,以及最后位置,每当动态内存用完时,它会按照原内存的2倍,重新申请新内存。将原内存的数据拷贝到新内存,释放掉原内存。

二.vector的注意事项

1. 在不确定的情况下使用at而不是operator[]

  • at会检查是否越界,假设不确定当前访问动作是否会越界

2. 什么类型不可以作为vector的模板类型

  • 对于vector模板特化类型,因为在vector的实现过程中,变量会经常被拷贝或者赋值,所以vector的模板类型应该具有公有的拷贝构造函数和重载的赋值操作符函数。

3. vector的迭代器会失效的原因

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

  2. 会引起其底层空间改变的操作,都有可能是迭代器失效,比如:resize、reserve、insert、assign、 push_back等

  3. 在vector容器中间根据指定迭代器删除元素,也就是调用erase函数,此时因为当前位置会被后面的元素覆盖,所以该指定迭代器会失效,不过此时可以通过erase的返回值重新得到当前位置的正确迭代器;

  4. 在vector需重新申请内存的时候,比如扩容,比如释放未使用的内存等等这些过程中都会发生迭代器失效的问题,因为内存有了变动,此时就需要重新获得迭代器;

4. vector怎么迅速的释放内存

  1. 有人说是不是可以调用reserve(0)来进行释放,毕竟reserve函数会根据我们指定的大小重新申请的内存,那是行不通的哈,这个函数只有在传入大小比原有内存大时才会有动作,否则不进行任何动作。

  2. 至于通过resize或者clear等都是行不通的,这些函数都只会对当前已保存在容器中的所有元素进行析构,但对容器本身所在的内存空间是不会进行释放的。

  • 4.1 通过swap函数
  • 这时我们可以想想,什么情况下vector大小为0呢,就是作为一个空容器的时候,所以要想快速的释放内存,我们可以参考swap函数机制,用一个空的vector与当前vector进行交换,使用形如vector().swap(v)这样的代码,将v这个vector变量所代表的内存空间与一个空vector进行交换,这样v的内存空间等于被释放掉了,而这个空vector因为是一个临时变量,它在这行代码结束以后,会自动调用vector的析构函数释放动态内存空间,这样,一个vector的动态内存就被迅速的释放掉了。

  • 4.2 使用shrink_to_fit函数
  • 它的作用是释放掉未使用的内存,假设我们先调用clear函数把所有元素清掉,这样是不是整块容器都变成未使用了,然后再调用shrink_to_fit函数把未使用的部分内存释放掉,那不就把这个vector内存释放掉了吗。

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网,如有侵权请联系:561261067@qq.com

桂ICP备16001015号