STL常用序列容器学习笔记


本文简要介绍了STL通用容器的实现原理和要点。

vector

是一个常见的stl容器。它的用法与数组不同。它的内部实现是连续的空间分配。

Vector

和数组的区别在于它可以灵活地增加空间,但它是静态空间,在分配后不能动态扩展。的实现相对简单。主要的关键点是,当空间不足时,它会分配两倍的当前空间,将旧空间数据复制到新空间,然后删除旧空间。

这是一个向尾部添加元素的代码实现。可以看出,如果还有空间,它将被直接添加到尾部。如果没有剩余空间,它将被动态扩展。

可以在使用时使用,因为它已被重载。

使用迭代器时要注意它的失效问题。这个问题存在于许多STL容器中。

list

linked list与不同,元素在内存中不连续分布,不支持随机访问。优点是插入和删除时间的复杂性。在STL中,它实现了一个双链表,它的节点定义可以看到前一个和后一个指针,实现起来也相对简单。

deque

deque,具体实现与and不同,它是一小段连续的空间,每一段连续的空间通过指针数组串联起来(这个数组存储每个连续空间数组的头指针),这样所有的元素都可以被访问。采用这种存储布局是有原因的,并且有其应用场景。在分析了源代码之后,我们将理解为什么它应该这样做。

deque源代码分析

让我们看看一些源代码,看看它的实现细节。德克的迭代器实现代码如下(相比之下,对元素的访问需要在连续分配空间的每个段的边缘进行特殊处理,因为它的存储布局不同):

从上述迭代器的实现来看,需要注意的要点是连续分配空间的每个段的边缘。在查看迭代器之后,让我们看看类的实现代码。这里,大部分代码被删除,部分代码被保留。其中,重点实现了最常用的。时间复杂性更容易理解,过程也相似,但为什么是一样的呢?如果在标题中插入了一个元素,如果从开头开始还有空间,则直接插入第一个连续的空间。如果没有剩余空间,将创建一个新的连续空间,并将第一个地址放在中间。如果没有空间放置第一个地址,则调整并插入第一个地址。关于详细的过程,请参见源代码的具体实现:

实现比和复杂得多,主要是因为它的空间布局不同。下面的代码主要是用来实现一些与德奎团队头尾操作(,)中的空间变化相关的代码:

下面的原始代码被调整。如果没有合适的空间来插入新的连续的空间头地址,它将被重新分配(例如,在这种情况下,团队的后面被完全插入,但是前面仍然很大程度上是空的,所以团队中的当前元素需要被移动,以便元素被分布在中间位置,并且末端和末端是自由的,以便于在后面插入新的元素;如果没有足够的空间,则需要新的分配空间,并且新空间的大小大于新指针元素2)的数量。

让我们更详细地看看STL的源代码。顺便说一下,吐出STL的源代码。代码太臃肿,看起来太累了。如果你根据STL的实现原理自己实现一个小型的STL版本,它应该更简洁。

可以实现随机访问和动态扩展,但是在头部插入是昂贵的,并且在动态扩展期间需要复制所有元素,这也是低效的。插入和删除头尾元素的效率很高,但不能随机访问,搜索效率很高。每个节点都需要存储前节点和后节点指针,这有很大的额外存储开销。然而,它相当于两个容器的优缺点之间的某种平衡。在末尾插入和删除元素的效率非常高,而在中间插入几乎是一样的。但是,它可以实现随机访问。在动态扩展中,它不需要复制所有的元素,只需要重新分配足够的连续存储空间,最多复制到新的存储空间。相反,它是每个连续存储空间的第一个地址指针数组。容量比所有元件的容量小得多,并且动态扩展期间的成本非常小。因此,它具有更高的性能和更小的额外存储空间(但是它具有更大的最小存储器开销,因为它需要连续的存储空间开销,即当元素数量非常小时开销比更大,而当元素数量很大时开销比更小)。

stack

stack也是一种常用的数据结构。它的实现相对简单,并且依赖于它的内部实现。当然,它也可以被使用和实现。

queue

队列有一个通用的先进先出队列和一个优先级队列。优先级队列不仅要有序,还要强调高优先级的先出队列。

normal queue

normal queue的实现类似于堆栈实现,也是基于实现的。

priority _ queue implementation

priority队列的实现原理是基于堆实现的,堆的底层是一个数组。因此,底层的序列容器是选择,而不是其他容器,因为优先级队列是基于堆的。在堆的各种操作中,尾部的插入、删除、插入和删除实际上是尾部元素,在末尾被物理删除,并且其扩展是2倍,这与二叉树的下一层的节点数量是先前扩展的1倍和2倍的事实相一致。当然,也可以使用其他容器(例如,但不是最佳的)。至于堆实现优先级队列的原理,这里就不再赘述了。源代码的实现如下:

您可以看到,一旦您理解了堆的实现原理,优先级队列的实现原理就很容易理解了,这里不再继续分析与堆相关的STL源代码。