模块 Dynarray

module Dynarray: sig .. end

动态数组。

The Array 模块提供了固定长度的数组。 Dynarray 提供了长度可以随时间变化的数组，通过在数组末尾添加或删除元素来实现。

这通常用于累积数量未知或在计算过程中发生变化的元素，同时还提供对任意位置元素的快速访问。

    let dynarray_of_list li =
      let arr = Dynarray.create () in
      List.iter (fun v -> Dynarray.add_last arr v) li;
      arr

The Buffer 模块提供了类似的功能，但它专门用于将字符累积到动态调整大小的字符串中。

The Stack 模块提供了一个后进先出数据结构，可以轻松地基于动态数组实现。

警告。 在当前实现中，动态数组的内存布局不同于 Array 的内存布局。有关详细信息，请参阅 内存布局 部分。

未同步访问

对动态数组的并发访问必须进行同步（例如使用 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 填充。

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.

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

get a i 是 a 的第 i 个元素，从索引 0 开始。

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

set a i x 将 a 的第 i 个元素设置为 x。

i 必须是一个有效的索引。 set 不会向数组添加新元素 - 请参阅 Dynarray.add_last 以添加一个元素。

val length : 'a t -> int

length a 是数组中的元素数量。

val is_empty : 'a t -> bool

is_empty a 如果 a 为空（即 length a = 0），则为 true。

val get_last : 'a t -> 'a

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

val find_last : 'a t -> 'a option

find_last a 如果 a 为空，则为 None，否则为 Some (get_last a)。

val copy : 'a t -> 'a t

copy a 是 a 的浅拷贝，一个新的数组，包含与 a 相同的元素。

添加元素

注意：所有添加元素的操作都会引发 Invalid_argument，如果长度需要超过 Sys.max_array_length。

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 的最后一个元素。

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
    
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 将 f 按顺序折叠到 a 上，从累加器 acc 开始。

例如，如果 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

exists f a 如果 a 中的某个元素满足 f，则为 true。

例如，如果 a 的元素是 x0、x1、x2，那么 exists f a 等于 f x0 || f x1 || f x2。

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

for_all f a 如果 a 中的所有元素都满足 f，则为 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 是一个新的数组，包含满足 f 的所有 a 的元素。换句话说，它是一个数组 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。

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

ensure_extra_capacity a n 等效于 ensure_capacity a (length a + n)，它确保 a 有足够的空间容纳 n 个额外项。

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 来增加容量，因为它保留了这些摊销保证。

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%。我们认为，对于大多数 dynarray 的使用来说，开销要小得多，在许多情况下可以忽略不计，但您仍然可能更愿意使用自己的专用实现来提高性能。（如果您知道不需要 无泄漏 保证，您还可以加快删除元素的速度。）

代码示例

用于可变优先队列的最小堆

我们可以使用动态数组来实现一个可变的优先级队列。优先级队列提供一个添加元素的函数和一个提取最小元素的函数——根据某个比较函数。

(* 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