MutableList和ListBuffer之间的区别

Question

Scala MutableList和ListBuffer类之间有什么区别scala.collection.mutable？你什么时候使用一个与另一个？

我的用例是一个线性序列,我可以有效地删除第一个元素,prepend和append.什么是最好的结构？

Answer 1

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

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

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

鉴于你的要求,我会说ListBuffer并且MutableList是等同的.如果你想在某个时候导出他们的内部列表,那么问问自己你想要的开销:当你导出列表时,如果你继续改变缓冲区(然后去MutableList),或者只有你可以修改缓冲区时没有开销再次,在出口时没有(然后去ListBuffer).

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

所以我也建议ListBuffer,因为它也可能引起别人的注意和优化在未来不仅仅是"纯粹可变的"结构MutableList和LinkedList.

Answer 2

这为您提供了性能特征的概述:http://www.scala-lang.org/docu/files/collections-api/collections.html ; 有趣的是,MutableList并ListBuffer没有区别.该文件MutableList说,这是在内部使用的基类Stack和Queue,所以也许ListBuffer是更多地从用户的角度官僚阶级？

Answer 3

你想要一个可以增长 和收缩的列表(为什么是一个列表？),并且你想要不断的追加和前置.好吧,Buffer一个特征,有不断追加和前置,大多数其他操作是线性的.我猜测ListBuffer,一个实现的类Buffer,可以不断地删除第一个元素.

所以,我自己的建议是ListBuffer.