精华内容
下载资源
问答
  • Vector扩容机制

    2021-07-18 12:52:13
    Vector扩容机制 本文基于jdk16的源码,其他版本思路相同,代码有所不同而已,若存在问题,请大佬指点。 1、简单介绍 ①Vector类的定义说明 public class Vector<E> extends AbstractList<E> ...

    Vector扩容机制

    本文基于jdk16的源码,其他版本思路相同,代码有所不同而已,若存在问题,请大佬指点。

    1、简单介绍

    ①Vector类的定义说明

    public class Vector<E>
        extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
    

    ②Vector类的底层存储数据使用的是一个Object类型的数组

    protected Object[] elementData;
    

    ③Vector类是线程安全的,因为在其操作函数中带有synchronized

    public synchronized boolean add(E e) {
        modCount++;
        add(e, elementData, elementCount);
        return true;
    }
    

    ④开发中,需要线程同步安全,建议使用Vector

    2、扩容机制

    1、当使用的是无参构造函数创建Vector对象时,默认会初始化容量为10,每次扩容,容量 = 原容量 × 2

    Vector vector = new Vector();
    

    2、当使用的是一个参数的有参构造函数创建Vector对象时,初始化容量则为指定的长度,每次扩容,容量 = 原容量 × 2

    Vector vector = new Vector(8);
    

    3、当使用的是两个参数的有参构造函数创建Vector对象时,初始化容量则为指定的长度,每次扩容,容量 = 原容量 + 指定的扩容长度

    Vector vector = new Vector(8,2);
    

    (1)无参构造创建Vector对象

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-t3k9wqjN-1626583916162)(C:\Users\14538\AppData\Roaming\Typora\typora-user-images\image-20210718102500286.png)]

    从上面断点中进入Vector的无参构造中

    //用于保存数据的Object数组
    protected Object[] elementData;
    //容量扩容值,即当需要扩容时,进行多大的扩容
    protected int capacityIncrement;
    
    //Vector的无参构造
    public Vector() {
        //调用有参构造,并设置初始化容量为10
        this(10);
    }
    
    //从上面Vector的无参构造跳转到Vector的单个参数的有参构造
    public Vector(int initialCapacity) {
        	//此处调用Vector的两个参数的有参构造
        	//initialCapacity为容量,0为下次需要扩容时,扩展的长度
            this(initialCapacity, 0);
    }
    
    //从上面的单个参数的有参构造跳转到这里
    public Vector(int initialCapacity, int capacityIncrement) {
            super();
        	//如果初始化的容量小于0,抛出异常
            if (initialCapacity < 0)
                throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
        	//创建容量为initialCapacity的Object数组
            this.elementData = new Object[initialCapacity];
        	//容量增长值
            this.capacityIncrement = capacityIncrement;
    }
    

    无参构造初始化后,elementData数组大小为10

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-uT4sjjXr-1626583916166)(C:\Users\14538\AppData\Roaming\Typora\typora-user-images\image-20210718103401459.png)]

    添加元素

    在这里插入图片描述

    从上面断点进入上面的方法中

    //modCount用于记录数组被修改的次数
    protected transient int modCount = 0;
    
    public synchronized boolean add(E e) {
        //修改次数加1
        modCount++;
        //进行添加操作  e:需要添加的元素  elementData:保存数据的数组  elementCount:添加的下标位置
        add(e, elementData, elementCount);
        return true;
    }
    

    在这里插入图片描述

    调用上面的add(e, elementData, elementCount)方法进入以下代码

    //进行添加操作  e:需要添加的元素  elementData:保存数据的数组  s:添加元素的下标位置
    private void add(E e, Object[] elementData, int s) {
        //添加的下标值是否等于elementData的长度 即是否容量已满
        if (s == elementData.length)
            //进行扩容操作
            elementData = grow();
        //将元素进行保存
        elementData[s] = e;
        //下一次添加元素的下标位置加1
        elementCount = s + 1;
    }
    

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-UuGdm1Fv-1626583916175)(C:\Users\14538\AppData\Roaming\Typora\typora-user-images\image-20210718104252077.png)]

    当Vector的容量已满时,再次添加元素,需要进行扩容

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4oUrCvnM-1626583916178)(C:\Users\14538\AppData\Roaming\Typora\typora-user-images\image-20210718104429194.png)]

    进行扩容操作

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ELnNd4ig-1626583916180)(C:\Users\14538\AppData\Roaming\Typora\typora-user-images\image-20210718104637064.png)]

    //首先进入到这里
    private Object[] grow() {
        //进行扩容操作
        return grow(elementCount + 1);
    }
    
    
    //扩容操作
    private Object[] grow(int minCapacity) {
       		//之前的容量为elementData的长度
            int oldCapacity = elementData.length;
        	//新的容量主要看capacityIncrement > 0 ? capacityIncrement : oldCapacity
        	//如果指定的扩容长度大于0,则在原来的基础上加上指定的扩容长度 即newCapacity = oldCapacity + capacityIncrement
        	//否则在原来的基础上乘以2 即newCapacity = oldCapacity + oldCapacity
            int newCapacity = ArraysSupport.newLength(oldCapacity,
                    minCapacity - oldCapacity, /* minimum growth */
                    capacityIncrement > 0 ? capacityIncrement : oldCapacity
                                               /* preferred growth */);
        	//copyOf会保留原有的数据,在进行扩容
            return elementData = Arrays.copyOf(elementData, newCapacity);
    }
    

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ZoyfB792-1626583916182)(C:\Users\14538\AppData\Roaming\Typora\typora-user-images\image-20210718105318031.png)]

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CodAEHU6-1626583916185)(C:\Users\14538\AppData\Roaming\Typora\typora-user-images\image-20210718105434678.png)]

    (2)有参构造创建Vector对象(1个参数)

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-mNv3IhZf-1626583916187)(C:\Users\14538\AppData\Roaming\Typora\typora-user-images\image-20210718105552205.png)]

    //用于保存数据的Object数组
    protected Object[] elementData;
    //容量扩容值,即当需要扩容时,进行多大的扩容
    protected int capacityIncrement;
    
    //调用有参构造
    public Vector(int initialCapacity) {
        //调用两个参数的有参构造
        this(initialCapacity, 0);
    }
    
    //两个参数的有参构造 此时initialCapacity为8,capacityIncrement为0
    public Vector(int initialCapacity, int capacityIncrement) {
            super();
            if (initialCapacity < 0)
                throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
            //创建容量为initialCapacity的Object数组   this.elementData = new Object[8];
            this.elementData = new Object[initialCapacity];
        	//容量增长值   this.capacityIncrement = 0 
            this.capacityIncrement = capacityIncrement;
    }
    

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-S03gYlC1-1626583916189)(C:\Users\14538\AppData\Roaming\Typora\typora-user-images\image-20210718110010402.png)]

    当容量已满时,进行扩容的操作与无参构造相同

    (3)有参构造创建Vector对象(2个参数)

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JUPMtCZB-1626583916190)(C:\Users\14538\AppData\Roaming\Typora\typora-user-images\image-20210718110421399.png)]

    直接进入到两个参数的构造函数中

    //initialCapacity :初始容量  capacityIncrement:扩容长度
    public Vector(int initialCapacity, int capacityIncrement) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        //创建Object数组
        this.elementData = new Object[initialCapacity];
        //扩容长度赋值
        this.capacityIncrement = capacityIncrement;
    }
    

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gtUouh8b-1626583916191)(C:\Users\14538\AppData\Roaming\Typora\typora-user-images\image-20210718110714512.png)]

    当Vector的8个容量已满时,需要进行扩容

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9937X3Zm-1626583916193)(C:\Users\14538\AppData\Roaming\Typora\typora-user-images\image-20210718110853684.png)]

    中间步骤都相同,这里只看下具体的扩容操作

    这里因为我们创建Vector对象是调用的是两个参数的构造函数,即给了它扩容的长度为2,所以此处扩容是在原来的基础上加了2

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-iHi0k2YJ-1626583916195)(C:\Users\14538\AppData\Roaming\Typora\typora-user-images\image-20210718111045105.png)]

    3、Vector与ArrayList的简单比较

    底层结构版本线程安全(同步)效率扩容倍数
    ArrayList可变数组Object[]jdk1.2不安全,效率高如果为有参构造,初始化容量为指定容量,扩容为原容量的1.5倍; 如果为无参构造,初始化容量为10,之后每次扩充为原容量的1.5倍
    Vector可变数组Object[]jdk1.0安全, 效率不高如果为无参构造,初始化容量为10,扩容为原容量的2倍; 如果为单参数构造,初始化容量为指定容量,扩容为原容量的2倍; 如果为两个参数的构造,初始化容量为指定容量,扩容为原容量加上扩容长度
    展开全文
  • vector底层+扩容

    2021-08-13 09:23:21
    1、底层实现 Vector在堆中分配了一段连续的内存空间来存放元素。 包括三个迭代器,first 指向的是vector中对象的起始字节位置;...2、扩容过程: 如果集合已满,在新增数据的时候,就要分配一块更大的内存,

    1、底层实现

    Vector在堆中分配了一段连续的内存空间来存放元素。

    包括三个迭代器,first 指向的是vector中对象的起始字节位置;last指向当前最后一个元素的末尾字节;end指向整个vector容器所占用内存空间的末尾字节。
    在这里插入图片描述
    last - first表示 vector 容器中目前已被使用的内存空间;
    end - last 表示 vector 容器目前空闲的内存空间;
    end - first表示 vector 容器的容量。

    2、扩容过程:

    如果集合已满,在新增数据的时候,就要分配一块更大的内存,将原来的数据复制过来,释放之前的内存,在插入新增的元素。所以对vector的任何操作,一旦引起空间重新配置,指向原vector的所有迭代器就都失效了 ;

    2.1size() 和capacity()

    堆中分配内存,元素连续存放,内存空间只会增长不会减少。vector有两个函数,一个是capacity(),在不分配新内存下最多可以保存的元素个数,另一个size(),返回当前已经存储数据的个数。对于vector来说,capacity是永远大于等于size的,capacity和size相等时,vector就会扩容,capacity变大(翻倍)。

    2.2resize()和reserve()

    ①resize():改变当前容器内含有元素的数量(size()),而不是容器的容量。

    • 当resize(len)中len > capacity(),则数组中的size和capacity均设置为len;
    • 当resize(len)中len <= capacity(),则数组中的size设置为len,而capacity不变;

    ②reserve():改变当前容器的最大容量(capacity)

    • 如果reserve(len)中len >当前的capacity(),那么会重新分配一块能存len个对象的空间,然后把之前的对象通过copy construtor复制过来,销毁之前的内存;
    • 当reserve(len)中len<=当前的capacity(),则数组中的capacity不变,size不变,即不对容器做任何改变。

    3细节:

    3.1、为什么要成倍的扩容而不是一次增加一个固定大小的容量呢?

    采用成倍方式扩容,可以保证常数的时间复杂度,而增加指定大小的容量只能达到O(n)的时间复杂度。

    3.2、为什么是以两倍的方式扩容而不是三倍四倍,或者其他方式呢?

    考虑可能产生的堆空间浪费,所以增长倍数不能太大,一般是1.5或2;GCC是2;VS是1.5

    k =2 每次扩展的新尺寸必然刚好大于之前分配的总和,之前分配的内存空间不可能被使用,这样对于缓存并不友好,采用1.5倍的增长方式可以更好的实现对内存的重复利用。

    C++并没有规定扩容因子K,这是由标准库的实现者决定的。

    展开全文
  • vector动态扩容

    2021-04-07 09:28:30
    扩容的大小叫做扩容因子,扩容因子由编译器决定,VS的扩容因子为1.5,G++中,扩容因子为2。如果个人电脑是windows一般不用G++,而是用VS的IDE来编译运行,如果是linux系统,一般用G++,Mac系统一般用clang(linux也...

    vector以连续的数组存放数据,当vector空间已满时会申请新的空间并将原容器中的内容拷贝到新空间中,并销毁原容器,存储空间的重新分配会导致迭代器失效,因为分配空间后需要进行拷贝,编译器会预分配更多空间以减少发生拷贝影响程序效率。


    扩容的大小叫做扩容因子,扩容因子由编译器决定,VS的扩容因子为1.5,G++中,扩容因子为2。如果个人电脑是windows一般不用G++,而是用VS的IDE来编译运行,如果是linux系统,一般用G++,Mac系统一般用clang(linux也可以用clang,但是G++是主流。G++就是将包含代码的文本文件编译成可执行文件,然后再能执行。

    扩容因子的影响:

    • 扩容因子大,每次需要分配的新内存空间越多,分配空间耗时。空闲空间较多,内存利用率低。
    • 扩容因子小,需要再分配的可能性更高,扩容耗时。空闲空间较少,内存利用率较。一般认为扩容因子1.5优于2.0,原因是以1.5作为扩容因子可以实现复用释放的内存空间。
    • 以2为扩容因子时,分配空间为:1,2,4,8,16
      • 分配空间空闲空间
        10
        21
        41+2=3
        83+4=7
        167+8=15

         

    从上述表中可以看到空闲空间始终小于分配的空间。

    如果扩容因子是1.5,分配空间为:1,2,3,4,6,9

     

    分配空间空闲空间
    10
    21
    31+2=3
    43+3=6
    66+4=10

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

    ————————————————
    版权声明:本文为CSDN博主「CCCSR」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
    原文链接:https://blog.csdn.net/Rengachan/article/details/109604104

    展开全文
  • Vector扩容机制

    2021-09-27 17:45:36
    同样的Vector的初始化也有无参和有参 无参: public Vector() { this(10); } 直接给定初始容量为10;...定义初始化容量大小,扩容参数为0 两个参数: public Vector(int initialCapacity, int capacityIncrement) {

    同样的Vector的初始化也有无参和有参

    无参:

        public Vector() {
            this(10);
        }
    

    直接给定初始容量为10;

    一个参数:

        public Vector(int initialCapacity) {
            this(initialCapacity, 0);
        }
    

    定义初始化容量大小,扩容参数为0

    两个参数:

    public Vector(int initialCapacity, int capacityIncrement) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
        this.capacityIncrement = capacityIncrement;
    }
    

    定义容量大小,和扩容参数大小

    添加元素,调用add()

        public synchronized boolean add(E e) {
            modCount++;     //修改次数+1
            ensureCapacityHelper(elementCount + 1);   //判断是否需要扩容
            elementData[elementCount++] = e;
            return true;
        }
    

    调用ensureCapacityHelper()判断是否扩容

        private void ensureCapacityHelper(int minCapacity) {
            // overflow-conscious code
            if (minCapacity - elementData.length > 0)   //放入元素后的长度 > 数组长度 ,扩容
                grow(minCapacity);
        }
    

    需要扩容,调用grow()扩容

        private void grow(int minCapacity) {
            // overflow-conscious code
            int oldCapacity = elementData.length;
            int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                             capacityIncrement : oldCapacity); 
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
    
    Vector总结:

    无参的Vector初始容量为10;

    如果实例化时初始化参数 capacityIncrement > 0,那么扩容时,新容量 = 旧容量 + 扩容参数,

    没有实例化时没有初始参数 capacityIncrement > 0,那么扩容时,新容量 = 2 * 旧容量,

    展开全文
  • vector扩容机制:当向vector插入元素时,如果元素的有效个数和空间容量相等时,vector内部会自动触发扩容机制,而扩容主要分3步骤:开辟新空间,拷贝元素,释放旧空间。 但是每次扩容时,新空间的开辟不能太大,也...
  • vector扩容机制及扩容后数据地址变化 vector是STL中的动态数组。和数组不同,数组长度一旦确定就无法改变。而vector是可以灵活增加的。(可以不断地push_back()) 1、size() 和capacity() capacity()返回的是总的...
  • 文章目录一、概述二、 高效使用vector,避免扩容1.扩容机制回顾2.如何避免扩容导致效率低三、为什么选择以倍数方式扩容1. 以等长个数进行扩容2. 以倍数方式进行扩容3. 为什么选择1.5倍或者2倍方式扩容,而不是3倍、4...
  • vector扩容

    2021-01-06 17:42:16
    扩容原理概述 新增元素:Vector通过一个连续的数组存放元素,如果集合已满,在新增数据的时候,就要分配一块更大的内存,将原来的数据复制过来,释放之前的内存,在插入新增的元素; 对vector的任何操作,一旦引起...
  • C++的STL中vector扩容思想及实现 原理 C++的STL库中的vector,是一种使用很频繁的容器,因为它是一个自动扩容的容器,使用起来比较灵活,可以一直往容器的末尾添加数据。 那么它是怎么实现自动扩容的呢?其实关键...
  • c++ stl vector扩容机制

    2021-09-02 21:13:13
    vector> using namespace std; int main() { std::vector<int> vec; size_t cap = vec.capacity(); for (int i = 0; i < 10000; i++) { vec.push_back(i); if (cap != vec.capacity()) .
  • vector扩容时以2倍或1.5倍扩容的原因

    千次阅读 2021-02-01 08:33:37
    vector扩容原理 Vector通过一个连续的数组存放元素,如果集合已满,在新增数据的时候,就要分配一块更大的内存,将原来的数据复制过来,释放之前的内存,在插入新增的元素; 对vector的任何操作,一旦引起空间重新...
  • 1、简介: public class Vector<E> extends AbstractList<... 但是, Vector的大小可以根据需要增大或缩小,以便在创建Vector后添加和删除项目。 从Java 2平台v1.2开始,该类被改进以实现Lis
  • 但是笔者却发现了一个奇怪的现象,std::vector扩容时,对其中的元素竟然进行的是深复制。请看示例代码: #include <iostream> #include <vector> struct Test { Test() {std::cout << "Test" &...
  • JDK14中Vector类的动态扩容 Vector类的动态扩容 Vector与ArrayList一样,也是长度可变的动态数组。 当集合中的元素数量大于当前集合的长度时,Vector扩容为原来的2倍,而ArrayList只会扩容为原来的1.5倍。 源码...
  • 简单了解java的Vector扩容

    千次阅读 2021-03-15 01:44:30
    import java.util..../**** VectorTest** Description: JDK 1.8* 测试Vector扩容方式,通过测试可以看出其每次以2的倍数形式扩充Object数组** @author Jalen* @date 2019/8/27 13:31*/public class VectorTes...
  • vector> using namespace std; void test() { vector<int> v; v.push_back(1); size_t capacity = v.capacity(); cout << "v2:capacity():" << capacity << endl; v.push_ba
  • 不同于原生的数组需要我们在声明时就得指定数组的大小,这无疑给我们的开发工作带来了很多便利,那么,vector这个类究竟在底层做了什么呢? 原理 在标准类库中,当我们采用push_back操作,往vector中添加元素时,若...
  • vector的insert()扩容

    2021-04-24 15:56:07
    不一定按照两倍size()扩容 //insert扩容原理 //capacity() = n, size() = m, 待插入元素的个数t, //1、t < n - m;此时不会扩容 //2 n - m < t < m;此时按照2 * m扩容 //3、m < t < n,扩容t + ...
  • 要解释为什么要两倍扩容我们可以分两步理解? 1.为什么选择成倍扩容,而不是成等差扩容? (1)我们假设我们使用m扩容,一共有n个元素,那么我们需要扩展多少次才能装下这n个元素,通过计算我们可以得到:,那么...
  • 一、vector Visual Studio... 推荐文章:vector扩容原理说明 如有错误或不足欢迎评论指出!创作不易,转载请注明出处。如有帮助,记得点赞关注哦(⊙o⊙) 更多内容请关注个人博客:https://blog.csdn.net/qq_43148810
  • push_back和emplace_back比较以及vector扩容push_back和emplace_back的比较使用测试类测试过程将实体类对象传入将右值数字传入将实体类对象move()转右值之后传入vector扩容过程 关于这部分内容,也是C++中的...
  • 这里写自定义目录标题vector 容器扩容的整个过程功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右...
  • 以如下代码,对底层扩容代码解读 Vector vector = new Vector(); // Vector vector = new Vector(8); for (int i = 0; i < 10; i++) { vector.add(i); } vector.add(10); 无参构造器 Vector vector = new ...
  • 当底层实现涉及到扩容时,容器或重新分配一段更大的连续内存(如果是离散分配则不需要重新分配,离散分配都是插入新元素时动态分配内存),要将容器原来的数据全部复制到新的内存上,这无疑使效率大大降低。...
  • JDK1.7的ArrayList的 扩容机制源码。JDK1.7的源码是 ,在实例化这个 ArrayList 集合对象的时候。不管 调用者初始化完ArrayList对象后 继不继续 使不使用,在初始化对象的时候,都会创建一个长度为 10 的 Object 的...
  • Vector动态扩容

    2020-12-18 18:00:54
    Vector动态扩容无聊看了一下Vector的源码看看动态扩容怎么实现的一.vector的介绍首先这玩意是动态的,非常灵活 储存的时候是连续的线性空间,插播一个在 中看到的问题, 提出质疑原文如下:所以它的迭代器也是完全可以用...
  • vector扩容机制

    2021-03-24 09:06:27
    当向vector插入元素时,若超出了end_of_storage
  • 默认容量为10 扩容机制 增长的因子 原有容量+容量的一半=新的数组 (1.5倍)例如:扩容前10 -> 扩容后 15 Vector扩容机制(拓展) vector是以2倍的方式扩容的 1.为什么要成倍的扩容而不是一次增加一个固定大小的...
  • ArrayList扩容:new ArrayList()以后,size为0,第一次add后size为10,当数组满后,以当前数组容量的1.5倍进行扩容。...Vector扩容:Vector有三个构造方法: public Vector(int initialCapacity,...
  • 1、vector的内存是在栈中? 前两天面试官问我,vector怎么进行内存分配?我回答:在栈中分配,由操作系统负责。 果然没有那么简单,现在想想我真是个sb。...2、vector扩容怎么拷贝? 经常问的一个..

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 29,115
精华内容 11,646
关键字:

vector什么时候扩容