模組 Stdlib.Dynarray

module Dynarray: Dynarray

非同步存取

對動態陣列的並行存取必須同步（例如使用 Mutex.t）。非同步存取動態陣列是一個程式設計錯誤，可能導致動態陣列狀態無效，在這種情況下，某些操作會失敗並拋出 Invalid_argument 例外。

動態陣列

type !'a t

一個包含 'a 類型值的動態陣列。

動態陣列 a 在索引介於 0 和 Dynarray.length a - 1 之間（包含）時，提供常數時間的 get 和 set 操作。它的 Dynarray.length 可以透過在陣列末尾新增或移除元素而隨時間改變。

如果一個動態陣列 a 的索引在 0 .. length a - 1 範圍內，則稱該索引有效，否則稱之為無效。

val create : unit -> 'a t

create () 是一個新的空陣列。

val make : int -> 'a -> 'a t

make n x 是一個新的長度為 n 的陣列，並以 x 填滿。

引發如果 n < 0 或 n > Sys.max_array_length，則引發 Invalid_argument。

val init : int -> (int -> 'a) -> 'a t

init n f 是一個新的長度為 n 的陣列 a，使得 get a i 為 f i。換句話說，a 的元素是 f 0，然後是 f 1，然後是 f 2...，最後是 f (n - 1)，並按照此順序評估。

這與 Array.init 類似。

引發如果 n < 0 或 n > Sys.max_array_length，則引發 Invalid_argument。

val get : 'a t -> int -> 'a

get a i 是 a 的第 i 個元素，索引從 0 開始。

引發如果索引無效，則引發 Invalid_argument。

val set : 'a t -> int -> 'a -> unit

set a i x 將 a 的第 i 個元素設定為 x。

i 必須是有效的索引。set 不會向陣列新增新元素——請參閱 Dynarray.add_last 以新增元素。

引發如果索引無效，則引發 Invalid_argument。

val length : 'a t -> int

length a 是陣列中的元素數量。

val is_empty : 'a t -> bool

如果 a 為空，也就是說，如果 length a = 0，則 is_empty a 為 true。

val get_last : 'a t -> 'a

get_last a 是 a 中索引為 length a - 1 的元素。

引發如果 a 為空，則引發 Invalid_argument。

val find_last : 'a t -> 'a option

如果 a 為空，則 find_last a 為 None，否則為 Some (get_last a)。

val copy : 'a t -> 'a t

copy a 是 a 的淺拷貝，一個包含與 a 相同元素的新陣列。

加入元素

注意：如果長度需要增長超過 Sys.max_array_length，則所有新增元素的操作都會引發 Invalid_argument。

val add_last : 'a t -> 'a -> unit

add_last a x 將元素 x 新增到陣列 a 的末尾。

val append_array : 'a t -> 'a array -> unit

append_array a b 將 b 的所有元素依照它們在 b 中出現的順序新增到 a 的末尾。

例如

      let a = Dynarray.of_list [1;2] in
      Dynarray.append_array a [|3; 4|];
      assert (Dynarray.to_list a = [1; 2; 3; 4])

val append_list : 'a t -> 'a list -> unit

與 Dynarray.append_array 類似，但使用列表。

val append : 'a t -> 'a t -> unit

append a b 類似於 append_array a b，但 b 本身是一個動態陣列，而不是固定大小的陣列。

警告：append a a 是一個程式設計錯誤，因為它在 a 上迭代並同時向其中新增元素——請參閱下面的迭代章節。它會失敗並拋出 Invalid_argument。如果您真的想將 a 的副本附加到自身，可以使用 Dynarray.append_array a (Dynarray.to_array a)，這會將 a 複製到一個臨時陣列中。

val append_seq : 'a t -> 'a Seq.t -> unit

與 Dynarray.append_array 類似，但使用序列。

警告：append_seq a (to_seq_reentrant a) 同時遍歷 a 並向其中新增元素；這些操作的順序未指定，可能導致無限迴圈——新元素可能會反過來被 to_seq_reentrant a 產生並一遍又一遍地新增。

val append_iter : 'a t -> (('a -> unit) -> 'x -> unit) -> 'x -> unit

