[读书日志]从零开始学习Chisel 第八篇：Scala的集合（敏捷硬件开发语言Chisel与数字系统设计）

5.Scala的集合

Scala的集合包括数组，列表，集，映射，序列，元组，数组缓冲和列表缓冲等。

5.1 数组

5.1.1数组的定义

数组是计算机内一片地址连续的内存空间。数组元素类型可以是任意的，不同元素类型会导致每个元素的内存大小不一样，但所有元素类型必须一致。数组对象是定长的，在构造时可以选择任意长度的数组，但构造完毕就不能再更改长度了。构造数组对象的语法如下：

new Array[T](n)，方框中的T表示元素个数，可以显式声明也可以自动推断；圆括号内的n代表有n个元素。Array的伴生对象中还定义了一个apply工厂方法。

scala> val charArray = Array('a','b','c')
val charArray: Array[Char] = Array(a, b, c)

5.1.2数组的索引与元素修改

数组的下标写在圆括号中，数组元素是可变的，可以对数组元素重新赋值。

scala> val intArray = new Array[Int](3)
val intArray: Array[Int] = Array(0, 0, 0)

scala> intArray(0) = 1

scala> intArray(1) = 2

scala> intArray(2) = 3

scala> intArray
val res0: Array[Int] = Array(1, 2, 3)

5.2 列表

5.2.1列表的定义

列表是一种基于链表的数据结构，列表也是定长的，每个元素类型相同，不可再重新赋值。

scala> val intList = List(1,1,10,-5)
val intList: List[Int] = List(1, 1, 10, -5)

scala> intList(0)
val res1: Int = 1

scala> intList(3)
val res2: Int = -5

5.2.2列表添加数据

注意，这些操作都会返回一个新的列表，因为列表是不可变的对象。其中，+:和+:在调用时必须将添加后的列表显式地赋值给另一个列表。

scala> val x = List(1)
val x: List[Int] = List(1)

scala> val y = 2 +: x
val y: List[Int] = List(2, 1)

scala> val z = 3 :+ x
-- [E008] Not Found Error: ---------------------------------------------------------------------
1 |val z = 3 :+ x
  |        ^^^^
  |        value :+ is not a member of Int
1 error found

scala> val z = x :+ 3
val z: List[Int] = List(1, 3)

5.2.3列表子对象Nil

列表的子对象Nil表示空列表，它的类型是List[Nothing]，因为List的类型参数是协变的，所以List[Nothing]是所有列表的子类，即Nil兼容所有的元素。使用这个特性可以构造列表：

scala> 1 :: 2 :: 3 :: Nil
val res5: List[Int] = List(1, 2, 3)

数组和列表元素不仅可以是值类型，也可以是自定义的类，甚至是数组和列表本身，构成嵌套的数组和列表。如果元素类型是Any，那么数组和列表就可以包含不同类型的元素。

scala> List(Array(1,2,3),Array(10,100,100))
val res6: List[Array[Int]] = List(Array(1, 2, 3), Array(10, 100, 100))

scala> List(1,'1',"1")
val res7: List[Int | Char | String] = List(1, 1, 1)

这里在新版Scala中有别于书上的内容，书上显示的是List[Any]，但在最新版Scala中是三种类型的或。

5.3 数组缓冲与列表缓冲

列表可以很容易地在头部添加数据，但在尾部添加数据随着列表变大会消耗更长时间。往列表尾部添加元素很慢，所以一种方案是先往列表头部添加，再把列表整体翻转。

另一种方案是使用定义在scala.collection.mutable包中的ArrayBuffer和ListBuffer。这两种并不是真正的数组和列表，可以将其认为是暂存在缓冲区的数据。在数组缓冲和列表缓冲的头部，尾部都能添加，删去元素，且耗时是固定的，数组缓冲比数组速度慢一些。以下是三种常用的操作符：

代码示例如下：

scala> import scala.collection.mutable.{ArrayBuffer, ListBuffer}

scala> val ab = new ArrayBuffer[Int]()
val ab: scala.collection.mutable.ArrayBuffer[Int] = ArrayBuffer()

