12. 集合：常见序列类

在本章中，我们会研究一下最常见的序列类。正如11.1小节“选择集合类”中所提到的，序列类的使用建议如下：

Vector是首选的不可变索引序列（immutable indexed sequence）。
List是首选的不可变线性序列（immutable linear sequence）。
ArrayBuffer是首选的可变索引序列（mutable indexed sequence）。
ListBuffer是首选的可变线性序列（mutable linear sequence）。

Vector

正如11.1小节“选择集合类”中我们就讨论过，Vector是首选的不可变索引序列类，因为它具有通用的性能特征。需要不可变序列时使用它。

因为Vector是不可变的，所以可以通过过滤和转换方法创建另一个Vector。快速浏览下面创建和使用Vector的例子：

    val a = Vector(1, 2, 3, 4, 5)
    val b = a.filter(_ > 2)  // Vector(3, 4, 5)
    val c = a.map(_ * 10)    // Vector(10, 20, 30, 40, 50)

List

如果你从Java来到Scala，很快会发现尽管名字相同，但Scala List与 Java List （例如 Java ArrayList）完全不同。Scala List类是不可变的，大小和包含的元素都不能改变。它基于链表实现，首选的方法是prepend元素。由于是链表，所以遍历需要从头到尾，实际上，通常认为它由head、tail 方法（以及isEmpty）组成。

与Vector类似，由于List是不可变的，所以可以通过过滤和转换方法创建另一个List，快速浏览下面创建和使用List的例子：

    val a = List(1, 2, 3, 4, 5)
    val b = a.filter(_ > 2)     // List(3, 4, 5)
    val c = a.map(_ * 10)       // List(10, 20, 30, 40, 50)

List和Vector TODO（鸽子栏）

你可能想知道何时使用List而不是Vector。11.2小节“理解集合的性能”中详细介绍了性能特征，提供了选择的通用规则。

在一个有趣的实验中，Scala语言的创建者Martin Odersky，在Scala贡献者网站上的这个帖子（ https://oreil.ly/hrnGT ）中指出，Tiark Rompf曾经试图用Vector替换Scala编译器中的所有List，结果性能下降了10%。

所以认为Vector有一定的开销，导致在处理小序列时效率较低。因此 List 有其用处，尤其是当你把它想象成它是一个简单的单链表时。（在Martin Odersky 先生的评论中，Java Champion， Scala Future的创造者Viktor Klang—认为List是一个优秀的栈。）

ArrayBuffer

ArrayBuffer 是集合库中首选的可变索引序列类。因为它是可变的，可以通过转换方法来修改内容。例如，将map方法与Vector或List一起使用，并将结果赋给一个新变量：

    val x = Vector(1, 2, 3)
    val y = x.map(_ * 2) // y: ArrayBuffer(2, 4, 6)

对于ArrayBuffer，使用mapInPlace而不是map方法，会原地修改值：

    import collection.mutable.ArrayBuffer
    val ab = ArrayBuffer(1, 2, 3)
    ab.mapInPlace(_ * 2) // ab: ArrayBuffer(2, 4, 6)

Buffers TODO（耗子栏）

在Scala中，Buffer只是一个可以增长和收缩的序列。

Array

Scala Array很独特：其元素可变，其大小不可变—不能增减。相比之下，List和Vector是完全不可变的，而ArrayBuffer是完全可变的。

Array 的独特之处在于它是基于Java数组的，所以Scala Array[Int] 是基于Java Int[] 的。

虽然Array经常出现在Scala的范例中，但实际开发中建议把Vector类作为首选的不可变索引序列类，ArrayBuffer作为首选的可变索引序列。基于这个建议，我的实际代码中使用Vector和ArrayBuffer，在需要时转换为Array。

对于某些特定的操作，Array相比其他集合有更好的性能，所以了解它的工作原理是很重要的。详细内容参考11.2小节，“理解集合的性能”。

12.1 Vector作为首选的不可变序列

问题

你想为Scala应用程序选择一个快速的、通用的、不可变的序列集合类型。

解决方案

Vector类是首选的通用不可变索引序列。如果更需要不可变线性序列，可以使用List。

创建Vectors

和其它不可变序列一样创建和使用 Vector。可以通过初始元素创建一个 Vector，然后通过索引访问元素：

    val v = Vector("a", "b", "c")
    v(0) // "a"
    v(1) // "b"

因为Vector有索引，所以调用 x(9_999_999) 几乎立即返回：

    val x = (1 to 10_000_000).toVector
    x(9_999_999) // 10000000

还可以创建一个空的Vector，并向其添加元素，记住要将结果赋给一个新变量：

    val a = Vector[String]()         // a: Vector[String] = Vector()
    val b = a ++ List("a", "b")      // b: Vector(a, b)

Add, Append和Prepend元素

由于不能修改Vector，所以将结果指定给新变量时，可以向现有Vector添加元素：

    val a = Vector(1, 2, 3)
    val b = a ++ List(4, 5)     // b: Vector(1, 2, 3, 4, 5)
    val c = b ++ Seq(6)         // c: Vector(1, 2, 3, 4, 5, 6)

和其他不可变序列一样，通过下面方法给Vector中append和prepend元素：

+: 方法，别名prepended。
++: 方法，别名prependedAll。
:+ 方法，别名appended。
:++ 方法，别名appendedAll。

下面是例子，将每个操作的结果赋值var变量：

    // prepending
    var a = Vector(6)

    a = 5 +: a                      // a: Vector(5, 6)
    a = a.prepended(4)              // a: Vector(4, 5, 6)

    a = List(2,3) ++: a             // a: Vector(2, 3, 4, 5, 6)
    a = a.prependedAll(Seq(0,1))    // a: Vector(0, 1, 2, 3, 4, 5, 6)

    // appending
    var b = Vector(1)

    b = b :+ 2                      // b: Vector(1, 2)
    b = b.appended(3)               // b: Vector(1, 2, 3)

    b = b :++ List(4,5)             // b: Vector(1, 2, 3, 4, 5)
    b = b.appendedAll(List(6,7))    // b: Vector(1, 2, 3, 4, 5, 6, 7)

