Scala 集合：Seq API

Seq 是一个特质类型（定义如下），用于表示按照一定顺序排列的元素序列，Seq 继承了偏函数 PartialFunction 特质，所以一个序列本质上也是一个偏函数，对应的函数类型是 Int => A ，其中 A 是对应 Seq 的元素类型，而输入参数是 Seq 的下标。

trait Seq[+A] extends PartialFunction[Int, A]
                      with Iterable[A]
                      with GenSeq[A]
                      with GenericTraversableTemplate[A, Seq]
                      with SeqLike[A, Seq[A]]

Seq 同样分为可变和不可变两大类，此外还派生出 IndexedSeq 和 LinearSeq 两个重要的子特质：

• IndexedSeq ：代表索引序列，对于基于索引的操作来说效率较高，一般底层依赖于数组实现。
• LinearSeq ：代表线性序列，对于 head、tail，以及 isEmpty 一类的方法效率较高，一般底层依赖于链表实现。

IndexedSeq 特质典型的实现类有 ArraySeq、Vector，以及 Range 等，其中 Vector 基于 Trie 树实现，在随机读和随机更新方面进行了权衡，虽然随机读的时间相对于数组略长，但是随机更新性能要优于数组和链表，是 iimmutable IndexedSeq 的默认实现。

LinearSeq 特质的典型实现类就是 List 类型，不过 List 是一个抽象类，默认基于 ListBuffer 构建。ListBuffer 的父特质 Buffer 也是 Seq 派生的一个重要子特质，Buffer 特质声明为 mutable，用于定义可变的 Seq 集合，除了 ListBuffer 实现类，Scala 主要还提供了基于数组的 ArrayBuffer 实现。

一. 获取集合索引

1.1 indexOf & lastIndexOf

函数 indexOf 和 lastIndexOf 均用于从给定 Seq 对象中检索指定元素的下标值（如果不存在则返回 -1），区别在于 indexOf 从左至右开始检索，而 lastIndexOf 则从右至左开始检索，同时这两个方法均允许指定检索的起始下标。函数定义如下：

def indexOf[B >: A](elem: B): Int
def indexOf[B >: A](elem: B, from: Int): Int

def lastIndexOf[B >: A](elem: B): Int
def lastIndexOf[B >: A](elem: B, end: Int): Int

示例：

val seq = Seq('a' to 'z': _*)
seq.indexOf('c') // 输出：2
seq.lastIndexOf('h') // 输出：7

1.2 indexWhere & lastIndexWhere

函数 indexWhere 和 lastIndexWhere 相对于 indexOf 和 lastIndexOf 更加灵活一些，这两个函数均允许指定谓词 A => Boolean 来对集合中的元素进行筛选，并返回满足条件的第 1 个元素对应的下标。函数定义如下：

def indexWhere(p: A => Boolean, from: Int): Int
def indexWhere(p: A => Boolean): Int

def lastIndexWhere(p: A => Boolean): Int
def lastIndexWhere(p: A => Boolean, end: Int): Int

示例：

val seq = Seq(1 to 9: _*)
seq.indexWhere(x => x % 2 == 0 && x > 5) // 输出：5
seq.lastIndexWhere(x => x % 2 == 1 && x < 5) // 输出：2

实际上 indexOf 和 lastIndexOf 底层分别使用 indexWhere 和 lastIndexWhere 进行实现。

1.3 indexOfSlice & lastIndexOfSlice

函数 indexOfSlice 和 lastIndexOfSlice 用于检索给定的子序列在 Seq 对象中的位置，并返回子序列第 1 个元素对应的下标，如果不存在则返回 -1。函数定义如下：

def indexOfSlice[B >: A](that: GenSeq[B]): Int
def indexOfSlice[B >: A](that: GenSeq[B], from: Int): Int

def lastIndexOfSlice[B >: A](that: GenSeq[B]): Int
def lastIndexOfSlice[B >: A](that: GenSeq[B], end: Int): Int

示例：

val seq = Seq(1 to 9: _*)
seq.indexOfSlice(Seq(7, 8)) // 输出：6
seq.lastIndexOfSlice(Seq(7, 8)) // 输出：6
seq.indexOfSlice(Seq(1, 8)) // 输出：-1
seq.lastIndexOfSlice(Seq(1, 8)) // 输出：-1

1.4 indices

函数 indices 用于获取 Seq 对象的索引集合，返回一个 Range 对象，示例：

