永続配列

通常の配列の機能と同様、=演算子で、ある時点での配列変数を「コピー」してそれぞれ別の配列として更新が可能 通常の配列でこれを行うと配列のすべてのデータがコピーされて時間がかかるが、永続配列はそうならないような実装となる

コンストラクタ

a = initPersistentArray[T](v:seq[T]):PersistentArray

$v$を初期値とする配列を作成する

値の代入

a[k] = val

通常の配列と同様, $a$のインデックス$k$にvalに更新します。

値の参照

var x = a[k]

通常の配列と同様, $a$のインデックス$k$を参照可能である。

配列のコピー

var b = a

通常の配列でこれを行うとaの全要素がコピーされてbが作成されますが、永続配列の場合はそれを行わずに実現し、bに対してもaとは独立に更新や参照が可能です。 以下のように代入前に$a$を$b$にコピー(実際はコピーしていない)しておくとb[k]の値は更新されず、更新後もbによって更新前の値が保持されbに対して別の更新をすることも可能です。

var a = initPersistentArray[int](@[3, 1, 4, 1, 5])
var b = a # 実際にはaのすべての要素をコピーしているわけではない
a[2] = 7
echo a[2] # 7
echo b[2] # 4
echo b[3] # 1
b[3] = 9
echo b[3] # 9
echo a[3] # 1

計算量

配列のサイズを$N$として

• $O(\log_3 N)$