修改元素

如果需要修改Vector中的元素，可在调用update方法时设置index和elem参数来替换元素，同时将结果赋给一个新变量：

    val a = Vector(1, 2, 3)
    val b = a.updated(index=0, elem=10) // b: Vector(10, 2, 3)
    val c = b.updated(1, 20)            // c: Vector(10, 20, 3)

同样，使用 patch 方法一次替换多个元素：

    val a = Vector(1, 2, 3, 4, 5, 6)

    // specify (a) the index to start at, (b) the new sequence
    // you want, and (c) the number of elements to replace
    val b = a.patch(0, List(10,20), 2) // b: Vector(10, 20, 3, 4, 5, 6)
    val b = a.patch(0, List(10,20), 3) // b: Vector(10, 20, 4, 5, 6)
    val b = a.patch(0, List(10,20), 4) // b: Vector(10, 20, 5, 6)

    val b = a.patch(2, List(30,40), 2) // b: Vector(1, 2, 30, 40, 5, 6)
    val b = a.patch(2, List(30,40), 3) // b: Vector(1, 2, 30, 40, 6)
    val b = a.patch(2, List(30,40), 4) // b: Vector(1, 2, 30, 40)

使用patch，插入元素可以通过设置替换的元素数量为0：

    val a = Vector(10, 20, 30)
    val b = a.patch(1, List(15), 0) // b: Vector(10, 15, 20, 30)
    val b = a.patch(2, List(25), 0) // b: Vector(10, 20, 25, 30)

讨论

Scala 文档（ https://oreil.ly/idUJt ）中关于不可变集合类的声明如下：

Vector是种集合类型，可解决使用List时，随机访问操作低效的问题。 Vector可以在“有效”常数时间内访问列表中的任何元素,因为Vector在快速随机选择和快速随机函数更新之间取得了很好的平衡，是不可变索引序列的默认实现。

在“理解集合的层次”中所述，创建 IndexedSeq 的实例时，Scala 会返回Vector：

    scala> val x = IndexedSeq(1,2,3)
    x: IndexedSeq[Int] = Vector(1, 2, 3)

因此，我看到一些开发人员在创建索引不可变序列时，使用IndexedSeq而不是Vector，并将实现细节留给编译器。

12.2 创建和填充List

问题

你想要创建一个 List 并填充它。

解决方案

创建和初始填充 List方法有很多，下面有六个例子，从两个基本的例子开始：

    // (1) basic, general use cases
    val xs = List(1, 2, 3)          // List(1, 2, 3)
    val xs = 1 :: 2 :: 3 :: Nil     // List(1, 2, 3)
    val xs = 1 :: List(2, 3)

    // (2) both of these create an empty list
    val xs: List[String] = List()
    val xs: List[String] = Nil

接下来，这些例子展示了如何让编译器隐式设置List类型，然后显式控制类型：

    // (3a) implicit and explicit types, with mixed values
    val xs = List(1, 2.0, 33D, 4_000L)                  // implicit type (List[AnyVal])
    val xs: List[Double] = List(1, 2.0, 33D, 4_000L)    // explicit type

    // (3b) another example of explicitly setting the list type,
    // where the second example declares the type to be List[Long]
    val xs = List(1, 2, 3)                              // List[Int] = List(1, 2, 3)
    val xs: List[Long] = List(1, 2, 3)                  // List[Long] = List(1, 2, 3)

下面例子展示了基于范围创建List的多种方法，包括Int和Char类型上的to和by方法（多亏了类型的隐式转换）：

    // (4) using ranges
    val xs = List.range(1, 10)      // List(1, 2, 3, 4, 5, 6, 7, 8, 9)
    val xs = List.range(0, 10, 2)   // List(0, 2, 4, 6, 8)

    (1 to 5).toList                 // List(1, 2, 3, 4, 5)
    (1 until 5).toList              // List(1, 2, 3, 4)
    (1 to 10 by 2).toList           // List(1, 3, 5, 7, 9)
    (1 to 10 by 3).toList           // List(1, 4, 7, 10)

    ('a' to 'e').toList             // List(a, b, c, d, e)
    ('a' to 'e' by 2).toList        // List(a, c, e)

下面例子展示了填充List的多种方法：

    // (5) different ways to fill lists
    val xs = List.fill(3)("foo")          // xs: List(foo, foo, foo)
    val xs = List.tabulate(5)(n => n * n) // xs: List(0, 1, 4, 9, 16)
    val xs = "hello".toList               // xs: List[Char] = List(h,e,l,l,o)

    // create a list of alphanumeric characters
    val alphaNum = (('a' to 'z') ++ ('A' to 'Z') ++ ('0' to '9')).toList
    // result contains 52 letters and 10 numbers

    // create a list of 10 printable characters
    val r = scala.util.Random
    val printableChars = (for i <- 0 to 10 yield r.nextPrintableChar).toList
    // result is like: List(=, *, W, ?, W, 1, L, <, F, d, O)

最后，如果使用List时数据经常变化，在数据变化的时候用ListBuffer，然后在数据停止变化时再转换成List：

    // (6) use a ListBuffer while data is frequently changing
    import collection.mutable.ListBuffer
    val a = ListBuffer(1)       // a: ListBuffer(1)
    a += 2                      // a: ListBuffer(1, 2)
    a += 3                      // a: ListBuffer(1, 2, 3)

    // convert it to a List when the changes stop
    val b = a.toList            // b: List(1, 2, 3)

ListBuffer（ https://oreil.ly/Cm5gT ）是基于链表实现的Buffer。提供常数时间的prepend和append操作，且大多数操作是线性的。

讨论

需要特别关注的是，Scala的 List与Java的 List（如Java ArrayList）是完全不同的两个类型。在22.1小节“在Scala中使用Java Collections”，展示了java.util.List转换为Scala Buffer或Seq，而不是Scala List。

Scala的 List 只是一个以 Nil 元素结尾的顺序集合：

    // empty list
    val xs: List[String] = Nil  // List[String] = List()

    // three elements that end with a Nil element
    val xs = 1 :: 2 :: 3 :: Nil // List(1, 2, 3)

    // this is an error, because it does not end with a Nil
    val xs = 1 :: 2 :: 3        // error

    // prepending a `1` to a `List(2, 3)`
    val xs = 1 :: List(2, 3)    // List(1, 2, 3)

