Creates a map from an association list with possibly repeated keys. The values in the map for a given key appear in the same order as they did in the association list.
val of_alist_fold :
('a, 'cmp)comparator->('a * 'b) list->init:'c->f:('c->'b->'c)->('a, 'c, 'cmp)t
Combines an association list into a map, folding together bound values with common keys.
val of_alist_reduce :
('a, 'cmp)comparator->('a * 'b) list->f:('b->'b->'b)->('a, 'b, 'cmp)t
Combines an association list into a map, reducing together bound values with common keys.
val of_iteri :
('a, 'cmp)comparator->iteri:(f:(key:'a->data:'b-> unit)-> unit)->[ `Ok of ('a, 'b, 'cmp)t| `Duplicate_key of 'a ]
of_iteri ~iteri behaves like of_alist, except that instead of taking a concrete datastruture, it takes an iteration function. For instance, to convert a string table into a map: of_iteri (module String) ~f:(Hashtbl.iteri table). It is faster than adding the elements one by one.
val of_sorted_array :
('a, 'cmp)comparator->('a * 'b) array->('a, 'b, 'cmp)tOr_error.t
Creates a map from a sorted array of key-data pairs. The input array must be sorted (either in ascending or descending order), as given by the relevant comparator, and must not contain duplicate keys. If either of these conditions does not hold, an error is returned.
val of_sorted_array_unchecked :
('a, 'cmp)comparator->('a * 'b) array->('a, 'b, 'cmp)t
Like of_sorted_array except that it returns a map with broken invariants when an Error would have been returned.
of_increasing_iterator_unchecked c ~len ~f behaves like of_sorted_array_unchecked c
(Array.init len ~f), with the additional restriction that a decreasing order is not supported. The advantage is not requiring you to allocate an intermediate array. f will be called with 0, 1, ... len - 1, in order.
length map returns the number of elements in map. O(1), but Tree.length is O(n).
val set : ('k, 'v, 'cmp)t->key:'k->data:'v->('k, 'v, 'cmp)t
Returns a new map with the specified new binding; if the key was already bound, its previous binding disappears.
val add :
('k, 'v, 'cmp)t->key:'k->data:'v->('k, 'v, 'cmp)tOr_duplicate.t
add t ~key ~data adds a new entry to t mapping key to data and returns `Ok with the new map, or if key is already present in t, returns `Duplicate.
val add_exn : ('k, 'v, 'cmp)t->key:'k->data:'v->('k, 'v, 'cmp)t
val add_multi :
('k, 'v list, 'cmp)t->key:'k->data:'v->('k, 'v list, 'cmp)t
If key is not present then add a singleton list, otherwise, cons data onto the head of the existing list.
val remove_multi : ('k, 'v list, 'cmp)t->'k->('k, 'v list, 'cmp)t
If the key is present, then remove its head element; if the result is empty, remove the key.
val find_multi : ('k, 'v list, 'cmp)t->'k->'v list
Returns the value bound to the given key, or the empty list if there is none.
val change :
('k, 'v, 'cmp)t->'k->f:('v option->'v option)->('k, 'v, 'cmp)t
change t key ~f returns a new map m that is the same as t on all keys except for key, and whose value for key is defined by f, i.e., find m key = f (find
t key).
val update : ('k, 'v, 'cmp)t->'k->f:('v option->'v)->('k, 'v, 'cmp)t
update t key ~f is change t key ~f:(fun o -> Some (f o)).
val iteri : ('k, 'v, _)t->f:(key:'k->data:'v-> unit)-> unit
val iter2 :
('k, 'v1, 'cmp)t->('k, 'v2, 'cmp)t->f:
(key:'k->data:[ `Left of 'v1| `Right of 'v2| `Both of 'v1 * 'v2 ]->
unit)->
unit
Iterates two maps side by side. The complexity of this function is O(M + N). If two inputs are [(0, a); (1, a)] and [(1, b); (2, b)], f will be called with [(0,
`Left a); (1, `Both (a, b)); (2, `Right b)].
val map : ('k, 'v1, 'cmp)t->f:('v1->'v2)->('k, 'v2, 'cmp)t
Returns a new map with bound values replaced by f applied to the bound values.
val mapi :
('k, 'v1, 'cmp)t->f:(key:'k->data:'v1->'v2)->('k, 'v2, 'cmp)t
Like map, but the passed function takes both key and data as arguments.
val fold : ('k, 'v, _)t->init:'a->f:(key:'k->data:'v->'a->'a)->'a
Folds over keys and data in the map in increasing order of key.
val fold_right :
('k, 'v, _)t->init:'a->f:(key:'k->data:'v->'a->'a)->'a
Folds over keys and data in the map in decreasing order of key.
val fold2 :
('k, 'v1, 'cmp)t->('k, 'v2, 'cmp)t->init:'a->f:
(key:'k->data:[ `Left of 'v1| `Right of 'v2| `Both of 'v1 * 'v2 ]->'a->'a)->'a
Folds over two maps side by side, like iter2.
val filter_keys : ('k, 'v, 'cmp)t->f:('k-> bool)->('k, 'v, 'cmp)t
filter, filteri, filter_keys, filter_map, and filter_mapi run in O(n * lg n) time; they simply accumulate each key & data pair retained by f into a new map using add.
val filter : ('k, 'v, 'cmp)t->f:('v-> bool)->('k, 'v, 'cmp)t
val filteri :
('k, 'v, 'cmp)t->f:(key:'k->data:'v-> bool)->('k, 'v, 'cmp)t
val filter_map :
('k, 'v1, 'cmp)t->f:('v1->'v2 option)->('k, 'v2, 'cmp)t
Returns a new map with bound values filtered by f applied to the bound values.
val filter_mapi :
('k, 'v1, 'cmp)t->f:(key:'k->data:'v1->'v2 option)->('k, 'v2, 'cmp)t
Like filter_map, but the passed function takes both key and data as arguments.
val partition_mapi :
('k, 'v1, 'cmp)t->f:(key:'k->data:'v1->[ `Fst of 'v2| `Snd of 'v3 ])->('k, 'v2, 'cmp)t * ('k, 'v3, 'cmp)t
partition_mapi t ~f returns two new ts, with each key in t appearing in exactly one of the resulting maps depending on its mapping in f.
val partition_map :
('k, 'v1, 'cmp)t->f:('v1->[ `Fst of 'v2| `Snd of 'v3 ])->('k, 'v2, 'cmp)t * ('k, 'v3, 'cmp)t
partition_map t ~f = partition_mapi t ~f:(fun ~key:_ ~data -> f data)
Hash function: a building block to use when hashing data structures containing maps in them. hash_fold_direct hash_fold_key is compatible with compare_direct iff hash_fold_key is compatible with (comparator m).compare of the map m being hashed.
val equal : ('v->'v-> bool)->('k, 'v, 'cmp)t->('k, 'v, 'cmp)t-> bool
equal cmp m1 m2 tests whether the maps m1 and m2 are equal, that is, contain the same keys and associate each key with the same value. cmp is the equality predicate used to compare the values associated with the keys.
val merge :
('k, 'v1, 'cmp)t->('k, 'v2, 'cmp)t->f:
(key:'k->[ `Left of 'v1| `Right of 'v2| `Both of 'v1 * 'v2 ]->'v3 option)->('k, 'v3, 'cmp)t
Merges two maps. The runtime is O(length(t1) + length(t2)). You shouldn't use this function to merge a list of maps; consider using merge_skewed instead.
val merge_skewed :
('k, 'v, 'cmp)t->('k, 'v, 'cmp)t->combine:(key:'k->'v->'v->'v)->('k, 'v, 'cmp)t
A special case of merge, merge_skewed t1 t2 is a map containing all the bindings of t1 and t2. Bindings that appear in both t1 and t2 are combined into a single value using the combine function. In a call combine ~key v1 v2, the value v1 comes from t1 and v2 from t2.
The runtime of merge_skewed is O(l1 * log(l2)), where l1 is the length of the smaller map and l2 the length of the larger map. This is likely to be faster than merge when one of the maps is a lot smaller, or when you merge a list of maps.
symmetric_diff t1 t2 ~data_equal returns a list of changes between t1 and t2. It is intended to be efficient in the case where t1 and t2 share a large amount of structure. The keys in the output sequence will be in sorted order.
split t key returns a map of keys strictly less than key, the mapping of key if any, and a map of keys strictly greater than key.
Runtime is O(m + log n), where n is the size of the input map and m is the size of the smaller of the two output maps. The O(m) term is due to the need to calculate the length of the output maps.
val append :
lower_part:('k, 'v, 'cmp)t->upper_part:('k, 'v, 'cmp)t->[ `Ok of ('k, 'v, 'cmp)t| `Overlapping_key_ranges ]
append ~lower_part ~upper_part returns `Ok map where map contains all the (key, value) pairs from the two input maps if all the keys from lower_part are less than all the keys from upper_part. Otherwise it returns `Overlapping_key_ranges.
Runtime is O(log n) where n is the size of the larger input map. This can be significantly faster than Map.merge or repeated Map.add.
subrange t ~lower_bound ~upper_bound returns a map containing all the entries from t whose keys lie inside the interval indicated by ~lower_bound and ~upper_bound. If this interval is empty, an empty map is returned.
Runtime is O(m + log n), where n is the size of the input map and m is the size of the output map. The O(m) term is due to the need to calculate the length of the output map.
val fold_range_inclusive :
('k, 'v, 'cmp)t->min:'k->max:'k->init:'a->f:(key:'k->data:'v->'a->'a)->'a
fold_range_inclusive t ~min ~max ~init ~f folds f (with initial value ~init) over all keys (and their associated values) that are in the range [min, max] (inclusive).
val range_to_alist : ('k, 'v, 'cmp)t->min:'k->max:'k->('k * 'v) list
range_to_alist t ~min ~max returns an associative list of the elements whose keys lie in [min, max] (inclusive), with the smallest key being at the head of the list.
closest_key t dir k returns the (key, value) pair in t with key closest to k that satisfies the given inequality bound.
For example, closest_key t `Less_than k would be the pair with the closest key to k where key < k.
to_sequence can be used to get the same results as closest_key. It is less efficient for individual lookups but more efficient for finding many elements starting at some value.
nth t n finds the (key, value) pair of rank n (i.e., such that there are exactly n keys strictly less than the found key), if one exists. O(log(length t) + n) time.
to_sequence ?order ?keys_greater_or_equal_to ?keys_less_or_equal_to t gives a sequence of key-value pairs between keys_less_or_equal_to and keys_greater_or_equal_to inclusive, presented in order. If keys_greater_or_equal_to > keys_less_or_equal_to, the sequence is empty. Cost is O(log n) up front and amortized O(1) to produce each element.
Using_comparator is a similar interface as the toplevel of Map, except the functions take a ~comparator:('k, 'cmp) Comparator.t, whereas the functions at the toplevel of Map take a ('k, 'cmp) comparator.