这让我想知道在C++中是否也是如此(因为有一个向量类,在插入新元素时会自动调整大小)。
由于它们的内存使用模式非常不同,因此很难进行比较。
向量缩放
向量会根据需要动态地调整自己的大小。它通过分配一个新的内存块,将数据从旧块移动(或复制)到新块中,然后释放旧块来实现。在典型情况下,新块的大小是旧块的1.5倍(与普遍信仰相反,在实践中2倍似乎相当少见)。这意味着在重新分配期间的短时间内,它需要的内存大约等于实际存储的数据量的2.5倍。其余的时间,“块”中使用的部分至少填满了2/3,最多完全填满。如果所有大小可能性相等,那么我们可以预计平均填满大约为5/6。从另一个方向看,我们可以预计在任何给定时间大约有1/6或约17%的空间被“浪费”。
当我们像这样通过一个常数因子来调整大小时(而不是例如始终添加特定大小的块,如以4Kb增量增长),我们得到所谓的摊销常数时间添加。换句话说,随着数组的增长,重新调整大小发生的次数指数级地减少。数组中项目被复制的平均次数趋于常量(通常约为3,但取决于使用的增长因子)。
链表分配
使用链表时情况就有些不同了。我们从未见过调整大小,因此我们不会在某些插入时看到额外的时间或内存使用。同时,我们确实始终看到额外的时间和内存使用。特别是,链表中的每个节点都需要包含指向下一个节点的指针。根据节点中数据的大小与指针的大小比较,这会导致显着的开销。例如,假设您需要一个int
类型的栈。在典型情况下,int
与指针的大小相同,这意味着会出现50%的开销-始终如此。指针比int
更大变得越来越常见;两倍的大小非常普遍(64位指针,32位int)。在这种情况下,您会面临约67%的开销-明显地,每个节点将指针占用的空间是要存储的数据的两倍。
不幸的是,这通常只是冰山一角。在典型的链表中,每个节点都是单独动态分配的。至少如果您正在存储小的数据项(例如int
),则为节点分配的内存可能会比您实际请求的数量大(通常会这样)。因此,您请求12字节的内存来容纳一个int和一个指针,但您获得的内存块可能会被舍入到16或32字节。现在你看到至少有75%的额外开销,很可能是约88%。
当你有相对较少、每个节点都很大的情况下,链表可以发挥良好作用。 如果(对于栈而言更加典型),你处理的是相对较多、每个项都很小的情况,那么你很可能不会在时间或内存使用方面看到节省。 相反,对于这种情况,链表更有可能浪费大量的时间和内存。
是的,你说的对,这对于C++是正确的。因此,在C++中使用的标准栈类std::stack
内的默认容器既不是向量也不是链表,而是双端队列(deque
)。这几乎具有向量的所有优点,但它的重新调整大小能力更好。
基本上,std::deque
在内部是一种“数组的链接列表”。这样,当它需要重新调整大小时,它只需添加另一个数组。
std::stack
实际上不是一个容器,而是一个使用内部容器实现的容器适配器。默认情况下,它使用 std::deque
,但您可以使用任何容器。std::vector
是一个真正的容器。您可以拥有一个使用 std::vector
作为内部容器的 std::stack
,但接口将会不同。 - Gorpik是的,对于C++
或任何其他语言都是正确的。动态数组是一个概念。C++有vector
并不改变这个理论事实。在C++
中的向量实际上会在内部进行调整大小,因此这项任务不是开发人员的责任。当使用vector
时,实际成本并没有神奇地消失,而只是转移到了标准库实现。
std::vector
是使用动态数组实现的,而 std::list
则是使用链表实现的。使用这两种数据结构都有权衡之处。选择最适合您需求的那一个。
正如您所指出的,如果动态数组已满,则添加项目需要更长的时间,因为它必须扩展自身。但是,由于所有成员都在内存中紧密分组,因此访问速度更快。这种紧密分组通常也使其更易于缓存。
链表永远不需要调整大小,但遍历它们需要更长的时间,因为 CPU 必须在内存中跳转。
这让我想知道在C++中是否也是这样,因为有一个向量类可以在插入新元素时自动调整大小。
是的,它仍然适用,因为vector
的重新分配是一种潜在的昂贵操作。 在内部,如果向量的预分配大小达到并且您尝试添加新元素,则会发生新的分配,并且旧数据将移动到新的内存位置。
来自C++文档:
vector::push_back - 在末尾添加元素
在向量的末尾添加一个新元素,该元素位于当前最后一个元素之后。将val的内容复制(或移动)到新元素中。
这实际上通过一增加容器大小,如果新向量大小超过当前向量容量,则会自动重新分配已分配的存储空间。
http://channel9.msdn.com/Events/GoingNative/GoingNative-2012/Keynote-Bjarne-Stroustrup-Cpp11-Style
跳到44:40。正如Bjarne在视频中所解释的那样,尽可能使用std::vector
而不是std::list
。由于std::vector
将所有元素都存储在内存中的相邻位置,因此具有缓存在内存中的优势。这对于添加、删除和搜索std::vector
中的元素都是适用的。他指出,std::list
比std::vector
慢50-100倍。
如果您真的需要一个堆栈,应该使用std::stack
而不是自己编写。
std::stack
被实现为一个适配器,因此您可以将容器传递给它,并使其作为堆栈工作。默认情况下,使用std::deque
。http://www.cplusplus.com/reference/stack/stack/ - Svalorzen