如上所示， :: 方法（称为cons）接受两个参数：

head元素，是单一的元素。
tail元素，既可以是List也可以是Nil值

:: 方法和Nil值起源于Lisp编程语言，在Lisp语言中，这样的列表被大量使用。关于List的一个重要的事情是，添加元素时总是prepend元素在最前面，如下所示：

    val a = List(3) // List(3)
    val b = 2 :: a  // List(2, 3)
    val c = 1 :: b  // List(1, 2, 3)

下面这段引用来自List类的Scaladoc（ https://oreil.ly/IBtdo ），讨论了List类的重要属性：

这个类最适用于类似栈的后进先出(LIFO)访问模式。如果需要随机访问或FIFO等访问模式，考虑比List更适合的集合。List的prepend和head/tail时间复杂度O(1)。其它大多数操作都是O(n)。

另见

4.14小节“在匹配表达式中使用列表”，展示了在匹配表达式中处理List，尤其是Nil元素。
11.2小节“理解集合的性能”，有更多关于List性能特质的内容。
向列表中添加元素在12.3小节有更多的讨论。

12.3 List中添加元素

问题

你想给正在使用的List添加元素。

解决方案

“如何给List添加元素？”是一个比较麻烦的问题，因为List是不可变的，不能添加新元素。如果List经常变化，考虑使用ListBuffer（如12.5小节所述），然后在需要时候转换成List。

上述建议适用于不断修改List中数据的场景。但如果只想向List中添加一些元素，而不是不断更新它 — 因为在List中prepending元素很快，所以首选的方式是通过 :: 方法prepend元素，同时将结果赋值给新的List：

    val a = List(2)  // a: List(2)

    // prepend with ::
    val b = 1 :: a   // b: List(1, 2)
    val c = 0 :: b   // c: List(0, 1, 2)

还可以使用 ::: 方法在一个列表前面添加另一个列表：

    val a = List(3, 4)       // a: List(3, 4)
    val b = List(1, 2) ::: a // b: List(1, 2, 3, 4)

可以把变量声明为var，并将结果重新赋值回该变量，而不是不断地把prepend操作结果赋值给一个新变量：

    var x = List(5)       // x: List[Int] = List(5)
    x = 4 :: x            // x: List(4, 5)
    x = 3 :: x            // x: List(3, 4, 5)
    x = List(1, 2) ::: x  // x: List(1, 2, 3, 4, 5)

正如这些例子所说明的，:: 和 ::: 方法是右关联的。这意味着列表是从右到左构建的，可以在下面例子中更清楚地看到这一点：

    val a = 3 :: Nil        // a: List(3)
    val b = 2 :: a          // b: List(2, 3)
    val c = 1 :: b          // c: List(1, 2, 3)
    val d = 1 :: 2 :: Nil   // d: List(1, 2)

要弄清楚 :: 和 ::: 的工作原理，了解 Scala 编译器很有帮助，Scala编译器将第一个例子的代码转换为第二个例子的代码：

    List(1, 2) ::: List(3, 4)     // what you type
    List(3, 4).:::(List(1, 2))  // how the compiler interprets that code

结果都是List(1,2,3,4)。

讨论

这种创建List的方式源于 Lisp 编程语言：

    val x = 1 :: 2 :: 3 :: Nil // x: List(1, 2, 3)

令人惊讶的是，Lisp在1958年首次被指定，这种方式创建链表非常直接，至今仍在使用这种风格。

其他方法如prepend、append

虽然 :: 和 ::: 是List的常用方法，但还有其他方法可以将一个元素添加到List中：

    val x = List(1)

    // prepend
    val y = 0 +: x // y: List(0, 1)

    // append
    val y = x :+ 2 // y: List(1, 2)

需要记住，List的append是一个相对较慢的操作，不建议使用这种方法，特别是大型列表。正如List类Scaladoc（ https://oreil.ly/IBtdo ）所声明：“这个类最适用于类似栈的后进先出(LIFO)使用场景，如果需要随机访问或FIFO等类似的操作，请考虑选择比List更适合的集合。List的prepend和head/tail时间复杂度为O(1)。而其相关的大多数操作都是O(n)”。有关List性能的讨论，参考11.2小节：“理解集合的性能”。

如果较少使用List类，可以通过 ++ 或concat方法把两个列表连接成一个新列表：

    val a = List(1, 2, 3)
    val b = List(4, 5, 6)

    // '++' is an alias for 'concat', so they work the same
    val c = a ++ b       // c: List(1, 2, 3, 4, 5, 6)
    val c = a.concat(b)  // c: List(1, 2, 3, 4, 5, 6)

这些方法在不可变集合中使用一致，所以很容易记住。

方法结尾 TODO（鸽子栏）

任何以 : 字符结尾的 Scala 方法都是从右向左执行的。这意味着方法由右操作符调用。分析下面代码可以看出这点，两种方法都会打印42：

    @main def rightAssociativeExample =
        val p = Printer()
        p >> 42  // prints "42"
        42 >>: p // prints "42"

    class Printer:
        def >>(i: Int) = println(s"$i")
        def >>:(i: Int) = println(s"$i")

除了使用例子中的方法，也可以像下面一样调用这两个方法：

    p.>>(42)
    p.>>:(42)

但是定义第二个方法时以冒号结束，所以可以被用做右关联的操作符。

另见

连接两个列表可以创建一个新列表。参考13.12小节的“合并顺序集合”中的例子。
如果想使用可变的线性列表。参考12.5小节如何使用 ListBuffer 类的例子。

12.4 List（或ListBuffer）中删除元素

问题

你想从List或ListBuffer中删除元素。

解决方案

使用 filter、take 和 drop 等方法过滤 List 中的元素，使用 -=、--= 和 remove 等方法删除 ListBuffer 中的元素。

List

