MutableList 和 ListBuffer 的区别 [英] Difference between MutableList and ListBuffer

问题描述

Scala 的 MutableList 和 scala.collection.mutable 中的 ListBuffer 类有什么区别?你会在什么时候使用一个和另一个?

What is the difference between Scala's MutableList and ListBuffer classes in scala.collection.mutable? When would you use one vs the other?

我的用例是有一个线性序列，我可以有效地删除第一个元素、前置和附加.什么是最好的结构?

My use case is having a linear sequence where I can efficiently remove the first element, prepend, and append. What's the best structure for this?

推荐答案

关于它们如何工作的一点解释.

A little explanation on how they work.

ListBuffer 在内部使用 Nil 和 :: 来构建不可变的 List 并允许恒定时间删除第一个 和最后一个 元素.为此，它在列表的第一个和最后一个元素上保留一个指针，并且实际上允许更改(否则不可变的):: 类的头部和尾部(private[scala] var :: 的成员).它的 toList 方法也可以在恒定时间内返回正常的不可变 List ，因为它可以直接返回内部维护的结构.它也是不可变 List 的默认构建器(因此确实可以合理地期望具有恒定时间附加).如果您调用 toList 然后再次将元素追加到缓冲区，则相对于缓冲区中的当前元素数量，重新创建新结构需要线性时间，因为它不能改变导出的列表没有了.

ListBuffer uses internally Nil and :: to build an immutable List and allows constant-time removal of the first and last elements. To do so, it keeps a pointer on the first and last element of the list, and is actually allowed to change the head and tail of the (otherwise immutable) :: class (nice trick allowed by the private[scala] var members of ::). Its toList method returns the normal immutable List in constant time as well, as it can directly return the structure maintained internally. It is also the default builder for immutable Lists (and thus can indeed be reasonably expected to have constant-time append). If you call toList and then again append an element to the buffer, it takes linear time with respect to the current number of elements in the buffer to recreate a new structure, as it must not mutate the exported list any more.

MutableList 在内部与 LinkedList 一起工作，而是一个(公开的，不像 ::)可变链表实现，它知道它的元素和后继(如 ::).MutableList 还保留指向第一个和最后一个元素的指针，但 toList 以线性时间返回，因为结果 List 是从 构造的链表.因此，在导出 List 后不需要重新初始化缓冲区.

MutableList works internally with LinkedList instead, an (openly, not like ::) mutable linked list implementation which knows of its element and successor (like ::). MutableList also keeps pointers to the first and last element, but toList returns in linear time, as the resulting List is constructed from the LinkedList. Thus, it doesn't need to reinitialize the buffer after a List has been exported.

根据您的要求，我认为 ListBuffer 和 MutableList 是等效的.如果你想在某个时候导出他们的内部列表，那么问问自己你想要的开销:当你导出列表时，如果你继续改变缓冲区则没有开销(然后去MutableList)，或者仅当您再次更改缓冲区，并且在导出时不更改(然后使用 ListBuffer).

Given your requirements, I'd say ListBuffer and MutableList are equivalent. If you want to export their internal list at some point, then ask yourself where you want the overhead: when you export the list, and then no overhead if you go on mutating buffer (then go for MutableList), or only if you mutable the buffer again, and none at export time (then go for ListBuffer).

我的猜测是，在 2.8 集合大修中，MutableList 早于 ListBuffer 和整个 Builder 系统.实际上，MutableList 在 collection.mutable 包中主要有用:它有一个 private[mutable] def toLinkedList 方法，该方法在恒定时间内返回，因此可以有效地用作所有在内部维护 LinkedList 的结构的委托构建器.

My guess is that in the 2.8 collection overhaul, MutableList predated ListBuffer and the whole Builder system. Actually, MutableList is predominantly useful from within the collection.mutable package: it has a private[mutable] def toLinkedList method which returns in constant time, and can thus efficiently be used as a delegated builder for all structures that maintain a LinkedList internally.

所以我也推荐 ListBuffer，因为它在未来也可能会比 MutableList 和 LinkedList<这样的纯可变"结构更受关注和优化/代码>.

So I'd also recommend ListBuffer, as it may also get attention and optimization in the future than "purely mutable" structures like MutableList and LinkedList.

这篇关于MutableList 和 ListBuffer 的区别的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！