Ein Anfängerpuzzle über den Quellcode von + = Methode der ListBuffer-Klasse in Scala

Question

ListBuffer könnte effizient ein Element an sein Ende anhängen und dann in eine List konvertiert werden.

Ich studierte den Quellcode von ListBuffer Append-Methode (+=), aber es war schwierig zu verstehen, seine Funktionsweise. Der detaillierte Quellcode ist here.

excerpted Ein Quellcode:

final class ListBuffer[A] extends AbstractBuffer[A] { 
    private var start: List[A] = Nil 
    private var last0: ::[A] = _ 
    private var exported: Boolean = false 
    private var len = 0 

    def += (x: A): this.type = { 
    if (exported) copy() 
    if (isEmpty) { 
     last0 = new :: (x, Nil) 
     start = last0 
    } else { 
     val last1 = last0  // last1 is a local variable, is it necessary here? 
     last0 = new :: (x, Nil) 
     last1.tl = last0  // 
    } 
    len += 1 
    this 
    } 
} 

Im else Teil eine lokale Variable last1 definiert und anschließend mehrere Elemente am Ende enthalten, konstruiert. Die last0 zeigt immer auf die letzte Zelle.

Also ist last1 hier notwendig? Nach dem Blockieren wird es nicht mehr verfügbar sein. Ich kann nicht verstehen, warum der Autor last1 hier definieren muss.

Answer 1

Was geschieht hier ist im Wesentlichen

last0.ti = new :: (x, Nil) // put new element x at end of list 

Außer es ein Problem mit dieser Reduktion: last0 muss immer auf „Punkt“ am Ende. So wird last1 eine temporäre Referenz zum Ende der Liste, so dass auf end-of-the-list.t1 zugegriffen werden kann und ein neues Ende der Liste hinzugefügt werden kann.

Answer 2

Also gibt es 3 Zeilen.

last1 zeigt auf den aktuellen last0.

last0 wird auf das neue letzte Element gesetzt.

last1.t1 wird auf last0 gesetzt.

last1 ist kein neues Objekt. Es zeigt einfach auf den aktuellen letzten. t1 Ich nehme an, dass der Klassenzeiger auf sein nächstes Element zeigt. Also, was es tut, zeigt das aktuelle letzte Element auf das neue Element.

Dies kann in scala verwirrend sein, da es Mutables und Vars verwendet, die wenn möglich in scala vermieden werden.

Answer 3

Nun,

val last1 = last0  // last1 is a local variable, is it necessary here? 
    last0 = new :: (x, Nil) 
    last1.tl = last0  // 

Wie Sie sehen können, ist es in der Tat zu ändern .tlverwendet, nachdem wir last0 geändert haben.

Was ist .tl für dann?

@SerialVersionUID(509929039250432923L) // value computed by serialver for 2.11.2, annotation added in 2.11.4 
final case class ::[B](override val head: B, private[scala] var tl: List[B]) extends List[B] { 
    override def tail : List[B] = tl 
    override def isEmpty: Boolean = false 
} 

Wie Sie sehen können, ist :: Klasse nicht wirklich unveränderlich: dort auf den Rest der Liste eine Referenz ist, die geändert werden kann, das ist genau das, was die letzte Zeile der Fall ist.

Nun, warum müssten Sie das ändern, nachdem Sie last0 geändert haben?Das liegt daran, dass wir eine temporäre Variable brauchen, um das neu erzeugte letzte Element zu behalten, und wir müssen diesem Element trotzdem last0 zuweisen - also geben wir einfach last0 neu und erstellen das neue letzte Element auf einmal und verknüpfen das alte letzte Element (gehalten in last1) nach.

Ich hoffe, es hilft.