列表是不可改变的，所以不能从中删除元素，但可以过滤掉不需要的元素，同时将结果赋值给一个新的变量：

    val a = List(5, 1, 4, 3, 2)
    val b = a.filter(_ > 2)     // b: List(5, 4, 3)
    val b = a.take(2)           // b: List(5, 1)
    val b = a.drop(2)           // b: List(4, 3, 2)
    val b = a diff List(1)      // b: List(5, 4, 3, 2)

可以把变量声明为var，并将操作的结果重新赋值给它，而不是不断地将操作结果分配给一个新的变量：

    var x = List(5, 1, 4, 3, 2)
    x = x.filter(_ > 2) // x: List(5, 4, 3)

见13.7小节“使用过滤器过滤集合”，获得一个集合的子集其他方法有：filter、partition、splitAt和take。

ListBuffer

如果需要经常修改一个列表，最好使用ListBuffer而不是List。ListBuffer是可变的，所以和其他可变集合一样，使用 -= 和 --= 方法来删除元素。例如像这样创建一个ListBuffer：

    import scala.collection.mutable.ListBuffer
    val x = ListBuffer(1, 2, 3, 4, 1, 2, 3, 4)
        // result: x: scala.collection.mutable.ListBuffer[Int] =
        // ListBuffer(1, 2, 3, 4, 1, 2, 3, 4)

你可以通过使用 -= 一次删除一个元素：

    x -= 2 // x: ListBuffer(1, 3, 4, 1, 2, 3, 4)

注意，只有第一次出现的数字2从x中被删除。

你可以使用 --= 按值删除两个或多个元素：

    val x = ListBuffer(1, 2, 3, 4, 5, 6)

    // 1, 2, and 3 are removed:
    x --= Seq(1,2,3) // x: ListBuffer(4, 5, 6)

    // nothing matched, so nothing removed:
    x --= Seq(8, 9)  // x: ListBuffer(4, 5, 6)

可以使用remove来按索引位置删除元素。要么提供索引，要么提供起始索引和要删除元素的数量：

    val x = ListBuffer(1, 2, 3, 4, 5, 6)

    // remove the 0th element
    val a = x.remove(0)     // a=1, x=ListBuffer(2, 3, 4, 5, 6)

    // remove three elements, starting from index 1. this `remove`
    // method does not return a value.
    x.remove(1, 3)          // x: ListBuffer(2, 6)

    // be aware that `remove` can throw an exception
    x.remove(100)           // java.lang.IndexOutOfBoundsException

讨论

当你刚开始使用Scala的时候，大量名字是符号的方法（例如 ++、-- 和 --= 等方法）看起来令人生畏。但是 ++ 和 -- 在immutable集合中的使用是一致的，而 -= 和 --= 在mutable集合中的使用是一致的，所以使用它们很快就会成为习惯。

另见

在处理不可变的集合时，filtering可以是删除的一种形式，参见第13章的过滤器小节。

12.5 用ListBuffer创建可变列表

你想使用一个可变的列表，如LinearSeq，而不是IndexedSeq，因为List是不可变的。

解决方案

要处理一个可变的列表，只要数据在变化，就使用ListBuffer，需要时可将ListBuffer转换成List。

下面的例子演示了如何创建一个ListBuffer，然后根据需要添加和删除元素，最后在完成后将其转换为一个List：

    import scala.collection.mutable.ListBuffer

    // create an empty ListBuffer[String]
    val b = new ListBuffer[String]()

    // add one element at a time to the ListBuffer
    b += "a"                        // b: ListBuffer(a)
    b += "b"                        // b: ListBuffer(a, b)
    b += "c"                        // b: ListBuffer(a, b, c)

    // add multiple elements (++= is an alias for addAll)
    b ++= List("d", "e", "f")       // b: ListBuffer(a, b, c, d, e, f)
    b.addAll(Vector("d", "e", "f")) // b: ListBuffer(a, b, c, d, e, f, d, e, f)

    // remove the first "d"
    b -= "d" // b: ListBuffer(a, b, c, e, f, d, e, f)

    // remove multiple elements specified by another sequence
    b --= Seq("e", "f")             // b: ListBuffer(a, b, c, d)

    // convert the ListBuffer to a List when you need to
    val xs = b.toList               // xs: List(a, b, c, d)

讨论

因为List是不可变的，如果当你你需要创建一个不断变化的列表，在列表被修改时使用ListBuffer可能会更好，然后在需要List时将其转换为List。

ListBuffer Scaladoc（ https://oreil.ly/Cm5gT ）指出：

ListBuffer是“基于列表实现的Buffer。它提供了常数时间的prepend和append。大多数其他操作是线性的"。

因此，如果你想随机访问元素，例如通过索引访问元素（如list(1_000_000)），就不要使用ListBuffer，而是使用ArrayBuffer。详见11.2小节“理解集合的性能”。

小型List

根据你的需要，从一个现有List中创建一个新的List是可以的，特别当它们很小时候，可以在创建List时可就添加元素：

    val a = List(2) // a: List(2)
    val b = 1 :: a  // b: List(1, 2)
    val c = 0 :: b  // c: List(0, 1, 2)

该技术在12.3小节中有更多讨论。

12.6 使用LazyList

问题

你希望像List一样使用集合，但是需要调用它的惰性转换方法（map、filter等）。

解决方案

LazyList和List很像，不同之处在于它的元素是惰性计算的，和视图（view）创建惰性版本的集合类似。因为LazyList的元素是惰性计算的，一个LazyList可以无限长。和视图类似，只有元素被访问时才会计算。除此之外，LazyList的行为和List类似。

例如，就像List可以用 :: 构造一样，LazyList可以用 #:: 方法构造，在表达式的末尾使用LazyList.empty而不是Nil：

    scala> val xs = 1 #:: 2 #:: 3 #:: LazyList.empty
    val xs: LazyList[Int] = LazyList(<not computed>)

REPL输出显示，LazyList还没有被计算。这意味着LazyList已经被创建，但还没有分配元素。作为另一个例子，你可以创建一个带有范围的LazyList：

    scala> val xs = (1 to 100_000_000).to(LazyList)
    val xs: LazyList[Int] = LazyList(<not computed>)

