package base

  1. Overview
  2. Docs
package base
Legend:
Library
Module
Module type
Parameter
Class
Class type

Build_increasing can be used to construct a map incrementally from a sequence that is known to be increasing.

The total time complexity of constructing a map this way is O(n), which is more efficient than using Map.add by a logarithmic factor.

This interface can be thought of as a dual of to_sequence, but we don't have an equally neat idiom for the duals of sequences (of_sequence is much less general because it does not allow the sequence to be produced asynchronously).

type ('a, 'b, 'c) tree := ('a, 'b, 'c) t
type ('k, 'v, 'w) t
val empty : ('k, 'v, 'w) t
val add_exn : ('k, 'v, 'w) t -> comparator:('k, 'w) Comparator.t -> key:'k -> data:'v -> ('k, 'v, 'w) t

Time complexity of add_exn is amortized constant-time (if t is used linearly), with a worst-case O(log(n)) time.

val to_tree : ('k, 'v, 'w) t -> ('k, 'v, 'w) tree

Time complexity is O(log(n)).

OCaml

Innovation. Community. Security.

GitHub Discord Twitter Peertube RSS
About
Changelog Releases Industrial Users Academic Users Why OCaml
Ecosystem
Packages Community Events OCaml Planet Jobs
Resources
Install OCaml Get Started Platform Tools Language Manual Standard Library API Books Exercises Papers OCaml Playground Logo
Policies
Carbon Footprint Governance Privacy Code of Conduct