scala> ab += 10
val res8: scala.collection.mutable.ArrayBuffer[Int] = ArrayBuffer(10)

scala> -10 +=: ab
val res9: scala.collection.mutable.ArrayBuffer[Int] = ArrayBuffer(-10, 10)

scala> val lb = new ListBuffer[String]()
val lb: scala.collection.mutable.ListBuffer[String] = ListBuffer()

scala> lb += "one"
val res10: scala.collection.mutable.ListBuffer[String] = ListBuffer(one)

scala> lb ++= Seq("abc","oops","good")
val res11: scala.collection.mutable.ListBuffer[String] = ListBuffer(one, abc, oops, good)

scala> lb -= "abc"
val res12: scala.collection.mutable.ListBuffer[String] = ListBuffer(one, oops, good)

scala> lb.toArray
val res13: Array[String] = Array(one, oops, good)

scala> lb.toList
val res14: List[String] = List(one, oops, good)

5.4 元组

5.4.1元组的定义

元组也是不可变的，但可以包含不同类型的对象，使用圆括号表示。

5.4.2元组的索引

元组无法通过下标索引，只能用._n来访问每一个元素。第一个元素是._1，而不是._0。

scala> val t = ("God", 'A', 2333)
val t: (String, Char, Int) = (God,A,2333)

scala> t._1
val res15: String = God

scala> t._2
val res16: Char = A

scala> t._3
val res17: Int = 2333

元组并不是一个类，而是一系列类Tuple1~Tuple22，除了通过字面量的写法构造元组，也可以显式通过new TupleX(元组元素)来构造。也就是说，元组最多包含22个元素，除非自定义Tuple23等类。但是元组可以嵌套，索引元组仍然可以包含任意数量的元素。

5.4.3元组作为函数的入口函数

一元组没有字面量，只能显式地通过new Tuple1(元组元素)来构造，二元组也称为对偶，在映射中会用到。当函数的入参数量为一个时，调用函数时传递进去的元组字面量也可以省略圆括号。

scala> def getType(x: Any) = x.getClass
def getType(x: Any): Class[?]

scala> getType(1)
val res18: Class[?] = class java.lang.Integer

scala> getType(1,2,3)
val res19: Class[?] = class scala.Tuple3

5.4.4元组的遍历

元组数据的遍历需要先调用productIterator方法以获取其迭代器，然后对迭代器进行编译。

scala> val t1 = (1, "a", "b", true, 2)
val t1: (Int, String, String, Boolean, Int) = (1,a,b,true,2)

scala> for (item <- t1.productIterator) {
     | println("item" + item)
     | }
item1
itema
itemb
itemtrue
item2

5.5 映射

5.5.1映射的定义

映射是包含一系列键-值对的集合，键和值的类型可以是任意的，但每个键-值对的类型必须一致。映射不是一个类，而是一个特质，无法通过new创建，只能通过伴生对象的apply方法来构造。

scala> val map = Map(1 -> "+", 2 -> "-", 3 -> "*", 4 -> "/")
val map: Map[Int, String] = Map(1 -> +, 2 -> -, 3 -> *, 4 -> /)

表达式object1 -> object2是一个对偶（二元组），所以键-值对也可以写成对偶的形式。

scala> val tupleMap = Map(('a', 'A'), ('b', 'B'))
val tupleMap: Map[Char, Char] = Map(a -> A, b -> B)

scala> tupleMap('a')
val res20: Char = A

5.5.2映射的三种取值方式

当我们创建了一个映射，将其赋值给变量map，那么我们可以使用以下三种方式通过“键”来索引对应的“值”。

map("键")，返回对应的值，如果没有则报错；

map.get("键")，返回对应的值，如果没有则返回None

map.getOrElse(“键”,"默认值")，返回对应的值，如果没有则返回默认值。

scala> val map = Map(1 -> "+", 2 -> "-", 3 -> "*", 4 -> "/")
val map: Map[Int, String] = Map(1 -> +, 2 -> -, 3 -> *, 4 -> /)