val seq = Seq("A", "B", "C")
seq.indices // 输出：Range 0 until 3

二. 获取集合长度

2.1 length & size

函数 length 和 size 都可以返回当前 Seq 对象的长度，区别在于 size 是 Traversable 中定义的方法，而 length 是 Seq 中定义的方法，二者在功能上是等价的。示例：

val seq = Seq(1 to 9: _*)
seq.size // 输出：9
seq.length // 输出：9

2.2 lengthCompare

函数 lengthCompare 接收一个参数 n，用于将当前 Seq 对象的长度 l 与该参数进行比较，如果 l > n 则返回 1，如果 l == n 则返回 0，如果 l < n 则返回 l - n 。示例：

val seq = Seq(1 to 9: _*)
seq.lengthCompare(8) // 输出：1
seq.lengthCompare(9) // 输出：0
seq.lengthCompare(18) // 输出：-1

为什么 seq.lengthCompare(18) 的结果是 -1，而不是 -9 呢，这是因为这里实际使用的实现类 List 覆盖实现了该方法，强制返回 -1。

2.3 segmentLength & prefixLength

函数 segmentLength 接收一个谓词 A => Boolean ，用于从指定下标 from 开始往右检索连续满足条件的子序列的最大长度，函数定义如下：

def segmentLength(p: A => Boolean, from: Int): Int

而函数 prefixLength 是 segmentLength 的特殊版本，其 from 参数设置为 0，表示从头开始检索，即检索集合满足给定条件的最长前缀子序列，并返回其长度。示例：

val seq = Seq(1 to 9: _*)
seq.segmentLength(_ < 5, 2) // 输出：2
seq.prefixLength(_ < 5) // 输出：4

三. 查询操作

3.1 apply

函数 apply 用于从 Seq 对象中获取指定下标的元素，例如 seq.apply(2) 用于获取下标为 2 的元素，也可以简写为 seq(2) ，示例：

val seq = Seq("A", "B", "C")
seq.apply(2) // 输出：C
seq(2) // 输出：C

四. 插入操作

4.1 +: & :+

函数 +: 和 :+ 均用于往 Seq 对象中追加元素，并返回一个新的集合对象，区别在于 +: 是前置追加，而 :+ 是后置追加，示例：

val seq = Seq(2, 3, 4)
1 +: seq // 输出：List(1, 2, 3, 4)
seq :+ 5 // 输出：List(2, 3, 4, 5)

4.2 padTo

函数 padTo 用于将当前 Seq 对象中的前 len 个元素复制到新集合中，并在集合元素不够时使用给定的 elem 默认值填充。函数定义如下：

def padTo[B >: A, That](len: Int, elem: B)(implicit bf: CanBuildFrom[Repr, B, That]): That

示例：

val seq = Seq(2, 3, 4)
seq.padTo(5, 0) // 输出：List(2, 3, 4, 0, 0)
seq.padTo(2, 0) // 输出：List(2, 3, 4)

五. 更新操作

5.1 updated

函数 updated 用于更新 Seq 对象中指定下标位置的元素值，对于不可变集合的修改会创建出一个新的集合，而对于可变集合来说则是原地修改，所以对于可变集合可以简写为 () 操作符。示例：

val seq = Seq(1, 2, 3)
seq.updated(2, 8) // 输出：List(1, 2, 8)
val mseq = mutable.Seq(1, 2, 3)
mseq(2) = 8
mseq // 输出：ArrayBuffer(1, 2, 8)

5.2 patch

函数 patch 使用给定的元素序列 patch 替换 Seq 对象中 [from, from + replaced) 下标的元素。函数定义如下：

def patch[B >: A, That](from: Int, patch: GenSeq[B], replaced: Int)(implicit bf: CanBuildFrom[Repr, B, That]): That

示例：

val seq = Seq(1 to 9: _*)
seq.patch(3, Seq(8, 8, 8, 8, 8), 2) // 输出：List(1, 2, 3, 8, 8, 8, 8, 8, 6, 7, 8, 9)

六. 排序操作

6.1 sorted & sortBy & sortWith

函数 sorted、sortBy 和 sortWith 均用于对 Seq 对象中的元素进行 排序 操作，区别在于：

• sorted ：按照元素的值从小到大进行排序。
• sortBy ：按照指定的因子从小到大对集合中的元素进行排序。
• sortWith ：接收一个比较函数 (A, A) => Boolean ，已该函数对集合中的元素进行排序。

示例：

