STL之vector扩容机制

2023-05-16

前言

    大家好,我是萝卜。上期结尾说到vector的push_back操作一般情况下时间复杂度为O(1),是否存在特殊情况。那么本期就讲讲vector在容器空间不足时进行push_back操作会发生什么。

    vector作为STL的常用容器之一,其特性和数组类似,拥有一段连续的内存空间。vector申请的是一段连续的内存,当插入新的元素内存不够时,通常会再重新申请更大的一块内存,将原来的元素拷贝过去,释放旧空间。因为内存空间是连续的,所以在进行插入和删除操作时,会造成内存块的拷贝,时间复杂度为O(n)。

相关函数

在讲解vector扩容机制前,先了解四个函数:

size()capacity()resize()reserve()

  • size():

size()函数返回当前vector所容纳元素的数目,即使用的空间大小。

  • capacity()

capacity()函数返回当前vector在重新进行内存分配以前所能容纳的元素数量,即返回的是总的容量大小,capacity()-size()后就是未使用的空间大小。

使用者可以通过reserve()来改变capacity(),resize()改变size()。

  • resize()

resize,即重置容器空间。当设置值小于当前容器空间时,会将目前容器中超出设置值的空间释放掉;当设置值大于当前容器空间时,会在当前空间的基础上增加容量。

举个例子,vector当前容量为10,若使用resize(20)设置容量为20,则需要再扩容增加10个;若使用resize(5)设置容量为5,则将6-10的空间进行释放。

源码如下:

void resize(size_type __new_size){
    if (__new_size > size()){ 
        _M_default_append(__new_size - size());
    }
    else if (__new_size < size()){
        _M_erase_at_end(this->_M_impl._M_start + __new_size);
    }
}
  • reserve()

reserve,即预留容器空间。当设置值大于当前容器空间时,会增加当前容器空间的大小,源码如下:

void reserve(size_type __n){
    if (__n > max_size()){
        __throw_length_error(__N("vector::reserve"));
    }
    if (capacity() < __n){
        _M_reallocate(__n);
    }
}

扩容机制

不同编译器在vector的扩容策略上显然不太一致,在vector的size()(当前容器所用空间)等于capacity()(当前容器总空间)时会发生扩容。

不同的的编译器实现方式不同,vs编译器每次是以1.5倍且向下取整的策略进行扩容,gcc编译器则是每次以2.0倍的策略进行扩容。

扩容因子的比较

扩容的大小叫做扩容因子,扩容因子由编译器决定,VS的扩容因子为1.5,G++中,扩容因子为2。

  • 扩容因子大,每次需要分配的新内存空间越多,分配空间耗时。空闲空间较多,内存利用率低。

  • 扩容因子小,需要再分配的可能性更高,扩容耗时。空闲空间较少,内存利用率较。

一般认为扩容因子1.5优于2.0,原因是以1.5作为扩容因子可以实现复用释放的内存空间。

以2为扩容因子时,空闲的空间始终要小于需要分配的空间

以1.5为扩容因子时,随着分配空间增大,之前释放的空闲空间能够满足当次扩容所需的空间,实现内存的复用

扩容后数据地址变化

在扩容时,系统会选择一端更大的内存,将数据从原来的内存拷贝过来,同时释放原有的内存。这时数据存在的地址就发生了改变。我们可以通过&vector[0]的方式来查看数据首地址。

注意:对于vector,&vector和&vector[0]是不一样的; 而对于数组,&array与&array[0]是一样的。

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

STL之vector扩容机制 的相关文章

