草庐IT

C++中STL的vector扩容机制

魏天乐大帅哥 2024-05-14 原文

目录

前言

前阵子面试的时候，被问到往vector中插入一个数据可能会发生什么？

我答:可能会扩容;

为啥vector支持变长？

我答:它实在堆上动态申请内存，因此有自己的一套扩容机制，可以操作内存大小;
它有size()和capacity()记录当前的有效元素个数和容量, 还有配套的resize()管理实际存放元素个数接口 和 reserve()管理容量接口;

下面我们详解;

发生扩容

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

扩容机制

size()和capacity()

不同编译器在vector的扩容策略上显然不太一致，在vector的size()(当前容器所用的空间) 等于capacity()(当前容器总空间)时，再次插入一个元素就会发生扩容。

vs编译器每次是以1.5倍且向下取整的策略进行扩容，gcc编译器则是每次以2.0倍的策略进行扩容。(注意，初始size和capacity是0，在0的基础上第一次进行扩容的时候取第一次插入元素的个数！)

size()和capacity()是俩成员函数，vector中并没有直接存int size 和 capacity，存的其实是有效数据的始末地址和容量结尾地址

通过源码分析有三个指针：

start和finish和end_of_storage，他们三个指针用减法能算出来逻辑上的int size和int capacity数量;

reserve()和resize()

  • reserve()来改变capacity()容量的大小，是预留容器空间;

  • resize()改变size()，是有效存储元素个数;

通过源码分析：

reserve(int n)

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

调整capacity, 存在if判断，当n>当前capacity才有效，否则什么事都不发生;

resize(int n)

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);
    }
}

调整size：

当size>=capacity时,capacity和size都扩容到size大小，多出来的有效元素补上缺省值（int为0）;

当 size<capacity,释放多余的元素，size缩减到指定大小，capacity不变;

C++扩容spanclasstokenjava面试