尝试访问LazyList的head和tail。头部的元素会立即返回：

    scala> xs.head
    res0: Int = 1

但是尾部元素还没被执行到：

    scala> xs.tail
    val res1: LazyList[Int] = LazyList(<not computed>)

输出仍然显示 “not computed”。正如11.4小节“在集合上创建惰性视图”中所讨论的，转化器方法是懒惰计算的，所以当转化器被调用时，在 REPL 中看到输出 “ < not computed > ” ：

    scala> xs.take(3)
    val res2: LazyList[Int] = LazyList(<not computed>)

    scala> xs.filter(_ < 200)
    val res3: LazyList[Int] = LazyList(<not computed>)

    scala> xs.filter(_ > 200)
    val res4: LazyList[Int] = LazyList(<not computed>)

    scala> xs.map { _ * 2 }
    val res5: LazyList[Int] = LazyList(<not computed>)

然而，对不是转化器的方法要小心。下面strict方法调用会被立即计算，很容易导致java.lang.OutOfMemoryError错误：

    xs.max
    xs.size
    xs.sum

转换器方法 TODO（鸽子栏）

Transformer methods是一种集合方法，根据你提供转换数据的算法，将一个给定的输入集合转换为一个新的输出集合。这包括map、filter和reverse等方法。当使用这些方法时，你正在将输入集合转换为一个新的输出集合。

像max、size和sum这样的方法不符合这个定义，它们在对LazyList进行操作时，如果LazyList需要的内存超过可分配的内存，会得到一个java.lang.OutOfMemoryError错误。

作为比较，如果我尝试在这些例子中使用List。在创建List时就会遇到一个java.lang.OutOfMemory错误：

    val xs = (1 to 100_000_000).toList
    // result: java.lang.OutOfMemoryError: Java heap space

相反，LazyList给你一个选择来指定很大的列表，并开始处理其元素：

    val xs = (1 to 100_000_000).to(LazyList)
    xs(0) // returns 1
    xs(1) // returns 2

讨论

在Scala 2.13集合的重新设计中，LazyList取代了已经废弃的Stream类。根据官方博客集合被重新设计的文章中（ https://oreil.ly/wYwOw ），这是为了减少集合设计的混乱而做的。根据博客，LazyList的头部和尾部都可以被懒惰访问，而在Stream中只有尾部被懒惰访问。

LazyList Scaladoc（ https://oreil.ly/ZkuQ5 ）还包含几个与性能有关的重要说明，包括这些：

元素是记忆化的，意味着每个元素的值最多被计算一次。
元素按顺序计算，且不会跳过。
LazyList的长度可以是无限的，在这种情况下，count、sum、max和min等方法将不会终止。

更多的细节和例子，参考Scaladoc。

另见

11.4小节“在集合上创建惰性视图”，展示了如何在集合上创建视图，它的工作原理类似于LazyList。

12.7 ArrayBuffer为首选的可变序列

问题

你想要创建一个大小可变的数组，也就是一个完全可变的数组。

解决方案

数组是可变的，因为它的元素可以改变，但大小不能改变。要创建一个大小可变的可变索引序列，可以使用ArrayBuffer类。

要使用ArrayBuffer，将其导入作用域，然后创建实例。可以通过指定ArrayBuffer包含的类型，来声明一个没有初始元素的ArrayBuffer，然后再添加元素：

    import scala.collection.mutable.ArrayBuffer
    val a = ArrayBuffer[String]()

    a += "Ben"       // a: ArrayBuffer(Ben)
    a += "Jerry"     // a: ArrayBuffer(Ben, Jerry)
    a += "Dale"      // a: ArrayBuffer(Ben, Jerry, Dale)

ArrayBuffer拥有你在其他可变序列中找到的所有方法。这些是向ArrayBuffer添加元素的一些常见方法：

    import scala.collection.mutable.ArrayBuffer

    // initialize with elements
    val characters = ArrayBuffer("Ben", "Jerry")

    // add one element
    characters += "Dale"

    // add multiple elements with any IterableOnce type
    characters ++= List("Gordon", "Harry")
    characters ++= Vector("Andy", "Big Ed")

    // another way to add multiple elements
    characters.appendAll(List("Laura", "Lucy"))

    // `characters` now contains these strings:
    ArrayBuffer(Ben, Jerry, Dale, Gordon, Harry, Andy, Big Ed, Laura, Lucy)

如前面的例子所示，添加元素就是appending。下面的例子展示了向ArrayBuffer prepend元素的几种方法：

    val a = ArrayBuffer(10)         // a: ArrayBuffer[Int] = ArrayBuffer(10)
    a.prepend(9)                    // a: ArrayBuffer(9, 10)
    a.prependAll(Seq(7,8))          // a: ArrayBuffer(7, 8, 9, 10)

    // `+=:` is an alias for `prepend`, `++=:` is an alias for `prependAll`
    6 +=: a                         // a: ArrayBuffer(6, 7, 8, 9, 10)
    List(4,5) ++=: a                // a: ArrayBuffer(4, 5, 6, 7, 8, 9, 10)

讨论

这里有几种原地更新ArrayBuffer元素的方法：

    import scala.collection.mutable.ArrayBuffer

    // creates an ArrayBuffer[Char]
    val a = ArrayBuffer.range('a', 'f')     // a: ArrayBuffer(a, b, c, d, e)

    a.update(0, 'A')                        // a: ArrayBuffer(A, b, c, d, e)
    a(2) = 'C'                              // a: ArrayBuffer(A, b, C, d, e)

    a.patchInPlace(0, Seq('X', 'Y'), 2)     // a: ArrayBuffer(X, Y, C, d, e)
    a.patchInPlace(0, Seq('X', 'Y'), 3)     // a: ArrayBuffer(X, Y, d, e)
    a.patchInPlace(0, Seq('X', 'Y'), 4)     // a: ArrayBuffer(X, Y)

使用patchInPlace时：

第一个Int参数是你希望开始替换元素的索引。
第二个Int参数是你要替换元素的数量。

第一个例子展示了如何用两个新元素替换两个旧元素。最后一个例子显示了如何用两个新元素替换四个旧元素。