随机推荐

  • CAN总线协议入门基础原理

    CAN 是 Controller Area Network 的缩写 xff08 以下称为 CAN xff09 xff0c 是 ISO 1 国际标准化的串行通信协议 CAN 通过 ISO11898 及 ISO11519 进行了标准化 xff0
  • SPI总线协议基本原理及相关配置

    单片机应用中 xff0c 最常用的通信协议主要有三个 xff0c 即USART IIC和SPI 关于前两个的介绍在之前文章学习过 xff0c 这次介绍一下第三个通信协议 SPI SPI Serial Peripheral Interface
  • 利用定时器的输出比较功能产生PWM驱动舵机

    一 定时器基本原理 首先我们来看一下ST官方给出的关于定时器的相关介绍 xff1a xff08 以STM32F103C8T6为例 xff09 STM32F103C8T6 含有 4 个 16 位定时器 xff0c 分别是一个高级定时器 TIM
  • ST-LINK固件升级

    关于st link固件升级注意的问题 在下载调试的过程中 xff0c 程序可能由于st link版本过旧而提示 command not supported 的错误 xff0c 这就要求我们升级st link固件才可以正常下载 但是在升级的过
  • 关于英伟达jetson nano的搭配双目摄像头跑ORB_SLAM2

    1 安装系统 按照商家给的资料安装 xff0c 将Ubuntu18 04LTS镜像拷贝到tf卡中 xff0c 插上jetson nano就可以安装了 2 系统设置 进入系统我先把系统语言设置为中文 xff0c 在右上角的设置中找到系统设置中
  • 双目摄像头(CSI-IMX219)的标定

    1 介绍 网上关于这类标定有挺多教程的 xff0c 但由于这个摄像头的特殊性 xff0c 所以不可能完全安装教程来走 目前来说有3种标定方法 xff1a ROS操作系统来标定 matlab标定 opencv标定 这三种方法我先试了用ROS来
  • 小学生学AD16(入门级别,看这篇就够了)

    1 软件安装 xff1a AD16的安装我就不多介绍了 xff0c csdn一搜一大把 要学一个软件 xff0c 那么软件安装是必经之路 xff0c 不要认为软件安装不重要 xff08 如果你的安装完之后桌面没快捷方式 xff0c 那么可以
  • Arduino串口绘图器双通道绘制

    Serial print val Serial print 34 34 Serial println muBiao 其实只用在两个变量之间加个 xff0c 就行了 参考网址 https www norwegiancreations com
  • 关于神舟笔记本TX8连副屏经常蓝屏的问题

    大概率是3060显卡驱动的问题 xff0c 可以试试重新安装显卡驱动 若还是不行就换个接口 xff0c 不要用hdim的接口 xff0c 那个是直接连3060的 换剩下两个的minidp接口其中一个 xff0c 第一个不要接 xff0c 那
  • 51单片机入门(小学生都能学会)

    序 xff1a 时隔一年 xff0c 我终于从二年级到三年级了 xff01 由于小学三年级这学期要学单片机 xff0c 故写下这篇笔记留下些什么 由于自己也是新手 xff0c 欢迎各位指出本文的各种错误 1 什么是51单片机 为什么要说这个
  • 解决使用WinScp连接Ubantu系统失败的问题---SSH无法连接

    起因 为了互通Linux系统和Windows系统的文件 xff0c 以更好的实现文件管理和资源共享 所以在查阅资料后 xff0c 使用WinScp xff0c WinSCP是一个Windows环境下使用SSH的开源图形化SFTP客户端 它的
  • 小学生51系列之基础知识

    1 单片机的基本结构 说到基本结构 xff0c 就是指51单片机的硬件组成 51单片机由中央处理器CPU 储存器 定时器 I O端口 组成 其中储存器包含数据储存器 xff08 RAM xff09 和程序储存器 xff08 ROM xff0
  • ros 接入Livox Mid-70

    最近在研究3d避障激光 大疆Livox mid 70 xff0c 记录下接入过程 环境信息 xff1a Ubuntu 18 04 ros melodic 1 livox view 点云可视化 xff08 1 xff09 根据livox mi
  • ROS+opencv实践-二维码识别

    一 安装二维码识别的功能包 sudo apt span class token operator span get install ros span class token operator span melodic span class
  • C语言简单链表详细步骤详解

    43 链表 gt 小阿豪带你写链表 xff01 xff01 xff01 xff01 进入正文 span class token number 1 span 首先 xff0c 先想好自己要创建的链表格式以及最后的的显示界面 xff01 xff
  • 滚球控制系统详解 —— (附核心代码)

    最近练习了17年的国赛题 滚球控制系统 这里展示一下画圆 xff1a 观看完整视频点这里 接下来 xff0c 我来分享一下从搭整体结构到调试完的过程 这是我搭完的整体结构 xff08 缩小版 xff09 不管什么题 xff0c 结构部分还是
  • 【Linux网络编程】你了解TIME_WAIT状态吗?

    在Linux网络编程中 xff0c 我相信大多数人觉得最难理解的就是TCP中的TIME WAIT状态了吧 xff0c 那么TIME WAIT的概念到底是什么 xff0c 有几个类型呢 xff0c 以及在面试中经常会问到的TIME WAIT状
  • 【图解】八幅图带你轻松掌握八大排序(上):冒泡排序、选择排序、插入排序、快速排序

    在算法中 xff0c 八大排序算是最简单的也是重中之重 xff0c 所以掌握好八大排序的思想是非常重要的 xff0c 很多人学排序的时候会觉得似懂非懂 xff0c 本篇文章作者耗时两小时绘制了八大排序的详细图解 xff0c 让大家快速理解八
  • 最详细整理STL之vector基础

    前言 xff1a Vector是一种可以存储任意类型的动态数组 xff0c 属于序列式容器 xff0c 可以用sort对其进行排序 xff0c 底层数据结构是数组 xff0c 可以随机访问元素 Vectors 包含着一系列连续存储的元素 其
  • STL之vector扩容机制

    前言 大家好 xff0c 我是萝卜 上期结尾说到vector的push back操作一般情况下时间复杂度为O 1 xff0c 是否存在特殊情况 那么本期就讲讲vector在容器空间不足时进行push back操作会发生什么 vector作为