SFC2020
SFC2020 管理员

554枚
铜币

689点
威望

0个
银元

Scala的Seq实现的初步分析

2020-06-30 10:54

3480

图片:微信图片_20200417110302.jpg



对于Scala Seq集合
有常见操作:

val platformTypes = Seq("ANDROID", "IOS", "WEB")

该Seq类型在顶级包scala中被定义:

type Seq[+A] = scala.collection.Seq[A] //+A是协变
val Seq = scala.collection.Seq

查看Seq源码,实际Seq本身的定义是非常简单的,且Scala的所有集合基本都是一个类似的使用模板的实现结构

trait Seq[+A] extends PartialFunction[Int, A] //支持偏函数                      
with Iterable[A]//支持迭代器                      
with GenSeq[A]//可并行操作的所有序列的共同特质                      
//常规集合类的伴随对象的模板特质,代表一种无约束的更高等级的类型                      
with GenericTraversableTemplate[A, Seq]                      
with SeqLike[A, Seq[A]] {//Seq[A]的模板特质,Seq主要操作的实现      

//构建该类的实例的工厂伴生对象  
//指定伴生对象,实际Seq()是调用的GenericCompanion的apply()方法  
override def companion: GenericCompanion[Seq] = Seq
  

//类型  
override def seq: Seq[A] = this
}

/**  

*  类似工厂方法,Coll的当前默认实现是List
*  @define coll sequence
*  @define Coll `Seq`
*/object Seq extends SeqFactory[Seq] { //SeqFactory是Seq及其子类的伴生对象模板,仅有unapplySeq方法在模式匹配{case Seq(…)=>}中调用  
/**GenTraversableFactory是Traversable及其子类的伴随对象的模板。此类提供了一组用于创建$Coll对象的操作。它通常由Traversable子类的伴随对象继承。当然这里是间接的*/
//每个集合的伴生对象都定义了隐式方法canBuildFrom  
implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, Seq[A]] = ReusableCBF.asInstanceOf[GenericCanBuildFrom[A]]  
//Seq的构造器,默认使用的是不可变的Seq(使用构造器生成一个Seq)  
//所以使用Seq(),构造的都是不可变数据结构  
def newBuilder[A]: Builder[A, Seq[A]] = immutable.Seq.newBuilder[A]//然而最底层实现其实是一个可变的ListBuffer(继承了Builder特质)
}

/** Explicit instantiation of the `Seq` trait to reduce class file size in subclasses. */

abstract class AbstractSeq[+A] extends AbstractIterable[A] with Seq[A]

canBuildFrom在转化集合时(如 toList)会自动引入(因为在伴生对象域内的隐式方法都会自动对本类型的实例可见)

最终调用CanBuildFrom的apply()方法构造一个对应的builder(该builder就是上面ReusableCBF返回的子类的newBuilder方法实现,也就是immutable.Seq.newBuilder[A])

def to[Col[_]](implicit cbf: CanBuildFrom[Nothing, A, Col[A @uV]]): Col[A @uV] = {  
val b = cbf()  
b ++= seq  
b.result()
}

newBuilder不仅在集合转化中实现,使用伴生对象创建Seq实例时newBuilder方法也会被调用。在调用本Seq的伴生对象时会调用GenericCompanion的apply来使用

abstract class GenericCompanion[+CC[X] <: GenTraversable[X]] {  
/** The underlying collection type with unknown element type */  
protected[this] type Coll = CC[_]

def newBuilder[A]: Builder[A, CC[A]]


def empty[A]: CC[A] = newBuilder[A].result()
  

//使用Seq中的定义def newBuilder[A]: Builder[A, Seq[A]] = immutable.Seq.newBuilder[A]实现来生成Seq对象实例  
def apply[A](elems: A*): CC[A] = {    
if (elems.isEmpty) empty[A]    
else {      
val b = newBuilder[A]      
//使用builder存储元素,并返回结果      
b ++= elems      
b.result()    
}  
}
}

几乎所有集合的具体实现都在*Like中实现。这是一种作为通用模板的特质,Seq集合对应的是SeqLike。

其中SeqLike的方法indexOfSlice、lastIndexOfSlice、indexOf等都使用了kmp算法查找。而contain使用迭代器。

原文 https://dreamylost.cn/。不定时搬运自己的博客到这里来。

本文源自梦境迷离 ScalaCoder,转载目的在于传递更多信息,版权归原作者所有。


返回顶部