关于ArrayBuffer和ListBuffer的说明

ArrayBuffer Scaladoc（ https://oreil.ly/dtWfX ）提供了关于ArrayBuffer性能的细节：“追加、更新和随机访问需要常数时间（摊销的时间）。前置添加和删除在缓冲区大小上是线性的。”

如果你需要一个更像List（即线性序列而不是索引序列）的可变顺序集合，请使用ListBuffer而不是ArrayBuffer。Scala关于ListBuffer的文档指出：“Buffer基于List实现。它提供了常数时间的prepend和append。其它大多数操作是线性的"。更多关于ListBuffer的细节，请参见12.5小节。

12.8 从Array和ArrayBuffer中删除元素

问题

你想从Array或者ArrayBuffer中删除元素。

解决方案

ArrayBuffer是可变序列，因此 -=、--=、remove以及clear方法都可以删除元素。

对于Array，不能改变它的大小，所以不能直接删除元素。可以把数组中的元素重新赋值，这具有替换它们的效果。

讨论

你也可以对ArrayBuffer和Array使用其他功能方法，同时将结果分配给一个新变量。

删除ArrayBuffer的元素

给定ArrayBuffer：

    import scala.collection.mutable.ArrayBuffer
    val x = ArrayBuffer('a', 'b', 'c', 'd', 'e')

使用 -= 删除一个或者更多的元素：

    // remove one element
    x -= 'a'            // x: ArrayBuffer(b, c, d, e)

    // remove multiple elements
    x --= Seq('b', 'c') // x: ArrayBuffer(d, e)

如最后一个例子所示，使用 --= 来删除另一个集合（继承 IterableOnce 的任意集合）中多个元素：

    val x = ArrayBuffer.range('a', 'f')     // ArrayBuffer(a, b, c, d, e)

    x --= Seq('a', 'b')                     // x: ArrayBuffer(c, d, e)
    x --= Array('c')                        // x: ArrayBuffer(d, e)
    x --= Set('d')                          // x: ArrayBuffer(e)

根据ArrayBuffer中的索引，使用remove方法删除元素，或者根据开始索引删除一系列的元素：

    val x = ArrayBuffer('a', 'b', 'c', 'd', 'e', 'f')

    x.remove(0)     // x: ArrayBuffer(b, c, d, e, f)

    // delete three elements, starting at index 1 (results in deleting c, d, and e)
    x.remove(1, 3)  // x: ArrayBuffer(b, f)

clear方法从ArrayBuffer中删除所有元素：

    val x = ArrayBuffer(1,2,3,4,5)
    x.clear // x: ArrayBuffer[Int] = ArrayBuffer()

clearAndShrink从ArrayBuffer中删除所有元素并调整其内部表示：

    // create and populate an ArrayBuffer
    val x = ArrayBuffer.range(1, 1_000_000)

    // remove all elements and resize the internal representation
    x.clearAndShrink(0) // x: ArrayBuffer[Int] = ArrayBuffer()

clear和clearAndShrink -- TODO（耗子栏）

根据ArrayBuffer的Scaladoc（ https://oreil.ly/dtWfX ），clear方法实际上并不调整内部表示。如果也要调整，使用clearAndShrink方法。clearAndShrink Scaladoc指出：“清除缓冲区并缩小到 @param 大小（四舍五入到下一个自然大小）”。

替换数组中的元素

Array的大小不能被改变，所以不能直接删除元素。但是可以重新分配数组中的元素，这具有替换它们的效果：

    val a = Array("apple", "banana", "cherry")
    a(0) = ""     // a: Array("", banana, cherry)
    a(1) = null // a: Array("", null, cherry)

讨论

对于Array和ArrayBuffer，也可以通过常用的功能过滤方法来过滤元素，并把结果赋值给一个新的序列：

    val a = Array(1,2,3,4,5)        // a: Array[Int] = Array(1, 2, 3, 4, 5)
    val b = a.filter(_ > 3)         // b: Array(4, 5)
    val c = a.take(2)               // c: Array(1, 2)
    val d = a.drop(2)               // d: Array(3, 4, 5)
    val e = a.find(_ > 3)           // e: Some(4)
    val f = a.slice(0, 3)           // f: Array(1, 2, 3)

你可以根据需要，对Array和ArrayBuffer使用其它的功能过滤方法。

12.9 创建和修改Array

问题

你想创建一个 Array，并选择性地填充它。

解决方案

定义和填充Array的方式有很多种。可以创建具有初始值的数组，Scala能够隐式地推断数组类型：

    val nums = Array(1,2,3)             // Array[Int] = Array(1, 2, 3)
    val fruits = Array("a", "b", "c")   // Array[String] = Array(a, b, c)

如果你不喜欢Scala自动推断类型，可以手动指定：

    val a = Array(1, 2)         // a: Array[Int] = Array(1, 2)
    val a = Array[Long](1, 2)   // a: Array[Long] = Array(1, 2)

你可以创建一个空数组，然后添加新的元素，同时将结果赋值给一个新的变量：

    val a = Array[Int]()            // a: Array[Int] = Array()

    // append one element or multiple elements
    val b = a :+ 1                  // b: Array(1)
    val c = b ++ Seq(2,3)           // c: Array(1, 2, 3)

    // prepend one element or multiple elements
    val d = 10 +: c // d: Array(10, 1, 2, 3)
    val e = Array(8,9) ++: d        // e: Array(8, 9, 10, 1, 2, 3)

同样可以定义一个数组，拥有初始大小和类型，然后填充它。在第一步中，下面例子创建了一个Array[String]，它有1000个初始null元素，然后向其中添加元素：

    // create an array with an initial size
    val babyNames = new Array[String](1_000)

    // somewhere later in the code ...
    babyNames(0) = "Alvin"     // Array(Alvin, null, null ...)
    babyNames(1) = "Alexander" // Array(Alvin, Alexander, null ...)

虽然在Scala中通常会尽量避免null值，但可以为数组创建一个空的var引用，然后再分配给它：

    // this makes `fruits` a null value
    var fruits: Array[String] = _       // fruits: Array[String] = null

    // later in the code ...
    fruits = Array("apple", "banana")   // fruits: Array(apple, banana)

