2022/4/27 6_collection
huaxiaozhuan.com/Scala/chapters/6_collection.html 7/34
这种遍历方式非常高效,
时间复杂度为
,其中
为叶子结点数量。
如果我们让
Tree
继承自
Iterable[Int] ,
则我们可以这样定义一个
iterator
方法:
表面上看起来这个实现并不复杂。
但是对于
++
的实现而言,
存在一个运行效率的问题:
像
left.iterator ++ right.iterator
这样拼接起来的迭代器,
每交出一个元素,
都需要多一
层计算来判断是用哪个迭代器
(
left.iterator
还是
right.iterator
)
。
因此总体而言,
其计
算复杂度为
。
5.
Iterable
下面的三个特质
Seq、Set、Map
的共同特点是:
它们都实现了
PartialFunction
特质,
定义了相应的
apply
方法和
isDefinedAt
方法。
不过,
每种特质实现
PartialFunction
的方式各不相同。
例如:
对于 Seq
而言
apply
是位置下标,
元素下标从
0
开始;对于
Set ,
apply
是成员测
试;对于
Map ,
apply
是选择指定 key
的值。
三、
Seq
1.
Seq
代表序列,
它有长度
length
、且元素从固定的下标
0
开始。
2.
Seq
包含的操作:
下标和长度:
xs(i) :
获取下标
i
对应的元素。
也可以展开为
xs apply i
。
xs isDefinedAt i
:
测试
i
是否是
xs
的一个有效索引。
xs.length :
返回
xs
的长度。
xs.lengthCompare ys :
对比
xs
和
ys
的长度。
如果
xs
长度较短,
则返回
-1 ;
如果
xs
长度较长,则返回
1 ;
如果长度相同,
则返回
0
。
如果其中一个序
列的长度为无限长,
比较规则仍然有效。
下标检索:
xs indexof x
:
xs
中首次出现
x
元素的下标
(
允许多个存在
)
。
sealed abstract class Tree extends Traversable[Int]{
def foreach[U](f: Int => U) = this match{
case Node(elem) =>
f(elem)
case Branch(left, right) =>
left foreach f
right foreach f
}
}
sealed abstract class Tree extends Iterable[Int]{
def iterator: Iterator[Int] = this match{
case Node(elem) => Iterator.single(elem)
case Branch(left, right) => left.iterator ++ right.iterator
}
}
Seq(1,2,3)(0) // 返回 1
Set(1,2,3)(0) // 返回 false
Map(1-> "a", 0 -> "b")(0) // 返回 "a"