append_iter a iter x 將 x 的每個元素新增到 a 的末尾。這等同於 iter (add_last a) x。

例如，append_iter a List.iter [1;2;3] 會將元素 1、2 和 3 新增到 a 的末尾。append_iter a Queue.iter q 會從佇列 q 中新增元素。

移除元素

val pop_last_opt : 'a t -> 'a option

pop_last_opt a 移除並傳回 a 的最後一個元素，如果陣列為空，則傳回 None。

val pop_last : 'a t -> 'a

pop_last a 移除並傳回 a 的最後一個元素。

引發如果陣列為空，則引發 Not_found。

val remove_last : 'a t -> unit

remove_last a 移除 a 的最後一個元素（如果有的話）。如果 a 為空，則不執行任何操作。

val truncate : 'a t -> int -> unit

truncate a n 將 a 截斷為最多包含 n 個元素。

它會移除索引大於或等於 n 的元素。如果 n >= length a，則不執行任何操作。

truncate a n 等同於

      if n < 0 then invalid_argument "...";
      while length a > n do
        remove_last a
      done

引發如果 n < 0，則引發 Invalid_argument。

val clear : 'a t -> unit

clear a 等同於 truncate a 0，它會移除 a 的所有元素。

迭代

迭代函式遍歷動態陣列的元素。a 的遍歷會按照索引遞增的順序計算：從索引為 0 的元素到索引為 length a - 1 的元素。

在陣列的迭代過程中更改陣列的長度（透過新增或移除元素）是一個程式設計錯誤。如果任何迭代函式偵測到這種長度變化，它都會失敗並拋出 Invalid_argument。

