00:00
好,那么这个俄呢,讲完之后呢,我们这个wa呢,因为他也不用了,所以咱就可以稍微的快速的去说一下了啊这个VE的话呢,我们直接呢,就说1.8了。啊,为啥你不看一个1.7呢,基于两个原因,第一个呢,他现在也不咋用了。第二个原因的话呢,其实1.7跟1.8呢,也没什么区别。反正也不咋用了,所以1.8的时候呢,干脆呢都没改什么意思啊,就是它呢,就类似于咱们1.7当中的啊,当我们一开始做一个这样的声明。我叫V了啊,你一个。啊,这个时候呢,在1.8当中啊,你发现呢,他也都把这个数组都造好了。啊,然后再通过这个V呢,我们第二个I的方法是吧,来一个A,那这个呢,就往里边去放。啊,然后v.a的啊,这个来个BB是吧,哎,他也往里边去放,他呢,一开始呢,我先把这个事儿先说清楚啊,这个呢,我们一上来造对象,那底层呢就是呃。初始化数组。诶提升了初始化速度,然后呢,长度为。
01:02
诶长度为十是吧,哎,那就意味着它底层这个所谓的叫啊数组啊element推塔化呢。这个我们写上object啊。这样一个数组的话呢,它也是new啊。Object这个十呢,就也出现了。说这呢,可是1.8的啊。哎,1.8呢,它就给你造好了,然后这个呢也类似啊,那无外乎呢,就是把你放到角标零的位置啊。哎,这个呢,叫A了。啊,下边类似。啊,这个呢是角标一的位置,这个叫BB啊好,然后呢,这块呢,不断的往里边添加添加添加,哎,我们说当添加D。啊,11个元素时。哎,是不是需要扩容啊。他说,默认扩容为原来的。二倍。哎,它这个是扩容的二倍啊,所以这个1.5倍也好,二倍也好,这个呢,其实都他提前定义好的啊,因为这个倍数多吧。
02:06
空的就多一些是吧。比如原来是这么多,然后呢,你要定义成二倍,那这块呢,就会空的空间多一点,你要定义的这个短像1.5倍吧。有可能后边不够了,还得再扩是吧。这就是找到一个平衡。啊,那相对来说,他可能考虑过这个统计上的一个规律哈,呃,像这个1.5呢,应该要好一点。所以呢,他不是先有的这个vector嘛,1.0的版本就有了,它先是二倍,后来发现呢,我们整1.5倍呢,其实就更好一点是吧,节省点空间诶,所以这个他就后来呢,相当于多用点1.5倍啊。好,那么对于这个逻辑呢,CTRLC一下回到这个list这块。哎。诶,CTRLV过来啊,这个就去掉了啊。打一个断点,咱们现在还是1.8的啊,直接抵八个。诶过来了是吧,好,这是我们进入源码。啊,还是克拉斯点啊,咱们再出来,出来呢,还得再出来一次,然后再进来啊进来了好,那这时候就十就出现了。
03:07
啊,这个十出现了,然后我们再进到这个源码里边。啊,又跑到这儿来了,那他这有一个呢,叫capacity。啊,Increment是吧。也就这块它第二个参数。我再我再点一下吧。啊,你看这块这个刚才那负了是个零哈。这个零的话呢,一会儿呢,哎。会不会见到他啊,哎,你就现在知道啊,这是个零,然后这个位置的话呢,刚才过来是不是个十啊。这个十进来了,然后往下走。这个没进去,走到这儿了,这个数组是不是就造好了。啊,这个速度没问题,然后往下再走一行,这个我们看下这个Z4往下走element data走,这是不是就长度为十就出来了。没问题啊好,接着再往下走出来了啊,再走出来了,再走出来了,这不就到这儿了吗?相当于我们这个执行完以后呢,咱们当前这个V啊,提升这个数组呢,就造好了,然后呢,再往下执行一步。
04:05
啊,这是我们要添加了啊,添加这块呢,其实也没啥好看的,就加进去,主要呢,我们想看一下这个扩容的事儿啊,好进到源码。这个mood can,这个咱就不多说了啊,然后往下走。这个位置的话呢,其实是在做这个扩容的一个判断了。啊,这个element count,它这个呢,不像咱们那个用的size是吧。它叫element count啊这个呢,Count加加。哎,这个呢,加个一第一个元素呢,这不就是零嘛。零加一是吧,你看我们这个位置的话呢,是不是也行。这就相当于咱们release那个size。然后呢,进到这个源码里边。啊,然后这块呢,过来它是一啊,减去我们当前这个长度,这是十吧。这是十,所以说这块不用扩容是吧。呃,第一个元素你肯定不用扩了,咱这块呢,想看一看,万一要不够的话呢,得扩怎么扩哈,你看我点到这个格这块。进来了啊,进来以后呢,呃,假设我们现在需要扩容了,那你十个呢,再加一个,这就相当于这是11了,不是要不够了吗。
05:07
诶,你看这块怎么扩的啊,把你原有的这个元素的这个长度再加上一个,诶我刚才说了不是有这样一个变量吗。这个变量咱们说是零是吧,所以呢,它就是取的这个吧。是吧,取的这个,那就是他加他。这不就二倍吗?如果他要不是零的话呢,它还很灵活哈,假假设这个位置你写的是十,十大于零,那就这就是十,相对呢,我不管你原有的多长,只是每次加十个是吧。对吧。他不是很灵活吗?诶,这个呢,因为咱们刚才看到那个构造器里边传的是个零啊,所以只不过呢,所以它就是O的加O的了,你要这块传的是个十,就相当于每次扩容十个哈。是O加上这个十嘛。那就成这意思了啊,这个我们就看着了,看着咱就完事了啊好,这个直接的就回来了。好,那这样话呢,咱们不就把这个ER呢,就也说清楚了啊。
06:04
啊,这个的话呢,不是咱们的重点,诶,所以大家了解下就行啊,然后呢,诶稍微再多说一句,你看我们这个a release的话呢,它在一开始的时候并没有创建长途微视的这个数组,但是呢,你会发现这个API文档哈,哪怕咱们现在看的是最期的这个17的这个文档。哎,我们这块呢,你看一下这个。A release哈,进来以后,然后你看它这个空间构造器哈,它这块呢,仍然写的是这样的一句话。是吧,说构建了一个空的list,然后有一个初始化容量是十,其实我们发现呢,其实并没有创建是吧。所以你说他这句话错了吧?也有道理,因为确实也没造。但是你要说他不对吧。他也能说出来点道理,反正你在第一次添加之前呢,我给你造了。只不过呢,我把这个行为呢,操作是不是后置了。后置道,咱们说的就像懒汉室一样,你需要的时候我再给你造是吧?哎,所以呢,也算不错。是吧,诶你知道这么个事儿就行啊。
07:01
实际上这块底层并没有创建嘛。好,那么vector呢就过了。啊,你看vector的话呢,在1.8里边跟1.7都一样,相当于还是一个类似于叫恶汉式的一个场景,就因为它也不咋用嘛,所以都懒得改它了。好,那么下面的话呢,我们来看一下这叫link list了啊link list呢,咱们说底层呢,它是使用的链表,而且是个双向链表,那我们就得能通过看底层源码,要能看到这样的结构那才行。那么这呢,也是咱们直接呢,就看这个GD8当中这个源码的剖析了,所以你怎么七跟八没有区别吗?说这个数组怎么着呢,它也不是数组啊。是吧,它就链表啊,根本不涉及到数组这样的概念了,OK,这儿呢,我们看这源码剖析的话呢,诶咱们先,诶直接在这儿说一下吧。哎,相当于我们首先呢,也是啊先呢去创建一个对象了。哎,这个我们也加上泛型啊。哎,四周类型的。Link at least。OK,这么着啊,好,这一行代码执行完以后呢,底层干啥了呢,其实也没干啥。
08:03
啊,他也不是数组,也不涉及到数组的一个初始化。其实呢,就相当于是一个默认的就执行完就执行完了。OK啊,然后呢,我通过这个绿色的点,咱们去艾特一下啊,来一个A是吧。然后立点艾来一个这个BB。啊,这块的话呢,相当于我们有一个AB了啊,它是这样的啊,在这个例子里边,一会儿我们看的话呢,它会有两个属性哈,一个属性呢叫做first,一个属性呢叫做last。哎,都是让我们,哎这个里边呢,它存储的元素呢,它其实是个node了啊。哎,咱不是说它是一个双向链表吗。它既然是双向链表,咱们在讲上一节的时候呢,提到过这个双向链表。它里边呢,是不是一定得有个这个东西啊。啊,它得有个这个东西,我们才能证明它相当于是个双向链表啊好,再回到我们刚才这个位置啊,就是我们呢,会在这个例子里边呢,看到一个这样的东西哈,一个内部类了,然后呢,这个它呢定义了一个note类型的first note类型的last,就是相当于来记录一下我们当前这个列表里边的第一个元素和最后一个元素哈。
09:07
那你要是相逆,先逆完之后呢,那就这是个闹。这也是个闹是吧?因为都还没元素了嘛。哎,我要添加了一个元素呢。这是我要扭出来一个node了。它是一个双向列表,那当前我这个note里边呢,核心元素这就是AA吧。然后呢,前面呢,也没有闹吧,写成个N了啊哎,这呢也是个闹。那这块添加的时候呢,注意你现在就一个元素,所以说first是不是你,Last也是你。对的啊,好,就这时候他俩都不是闹了,就都塌。然后呢,我再加一个BB。ABB来了,核心的元素呢,就是BB。哎,BB啊好,然后这时候呢,就需要有些操作了啊,因为我们是双向列表了,这个A的话呢,这个就不闹了,是不是就得指向它。你呢,指向上一个,是不是也指向他呀。对的,然后这个位置呢,它是no。哎,然后这个first呢还是A,这个L呢也变了。
10:02
是不是就是BB了?就这样的,然后依次呢,再往后走。啊,这个思路呢,大家就清楚了,所以说这块我们第一次添加的时候,呃,做了啥事儿呢,就相当于我们得创建一个呃,Node类型的一个对象了。然后呢,这个first和last呢,都指向它,然后第二个时候呢,诶,再创建一个note类型的对象,跟第一个之间呢,有这种双向列表的关系了,然后first last啊这样的一个行为。啊,我简单的说一下啊,这个因为呢,它底层没有数组结构,所以这块呢,我们造对象这个事儿呢,你可以理解成呢,就是底层呢。啊,也没做啥。是吧,然后呢,第一次呢,我们调离艾操作的时候,呃,首先呢,我们说呢,是将。哎,将这个数据呢,叫AA是吧,哎,封装到一个no的对象中。跑远了啊,哎,弄的对象中。然后呢,我们这个,呃,List的这个,其实就我们这个对象啊。
11:00
哎,这个list对象的这个属性。那有一个叫first是吧,和这个都。哎,指向。词,哎,这个弄的对象是吧。哎,就是这样的。好,这是它了,然后呢,我们又添加了一个BB。啊,这个呢,将BB封装到一个node对象中。这个我们叫比如对象一吧。这个叫弄的对象二。啊,当中啊。嗯,然后呢,这是BB哈,这时候呢,我们这个对象一和对象二呢,就构成一个双向列表。构成一个。双向。链表,然后同时咱们这个last。他这时候呢,就会指向啊,咱们这个node对象二。哎,它指向哎node对象二,咱们这个first的话呢,还指向这个node对象一。
12:02
诶就这样个情况,然后这块呢,我们诶不停的点点点点点点往里边添加,添加它需要扩容吗。不需要是吧,哎,这呢,我们写一下啊说呢,因为啊这个link list。哎,它呢,使用的是双向链表。哎,链表。哎,不需要。诶考虑啊扩容问题。所以呢,你就只管往里加就可以了。说完了啊好,说完之后呢,下边我们就来测试一下这个代码了啊,CTRLC回过来。啊,再写一个单元测试啊三。这个呢,就关掉了啊。好这块呢,我们说清楚以后,下边呢,我们来看一下这个源码来证明呢,咱们说的是对的。啊,先看第一个事儿啊。所以这块呢,我们都不断延行,直接一点进来,你看一下不就得了。
13:01
这不就这哥俩吗?诶,这里就出现node类型了,哎,Node类型点一下。是不是他了?哎,我把这个呢,CTRLC一下啊,咱们放到这个啊,这呢我们写上啊说link list内部。哎,内一步声明,哎,就是我们这个node啊,CTRLV,然后一粘里边呢,还有其他的一些构造器啊,我就不写了啊,核心的内容往这一放,看得很清楚啊这呢,我们这个泛型是string,那这儿呢就是string。那这个呢,就是string,这是string,这个是string。哎,所以呢,你看一个N一个pre,这不就是指向前一个指向后一个,诶跟咱们自己写的这个结构这块,这不是一样的吗。啊,OK啊好。那么拉回来啊link list这呢,我们就看到它这个node了哈,哎,行,这个我们就先再翻回去。诶再回到这儿了,那这个构造器这个事儿呢,基本上是没什么作为了啊里边呢啥也没干,然后呢,我们首次呢去添加这咱就不用debug了,直接来吧,诶点一下ADD。
14:05
A呢,就进来了。然后就要调这个叫link last,点进来就跑到这来了。这个代码呢,你看他没几行,但是这块代码写的很漂亮啊。这个看能不能搞得定啊。来,咱们一起来看一下。现在这是AA了是吧。啊,这个脑袋得清楚啊,别迷糊,这个呢,现在是没有,咱们这是首次添加,所以这个呢,其实是个no啊。那只向L了。其实这块清楚,我就现在把last这个值呢付给L,然后呢,我现在呢new了一个node。这个note呢,咱们刚才看到了,我这块点一下,主要是为了方便让大家看清楚这个。这构造器的一个参数的意思啊,Element element next,给这个给。啊,这个回来啊好。现代化呢?我们用了一个node。我把你当前这个元素呢,放在中间位置,这不就是实打实的数据吗。然后呢,这个L呢,其实就相当于是你上一个元素是吧。
15:03
咱们这儿呢,只不过是第一个元素,这其实是闹,这其实你过来实打实的也是个闹是吧,下一个没有。哎,真的就直接写成no了,这就咱们新封装的这个AA的这个数据了。然后这个A这个数据呢,现在你是下最后一个了吗。所以就把塔他呢付给这个拉了,没问题吧。没问题啊,好,然后他问一下,说你这L是no吗?咱们第一次添加是no是吧,所以呢,我就把你给first了,说白了就是你即是最后一个,你也是第一个。然后赛加加了一下。这个呢,咱不用管它添加呀,删除啊等等,它都会有这个mode框的一个变化啊,诶这个呢,是不是就结束了。啊,这个方法执行完是不是咱们刚才呢,调I的时候呢,这不就掉它了吗。他就结束了。这呢是第一次,第一次完了以后呢,就像咱们看到的啊,现在呢,你这个node是A了,它既是一个first也是一个last了,好,现在我们添加第二个啊。
16:00
第二个呢,你调这个BB的时候呢,调的这块再进来,这就BB了呗。好,现在看啊。有。OK啊好,然后呢,我们现在你一个新的node,这个呢,不就是BB吗。然后呢,把你这L呢过来,其实不就AA的吗。哎,这个A呢,你还付给他了,相当于我们这时候BB的这个指针就指向A了啊。没问题吧?哎,就通过这L那边付的,就是它指A了,但A呢还没指过来呢啊。好,它指向A了,然后呢,BB的next呢是个no,没问题,好你新的这个元素。你就是最后一个了。哎,那原来呢是A,现在呢,这不是覆盖了吗。哎,变成last了,对,是BB了啊,然后这个L,注意,我把原来的这个last给了L了,然后我这个last改了L不受影响啊。L是不是还是A呀。好,L是闹吗?不是A直行到这来。哎,L到这L是A啊,A的nice呢,指向你这个了,是不是它这个指针就过去了。
17:01
好的,完事了,再再加加一下,结束了。所以这呢,他还是first哈,他呢现在是last了,然后他俩指针呢,互指了一下。是不是就可以了。哎,那么回过来执行完以后呢,这不就我们说的这样的场景吗。好,那么关于这个link list呢,这个事儿呢,咱们就说清楚了。哎,那下边也写哈,说link是不是存在扩容问题。不存在是吧,OK啊,那我们刚才在讲了这么多,诶,下边我们要写这个启示了啊,讲了这些源码呢,其实应该是有助于我们开发中的一些选择的,否则我们看他的目的呢,就纯粹是为了看而看了啊。其实第一个点。啊,咱们以前说过啊。呃,外基本不用是吧。哎,不使用了啊,这个呢,就已经放弃它了啊啊,除了它之外呢,有有link list,先来对比一下a release和link list,我们该如何选择。啊,就我们平时什么时候会用啊,什么用link呀。
18:00
哎,基于它底层的数据结构是吧,而类呢,我们说底层。使用的是数组结构啊,那就意味着我们叫哎查找。啊和。啊添加。注意这个添加呢,咱们指的是这个尾部添加是吧。哎,你中间的添加,那其实叫插入了啊。诶查找和尾部和这个添加呢,这个效率高。啊,这个我们说呢,叫时间复杂度。喂。是O1的呀。哎,是他的啊,诶然后呢,这块我们同步的去写啊,它呢,对于这个叫删除。啊和插入操作。是不是这个效率低呀?啊,这个呢,时间复杂度是。对,是on的啊。哎,是他的啊,这个和添加操作。哎,这样的,哎好,这个呢,是我们说的release,那什么场景用的你就清楚了,哎对应的我们这个,哎link list底层使用。
19:08
哎,它呢底层使用呢,叫双向链表。啊,这个结构。呃,那么它呢,就意味着我们,呃,先是先写一个高的吧,是删除和插入操作的效率比较高是吧。哎,对,这个比较高,哎这个是O1的,哎这呢咱们前面也稍微提到过啊,这边有这样的几个元素,哎假设的话呢,这个特别多哈,我现在想把这个元素呢给它把这个吧,把它给删掉了。嗯,你只需要呢,改一下前后两个元素这个指针的指向就可以了,是吧,这就删掉了啊想插入一个呢,是不是也类似的这样的一个操作。哎,其他位置的元素根本都不用动,哎,所以这就是O常数级别的就O1了啊。好,那么先生的这个操作呢。诶对这个啊,CTRLV一下这个查找呢,诶和这个添加啊,它的复杂度呢,就变成on了。
20:02
哎,但是这块你注意一下啊,查找的话呢,哎,指的就是它呢,不像数组直接有这个偏移量指数了,它这个元素的话位置在哪,它这不是挨着的是吧。逻辑上是挨着的,但是实际上物理层面它不挨着啊。不外这话呢,比如我想找第三个元素,它就得从第一个找到第二个,第二个再找第三个。就这样去找,这不就是on级别的吗?哎,那这个添加这个事儿呢,得多说一下啊,添加这块我们得假设什么呢?他没有去记录这个last的位置。这样的话,你要是每次添加我们都得从第一个呢,是不是一直找到最后一个是吧,这就是on的啊,但是如果说它专门有一个变量定义一下这个了。其实就是O1了是吧,因为在添加的时候,我直接就知道它在哪儿了,我就直接往后添加了,这就是OE的是吧。所以这块呢,我这个添加的话呢,这个你得具体再看一看。是吧,是O的还是有可能这个添加也是OE的是吧。就我在这儿严密一点啊,说有可能这个添加操作。
21:02
哎,它呢是这个O1的啊,但是我们这个查找的话呢,它一定是一个O的哈。好这块咱们就知道呢,在什么时候呢,选用哪一个了啊。行,然后呢,再多说一句,针对这个early的话呢,咱们发现它底层使用的是个数度结构,如果你选择这个了,我们其实呢,针对它的构造器呢,还是有选择的。啊,也就是说呢,啊说如果。哎,或者这样说吧,在选择了a release这个前提下啊,我们通过看源码发现呢,它默认的,呃,如果我们使用的是一个new这样的一个数据结构的话呢,这个它相当于底层。是不是创建。哎,长度为十的这个数组是吧。哎,那其实还有另外这个构造哈。哎,如果我们这块new的话呢,是array list,它还有个构造题呢,是有个int型的叫capacity。对,这个我们底层可以创建指定长度的这个数组。
22:03
呃,底层创建指定。啊,指定的我们叫capacity。这个长度的这个数组,好,那为什么要说它呢?那就是说呢,如果咱们在开发当中啊,大体你能够确定举个例子啊,比如说哎,把咱们班哎每个同学的一个姓名呢,咱们添加到release当中,咱们也知道呢,咱班有多少人了。那这时候的话呢,是不是就不建议你使用这个空餐的构造器了。因为它里边的虫下是不是得扩容了。那建议呢,你就使用这个假设呢,我们这儿啊,80个人直接我这块就写成80不就行了吗。这样的话,那就省去扩容了,那你效率不就更高一些吗。来看一下啊,比如我们CTRLN一下哎,A。啊,是吧。这个得往上移一下啊,陈主任重来啊。找一下我们的源码a release点进来,然后呢,CTRL f12这个a release,哎,这不就有一个这样的吗。
23:02
哎,然后这块你看,只要你大于零,我就直接呢,初始化长度为你这个capacity的这样的一个。受阻了。啊,所以这个呢,呃是我们可以呢优先考虑的啊,也就是说呢,诶如果诶开发中啊,大体确认啊,这个数组的这个长度啊,则推荐呢使用。啊,咱们这个构造器。呃,构造期啊,这样呢,我们就避免了底层的这个,呃扩容是吧,呃,一方面你扩容,还有一方面你复制数组的操作。哎,这样的话呢,我们说呢,效率会更高一些嘛,OK啊好,这个的话呢,就是我们针对这个例子呢,相关的这个源码的剖析啊,说的呢就比较清晰了。
我来说两句