val seq = Seq.fill(10)(Random.nextInt(100))
seq.sorted // 输出：List(28, 36, 42, 43, 63, 66, 69, 84, 85, 88)
seq.sortBy(_ % 10) // 输出：List(42, 63, 43, 84, 85, 66, 36, 88, 28, 69)
seq.sortWith((x, y) => y < x) // 输出：List(88, 85, 84, 69, 66, 63, 43, 42, 36, 28)

七. 反转操作

7.1 reverse & reverseIterator & reverseMap

函数 reverse 用于对 Seq 对象中的元素执行反转操作，而函数 reverseIterator 同样执行反转操作，只是返回的是一个迭代器对象，示例：

val seq = Seq(1 to 5: _*)
seq.reverse // 输出：List(5, 4, 3, 2, 1)
seq.reverseIterator // 输出：<iterator>

函数 reverseMap 相当于 reverse 和 map 的组合，不过执行效率更高，用于对反转的集合执行 map 操作，示例：

val seq = Seq(1 to 5: _*)
seq.reverseMap(_ - 5) // 输出：List(0, -1, -2, -3, -4)

八. 包含检查

8.1 contains & containsSlice

函数 contains 用于检查 Seq 对象是否包含指定单个元素，而函数 containsSlice 用于检查是否包含给定的元素序列，示例：

val seq = Seq(1 to 5: _*)
seq.contains(3) // 输出：true
seq.containsSlice(Seq(1, 2)) // 输出：true
seq.containsSlice(Seq(2, 1)) // 输出：false

九. 转换操作

9.1 transform

对于集合来说一般使用 map 函数执行转换操作，但是对于 可变 Seq 对象来说，Scala 还提供了 transform 函数，用于原地转换，示例：

val seq = mutable.Seq(1, 2, 3)
seq.transform(_ * 10)
seq // 输出：ArrayBuffer(10, 20, 30)

十. 集合运算

10.1 intersect

函数 intersect 用于求解两个集合的 交集 ，示例：

val seq1 = Seq(1, 2, 3, 3)
val seq2 = Seq(2, 3, 4, 5)
seq1.intersect(seq2) // 输出：List(2, 3)

注意：如果两个集合包含重复元素，假设该元素在集合 A 中出现 x 次，在集合 B 中出现 y 次，则该元素在交集结果中出现 min(x, y) 次。

10.2 union

函数 union 用于求解两个集合的 并集 ，示例：

val seq1 = Seq(1, 2, 3, 3)
val seq2 = Seq(2, 3, 4, 5)
seq1.union(seq2) // 输出：List(1, 2, 3, 3, 2, 3, 4, 5)

并集等价于 ++ 操作。

10.3 diff

函数 diff 用于求解两个集合的 差集 ，示例：

val seq1 = Seq(1, 2, 3, 3)
val seq2 = Seq(2, 3, 4, 5)
seq1.diff(seq2) // 输出：List(1, 3)

注意：如果两个集合包含重复元素，假设该元素在集合 A 中出现 x 次，在集合 B 中出现 y 次，则该元素在差集结果中出现 max(0, x - y) 次。

十一. 排列组合

11.1 permutations

函数 permutations 用于获取一个 Seq 对象中元素的全排列，示例：

val seq = Seq(1, 1, 3)
seq.permutations.foreach(println)

输出：

List(1, 1, 3)
List(1, 3, 1)
List(3, 1, 1)

注意：如果输入集合中包含重复元素，则在全排列时会出现重复的排列，函数 permutations 会对结果去重。

11.2 combinations

函数 combinations 按照顺序从 Seq 对象中选取指定个数的元素进行组合，下面的示例按照顺序每次选择 3 个元素构建组合：

val seq = Seq(1, 2, 3, 4)
seq.combinations(3).foreach(println)

输出：

List(1, 2, 3)
List(1, 2, 4)
List(1, 3, 4)
List(2, 3, 4)

十二. 检查两个序列对应的元素是否满足给定条件

12.1 corresponds

函数 corresponds 用于接收一个序列 that 作为参数，并接收一个谓词 (A,B) => Boolean ，函数会按照下标对两个集合中的元素逐一比对是否满足给定条件，如果全部满足则返回 true，函数定义如下：

def corresponds[B](that: GenSeq[B])(p: (A,B) => Boolean): Boolean

示例：

val seq1 = Seq(1, 2, 3)
val seq2 = Seq.range(2, 7, 2)
seq1.corresponds(seq2)(_ * 2 == _) // 输出：true