Map

type Node<K, V> = {#leaf : Leaf<K, V>; #internal : Internal<K, V>}

type Data<K, V> = { kvs : [var ?(K, V)]; var count : Nat }

type Internal<K, V> = { data : Data<K, V>; children : [var ?Node<K, V>] }

type Leaf<K, V> = { data : Data<K, V> }

type Map<K, V> = { var root : Node<K, V>; var size : Nat }

public func clone<K, V>(map : Map<K, V>) : Map<K, V>

Create a copy of the mutable key-value map.

Example:

import Map "mo:base/Map";
import Nat "mo:base/Nat";

persistent actor {
  let originalMap = Map.empty<Nat, Text>();
  Map.add(originalMap, Nat.compare, 0, "Zero");
  Map.add(originalMap, Nat.compare, 1, "One");
  Map.add(originalMap, Nat.compare, 2, "Two");
  let clonedMap = Map.clone(originalMap);
}

Runtime: O(n). Space: O(n). where n denotes the number of key-value entries stored in the map.

public func empty<K, V>() : Map<K, V>

Create a new empty mutable key-value map.

Example:

import Map "mo:base/Map";
import Nat "mo:base/Nat";
import Debug "mo:base/Debug";

persistent actor {
  let map = Map.empty<Nat, Text>();
  Debug.print(Nat.toText(Map.size(map))); // prints `0`
}

Runtime: O(1). Space: O(1).

public func singleton<K, V>(key : K, value : V) : Map<K, V>

Create a new empty mutable key-value map with a single entry.

Example:

import Map "mo:base/Map";
import Debug "mo:base/Debug";

persistent actor {
  let cityCodes = Map.singleton<Text, Nat>("Zurich", 8000);
  Debug.print(debug_show(Map.size(cityCodes))); // prints `1`
}

Runtime: O(1). Space: O(1).

public func clear<K, V>(map : Map<K, V>) : ()

Delete all the entries in the key-value map.

Example:

import Map "mo:base/Map";
import Nat "mo:base/Nat";
import Debug "mo:base/Debug";

persistent actor {
  let map = Map.empty<Nat, Text>();
  Map.add(map, Nat.compare, 0, "Zero");
  Map.add(map, Nat.compare, 1, "One");
  Map.add(map, Nat.compare, 2, "Two");
  Debug.print(debug_show(Map.size(map))); // prints `3`

  Map.clear(map);
  Debug.print(debug_show(Map.size(map))); // prints `0`
}

Runtime: O(1). Space: O(1).

public func isEmpty<K, V>(map : Map<K, V>) : Bool

Determines whether a key-value map is empty.

Example:

import Map "mo:base/Map";
import Nat "mo:base/Nat";
import Debug "mo:base/Debug";

persistent actor {
  let map = Map.empty<Nat, Text>();
  Map.add(map, Nat.compare, 0, "Zero");
  Map.add(map, Nat.compare, 1, "One");
  Map.add(map, Nat.compare, 2, "Two");

  Debug.print(debug_show(Map.isEmpty(map))); // prints `false`
  Map.clear(map);
  Debug.print(debug_show(Map.isEmpty(map))); // prints `true`
}

Runtime: O(1). Space: O(1).

public func size<K, V>(map : Map<K, V>) : Nat

Return the number of entries in a key-value map.

Example:

import Map "mo:base/Map";
import Nat "mo:base/Nat";
import Debug "mo:base/Debug";

persistent actor {
  let map = Map.empty<Nat, Text>();
  Map.add(map, Nat.compare, 0, "Zero");
  Map.add(map, Nat.compare, 1, "One");
  Map.add(map, Nat.compare, 2, "Two");

  Debug.print(Nat.toText(Map.size(map))); // prints `3`
}

Runtime: O(1). Space: O(1).

public func equal<K, V>(
  map1 : Map<K, V>,
  map2 : Map<K, V>,
  compare : (K, K) -> Order.Order,
  equal : (V, V) -> Bool
) : Bool

Test whether two imperative maps have equal entries. The order of the keys in both maps are defined by compare.

Example:

import Map "mo:base/Map";
import Nat "mo:base/Nat";
import Debug "mo:base/Debug";
import Text "mo:base/Text";

persistent actor {
let map1 = Map.empty<Nat, Text>();
  Map.add(map1, Nat.compare, 0, "Zero");
  Map.add(map1, Nat.compare, 1, "One");
  Map.add(map1, Nat.compare, 2, "Two");
  let map2 = Map.clone(map1);

  assert(Map.equal(map1, map2, Nat.compare, Text.equal));
}

Runtime: O(n). Space: O(1).

public func containsKey<K, V>(
  map : Map<K, V>,
  compare : (K, K) -> Order.Order,
  key : K
) : Bool

Tests whether the map contains the provided key.

Example:

import Map "mo:base/Map";
import Nat "mo:base/Nat";
import Bool "mo:base/Bool";
import Debug "mo:base/Debug";

persistent actor {
  let map = Map.empty<Nat, Text>();
  Map.add(map, Nat.compare, 0, "Zero");
  Map.add(map, Nat.compare, 1, "One");
  Map.add(map, Nat.compare, 2, "Two");

  Debug.print(Bool.toText(Map.containsKey(map, Nat.compare, 1))); // prints `true`
  Debug.print(Bool.toText(Map.containsKey(map, Nat.compare, 3))); // prints `false`
}

Runtime: O(log(n)). Space: O(1). where n denotes the number of key-value entries stored in the map and assuming that the compare function implements an O(1) comparison.

public func get<K, V>(
  map : Map<K, V>,
  compare : (K, K) -> Order.Order,
  key : K
) : ?V

Get the value associated with key in the given map if present and null otherwise.

Example:

import Map "mo:base/Map";
import Nat "mo:base/Nat";
import Debug "mo:base/Debug";

persistent actor {
  let map = Map.empty<Nat, Text>();
  Map.add(map, Nat.compare, 0, "Zero");
  Map.add(map, Nat.compare, 1, "One");
  Map.add(map, Nat.compare, 2, "Two");

  Debug.print(debug_show(Map.get(map, Nat.compare, 1))); // prints `?"One"`
  Debug.print(debug_show(Map.get(map, Nat.compare, 3))); // prints `null`
}

Runtime: O(log(n)). Space: O(1). where n denotes the number of key-value entries stored in the map and assuming that the compare function implements an O(1) comparison.

public func add<K, V>(
  map : Map<K, V>,
  compare : (K, K) -> Order.Order,
  key : K,
  value : V
) : ()

Insert a new key-value entry in the map. Traps if the key is already present in the map.

Example:

import Map "mo:base/Map";
import Nat "mo:base/Nat";

persistent actor {
  let map = Map.empty<Nat, Text>();
  Map.add(map, Nat.compare, 0, "Zero");
  Map.add(map, Nat.compare, 1, "One");
  Map.add(map, Nat.compare, 2, "Two");
}

Runtime: O(log(n)). Space: O(log(n)). where n denotes the number of key-value entries stored in the map and assuming that the compare function implements an O(1) comparison.

public func put<K, V>(
  map : Map<K, V>,
  compare : (K, K) -> Order.Order,
  key : K,
  value : V
) : ?V

Associates the value with the key in the map. If the key is not yet present in the map, a new key-value pair is added and null is returned. Otherwise, if the key is already present, the value is overwritten and the previous value is returned.

Example:

import Map "mo:base/Map";
import Nat "mo:base/Nat";
import Debug "mo:base/Debug";

persistent actor {
  let map = Map.empty<Nat, Text>();
  Map.add(map, Nat.compare, 1, "ONE");

  let oldZero = Map.put(map, Nat.compare, 0, "Zero"); // inserts new key-value pair.
  Debug.print(debug_show(oldZero)); // prints `null`, key was inserted.

  let oldOne = Map.put(map, Nat.compare, 1, "One");   // overwrites value for existing key.
  Debug.print(debug_show(oldOne)); // prints `?"ONE"`, previous value.
  Debug.print(debug_show(Map.get(map, Nat.compare, 1))); // prints `?"One"`, new value.
}

Runtime: O(log(n)). Space: O(log(n)). where n denotes the number of key-value entries stored in the map and assuming that the compare function implements an O(1) comparison.

public func replaceIfExists<K, V>(
  map : Map<K, V>,
  compare : (K, K) -> Order.Order,
  key : K,
  value : V
) : ?V

Overwrites the value of an existing key and returns the previous value. If the key does not exist, it has no effect and returns null.

Example:

import Map "mo:base/Map";
import Nat "mo:base/Nat";
import Debug "mo:base/Debug";

persistent actor {
  let map = Map.empty<Nat, Text>();
  Map.add(map, Nat.compare, 0, "Null");

  let oldZero = Map.replaceIfExists(map, Nat.compare, 0, "Zero"); // overwrites the value for existing key.
  Debug.print(debug_show(oldZero)); // prints `?"Null"`, previous value.
  Debug.print(debug_show(Map.get(map, Nat.compare, 0))); // prints `?"Zero"`, new value.

  let oldOne = Map.replaceIfExists(map, Nat.compare, 1, "One");  // no effect, key is absent
  Debug.print(debug_show(oldOne)); // prints `null`, key was absent.
}

Runtime: O(log(n)). Space: O(log(n)). where n denotes the number of key-value entries stored in the map and assuming that the compare function implements an O(1) comparison.

public func delete<K, V>(
  map : Map<K, V>,
  compare : (K, K) -> Order.Order,
  key : K
) : ()

Delete an existing entry by its key in the map. Traps if the key does not exist in the map.

import Map "mo:base/Map";
import Nat "mo:base/Nat";
import Debug "mo:base/Debug";

persistent actor {
  let map = Map.empty<Nat, Text>();
  Map.add(map, Nat.compare, 0, "Zero");
  Map.add(map, Nat.compare, 1, "One");
  Map.add(map, Nat.compare, 2, "Two");

  Map.delete(map, Nat.compare, 0);
  Debug.print(debug_show(Map.containsKey(map, Nat.compare, 0))); // prints `false`.
}

Runtime: O(log(n)). Space: O(log(n)) including garbage, see below. where n denotes the number of key-value entries stored in the map and assuming that the compare function implements an O(1) comparison.

Note: Creates O(log(n)) objects that will be collected as garbage.

public func maxEntry<K, V>(map : Map<K, V>) : ?(K, V)

Returns the maximum key in a BTree with its associated value. If the BTree is empty, returns null Retrieves the key-value pair from the map m with the maximum key. If the map is empty, returns null.

Example:

import Map "mo:base/Map";
import Nat "mo:base/Nat";
import Debug "mo:base/Debug";

persistent actor {
  let map = Map.empty<Nat, Text>();
  Map.add(map, Nat.compare, 0, "Zero");
  Map.add(map, Nat.compare, 1, "One");
  Map.add(map, Nat.compare, 2, "Two");

  Debug.print(debug_show(Map.maxEntry(map))); // prints `?(2, "Two")`.
}

Runtime: O(log(n)). Space: O(1). where n denotes the number of key-value entries stored in the map.

public func minEntry<K, V>(map : Map<K, V>) : ?(K, V)

Retrieves the key-value pair from the map with the minimum key. If the map is empty, returns null.

Example:

import Map "mo:base/Map";
import Nat "mo:base/Nat";
import Debug "mo:base/Debug";

persistent actor {
  let map = Map.empty<Nat, Text>();
  Map.add(map, Nat.compare, 0, "Zero");
  Map.add(map, Nat.compare, 1, "One");
  Map.add(map, Nat.compare, 2, "Two");

  Debug.print(debug_show(Map.minEntry(map))); // prints `?(0, "Zero")`.
}

Runtime: O(log(n)). Space: O(1). where n denotes the number of key-value entries stored in the map.

public func entries<K, V>(map : Map<K, V>) : IterType.Iter<(K, V)>

Returns an iterator over the key-value pairs in the map, traversing the entries in the ascending order of the keys.

Example:

import Map "mo:base/Map";
import Nat "mo:base/Nat";
import Debug "mo:base/Debug";

persistent actor {
  let map = Map.empty<Nat, Text>();
  Map.add(map, Nat.compare, 0, "Zero");
  Map.add(map, Nat.compare, 1, "One");
  Map.add(map, Nat.compare, 2, "Two");

  for (entry in Map.entries(map)) {
     Debug.print(debug_show(entry));
  }
  // prints:
  // `(0, "Zero")`
  // `(1, "One")`
  // `(2, "Two")`
}

Cost of iteration over all elements: Runtime: O(n). Space: O(1) retained memory plus garbage, see below. where n denotes the number of key-value entries stored in the map.

Note: Creates O(log(n)) temporary objects that will be collected as garbage.

public func reverseEntries<K, V>(map : Map<K, V>) : IterType.Iter<(K, V)>

Returns an iterator over the key-value pairs in the map, traversing the entries in the descending order of the keys.

Example:

import Map "mo:base/Map";
import Nat "mo:base/Nat";
import Debug "mo:base/Debug";

persistent actor {
  let map = Map.empty<Nat, Text>();
  Map.add(map, Nat.compare, 0, "Zero");
  Map.add(map, Nat.compare, 1, "One");
  Map.add(map, Nat.compare, 2, "Two");

  for (entry in Map.reverseEntries(map)) {
     Debug.print(debug_show(entry));
  }
  // prints:
  // `(2, "Two")`
  // `(1, "One")`
  // `(0, "Zero")`
}

Cost of iteration over all elements: Runtime: O(n). Space: O(1) retained memory plus garbage, see below. where n denotes the number of key-value entries stored in the map.

Note: Creates O(log(n)) temporary objects that will be collected as garbage.

public func keys<K, V>(map : Map<K, V>) : IterType.Iter<K>

Returns an iterator over the keys in the map, traversing all keys in ascending order.

Example:

import Map "mo:base/Map";
import Nat "mo:base/Nat";
import Debug "mo:base/Debug";

persistent actor {
  let map = Map.empty<Nat, Text>();
  Map.add(map, Nat.compare, 0, "Zero");
  Map.add(map, Nat.compare, 1, "One");
  Map.add(map, Nat.compare, 2, "Two");

  for (key in Map.keys(map)) {
     Debug.print(Nat.toText(key));
  }
  // prints:
  // `0`
  // `1`
  // `2`
}

Cost of iteration over all elements: Runtime: O(n). Space: O(1).

public func values<K, V>(map : Map<K, V>) : IterType.Iter<V>

Returns an iterator over the values in the map, traversing the values in the ascending order of the keys to which they are associated.

Example:

import Map "mo:base/Map";
import Nat "mo:base/Nat";
import Debug "mo:base/Debug";

persistent actor {
  let map = Map.empty<Nat, Text>();
  Map.add(map, Nat.compare, 0, "Zero");
  Map.add(map, Nat.compare, 1, "One");
  Map.add(map, Nat.compare, 2, "Two");

  for (value in Map.values(map)) {
     Debug.print(value);
  }
  // prints:
  // `Zero`
  // `One`
  // `Two`
}

Cost of iteration over all elements: Runtime: O(n). Space: O(1).

public func fromIter<K, V>(iter : IterType.Iter<(K, V)>, compare : (K, K) -> Order.Order) : Map<K, V>

Create a mutable key-value map with the entries obtained from an iterator.

Example:

import Map "mo:base/Map";
import Nat "mo:base/Nat";
import Iter "mo:base/Iter";

persistent actor {
  let iterator = Iter.fromArray([(0, "Zero"), (1, "One"), (2, "Two")]);
  let map = Map.fromIter<Nat, Text>(iterator, Nat.compare);
}

Runtime: O(n * log(n)). Space: O(n). where n denotes the number of key-value entries returned by the iterator and assuming that the compare function implements an O(1) comparison.

public func forEach<K, V>(map : Map<K, V>, operation : (K, V) -> ())

Apply an operation for each key-value pair contained in the map. The operation is applied in ascending order of the keys.

Example:

import Map "mo:base/Map";
import Nat "mo:base/Nat";
import Debug "mo:base/Debug";

persistent actor {
  let map = Map.empty<Nat, Text>();
  Map.add(map, Nat.compare, 0, "Zero");
  Map.add(map, Nat.compare, 1, "One");
  Map.add(map, Nat.compare, 2, "Two");

  Map.forEach<Nat, Text>(map, func (key, value) {
    Debug.print("key=" # Nat.toText(key) # ", value='" # value # "'");
  })
}

Runtime: O(n). Space: O(1) retained memory plus garbage, see below. where n denotes the number of key-value entries stored in the map.

Note: Creates O(log(n)) temporary objects that will be collected as garbage.

public func filter<K, V>(
  map : Map<K, V>,
  compare : (K, K) -> Order.Order,
  criterion : (K, V) -> Bool
) : Map<K, V>

Filter entries in a new map. Create a copy of the mutable map that only contains the key-value pairs that fulfil the criterion function.

Example:

import Map "mo:base/Map";
import Nat "mo:base/Nat";

persistent actor {
  let numberNames = Map.empty<Nat, Text>();
  Map.add(numberNames, Nat.compare, 0, "Zero");
  Map.add(numberNames, Nat.compare, 1, "One");
  Map.add(numberNames, Nat.compare, 2, "Two");

  let evenNumbers = Map.filter<Nat, Text>(numberNames, Nat.compare, func (key, value) {
    key % 2 == 0
  });
}

Runtime: O(n). Space: O(n). where n denotes the number of key-value entries stored in the map and assuming that the compare function implements an O(1) comparison.

public func map<K, V1, V2>(
  map : Map<K, V1>,
  compare : (K, K) -> Order.Order,
  project : (K, V1) -> V2
) : Map<K, V2>

Project all values of the map in a new map. Apply a mapping function to the values of each entriy in the map and collect collect the mapped entries in a new mutable key-value map.

Example:

import Map "mo:base/Map";
import Nat "mo:base/Nat";
import Text "mo:base/Text";
import Debug "mo:base/Debug";

persistent actor {
  let numberNames = Map.empty<Nat, Text>();
  Map.add(numberNames, Nat.compare, 0, "Zero");
  Map.add(numberNames, Nat.compare, 1, "One");
  Map.add(numberNames, Nat.compare, 2, "Two");

  let lowerCaseNames = Map.map<Nat, Text, Text>(numberNames, Nat.compare, func (key, value) {
    Text.toLower(value)
  });
  for (entry in Map.entries(lowerCaseNames)) {
     Debug.print(debug_show(entry));
  }
  // prints:
  // `(0, "zero")`
  // `(1, "one")`
  // `(2, "two")`
}

Runtime: O(n * log(n)). Space: O(n) retained memory plus garbage, see below. where n denotes the number of key-value entries stored in the map and assuming that the compare function implements an O(1) comparison.

Note: Creates O(log(n)) temporary objects that will be collected as garbage.

public func foldLeft<K, V, A>(
  map : Map<K, V>,
  base : A,
  combine : (A, K, V) -> A
) : A

Iterate all entries in ascending order of the keys, and accumulate the entries by applying the combine function, starting from a base value.

Example:

import Map "mo:base/Map";
import Nat "mo:base/Nat";
import Debug "mo:base/Debug";

persistent actor {
  let map = Map.empty<Nat, Text>();
  Map.add(map, Nat.compare, 0, "Zero");
  Map.add(map, Nat.compare, 1, "One");
  Map.add(map, Nat.compare, 2, "Two");

  let text = Map.foldLeft<Nat, Text, Text>(
     map,
     "",
     func (accumulator, key, value) {
       let separator = if (accumulator != "") { ", " } else { "" };
       accumulator # separator # Nat.toText(key) # " is " # value
     }
  );
  Debug.print(text);
  // prints `0 is Zero, 1 is One, 2 is Two`
}

Runtime: O(n). Space: O(1) retained memory plus garbage, see below. where n denotes the number of key-value entries stored in the map.

Note: Creates O(log(n)) temporary objects that will be collected as garbage.

public func foldRight<K, V, A>(
  map : Map<K, V>,
  base : A,
  combine : (K, V, A) -> A
) : A

Iterate all entries in descending order of the keys, and accumulate the entries by applying the combine function, starting from a base value.

Example:

import Map "mo:base/Map";
import Nat "mo:base/Nat";
import Debug "mo:base/Debug";

persistent actor {
  let map = Map.empty<Nat, Text>();
  Map.add(map, Nat.compare, 0, "Zero");
  Map.add(map, Nat.compare, 1, "One");
  Map.add(map, Nat.compare, 2, "Two");

  let text = Map.foldRight<Nat, Text, Text>(
     map,
     "",
     func (key, value, accumulator) {
       let separator = if (accumulator != "") { ", " } else { "" };
       accumulator # separator # Nat.toText(key) # " is " # value
     }
  );
  Debug.print(text);
  // prints `2 is Two, 1 is One, 0 is Zero`
}

Runtime: O(n). Space: O(1) retained memory plus garbage, see below. where n denotes the number of key-value entries stored in the map.

Note: Creates O(log(n)) temporary objects that will be collected as garbage.

public func all<K, V>(map : Map<K, V>, predicate : (K, V) -> Bool) : Bool

Check whether all entries in the map fulfil a predicate function, i.e. the predicate function returns true for all entries in the map. Returns true for an empty map.

Example:

import Map "mo:base/Map";
import Nat "mo:base/Nat";

persistent actor {
  let map = Map.empty<Nat, Text>();
  Map.add(map, Nat.compare, 0, "Zero");
  Map.add(map, Nat.compare, 1, "One");
  Map.add(map, Nat.compare, 2, "Two");

  let belowTen = Map.all<Nat, Text>(map, func (key, _) {
    key < 10
  }); // `true`
}

Runtime: O(n). Space: O(1) retained memory plus garbage, see below. where n denotes the number of key-value entries stored in the map.

Note: Creates O(log(n)) temporary objects that will be collected as garbage.

public func any<K, V>(map : Map<K, V>, predicate : (K, V) -> Bool) : Bool

Check whether at least one entry in the map fulfils the predicate function, i.e. the predicate function returns true for at least one entry in the map. Returns false for an empty map.

Example:

import Map "mo:base/Map";
import Nat "mo:base/Nat";

persistent actor {
  let map = Map.empty<Nat, Text>();
  Map.add(map, Nat.compare, 0, "Zero");
  Map.add(map, Nat.compare, 1, "One");
  Map.add(map, Nat.compare, 2, "Two");

  let aboveTen = Map.any<Nat, Text>(map, func (key, _) {
    key > 10
  }); // `false`
}

Runtime: O(n). Space: O(1) retained memory plus garbage, see below. where n denotes the number of key-value entries stored in the map.

Note: Creates O(log(n)) temporary objects that will be collected as garbage.

public func filterMap<K, V1, V2>(
  map : Map<K, V1>,
  compare : (K, K) -> Order.Order,
  project : (K, V1) -> ?V2
) : Map<K, V2>

Filter all entries in the map by also applying a projection to the value. Apply a mapping function project to all entries in the map and collect all entries, for which the function returns a non-null new value. Collect all non-discarded entries with the key and new value in a new mutable map.

Example:

import Map "mo:base/Map";
import Nat "mo:base/Nat";
import Text "mo:base/Text";
import Debug "mo:base/Debug";

persistent actor {
  let numberNames = Map.empty<Nat, Text>();
  Map.add(numberNames, Nat.compare, 0, "Zero");
  Map.add(numberNames, Nat.compare, 1, "One");
  Map.add(numberNames, Nat.compare, 2, "Two");

  let evenNumbers = Map.filterMap<Nat, Text, Text>(numberNames, Nat.compare, func (key, value) {
    if (key % 2 == 0) {
       ?Text.toLower(value)
    } else {
       null // discard odd numbers
    }
  });
  for (entry in Map.entries(evenNumbers)) {
     Debug.print(debug_show(entry));
  }
  // prints:
  // `(0, "zero")`
  // `(2, "two")`
}

Runtime: O(n * log(n)). Space: O(n) retained memory plus garbage, see below. where n denotes the number of key-value entries stored in the map.

Note: Creates O(log(n)) temporary objects that will be collected as garbage.

public func assertValid<K, V>(map : Map<K, V>, compare : (K, K) -> Order.Order) : ()

Internal sanity check function. Can be used to check that key/value pairs have been inserted with a consistent key comparison function. Traps if the internal map structure is invalid.

public func toText<K, V>(
  map : Map<K, V>,
  keyFormat : K -> Text,
  valueFormat : V -> Text
) : Text

Generate a textual representation of all the entries in the map. Primarily to be used for testing and debugging. The keys and values are formatted according to keyFormat and valueFormat.

Example:

import Map "mo:base/Map";
import Nat "mo:base/Nat";

persistent actor {
  let map = Map.empty<Nat, Text>();
  Map.add(map, Nat.compare, 0, "Zero");
  Map.add(map, Nat.compare, 1, "One");
  Map.add(map, Nat.compare, 2, "Two");

  let text = Map.toText<Nat, Text>(map, Nat.toText, func (value) { value });
  // `(0, Zero), (1, One), (2, Two)`
}

Runtime: O(n). Space: O(n) retained memory plus garbage, see below. where n denotes the number of key-value entries stored in the map and assuming that keyFormat and valueFormat have runtime and space costs of O(1).

Note: Creates O(log(n)) temporary objects that will be collected as garbage.

public func compare<K, V>(
  map1 : Map<K, V>,
  map2 : Map<K, V>,
  compareKey : (K, K) -> Order.Order,
  compareValue : (V, V) -> Order.Order
) : Order.Order

Compare two maps by primarily comparing keys and secondarily values. Both maps are iterated by the ascending order of their creation and order is determined by the following rules: Less: map1 is less than map2 if:

• the pairwise iteration hits a entry pair entry1 and entry2 where entry1 is less than entry2 and all preceding entry pairs are equal, or,
• map1 is a strict prefix of map2, i.e. map2 has more entries than map1 and all entries of map1 occur at the beginning of iteration map2. entry1 is less than entry2 if:
• the key of entry1 is less than the key of entry2, or
• entry1 and entry2 have equal keys and the value of entry1 is less than the value of entry2. Equal: map1 and map2 have same series of equal entries by pairwise iteration. Greater: map1 is neither less nor equal map2.

Example:

import Map "mo:base/Map";
import Nat "mo:base/Nat";
import Text "mo:base/Text";

persistent actor {
  let map1 = Map.empty<Nat, Text>();
  Map.add(map1, Nat.compare, 0, "Zero");
  Map.add(map1, Nat.compare, 1, "One");

  let map2 = Map.empty<Nat, Text>();
  Map.add(map2, Nat.compare, 0, "Zero");
  Map.add(map2, Nat.compare, 2, "Two");

  let orderLess = Map.compare(map1, map2, Nat.compare, Text.compare);
  // `#less`
  let orderEqual = Map.compare(map1, map1, Nat.compare, Text.compare);
  // `#equal`
  let orderGreater = Map.compare(map2, map1, Nat.compare, Text.compare);
  // `#greater`
}

Runtime: O(n). Space: O(1) retained memory plus garbage, see below. where n denotes the number of key-value entries stored in the map and assuming that compareKey and compareValue have runtime and space costs of O(1).

Note: Creates O(log(n)) temporary objects that will be collected as garbage.