scala> map(3)
val res21: String = *

scala> map(0)
java.util.NoSuchElementException: key not found: 0
  at scala.collection.immutable.Map$Map4.apply(Map.scala:535)
  ... 30 elided

scala> map.get(3)
val res23: Option[String] = Some(*)

scala> map.get(0)
val res24: Option[String] = None

scala> map.getOrElse(0,'A')
val res25: String | Char = A

5.5.3映射遍历的四种方式

for((k,v) <- map)，遍历所有的键和值，k是键，v是值；

for(k <- map.keys)，遍历所有的键；

for(v <- map.values)，遍历所有的值；

for(item <- map)，遍历所有的键-值对，此时的item是元组。

默认情况下使用的是scala.collection.immutable包中的不可变映射，也可以导入scala.collection.mutable包中的可变映射，这样可以动态地增加、删除键-值对。

5.6 集

集和映射一样，也是一个特质，也只能通过apply工厂方法构建对象。集只能包含字面值不相同的同类型元素，若构建时传入了重复参数，则会自动删去多余元素。集的apply方法测试集中是否包含传入的参数，返回true或false，而不是通过下标来索引元素。

scala> val set = Set(1,1,10,10,233)
val set: Set[Int] = Set(1, 10, 233)

scala> set(100)
val res26: Boolean = false

scala> set(10)
val res27: Boolean = true

与映射相同，也可以导入scala.collection.mutable包中的可变集。

5.7 序列

序列Seq也是一个特质，数组和列表都混入了这个特质，序列可遍历，可迭代，可以用0开始的下标索引，也可用于循环。序列包含一组相同类型的元素，不可变。序列使用apply方法进行构造。

5.8 集合的常用方法

5.8.1 map

map接收一个无副作用的函数作为入参，对调用该方法的集合的每个元素应用入参函数，并把所得结果全部打包在一个集合中返回。

scala> Array("apple", "orange", "pear").map(_ + "s")
val res28: Array[String] = Array(apples, oranges, pears)

scala> List(1,2,3).map(_ * 2)
val res29: List[Int] = List(2, 4, 6)

5.8.2 foreach

与map类似，只不过传入的是有副作用的函数。

scala> var sum = 0
var sum: Int = 0

scala> Set(1,-2,234).foreach(sum += _)

scala> sum
val res30: Int = 233

5.8.3 zip

zip方法把两个可迭代的集合一一对应，构成若干对偶，如果其中一个集合比另一个长，忽略多余的元素。

scala> List(1,2,3) zip Array('1','2','3')
val res31: List[(Int, Char)] = List((1,1), (2,2), (3,3))

scala> List(1,2,3) zip Set("good","OK")
val res32: List[(Int, String)] = List((1,good), (2,OK))

5.8.4 reduce

reduce的方法入参是一个二元操作函数，利用该二元操作函数对集合中的元素进行归约，即将上一步返回的值作为函数的第一个参数继续传递并参与运算，直到list中的所有元素被遍历，默认是从左到右的顺序。

(1 to 5).reduce(_ + _)		//1+2+3+4+5
(1 to 5).reduceLeft(_ + _)	//1+2+3+4+5
(1 to 5).reduceRight(_ + _)	//5+4+3+2+1

5.8.5 fold

与reduce类似，但可以传入一个初始值。

(1 to 5).fold(10)(_ + _)		//1+2+3+4+5
(1 to 5).foldLeft(10)(_ + _)	//1+2+3+4+5
(1 to 5).foldRight(10)(_ + _)	//5+4+3+2+1

5.8.6 scan

和fold差不多，但会把产生所有的中间结果放置在一个集合中保存。

(1 to 3).scan(10)(_ + _)		//{10,10+1,10+1+2,10+1+2+3}
(1 to 3).scanLeft(10)(_ + _)	//{10,10+1,10+1+2,10+1+2+3}
(1 to 3).scanRight(10)(_ + _)	//{10+1+2+3,10+1+2,10+1,10}