val iter : ('a -> unit) -> 'a t -> unit

iter f a 對 a 的每個元素呼叫 f。

val iteri : (int -> 'a -> unit) -> 'a t -> unit

iteri f a 對 a 中每個索引為 i 的元素 x 呼叫 f i x。

val map : ('a -> 'b) -> 'a t -> 'b t

map f a 是一個新陣列，其中每個元素的形式為 f x，而 x 是 a 的每個元素。

例如，如果 a 的元素是 x0、x1、x2，則 b 的元素是 f x0、f x1、f x2。

val mapi : (int -> 'a -> 'b) -> 'a t -> 'b t

mapi f a 是一個新陣列，其中每個元素的形式為 f i x，而 x 是 a 中索引為 i 的每個元素。

例如，如果 a 的元素是 x0、x1、x2，則 b 的元素是 f 0 x0、f 1 x1、f 2 x2。

val fold_left : ('acc -> 'a -> 'acc) -> 'acc -> 'a t -> 'acc

fold_left f acc a 使用累加器 acc 開始，依序在 a 上摺疊 f。

例如，如果 a 的元素是 x0、x1，則 fold f acc a 為

      let acc = f acc x0 in
      let acc = f acc x1 in
      acc

val fold_right : ('a -> 'acc -> 'acc) -> 'a t -> 'acc -> 'acc

fold_right f a acc 計算 f x0 (f x1 (... (f xn acc) ...))，其中 x0、x1、...、xn 是 a 的元素。

val exists : ('a -> bool) -> 'a t -> bool

如果 a 的某些元素滿足 f，則 exists f a 為 true。

例如，如果 a 的元素是 x0、x1、x2，則 exists f a 為 f x0 || f x1 || f x2。

val for_all : ('a -> bool) -> 'a t -> bool

如果 a 的所有元素都滿足 f，則 for_all f a 為 true。這包括 a 為空的情況。

例如，如果 a 的元素是 x0、x1，則 exists f a 為 f x0 && f x1 && f x2。

val filter : ('a -> bool) -> 'a t -> 'a t

filter f a 是一個新的陣列，其中包含 a 中所有滿足 f 的元素。換句話說，它是一個陣列 b，對於 a 中依序的每個元素 x，如果 f x 為 true，則會將 x 新增到 b。

例如，filter (fun x -> x >= 0) a 是一個新的陣列，其中包含 a 中所有非負數元素，並保持原始順序。

val filter_map : ('a -> 'b option) -> 'a t -> 'b t

filter_map f a 是一個新的陣列，其中包含元素 y，使得對於 a 的元素 x，f x 為 Some y。換句話說，它是一個陣列 b，對於 a 中依序的每個元素 x

如果 f x = Some y，則將 y 新增到 b，
如果 f x = None，則不會將任何元素新增到 b。

例如，filter_map int_of_string_opt inputs 會傳回一個新的整數陣列，這些整數是從 inputs 中的字串讀取的，並忽略無法轉換為整數的字串。

轉換為其他資料結構

注意：如果長度需要增長超過 Sys.max_array_length，則 of_* 函數會引發 Invalid_argument 異常。

除了特別標記為「可重入」的 to_* 函數外，其他函數都會對它們的動態陣列參數進行迭代。特別是，如果在執行過程中動態陣列的長度發生變化，則會產生程式設計錯誤，並且如果轉換函數觀察到此類變化，它們會引發 Invalid_argument 異常。

val of_array : 'a array -> 'a t

of_array arr 會傳回一個對應於固定大小陣列 a 的動態陣列。透過複製來進行操作，時間複雜度為 O(n)。

val to_array : 'a t -> 'a array

to_array a 會傳回一個對應於動態陣列 a 的固定大小陣列。這會總是分配一個新陣列並將元素複製到其中。

val of_list : 'a list -> 'a t

of_list l 是一個包含 l 中元素的陣列，且順序相同。

val to_list : 'a t -> 'a list

to_list a 是一個包含陣列 a 中元素的列表。

val of_seq : 'a Seq.t -> 'a t

of_seq seq 是一個包含與 seq 相同元素的陣列。

它會遍歷 seq 一次，並且只有在 seq 為有限時才會終止。

val to_seq : 'a t -> 'a Seq.t

to_seq a 是元素 get a 0、get a 1... get a (length a - 1) 的序列。

val to_seq_reentrant : 'a t -> 'a Seq.t

to_seq_reentrant a 是 Dynarray.to_seq 的可重入變體，意思是說在 a 的長度變更後，仍然可以存取其元素。

請求結果序列的第 i 個元素（可能會發生零次、一次或多次）將會在請求時存取 a 的第 i 個元素。如果此時 a 的元素少於 i 個，則序列會停止。

val to_seq_rev : 'a t -> 'a Seq.t

to_seq_rev a 是元素 get a (l - 1)、get a (l - 2)... get a 0 的序列，其中 l 是呼叫 to_seq_rev 時的 length a。

val to_seq_rev_reentrant : 'a t -> 'a Seq.t

to_seq_rev_reentrant a 是 Dynarray.to_seq_rev 的可重入變體，意思是說在 a 的長度變更後，仍然可以存取其元素。

在序列中被請求時，已從陣列中移除的元素會被跳過。

進階效能主題

底層陣列，容量

在內部，動態陣列會使用一個後端陣列（由 Array 模組提供的固定大小陣列），其長度大於或等於動態陣列的長度。我們將動態陣列的容量定義為其後端陣列的長度。

當考慮動態陣列程式的效能時，動態陣列的容量非常重要。

動態陣列的記憶體使用量與其容量成正比，而不是其長度。
當後端陣列末尾沒有剩餘的空間時，新增元素需要配置一個新的、更大的後端陣列。

實作使用標準的指數重新配置策略，以保證分攤常數時間運算；特別是，在動態陣列的生命週期內配置的所有後端陣列的總容量，在最壞情況下與新增的元素總數成正比。

換句話說，使用者不需要擔心容量和重新配置，並且它們在預設情況下會獲得合理的行為。然而，在某些對效能敏感的場景中，以下函數可以幫助控制記憶體使用量或保證最佳的重新配置次數。

val capacity : 'a t -> int

capacity a 是 a 的後端陣列的長度。

val ensure_capacity : 'a t -> int -> unit

ensure_capacity a n 確保 a 的容量至少為 n。

如果請求的容量超出 0 .. Sys.max_array_length 範圍，則引發 Invalid_argument 異常。一個範例是不使用 Dynarray.init 來重新實作 Dynarray.of_array。
```
    let of_array arr =
      let a = Dynarray.create () in
      Dynarray.ensure_capacity a (Array.length arr);
      Array.iter (fun v -> add_last a v) arr
    
```
使用 ensure_capacity 可保證最多只會發生一次重新配置，而不是可能發生多次。如果沒有 ensure_capacity 提示，則調整大小的次數將與 arr 的長度成對數關係，當 arr 很大時會產生一個明顯的常數因子減速。

val ensure_extra_capacity : 'a t -> int -> unit

ensure_extra_capacity a n 是 ensure_capacity a (length a + n)，它確保 a 有空間容納 n 個額外項目。

如果請求的總容量超出 0 .. Sys.max_array_length 範圍，則引發 Invalid_argument 異常。一個使用案例是實作 Dynarray.append_array。
```
    let append_array a arr =
      ensure_extra_capacity a (Array.length arr);
      Array.iter (fun v -> add_last a v) arr
    
```

val fit_capacity : 'a t -> unit

fit_capacity a 在必要時會重新配置後端陣列，以便產生的容量正好是 length a，末尾沒有額外的空白空間。這可用於確保長期存在的陣列不會浪費記憶體。

請注意，呼叫 fit_capacity 會破壞預設重新配置策略提供的分攤複雜度保證。在陣列上重複呼叫它可能會導致二次方複雜度，無論是在時間和配置的總字數方面。

如果您知道動態陣列已達到其最終長度，並且未來將保持固定，則只需呼叫 to_array 並僅保留產生的固定大小陣列。fit_capacity 在您需要保留動態陣列以備將來可能調整大小時非常有用。

val set_capacity : 'a t -> int -> unit

set_capacity a n 在必要時會重新配置後端陣列，以便產生的容量正好是 n。特別是，索引為 n 或更大的所有元素都會被移除。

與 Dynarray.fit_capacity 類似，此函數會破壞重新配置策略提供的分攤複雜度保證。在陣列上重複呼叫它可能會導致二次方複雜度，無論是在時間和配置的總字數方面。

這是一個進階函數；特別是，應該優先使用 Dynarray.ensure_capacity 來增加容量，因為它可以保留那些分攤保證。

引發如果 n < 0，則引發 Invalid_argument。

val reset : 'a t -> unit

reset a 清除 a 並將其後端陣列替換為空陣列。

它等同於 set_capacity a 0 或 clear a; fit_capacity a。

無記憶體洩漏：保留記憶體存活性

可從動態陣列 a 存取的使用者提供的值正好是位置 0 到 length a - 1 中的元素。特別是，沒有任何使用者提供的值會因在後端陣列中位置 length a 或之後存在而「洩漏」。

動態陣列的記憶體配置

在目前的實作中，'a Dynarray.t 的後端陣列不是 'a array，而是與 'a option array 或 'a ref array 具有相同表示法的東西。每個元素都位於一個「盒子」中，該盒子在第一次將元素新增到陣列時配置 -- 請參閱實作以了解更多詳細資訊。

使用 'a array 會很棘手，因為沒有明顯的類型正確方法來表示後端陣列末尾的空白空間 -- 使用使用者提供的值可能會使 API 複雜化或違反無洩漏保證。在非同步並行使用下保持記憶體安全的限制使情況更加困難。已經討論過各種不安全的方法來做到這一點，但目前尚未就標準實作達成共識。

在一個嚴重依賴動態陣列的實際自動定理證明程式中，我們測量到額外「裝箱」的開銷最多為 25%。我們認為，大多數動態陣列使用的開銷要小得多，在許多情況下可以忽略不計，但您可能仍然更喜歡使用您自己的專門實作來提高效能。（如果您知道不需要無洩漏保證，您也可以加快刪除元素的速度。）

程式碼範例

可變優先佇列的最小堆積

我們可以使用動態陣列來實作可變的優先佇列。優先佇列提供一個新增元素的函數，以及一個根據某些比較函數提取最小元素的函數。

(* We present our priority queues as a functor
   parametrized on the comparison function. *)
module Heap (Elem : Map.OrderedType) : sig
  type t
  val create : unit -> t
  val add : t -> Elem.t -> unit
  val pop_min : t -> Elem.t option
end = struct

  (* Our priority queues are implemented using the standard "min heap"
     data structure, a dynamic array representing a binary tree. *)
  type t = Elem.t Dynarray.t
  let create = Dynarray.create

 (* The node of index [i] has as children the nodes of index [2 * i + 1]
    and [2 * i + 2] -- if they are valid indices in the dynarray. *)
  let left_child i = 2 * i + 1
  let right_child i = 2 * i + 2
  let parent_node i = (i - 1) / 2

  (* We use indexing operators for convenient notations. *)
  let ( .!() ) = Dynarray.get
  let ( .!()<- ) = Dynarray.set

  (* Auxiliary functions to compare and swap two elements
     in the dynamic array. *)
  let order h i j =
    Elem.compare h.!(i) h.!(j)

  let swap h i j =
    let v = h.!(i) in
    h.!(i) <- h.!(j);
    h.!(j) <- v

  (* We say that a heap respects the "heap ordering" if the value of
     each node is smaller than the value of its children. The
     algorithm manipulates arrays that respect the heap algorithm,
     except for one node whose value may be too small or too large.

     The auxiliary functions [heap_up] and [heap_down] take
     such a misplaced value, and move it "up" (respectively: "down")
     the tree by permuting it with its parent value (respectively:
     a child value) until the heap ordering is restored. *)

  let rec heap_up h i =
    if i = 0 then () else
    let parent = parent_node i in
    if order h i parent < 0 then
      (swap h i parent; heap_up h parent)

  and heap_down h ~len i =
    let left, right = left_child i, right_child i in
    if left >= len then () (* no child, stop *) else
    let smallest =
      if right >= len then left (* no right child *) else
      if order h left right < 0 then left else right
    in
    if order h i smallest > 0 then
      (swap h i smallest; heap_down h ~len smallest)

  let add h s =
    let i = Dynarray.length h in
    Dynarray.add_last h s;
    heap_up h i

  let pop_min h =
    if Dynarray.is_empty h then None
    else begin
      (* Standard trick: swap the 'best' value at index 0
         with the last value of the array. *)
      let last = Dynarray.length h - 1 in
      swap h 0 last;
      (* At this point [pop_last] returns the 'best' value,
         and leaves a heap with one misplaced element at position 0. *)
      let best = Dynarray.pop_last h in
      (* Restore the heap ordering -- does nothing if the heap is empty. *)
      heap_down h ~len:last 0;
      Some best
    end
end

這個範例的原始程式碼包括當堆積變空時，僅在容量高於特定閾值的情況下釋放後端陣列的邏輯。可以透過從 pop 中呼叫以下函數來完成此操作。

let shrink h =
  if Dynarray.length h = 0 && Dynarray.capacity h > 1 lsl 18 then
    Dynarray.reset h

透過將所有元素新增到優先佇列，然後按順序提取它們，可以使用 Heap 函子來實作排序函數。

let heap_sort (type a) cmp li =
  let module Heap = Heap(struct type t = a let compare = cmp end) in
  let heap = Heap.create () in
  List.iter (Heap.add heap) li;
  List.map (fun _ -> Heap.pop_min heap |> Option.get) li