有关C++中STL的vector扩容机制的更多相关文章

  1. ruby - Ruby 是否提供响应 OS X 上的 Apple 事件的机制？ - 2

    我正在使用Ruby-Tk为OSX开发一个桌面应用程序，我想为该应用程序提供一个AppleEvents接口(interface)。这意味着应用程序将定义它将响应的AppleScript命令的字典(对应于发送到应用程序的Apple事件)，并且用户/其他应用程序可以使用AppleScript命令编写Ruby-Tk应用程序的脚本。其他脚本语言支持此类功能——Python通过位于http://appscript.svn.sourceforge.net/viewvc/appscript/py-aemreceive/的py-aemreceive库和Tcl通过位于http://tclae.source

  2. ruby - Ruby 的方法解除绑定(bind)机制有什么意义？ - 2

    Method#unbind返回对该方法的UnboundMethod引用，稍后可以使用UnboundMethod#bind将其绑定(bind)到另一个对象.classFooattr_reader:bazdefinitialize(baz)@baz=bazendendclassBardefinitialize(baz)@baz=bazendendf=Foo.new(:test1)g=Foo.new(:test2)h=Bar.new(:test3)f.method(:baz).unbind.bind(g).call#=>:test2f.method(:baz).unbind.bind(h).

  3. Selenium等待机制之显示等待 - 2

    显示等待需要用到两个类：WebDriverWait和expected_conditions两个类WebDriverWait：指定轮询间隔、超时时间等expected_conditions：指定了很多条件函数（也可以自定义条件函数）具体可以参考官网：selenium.webdriver.support.expected_conditions—Selenium4.5documentationfromseleniumimportwebdriverfromselenium.webdriver.common.byimportByfromselenium.webdriver.support.uiimpor

  4. 对VMware已经创建的虚拟机进行磁盘扩容过程以及会遇到的问题 - 2

    对VMware已经创建的虚拟机进行磁盘扩容过程以及会遇到的问题一.对VMware已经创建的虚拟机进行磁盘扩容过程1.虚拟机扩展磁盘容量2.扩展操作系统磁盘2.1查看扩展前磁盘容量信息2.2对新增加的磁盘进行分区2.3重启虚拟机2.4对新增磁盘格式化2.5将新的LVM添加到已有的LVM组（如果之前没有，则创建），实现扩容2.5.1之前没有LVM组，现在创建LVM组：2.5.2如果已经有了LVM：二.遇到的错误错误1.Volumegroup"centos"notfoundCannotprocessvolumegroupcentos错误2.Logicalvolumerootnotfoundinvol

  5. ruby - 为什么我不能让 swig wrap std::vector 到 Ruby 类？ - 2

    我有一个带有嵌入式Ruby解释器的应用程序，以及与swig生成的STL类的接口(interface)。多亏了swig，几乎所有事情都进行得很好，除了一件事:%moduleStuff%import"std_vector.i"namespacestd{%template(Vectord)vector;};%inline%{std::vectortest;%}当我尝试在Ruby中使用它时，类型Stuff::Vectord存在，但它不是生成的单例方法测试的返回类型。查看生成的C包装器文件，我可以看到类Vectord及其方法已定义，但查看_wrap_test_get我没有看到任何返回sth类St

  6. ruby - 不支持您提供的授权机制。请使用 AWS4-HMAC-SHA256 - 2

    我收到错误AWS::S3::Errors::InvalidRequest不支持您提供的授权机制。请使用AWS4-HMAC-SHA256.当我尝试将文件上传到新法兰克福地区的S3存储桶时。所有适用于USStandard区域。脚本:backup_file='/media/db-backup_for_dev/2014-10-23_02-00-07/slave_dump.sql.gz's3=AWS::S3.new(access_key_id:AMAZONS3['access_key_id'],secret_access_key:AMAZONS3['secret_access_key'])s3_

  7. centos7 根目录扩容 - 2

    需求        将测试环境根目录扩容到47G具体操作1.添加一块硬盘我们新添加了一块30G的硬盘2.查看本机磁盘环境lsblk我们可以看到根目录总容量为17G，新添加的设备sdb为30G 添加磁盘分区fdisk/dev/sdb创建分区：查看分区信息是否创建： 可以看见sdb1分区已创建。3.扩容现创建物理卷：pvcreate/dev/sdb1 查看物理卷和卷组：pvdisplay 将物理卷加入到卷组：vgextendcentos/dev/sdb1可以看到卷组的Freesize增加了vgdisplay 5.将卷组剩余空间(刚添加的30G)添加到逻辑卷/dev/centos/root lvex

  8. javascript - OL3 : Zoom to vector layer on map - 2

    我有一张带有openlayers3和矢量图层的map。我想将map调整为该矢量图层的大小，但到目前为止，我所能得到的只是将map居中放置在该矢量的最后一个点上，因为在创建map时无法访问矢量图层的点:if(trackMap!=null){for(vari=0;i 最佳答案 为什么不只适合ol.source.Vector的范围？varsource=newol.source.Vector();...map.getView().fitExtent(source.getExtent(),map.getSize());

  9. javascript - 三.js : 2xMeshes using same vector as position - 2

    刚刚在ThreeJS中从r67到r69进行了更新，结果在将它们的位置引用到一个(相同的)向量时遇到了问题。在我这样做之前:varvector=newTHREE.Vector3(50,50,50);_Mesh1.position=vector;_Mesh2.position=vector;这使得当我移动其中一个网格时它也移动了另一个成为可能。在r69中，位置向量保持不变(又名0、0、0)，这意味着每当我对另一个网格进行模式化时，我必须手动设置每个网格的X、Y和Z坐标。我是不是漏掉了一些零钱？或者我应该怎么做才能解决这个问题？ 最佳答案

  10. Qt 中的信息输出机制：QDebug、QInfo、QWarning、QCritical 的简单介绍和用法 - 2

    Qt中的信息输出机制介绍QDebug在Qt中使用qDebug输出不同类型的信息浮点数：使用%!f(MISSING)格式化符号输出浮点数布尔值：使用%!(MISSING)和%!(MISSING)格式化符号输出布尔值对象：使用qPrintable()函数输出对象的信息qInfoqWarningqCritical自定义信息输出格式不同输出方式的区别和底层逻辑总结介绍在Qt中，信息输出机制用于在程序运行时输出各种信息，包括调试信息、提示信息、警告信息和错误信息等。Qt提供了多种信息输出机制，主要包括以下几种：qDebug：最常用的信息输出机制，用于输出各种调试信息，例如变量的值、函数的返回值和对象的状

随机推荐