下面的例子展示了创建和填充Array的其他方法：

    val x = (1 to 5).toArray                // x: Array(1, 2, 3, 4, 5)
    val x = Array.range(1, 5)               // x: Array(1, 2, 3, 4)
    val x = Array.range(0, 10, 2)           // x: Array(0, 2, 4, 6, 8)
    val x = List(1, 2, 3).toArray           // x: Array(1, 2, 3)
    "Hello".toArray                         // x: Array[Char] = Array(H,e,l,l,o)
    val x = Array.fill(3)("foo")            // x: Array(foo, foo, foo)
    val x = Array.tabulate(5)(n => n * n)   // x: Array(0, 1, 4, 9, 16)

讨论

Array是非常有趣产物：

它基于Java数组，但Scala数组可以有泛型，所以你可以有一个 Array[A]。
它和Java数组一样，是mutable的，因为元素可以被改变，但又是immutable的，因为大小不能被改变。
它与Scala序列兼容，所以如果一个函数期望Seq[A]，可以传递给它一个Array[A]。

因为数组可变，所以使用函数式编程风格编写代码时，你肯定不想使用它。

关于基于Java数组，Scala 2.13数组页面（ https://oreil.ly/7GB8W ）对Array类型做了如下说明：

Scala数组与Java数组一一对应。也就是说，Scala Array[Int] 表示为Java int[]，Array[Double] 表示为Java double[] 等等。

你可以看到这一点，如果用这段代码创建一个名为Test.scala的文件：

    class Test:
        val nums = Array(1, 2, 3)

如果你用scalac编译该文件，然后用JAD等工具反编译，你会看到这样的Java代码：

    private final int nums[] = {
        1, 2, 3
    };

访问和更新元素

Array是一个indexed的顺序集合，所以通过索引位置访问和改变数值是直接而快速的。一旦你创建了Array，通过把所需的元素编号放在括号里，以此来访问元素：

    val a = Array('a', 'b', 'c')
    val elem0 = a(0) // elem0: a
    val elem1 = a(1) // elem1: b

就像通过索引访问数组元素一样，也可以用类似的方式更新元素：

    a(0) = 'A'      // a: Array(A, b, c)
    a(1) = 'B'      // a: Array(A, B, c)

为什么使用数组？

因为Array类型结合了不可变和可变的特点，你可能想知道什么时候应该使用它。一个原因是性能，数组的某些操作要比其他集合快。例如，用我当前电脑进行的测试中，一个包含500万个随机Int值的Array运行b.sortInPlace，始终需要大约500毫秒：

    import scala.util.Random

    val v: Vector[Int] = (1 to 5_000_000).toVector
    
    // create a randomized Array[Int]
    val a: Array[Int] = Random.shuffle(v).toArray
    a.sortInPlace         // takes ~500ms

相反，以同样的方式创建一个随机的Vector，不断地调用其sorted方法，需要超过3秒的时间：

    randomVector.sorted // takes about 3,100ms

所以在这个例子中，用 sortInPlace 对 Array[Int] 进行排序，要比用sorted对 Vector[Int] 进行排序快6倍左右。俗话说，不同情况（性能）可能会有所不同，但重要的是要知道，在某些情况下，Array可能比其他集合类型更快。另见部分有关于序列性能的链接。

数组如何像其他序列一样工作？-- TODO（鸽子栏）

当你意识到Scala Array是基于Java数组实现的时候，你可能会想Array怎么会像其他Scala序列一样工作。Programming in Scala书的第四版指出：“数组与序列是兼容的，因为有一个从Array到ArraySeq的隐式转换”。另外，另一个与ArrayOps相关的隐式转换 “添加所有的序列方法到数组中，但不会把数组变成一个序列”。

另见

Scala官方网站关于数组的页面（ https://oreil.ly/7GB8W ）对其进行了详细的讨论，包括其实现。
11.2小节“理解集合性能”中讨论了Array的性能。
在2016年的博客“Benchmarking Scala Collections”（ https://oreil.ly/RsqRb ）中，Li Haoyi描述了一系列的性能基准测试，展示了Array表现出色的地方。他的基准代码可以在（ https://github.com/lihaoyi/scala-bench ）中找到。

12.10 创建多维数组

问题

你希望创建一个多维数组，它有两个或更多维度的数据。

解决方案

有两个主要的解决方法：

用Array.ofDim创建一个多维数组。使用这种方式最多创建五维数组。在创建时知道行和列的数目。
按需创建数组的数组。

下面会介绍这两种方式。

使用Array.ofDim

使用Array.ofDim方法创建所需的数组：

    val rows = 2
    val cols = 3
    val a = Array.ofDim[String](rows, cols)

    // `a` now looks like this:
    Array[Array[String]] = Array(
        Array(null, null, null),
        Array(null, null, null)
    )

声明数组后，添加元素：

    a(0)(0) = "a" // row 1
    a(0)(1) = "b"
    a(0)(2) = "c"
    a(1)(0) = "d" // row 2
    a(1)(1) = "e"
    a(1)(2) = "f"

用括号访问元素，和使用一维数组方式类似：

    a(0)(0) // a
    a(1)(2) // f

用for循环遍历一个数组：

    scala> for
        | i <- 0 until rows
        | j <- 0 until cols
        | do println(s"($i)($j) = ${a(i)(j)}")
    (0)(0) = a
    (0)(1) = b
    (0)(2) = c
    (1)(0) = d
    (1)(1) = e
    (1)(2) = f

用相同的模式可以创建更多维度的多维数组。下面是创建三维数组的代码：

    val x, y, z = 10
    val a = Array.ofDim[Int](x,y,z)
    for
        i <- 0 until x
        j <- 0 until y
        k <- 0 until z
    do
        println(s"($i)($j)($k) = ${a(i)(j)(k)}")

使用数组的数组

另一种方式是创建数组，数组的元素也是数组：

    val a = Array(
        Array("a", "b", "c"),
        Array("d", "e", "f")
    )

    val x = a(0)        // x: Array(a, b, c)
    val x = a(1)        // x: Array(d, e, f)
    val x = a(0)(0)     // x: a

