精华内容
下载资源
问答
  • 支持动态扩容,每次存储空间不够的时候,它都会将空间自动扩容为 1.5 倍大小 为什么是1.5倍呢,这个数据是固定的吗? 于是在网上查找了资料,也对此进行了测试。 1. 网上有1.5倍和2倍两者方法,不同编译器结果不...

    前言

    在读到文章《数据结构与算法之美》关于数组和容器一节时 (笔记在此),提到 容器的优点

    • 将很多数组操作的细节封装起来,如数组插入、删除数据时需要搬移其他数据等
    • 支持动态扩容,每次存储空间不够的时候,它都会将空间自动扩容为 1.5 倍大小


    为什么是1.5倍呢,这个数据是固定的吗?

    于是在网上查找了资料,也对此进行了测试。

    1. 网上有1.5倍和2倍两者方法,不同编译器结果不一样

    • gcc,python list是2倍 (后面有验证,python不是一直2倍)
    • VS是1.5倍

    两者的区别是,2倍扩容时间复杂度更优,可以保证时间复杂度 O(n)O(n) ,而1.5倍扩容时,空间可重用。

    在这里插入图片描述
    from: c++STL vector扩容过程


    2. 代码测试

    1) VS2017

    int main()
    {
    	vector<int> a;
    	for (int i = 0; i < 20; i++) {
    		a.push_back(i);
    		cout << "size : " << i + 1 << "\t" 
    		cout<< "capacity : " << a.capacity() << endl;
    	}
    	system("pause");
    	return 0;
    }
    

    在这里插入图片描述

    2) gcc

    代码同上
    在这里插入图片描述

    3) python3

    import sys 
    l = [] 
    empty_size = sys.getsizeof(l) 
    print("The size of an empty list :", empty_size, "bytes") 
    print("In 64 bit machine,  size of a single element is 8 ")
    
    for i in range(0, 50):
    	l.append(i)
    	size = len(l)
    	capacity = (sys.getsizeof(l) - empty_size)//8
    	print("size: ", size, "\t", "capacity:", capacity)
    
    
    

    在这里插入图片描述

    发现前面是2倍,后面就不是了。出现成正比的“线性摊销”概念。

    /* This over-allocates proportional to the list size, making room
    * for additional growth.  The over-allocation is mild, but is
    * enough to give linear-time amortized behavior over a long
    * sequence of appends() in the presence of a poorly-performing
    * system realloc().
    * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
    */
    new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
    
    /* check for integer overflow */
    if (new_allocated > PY_SIZE_MAX - newsize) {
        PyErr_NoMemory();
        return -1;
    } else {
        new_allocated += newsize;
    }
    


    参考

    展开全文
  • 我们知道,vector 在需要的时候扩容,在 VS 下是 1.5倍,在 GCC 下是 2 倍。那么会产生两个问题: (1)为什么是成倍增长,而不是每次增长一个固定大小的容量呢? (2)为什么是以 2 倍或者 1.5 倍增长,而不是以 ...

    我们知道,vector 在需要的时候会扩容,在 VS 下是 1.5倍,在 GCC 下是 2 倍。那么会产生两个问题:

    (1)为什么是成倍增长,而不是每次增长一个固定大小的容量呢?

    (2)为什么是以 2 倍或者 1.5 倍增长,而不是以 3 倍或者 4 倍等增长呢?

    1、第一个问题 :

    如果已成倍方式增长。假定有 n 个元素,倍增因子为 m; 完成这 n 个元素往一个 vector 中的 push_back​操作,需要重新分配内存的次数大约为 logm(n); 第 i 次重新分配将会导致复制 m^(i) (也就是当前的vector.size() 大小)个旧空间中元素; n 次 push_back 操作所花费的时间复制度为O(n),如下图所示:

    m / (m - 1),这是一个常量,均摊分析的方法可知,vector 中 push_back 操作的时间复杂度为常量时间.​
          如果一次增加固定值大小 。假定有 n 个元素,每次增加k个;第i次增加复制的数量为为:100i ;n 次 push_back 操作所花费的时间复杂度为O(n^2):
                           
    均摊下来每次push_back 操作的时间复杂度为O(n);
    总结:对比可以发现采用采用成倍方式扩容,可以保证常数的时间复杂度,而增加指定大小的容量只能达到O(n)的时间复杂度,因此,使用成倍的方式扩容。

    2、第二个问题

    有人回答说:vector最关键在于查询,使用移位(2的幂)直接得到哈希链以及节点长度,然后相减直接得到键值,复杂度为O(2),性能近似于数组,插入删除可动态,这就是vector设计的基本目的。

    显然,增长的倍数不可能很大,也不会比 1 小,那么,它的最佳上限是多少呢?如果以 大于2 倍的方式扩容,下一次申请的内存会大于之前分配内存的总和,导致之前分配的内存不能再被使用。所以,最好的增长因子在 (1,2)之间。

    知乎上有这样一段解释:

    https://www.zhihu.com/question/36538542/answer/67929747

    当 k =1.5 时,在几次扩展以后,可以重用之前的内存空间了
    ————————————————
    版权声明:本文为CSDN博主「denghe1122」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。
    原文链接:https://blog.csdn.net/dengheCSDN/article/details/78985684

    展开全文
  • ArrayList Vector 扩容

    2018-07-29 23:12:10
    扩容点规则(什么时候扩容): 整除运算将容量扩展为原来的1.5倍加1, 扩容实现代码newCapacity = oldCapacity + oldCapacity/2 +1;扩容容量为1.5倍加一; 存储方式:数组 扩容方法:Arrays.copyOf(elementData, size...

    ArrayList 扩容(JDK1.6):

    默认大小:10

    扩容点规则(什么时候扩容): 整除运算将容量扩展为原来的1.5倍加1, 扩容实现代码newCapacity = oldCapacity + oldCapacity/2 +1;扩容容量为1.5倍加一;

    存储方式:数组

    扩容方法:Arrays.copyOf(elementData, size);

    扩容序列化:ArrayList实现java.io.Serializable的方式。当写入到输出流时,先写入“容量”,再依次写出“每一个元素”;当读出输入流时,先读取“容量”,再依次读取“每一个元素”。

     

    ArrayList 扩容(JDK1.7):

    默认大小:10

    扩容点规则(什么时候扩容): 采用newCapacity = oldCapacity +(oldCapacity>>1);改为移位运算,同时扩容容量变为1.5倍。

    存储方式:数组

    扩容方法:Arrays.copyOf(elementData, size);

     

    ArrayList 扩容(JDK1.8):

    默认大小:刚刚初始化一个Arraylist其容量是0,当添加一个之后容量就变成了10

    扩容点规则(什么时候扩容): 采用newCapacity = oldCapacity +(oldCapacity>>1);改为移位运算,同时扩容容量变为1.5倍。

    存储方式:数组

    扩容方法:Arrays.copyOf(elementData, size);

     

     

    Vector 扩容:

    默认大小: 10

    扩容点规则(什么时候扩容): int newCapacity = (capacityIncrement > 0) ?(oldCapacity + capacityIncrement) : (oldCapacity * 2); 

    当扩容因子大于0时,新数组长度为原数组长度+扩容因子,否子新数组长度为原数组长度的2倍。 

    存储方式:数组

    扩容方法:Arrays.copyOf(elementData, size);

     

    展开全文
  • 我们知道,vector 在插入新的元素时但是之前的内存已经满的时候需要扩容,在 VS 下是 1.5倍,在 GCC 下是 2 倍。那么会产生两个问题: (1)为什么是成倍增长,而不是每次增长一个固定大小的容量呢? (2)为什么是...

    我们知道,vector 在插入新的元素时但是之前的内存已经满的时候需要扩容,在 VS 下是 1.5倍,在 GCC 下是 2 倍。那么会产生两个问题:
    (1)为什么是成倍增长,而不是每次增长一个固定大小的容量呢?
    (2)为什么是以 2 倍或者 1.5 倍增长,而不是以 3 倍或者 4 倍等增长呢?

    1、第一个问题 :
    如果以成倍方式增长
    假定有 n 个元素,倍增因子为 m; 完成这 n 个元素往一个 vector 中的 push_back​操作,需要重新分配内存的次数大约为logm(n),就是说如果这n个元素都需要扩容才可以加入,那么最坏的情况下也是需要分配内存的次数是logm(n)
    第 i 次重新分配将会导致复制 m^(i) (也就是当前的vector.size() 大小)个旧空间中元素; n 次 push_back 操作所花费的时间复制度为O(n),如下图所示:
    在这里插入图片描述

    m / (m - 1),这是一个常量,均摊分析的方法可知,vector 中 push_back 操作的时间复杂度为常量时间.​

    但是如果一次增加固定值大小
    假定有 n 个元素,每次增加k个;第i次增加复制的数量为为:100i ;n 次 push_back 操作所花费的时间复杂度为O(n^2):
    在这里插入图片描述
    均摊下来每次push_back 操作的时间复杂度为O(n);
    总结对比
    可以发现采用采用成倍方式扩容,可以保证常数的时间复杂度,而增加指定大小的容量只能达到O(n)的时间复杂度,因此,使用成倍的方式扩容。

    2、第二个问题

    有人回答说:vector最关键在于查询,使用移位(2的幂)直接得到哈希链以及节点长度,然后相减直接得到键值,复杂度为O(2),性能近似于数组,插入删除可动态,这就是vector设计的基本目的。

    显然,增长的倍数不可能很大,也不会比 1 小,那么,它的最佳上限是多少呢?如果以 大于2 倍的方式扩容,下一次申请的内存会大于之前分配内存的总和,导致之前分配的内存不能再被使用。所以,最好的增长因子在 (1,2)之间。

    知乎上有这样一段解释:
    C++ STL中vector内存用尽后,为啥每次是两倍的增长,而不是3倍或其他数值?

    使用 k=2 增长因子的问题在于,每次扩展的新尺寸必然刚好大于之前分配的总和:
    在这里插入图片描述
    也就是说,之前分配的内存空间不可能被使用。这样对于缓存并不友好。最好把增长因子设为 1 < k < 2
    在这里插入图片描述
    当 k =1.5 时,在几次扩展以后,可以重用之前的内存空间了
    以上内容转自:
    STL vector(四) vector 扩容为什么要以1.5倍或者2倍扩容

    至于为什么当k = 1.5的时候可以重用之前的内存空间呢?博主并没有做出详细的解释
    我看了上面提到的知乎那篇问答中也有好多朋友在问知乎的那位大神这个问题(我在此再次膜一下^ – ^),当然也有好多dalao在盖楼解答,开始的时候不是很理解,多次阅读后我谈一下自己的理解:
    这个和等比数列的概念有关:
    我们知道等比数列的第n项的通项公式:an=a1*q^(n-1)
    前n项和公式是:Sn = a1*(1-q^n)/(1-q)
    就还用上面的红色框中的图片说说:c = 4

    • 当k = 2时:
      第n次扩容的时候需要分配的内存是:an = a1*q^(n-1) = 4*2^(n-1)
      而前n-1项的内存和为:Sn = a1*(1-q^(n-1))/(1-q) = 4*(1-2^(n-1)) /(1-2) = 4*2^(n-1)-4

      差值 = an - Sn = 4 > 0
      

      所以第n次扩容需要的空间恰好比前n-1扩容要求的空间总和要大,那么即使在前n-1次分配空间都是连续排列的最好情况下,也无法实现之前的内存空间重用

    • 当k = 1.5时:

      第n次扩容的时候需要分配的内存是:an = a1*q^(n-1) = 4*1.5^(n-1)
      而前n-1项的内存和为:Sn = a1*(1-q^(n-1))/(1-q) = 4*(1-1.5^(n-1)) /(1-1.5) = 8*1.5^(n-1)-8

      差值 = an - Sn = 8 - 4*1.5^(n-1)
      当n增长到一定的数值后,差值就会变为小于0,此时便可以实现内存空间复用
      
    展开全文
  • 文丨语鹦企服原创,未经授权不得转载我们在做社群裂变活动的时候,通常会有大量粉丝添加我们的企业微信,如果要一个个手动通过,会浪费大量的运营人力和时间,有什么办法可以自动通过好友吗?如何开启企业微信自动...
  • vector在push_back的时候当容量不足时会触发扩容,导致整个vector重新申请内存,并且将原有的数据复制到新的内存中,并将原有内存释放,这自然是会导致迭代器失效的,因为迭代器所指的内存都已经被释放。 举例如下:...
  • vector的模拟实现

    2019-01-05 10:25:02
    我们模拟实现我们感觉最需要注意的还是扩容问题什么时候扩容什么时候不用扩容。 已经一个检查vector扩容的接口函数 也不知怎么说vector常用的接口,感觉主要分三类,第一类创建vector类,第二类修改vector元素类,第...
  • 从网上各处搜集的知识整理出来 1.因为vector是线程安全的,所以效率低,这容易理解,类似StringBuffer 2.Vector空间满了之后,扩容是一倍,而ArrayList仅仅是一半 3.Vector分配内存的时候...
  • ArrayList是线程非安全的。因为ArrayList中所有的方法都不是同步的,在并发下一定会出现线程安全问题。...Vector可以指定增长因子,如果该增长因子指定了,那么扩容时候会每次新的数组大小会在原数组的...
  • ArrayList:动态数组,使用的时候,只需要操作即可,内部已经实现扩容机制。 线程不安全 有顺序,会按照添加进去的顺序排好 基于数组实现,随机访问速度快,插入和删除较慢一点 可以插入null元素,且可以重复 ...
  • 结构图1.Vector什么2.Vector的特点3.Vector内部数组扩容4.Vector继承的类和实现的接口5.Vector遍历 0.结构图 1.Vector什么 可以简单的认为Vector是一个动态数组;Vector是通过数组实现的,长度不够是,调用...
  • 1.Vector也是集合类,继承和实现方式如下,它也是实现了list接口。很多博客说Vector和ArrayList基本都是一样的,只不过Vector是线程安全的...Vector没有采取ArrayList临界值扩容的办法,而是每次不够的时候,直接根据c
  • 因为Vector和ArrayList除了数组扩容有点差别,还有加锁使Vector迈进了线程安全的行列外,底层实现大约是没有太大区别的!基本一致!线程安全问题更是另当别论了!继续往下看就OK! 扩容的区别: 从内部实现机制来讲...
  • ArrayList是线程不安全的,在多线程并发访问的时候可能会出现问题,如果想使用线程安全的集合类,java自带有vector,也就是说vector是线程安全的。但是arayList的底层是数组实现的,而且可以自动扩容,获得元素或者在...
  • STL注意问题

    2019-03-20 09:29:01
    1、在声明一个vector时候,尽量指明大小,如果输入数据不超过10^6, 那就声明一个10^6大小的vector,否则,vector...想一下,如果你的vector不断的扩容,不断的复制,效率能不低吗?这就是有的网友问为什么STL的vector没有...
  • 【Java基础笔记】

    2019-06-27 20:19:27
    [2] 需要扩容时候,ArrayList默认变为原来的1.5倍率,Vector变为原来的两倍。 [3] 构造函数来说,Vector可以设置,每次扩容的增量,但是ArrayList不可以。 2ArrayList和CopyOnWriteArrayList 的区别是什么? ...
  • 发生扩容时,ArrayList 扩容1.5倍,Vector 扩容2倍 2、进程 和 线程 的区别? 进程:指系统中正在运行的一个程序,拥有独立的内存单元,系统进行资源分配和调度的基本单位 线程:是CPU调度和分派的基本单位,包含...
  • java大厂面试题汇总

    2020-03-19 10:08:45
    HashMap底层工作原理,数据结构,什么时候扩容 ArrayList 和 Vector 的区别 说说 ArrayList,Vector, LinkedList 的存储性能和特性 快速失败 (fail-fast) 和安全失败 (fail-safe) 的区别是什么? List、Map、Set 三个...
  • vector扩容的过程? 怎么彻底清空vectorvector怎么查找元素?如果是一个结构怎么查找一个vector结构中的指定元素?(find find_if) map查找的复杂度? map的底层是怎么实现的?map与hashmap的区别?什么时候应该...
  • deque

    2018-08-09 23:40:12
    写在前面 STL:deque总结 主要内容 为什么需要deque?... deque的作用是什么?...问题1:vector虽然可以动态的增容,但是只能在vector的尾部进行插入和...问题2:当vector容量满的时候需要扩容,这时候需要开辟一块...
  • Java集合22题 ArrayList 和 Vector 的区别。 说说 ArrayList,Vector, LinkedList 的存储性能和特性。... 快速失败 (fail-fast) 和安全失败 (fail-safe) 的区别是什么?... Hashmap 什么时候进行扩容呢...
  • 面试常用的面试题

    2020-04-09 10:46:18
    Java集合10题 ArrayList 和 Vector 的区别。 说说 ArrayList,Vector, LinkedList 的存储性能和特性。 ... 快速失败 (fail-fast) 和安全失败 (fail-safe) 的区别是什么?... Hashmap 什么时候进行扩容呢? ...
  • java面试题

    2019-09-26 09:37:03
    #1.Java集合22题 ArrayList 和 Vector 的区别。 说说 ArrayList,Vector, LinkedList 的存储性能和特性。 ... 快速失败 (fail-fast) 和安全失败 (fail-safe) 的区别是什么?... Hashmap 什么时候进行扩容呢...
  • ArrayList 和 Vector 的区别。 说说 ArrayList,Vector, LinkedList 的存储性能和特性。 快速失败 (fail-fast) 和安全... Hashmap 什么时候进行扩容呢? List、Map、Set 三个接口,存取元素时,各有什么特点? ...
  • Java集合22题

    2019-06-24 09:42:56
    ArrayList 和 Vector 的区别。 说说 ArrayList,Vector, LinkedList 的存储性能和特性。 快速失败 (fail-fast) 和安全... Hashmap 什么时候进行扩容呢? List、Map、Set 三个接口,存取元素时,各有什么特点? ...
  • Java 集合 1.ArrayList 和 Vector 的区别。 2.说说 ArrayList,Vector, LinkedList 的存储性能和特性。 3.快速失败 (fail-fast) 和安全失败 (fail-safe) 的区别是什么?...6.Hashmap 什么时候进行扩容...

空空如也

空空如也

1 2 3 4
收藏数 61
精华内容 24
关键字:

vector什么时候扩容