这种方式对过程的控制更好些，并允许你创建”参差不齐“的数组（其中每个包含的数组可能是不同的大小）：

    val a = Array(
        Array("a", "b", "c"),
        Array("d", "e"),
        Array("f")
    )

将变量声明为var，并在多个步骤中创建相同的数组：

    var arr = Array(Array("a", "b", "c"))
    arr ++= Array(Array("d", "e"))
    arr ++= Array(Array("f"))

    // result:
    Array(Array(a, b, c), Array(d, e), Array(f))

讨论

反编译Array.ofDim可以帮助我们理解其背后的工作原理。创建下面的Scala类并将其保存到名为Test.scala的文件：

    class Test:
        val arr = Array.ofDim[String](2, 3)

用scalac编译这个文件，然后再用类似JAD的工具反编译，可以看到生成的Java代码：

    private final String arr[][];

类似地，创建如下Scala三维数组：

    val arr = Array.ofDim[String](2, 2, 2)

反编译后生成的Java数组如下：

    private final String arr[][][];

不出意外，用“数组的数组”这种方式生成的代码更加复杂。

Array.ofDim的使用方式是Array独有的，List、Vector、ArrayBuffer等不提供ofDim方法。但是，“数组的数组”方式对于Array类不是独有的。“List的List”和“Vector的Vector”也是可行的。

最后，如果你有一个数组，如有需要，可以用flatten方法将其转换为一个一维数组：

    val a = Array.ofDim[Int](2, 3)  // a: Array(Array(0, 0, 0), Array(0, 0, 0))
    val b = a.flatten               // b: Array(0, 0, 0, 0, 0, 0)

12.11 数组排序

问题

你想对 Array（或者ArrayBuffer）中的元素进行排序。

解决方案

使用13.14小节“集合排序”中的排序方法（sortBy, sorted, sortWith, sortInPlace, sortInPlaceBy, sortInPlaceWith），或者使用scala.util.Sorting.quickSort方法。本解决方案演示了quickSort方法。

如果数组元素类型继承自scala.math.Ordered，或者拥有隐式或显式的Ordering，可以使用scala.util.Sorting.quickSort方法排序。String类有隐式Ordering，可以使用quickSort：

    val fruits = Array("cherry", "apple", "banana")
    scala.util.Sorting.quickSort(fruits)
    fruits // Array(apple, banana, cherry)

注意，quickSort对Array进行原地排序，所以不需要将结果赋值给新变量。上面例子可以运行因为String类(通过StringOps)有隐式的Ordering。

讨论

Person类不能使用Sorting.quickSort。因为没有提供数据如何排序的信息：

    class Person(val firstName: String, val lastName: String):
        override def toString = s"$firstName $lastName"

    val peeps = Array(
        Person("Jessica", "Day"),
        Person("Nick", "Miller"),
        Person("Winston", "Bishop"),
        Person("", "Schmidt"),
        Person("Coach", ""),
    )

对该数组排序会导致错误：

    // results in this error: “No implicit Ordering defined for Person”
    scala.util.Sorting.quickSort(peeps)

解决方案是继承scala.math.Ordered特质，在13.14小节“对集合排序”小节有提到。或者提供隐式或显式的Ordering。下面展示了显式排序：

    object LastNameOrdering extends Ordering[Person]:
        def compare(a: Person, b: Person) = a.lastName compare b.lastName

    scala.util.Sorting.quickSort(peeps)(LastNameOrdering)
    // result: Array(Coach , Winston Bishop, Jessica Day, Nick Miller, Schmidt)

这种方法之所以有效，因为quickSort的重载方法第二个参数接收（隐式）Ordering 参数，类型签名如下：

    def quickSort[K](a: Array[K])(implicit arg0: math.Ordering[K]): Unit
                                  -------------------------------

使用given ordering

如上所述，arg0被标记为implicit参数。implicit参数在Scala 2中等价于Scala 3 using参数。这意味着当math.Ordering given在当前作用域时，不需要指定就会自动当做参数组中的arg0参数。

先定义一个given值，是 Ordering[Person] 的实例：

    given personOrdering: Ordering[Person] with
        def compare(a: Person, b: Person) = a.lastName compare b.lastName

然后，在peeps数组上调用quickSort时，结果和前面的例子相同：

    import scala.util.Sorting.quickSort
    quickSort(peeps)
    // result: peeps: Array[Person] =
    // Array(Coach , Winston Bishop, Jessica Day, Nick Miller, Schmidt)

当调用 quickSort 时，不需要传入 personOrdering 实例（！）。因为 personOrdering 定义为given值，所以编译器可以找到它。编译器知道需要Ordering[Person] 参数， personOrdering 有这种类型，还被定义为given值。

这就是Scala 2 implicit参数(以及Scala 3 using参数)结合given为我们做的事情。正如下面的quickSort代码，手动地将personOrdering参数传递到第二个参数组中：

    quickSort(peeps)(personOrdering)
                     --------------

由于代码中的确不需要 personOrdering 名字，因此即使没有变量名，也可以声明given参数。如下所示：

    given Ordering[Person] with
        def compare(a: Person, b: Person) = a.lastName compare b.lastName

更多详细信息，参考 23.8 小节，“通过given和using使用属于术语推断（Term Inference）”。

性能

这个解决方案是Array类特有的，对于Array性能来说，可能比在13.14小节“排序集合”中的解决方案更好。我的测试结论表明：对于包含百万个元素的整数数组，quickSort可能比sortInPlace快一些。但和任何性能讨论一样，确保在应用中测试这些替代方案。

另见

Scaladoc中关于Sorting，Ordered和Ordering的描述很棒。以下有更多详细描述和例子：

scala.util.Sorting （ https://oreil.ly/qAsxs ）
scala.math.Ordering （ https://oreil.ly/HtYQn ）
scala.math.Ordered（ https://oreil.ly/zrsEx ）

详见13.14小节 “集合排序”：在自定义类中混入 Ordered 特质。

上一页11. 集合：介绍下一页13 集合：常见序列方法

最后更新于3年前

这有帮助吗？