Skip to content
Aptos Docs

ordered_map - [mainnet]

This module provides an implementation for an ordered map.

Keys point to values, and each key in the map must be unique.

Currently, one implementation is provided, backed by a single sorted vector.

That means that keys can be found within O(log N) time. Adds and removals take O(N) time, but the constant factor is small, as it does only O(log N) comparisons, and does efficient mem-copy with vector operations.

Additionally, it provides a way to lookup and iterate over sorted keys, making range query take O(log N + R) time (where R is number of elements in the range).

Most methods operate with OrderedMap being self. All methods that start with iter_*, operate with IteratorPtr being self.

Uses cmp::compare for ordering, which compares primitive types natively, and uses common lexicographical sorting for complex types.

TODO: all iterator functions are public(friend) for now, so that they can be modified in a backward incompatible way. Type is also named IteratorPtr, so that Iterator is free to use later. They are waiting for Move improvement that will allow references to be part of the struct, allowing cleaner iterator APIs.

use 0x1::cmp;
use 0x1::error;
use 0x1::option;
use 0x1::vector;

Constants

const EITER_OUT_OF_BOUNDS: u64 = 3;

Map key already exists

const EKEY_ALREADY_EXISTS: u64 = 1;

Map key is not found

const EKEY_NOT_FOUND: u64 = 2;

New key used in replace_key_inplace doesn’t respect the order

const ENEW_KEY_NOT_IN_ORDER: u64 = 4;

Structs

Entry

Individual entry holding (key, value) pair

struct Entry<K, V> has copy, drop, store
Fields
key: K
value: V

Functions

new

Create a new empty OrderedMap, using default (SortedVectorMap) implementation.

public fun new<K, V>(): ordered_map::OrderedMap<K, V>
Implementation 
public fun new<K, V>(): OrderedMap<K, V> {
    OrderedMap::SortedVectorMap {
        entries: vector::empty(),
    }
}

new_from

Create a OrderedMap from a vector of keys and values. Aborts with EKEY_ALREADY_EXISTS if duplicate keys are passed in.

public fun new_from<K, V>(keys: vector<K>, values: vector<V>): ordered_map::OrderedMap<K, V>
Implementation 
public fun new_from<K, V>(keys: vector<K>, values: vector<V>): OrderedMap<K, V> {
    let map = new();
    map.add_all(keys, values);
    map
}

length

Number of elements in the map.

public fun length<K, V>(self: &ordered_map::OrderedMap<K, V>): u64
Implementation 
public fun length<K, V>(self: &OrderedMap<K, V>): u64 {
    self.entries.length()
}

is_empty

Whether map is empty.

public fun is_empty<K, V>(self: &ordered_map::OrderedMap<K, V>): bool
Implementation 
public fun is_empty<K, V>(self: &OrderedMap<K, V>): bool {
    self.entries.is_empty()
}

add

Add a key/value pair to the map. Aborts with EKEY_ALREADY_EXISTS if key already exist.

public fun add<K, V>(self: &mut ordered_map::OrderedMap<K, V>, key: K, value: V)
Implementation 
public fun add<K, V>(self: &mut OrderedMap<K, V>, key: K, value: V) {
    let len = self.entries.length();
    let index = binary_search(&key, &self.entries, 0, len);


    // key must not already be inside.
    assert!(index >= len || &self.entries[index].key != &key, error::invalid_argument(EKEY_ALREADY_EXISTS));
    self.entries.insert(index, Entry { key, value });
}

upsert

If the key doesn’t exist in the map, inserts the key/value, and returns none. Otherwise, updates the value under the given key, and returns the old value.

public fun upsert<K: drop, V>(self: &mut ordered_map::OrderedMap<K, V>, key: K, value: V): option::Option<V>
Implementation 
public fun upsert<K: drop, V>(self: &mut OrderedMap<K, V>, key: K, value: V): Option<V> {
    let len = self.entries.length();
    let index = binary_search(&key, &self.entries, 0, len);


    if (index < len && &self.entries[index].key == &key) {
        let Entry {
            key: _,
            value: old_value,
        } = self.entries.replace(index, Entry { key, value });
        option::some(old_value)
    } else {
        self.entries.insert(index, Entry { key, value });
        option::none()
    }
}

remove

Remove a key/value pair from the map. Aborts with EKEY_NOT_FOUND if key doesn’t exist.

public fun remove<K: drop, V>(self: &mut ordered_map::OrderedMap<K, V>, key: &K): V
Implementation 
public fun remove<K: drop, V>(self: &mut OrderedMap<K, V>, key: &K): V {
    let len = self.entries.length();
    let index = binary_search(key, &self.entries, 0, len);
    assert!(index < len, error::invalid_argument(EKEY_NOT_FOUND));
    let Entry { key: old_key, value } = self.entries.remove(index);
    assert!(key == &old_key, error::invalid_argument(EKEY_NOT_FOUND));
    value
}

contains

Returns whether map contains a given key.

public fun contains<K, V>(self: &ordered_map::OrderedMap<K, V>, key: &K): bool
Implementation 
public fun contains<K, V>(self: &OrderedMap<K, V>, key: &K): bool {
    !self.find(key).iter_is_end(self)
}

borrow

public fun borrow<K, V>(self: &ordered_map::OrderedMap<K, V>, key: &K): &V
Implementation 
public fun borrow<K, V>(self: &OrderedMap<K, V>, key: &K): &V {
    self.find(key).iter_borrow(self)
}

borrow_mut

public fun borrow_mut<K, V>(self: &mut ordered_map::OrderedMap<K, V>, key: &K): &mut V
Implementation 
public fun borrow_mut<K, V>(self: &mut OrderedMap<K, V>, key: &K): &mut V {
    self.find(key).iter_borrow_mut(self)
}

replace_key_inplace

Changes the key, while keeping the same value attached to it Aborts with EKEY_NOT_FOUND if old_key doesn’t exist. Aborts with ENEW_KEY_NOT_IN_ORDER if new_key doesn’t keep the order old_key was in.

public(friend) fun replace_key_inplace<K: drop, V>(self: &mut ordered_map::OrderedMap<K, V>, old_key: &K, new_key: K)
Implementation 
public(friend) fun replace_key_inplace<K: drop, V>(self: &mut OrderedMap<K, V>, old_key: &K, new_key: K) {
    let len = self.entries.length();
    let index = binary_search(old_key, &self.entries, 0, len);
    assert!(index < len, error::invalid_argument(EKEY_NOT_FOUND));


    assert!(old_key == &self.entries[index].key, error::invalid_argument(EKEY_NOT_FOUND));


    // check that after we update the key, order is going to be respected
    if (index > 0) {
        assert!(cmp::compare(&self.entries[index - 1].key, &new_key).is_lt(), error::invalid_argument(ENEW_KEY_NOT_IN_ORDER))
    };


    if (index + 1 < len) {
        assert!(cmp::compare(&new_key, &self.entries[index + 1].key).is_lt(), error::invalid_argument(ENEW_KEY_NOT_IN_ORDER))
    };


    self.entries[index].key = new_key;
}

add_all

Add multiple key/value pairs to the map. The keys must not already exist. Aborts with EKEY_ALREADY_EXISTS if key already exist, or duplicate keys are passed in.

public fun add_all<K, V>(self: &mut ordered_map::OrderedMap<K, V>, keys: vector<K>, values: vector<V>)
Implementation 
public fun add_all<K, V>(self: &mut OrderedMap<K, V>, keys: vector<K>, values: vector<V>) {
    // TODO: Can be optimized, by sorting keys and values, and then creating map.
    keys.zip(values, |key, value| {
        self.add(key, value);
    });
}

upsert_all

Add multiple key/value pairs to the map, overwrites values if they exist already, or if duplicate keys are passed in.

public fun upsert_all<K: drop, V: drop>(self: &mut ordered_map::OrderedMap<K, V>, keys: vector<K>, values: vector<V>)
Implementation 
public fun upsert_all<K: drop, V: drop>(self: &mut OrderedMap<K, V>, keys: vector<K>, values: vector<V>) {
    // TODO: Can be optimized, by sorting keys and values, and then creating map.
    keys.zip(values, |key, value| {
        self.upsert(key, value);
    });
}

append

Takes all elements from other and adds them to self, overwritting if any key is already present in self.

public fun append<K: drop, V: drop>(self: &mut ordered_map::OrderedMap<K, V>, other: ordered_map::OrderedMap<K, V>)
Implementation 
public fun append<K: drop, V: drop>(self: &mut OrderedMap<K, V>, other: OrderedMap<K, V>) {
    self.append_impl(other);
}

append_disjoint

Takes all elements from other and adds them to self. Aborts with EKEY_ALREADY_EXISTS if other has a key already present in self.

public fun append_disjoint<K, V>(self: &mut ordered_map::OrderedMap<K, V>, other: ordered_map::OrderedMap<K, V>)
Implementation 
public fun append_disjoint<K, V>(self: &mut OrderedMap<K, V>, other: OrderedMap<K, V>) {
    let overwritten = self.append_impl(other);
    assert!(overwritten.length() == 0, error::invalid_argument(EKEY_ALREADY_EXISTS));
    overwritten.destroy_empty();
}

append_impl

Takes all elements from other and adds them to self, returning list of entries in self that were overwritten.

fun append_impl<K, V>(self: &mut ordered_map::OrderedMap<K, V>, other: ordered_map::OrderedMap<K, V>): vector<ordered_map::Entry<K, V>>
Implementation 
fun append_impl<K, V>(self: &mut OrderedMap<K, V>, other: OrderedMap<K, V>): vector<Entry<K,V>> {
    let OrderedMap::SortedVectorMap {
        entries: other_entries,
    } = other;
    let overwritten = vector::empty();


    if (other_entries.is_empty()) {
        other_entries.destroy_empty();
        return overwritten;
    };


    if (self.entries.is_empty()) {
        self.entries.append(other_entries);
        return overwritten;
    };


    // Optimization: if all elements in `other` are larger than all elements in `self`, we can just move them over.
    if (cmp::compare(&self.entries.borrow(self.entries.length() - 1).key, &other_entries.borrow(0).key).is_lt()) {
        self.entries.append(other_entries);
        return overwritten;
    };


    // In O(n), traversing from the back, build reverse sorted result, and then reverse it back
    let reverse_result = vector::empty();
    let cur_i = self.entries.length() - 1;
    let other_i = other_entries.length() - 1;


    // after the end of the loop, other_entries is empty, and any leftover is in entries
    loop {
        let ord = cmp::compare(&self.entries[cur_i].key, &other_entries[other_i].key);
        if (ord.is_gt()) {
            reverse_result.push_back(self.entries.pop_back());
            if (cur_i == 0) {
                // make other_entries empty, and rest in entries.
                // TODO cannot use mem::swap until it is public/released
                // mem::swap(&mut self.entries, &mut other_entries);
                self.entries.append(other_entries);
                break;
            } else {
                cur_i -= 1;
            };
        } else {
            // is_lt or is_eq
            if (ord.is_eq()) {
                // we skip the entries one, and below put in the result one from other.
                overwritten.push_back(self.entries.pop_back());
            };


            reverse_result.push_back(other_entries.pop_back());
            if (other_i == 0) {
                other_entries.destroy_empty();
                break;
            } else {
                other_i -= 1;
            };
        };
    };


    self.entries.reverse_append(reverse_result);


    overwritten
}

trim

Splits the collection into two, such to leave self with at number of elements. Returns a newly allocated map containing the elements in the range [at, len). After the call, the original map will be left containing the elements [0, at).

public fun trim<K, V>(self: &mut ordered_map::OrderedMap<K, V>, at: u64): ordered_map::OrderedMap<K, V>
Implementation 
public fun trim<K, V>(self: &mut OrderedMap<K, V>, at: u64): OrderedMap<K, V> {
    let rest = self.entries.trim(at);


    OrderedMap::SortedVectorMap {
        entries: rest
    }
}

borrow_front

public fun borrow_front<K, V>(self: &ordered_map::OrderedMap<K, V>): (&K, &V)
Implementation 
public fun borrow_front<K, V>(self: &OrderedMap<K, V>): (&K, &V) {
    let entry = self.entries.borrow(0);
    (&entry.key, &entry.value)
}

borrow_back

public fun borrow_back<K, V>(self: &ordered_map::OrderedMap<K, V>): (&K, &V)
Implementation 
public fun borrow_back<K, V>(self: &OrderedMap<K, V>): (&K, &V) {
    let entry = self.entries.borrow(self.entries.length() - 1);
    (&entry.key, &entry.value)
}

pop_front

public fun pop_front<K, V>(self: &mut ordered_map::OrderedMap<K, V>): (K, V)
Implementation 
public fun pop_front<K, V>(self: &mut OrderedMap<K, V>): (K, V) {
    let Entry { key, value } = self.entries.remove(0);
    (key, value)
}

pop_back

public fun pop_back<K, V>(self: &mut ordered_map::OrderedMap<K, V>): (K, V)
Implementation 
public fun pop_back<K, V>(self: &mut OrderedMap<K, V>): (K, V) {
    let Entry { key, value } = self.entries.pop_back();
    (key, value)
}

prev_key

public fun prev_key<K: copy, V>(self: &ordered_map::OrderedMap<K, V>, key: &K): option::Option<K>
Implementation 
public fun prev_key<K: copy, V>(self: &OrderedMap<K, V>, key: &K): Option<K> {
    let it = self.lower_bound(key);
    if (it.iter_is_begin(self)) {
        option::none()
    } else {
        option::some(*it.iter_prev(self).iter_borrow_key(self))
    }
}

next_key

public fun next_key<K: copy, V>(self: &ordered_map::OrderedMap<K, V>, key: &K): option::Option<K>
Implementation 
public fun next_key<K: copy, V>(self: &OrderedMap<K, V>, key: &K): Option<K> {
    let it = self.lower_bound(key);
    if (it.iter_is_end(self)) {
        option::none()
    } else {
        let cur_key = it.iter_borrow_key(self);
        if (key == cur_key) {
            let it = it.iter_next(self);
            if (it.iter_is_end(self)) {
                option::none()
            } else {
                option::some(*it.iter_borrow_key(self))
            }
        } else {
            option::some(*cur_key)
        }
    }
}

lower_bound

Returns an iterator pointing to the first element that is greater or equal to the provided key, or an end iterator if such element doesn’t exist.

public(friend) fun lower_bound<K, V>(self: &ordered_map::OrderedMap<K, V>, key: &K): ordered_map::IteratorPtr
Implementation 
public(friend) fun lower_bound<K, V>(self: &OrderedMap<K, V>, key: &K): IteratorPtr {
    let entries = &self.entries;
    let len = entries.length();


    let index = binary_search(key, entries, 0, len);
    if (index == len) {
        self.new_end_iter()
    } else {
        new_iter(index)
    }
}

find

Returns an iterator pointing to the element that equals to the provided key, or an end iterator if the key is not found.

public(friend) fun find<K, V>(self: &ordered_map::OrderedMap<K, V>, key: &K): ordered_map::IteratorPtr
Implementation 
public(friend) fun find<K, V>(self: &OrderedMap<K, V>, key: &K): IteratorPtr {
    let lower_bound = self.lower_bound(key);
    if (lower_bound.iter_is_end(self)) {
        lower_bound
    } else if (lower_bound.iter_borrow_key(self) == key) {
        lower_bound
    } else {
        self.new_end_iter()
    }
}

new_begin_iter

Returns the begin iterator.

public(friend) fun new_begin_iter<K, V>(self: &ordered_map::OrderedMap<K, V>): ordered_map::IteratorPtr
Implementation 
public(friend) fun new_begin_iter<K, V>(self: &OrderedMap<K, V>): IteratorPtr {
    if (self.is_empty()) {
        return IteratorPtr::End;
    };


    new_iter(0)
}

new_end_iter

Returns the end iterator.

public(friend) fun new_end_iter<K, V>(self: &ordered_map::OrderedMap<K, V>): ordered_map::IteratorPtr
Implementation 
public(friend) fun new_end_iter<K, V>(self: &OrderedMap<K, V>): IteratorPtr {
    IteratorPtr::End
}

iter_next

Returns the next iterator, or none if already at the end iterator. Note: Requires that the map is not changed after the input iterator is generated.

public(friend) fun iter_next<K, V>(self: ordered_map::IteratorPtr, map: &ordered_map::OrderedMap<K, V>): ordered_map::IteratorPtr
Implementation 
public(friend) fun iter_next<K, V>(self: IteratorPtr, map: &OrderedMap<K, V>): IteratorPtr {
    assert!(!self.iter_is_end(map), error::invalid_argument(EITER_OUT_OF_BOUNDS));


    let index = self.index + 1;
    if (index < map.entries.length()) {
        new_iter(index)
    } else {
        map.new_end_iter()
    }
}

iter_prev

Returns the previous iterator, or none if already at the begin iterator. Note: Requires that the map is not changed after the input iterator is generated.

public(friend) fun iter_prev<K, V>(self: ordered_map::IteratorPtr, map: &ordered_map::OrderedMap<K, V>): ordered_map::IteratorPtr
Implementation 
public(friend) fun iter_prev<K, V>(self: IteratorPtr, map: &OrderedMap<K, V>): IteratorPtr {
    assert!(!self.iter_is_begin(map), error::invalid_argument(EITER_OUT_OF_BOUNDS));


    let index = if (self is IteratorPtr::End) {
        map.entries.length() - 1
    } else {
        self.index - 1
    };


    new_iter(index)
}

iter_is_begin

Returns whether the iterator is a begin iterator.

public(friend) fun iter_is_begin<K, V>(self: &ordered_map::IteratorPtr, map: &ordered_map::OrderedMap<K, V>): bool
Implementation 
public(friend) fun iter_is_begin<K, V>(self: &IteratorPtr, map: &OrderedMap<K, V>): bool {
    if (self is IteratorPtr::End) {
        map.is_empty()
    } else {
        self.index == 0
    }
}

iter_is_begin_from_non_empty

Returns true iff the iterator is a begin iterator from a non-empty collection. (I.e. if iterator points to a valid element) This method doesn’t require having access to map, unlike iter_is_begin.

public(friend) fun iter_is_begin_from_non_empty(self: &ordered_map::IteratorPtr): bool
Implementation 
public(friend) fun iter_is_begin_from_non_empty(self: &IteratorPtr): bool {
    if (self is IteratorPtr::End) {
        false
    } else {
        self.index == 0
    }
}

iter_is_end

Returns whether the iterator is an end iterator.

public(friend) fun iter_is_end<K, V>(self: &ordered_map::IteratorPtr, _map: &ordered_map::OrderedMap<K, V>): bool
Implementation 
public(friend) fun iter_is_end<K, V>(self: &IteratorPtr, _map: &OrderedMap<K, V>): bool {
    self is IteratorPtr::End
}

iter_borrow_key

Borrows the key given iterator points to. Aborts with EITER_OUT_OF_BOUNDS if iterator is pointing to the end. Note: Requires that the map is not changed after the input iterator is generated.

public(friend) fun iter_borrow_key<K, V>(self: &ordered_map::IteratorPtr, map: &ordered_map::OrderedMap<K, V>): &K
Implementation 
public(friend) fun iter_borrow_key<K, V>(self: &IteratorPtr, map: &OrderedMap<K, V>): &K {
    assert!(!(self is IteratorPtr::End), error::invalid_argument(EITER_OUT_OF_BOUNDS));


    &map.entries.borrow(self.index).key
}

iter_borrow

Borrows the value given iterator points to. Aborts with EITER_OUT_OF_BOUNDS if iterator is pointing to the end. Note: Requires that the map is not changed after the input iterator is generated.

public(friend) fun iter_borrow<K, V>(self: ordered_map::IteratorPtr, map: &ordered_map::OrderedMap<K, V>): &V
Implementation 
public(friend) fun iter_borrow<K, V>(self: IteratorPtr, map: &OrderedMap<K, V>): &V {
    assert!(!(self is IteratorPtr::End), error::invalid_argument(EITER_OUT_OF_BOUNDS));
    &map.entries.borrow(self.index).value
}

iter_borrow_mut

Mutably borrows the value iterator points to. Aborts with EITER_OUT_OF_BOUNDS if iterator is pointing to the end. Note: Requires that the map is not changed after the input iterator is generated.

public(friend) fun iter_borrow_mut<K, V>(self: ordered_map::IteratorPtr, map: &mut ordered_map::OrderedMap<K, V>): &mut V
Implementation 
public(friend) fun iter_borrow_mut<K, V>(self: IteratorPtr, map: &mut OrderedMap<K, V>): &mut V {
    assert!(!(self is IteratorPtr::End), error::invalid_argument(EITER_OUT_OF_BOUNDS));
    &mut map.entries.borrow_mut(self.index).value
}

iter_remove

Removes (key, value) pair iterator points to, returning the previous value. Aborts with EITER_OUT_OF_BOUNDS if iterator is pointing to the end. Note: Requires that the map is not changed after the input iterator is generated.

public(friend) fun iter_remove<K: drop, V>(self: ordered_map::IteratorPtr, map: &mut ordered_map::OrderedMap<K, V>): V
Implementation 
public(friend) fun iter_remove<K: drop, V>(self: IteratorPtr, map: &mut OrderedMap<K, V>): V {
    assert!(!(self is IteratorPtr::End), error::invalid_argument(EITER_OUT_OF_BOUNDS));


    let Entry { key: _, value } = map.entries.remove(self.index);
    value
}

iter_replace

Replaces the value iterator is pointing to, returning the previous value. Aborts with EITER_OUT_OF_BOUNDS if iterator is pointing to the end. Note: Requires that the map is not changed after the input iterator is generated.

public(friend) fun iter_replace<K: copy, drop, V>(self: ordered_map::IteratorPtr, map: &mut ordered_map::OrderedMap<K, V>, value: V): V
Implementation 
public(friend) fun iter_replace<K: copy + drop, V>(self: IteratorPtr, map: &mut OrderedMap<K, V>, value: V): V {
    assert!(!(self is IteratorPtr::End), error::invalid_argument(EITER_OUT_OF_BOUNDS));


    // TODO once mem::replace is public/released, update to:
    // let entry = map.entries.borrow_mut(self.index);
    // mem::replace(&mut entry.value, value)
    let key = map.entries[self.index].key;
    let Entry {
        key: _,
        value: prev_value,
    } = map.entries.replace(self.index, Entry { key, value });
    prev_value
}

iter_add

Add key/value pair to the map, at the iterator position (before the element at the iterator position). Aborts with ENEW_KEY_NOT_IN_ORDER is key is not larger than the key before the iterator, or smaller than the key at the iterator position.

public(friend) fun iter_add<K, V>(self: ordered_map::IteratorPtr, map: &mut ordered_map::OrderedMap<K, V>, key: K, value: V)
Implementation 
public(friend) fun iter_add<K, V>(self: IteratorPtr, map: &mut OrderedMap<K, V>, key: K, value: V) {
    let len = map.entries.length();
    let insert_index = if (self is IteratorPtr::End) {
        len
    } else {
        self.index
    };


    if (insert_index > 0) {
        assert!(cmp::compare(&map.entries[insert_index - 1].key, &key).is_lt(), error::invalid_argument(ENEW_KEY_NOT_IN_ORDER))
    };


    if (insert_index < len) {
        assert!(cmp::compare(&key, &map.entries[insert_index].key).is_lt(), error::invalid_argument(ENEW_KEY_NOT_IN_ORDER))
    };


    map.entries.insert(insert_index, Entry { key, value });
}

destroy_empty

Destroys empty map. Aborts if self is not empty.

public fun destroy_empty<K, V>(self: ordered_map::OrderedMap<K, V>)
Implementation 
public fun destroy_empty<K, V>(self: OrderedMap<K, V>) {
    let OrderedMap::SortedVectorMap { entries } = self;
    // assert!(entries.is_empty(), E_NOT_EMPTY);
    entries.destroy_empty();
}

keys

Return all keys in the map. This requires keys to be copyable.

public fun keys<K: copy, V>(self: &ordered_map::OrderedMap<K, V>): vector<K>
Implementation 
public fun keys<K: copy, V>(self: &OrderedMap<K, V>): vector<K> {
    self.entries.map_ref(|e| {
        let e: &Entry<K, V> = e;
        e.key
    })
}

values

Return all values in the map. This requires values to be copyable.

public fun values<K, V: copy>(self: &ordered_map::OrderedMap<K, V>): vector<V>
Implementation 
public fun values<K, V: copy>(self: &OrderedMap<K, V>): vector<V> {
    self.entries.map_ref(|e| {
        let e: &Entry<K, V> = e;
        e.value
    })
}

to_vec_pair

Transform the map into two vectors with the keys and values respectively Primarily used to destroy a map

public fun to_vec_pair<K, V>(self: ordered_map::OrderedMap<K, V>): (vector<K>, vector<V>)
Implementation 
public fun to_vec_pair<K, V>(self: OrderedMap<K, V>): (vector<K>, vector<V>) {
    let keys: vector<K> = vector::empty();
    let values: vector<V> = vector::empty();
    let OrderedMap::SortedVectorMap { entries } = self;
    entries.for_each(|e| {
        let Entry { key, value } = e;
        keys.push_back(key);
        values.push_back(value);
    });
    (keys, values)
}

destroy

For maps that cannot be dropped this is a utility to destroy them using lambdas to destroy the individual keys and values.

public fun destroy<K, V>(self: ordered_map::OrderedMap<K, V>, dk: |K|, dv: |V|)
Implementation 
public inline fun destroy<K, V>(
    self: OrderedMap<K, V>,
    dk: |K|,
    dv: |V|
) {
    let (keys, values) = self.to_vec_pair();
    keys.destroy(|_k| dk(_k));
    values.destroy(|_v| dv(_v));
}

for_each

Apply the function to each key-value pair in the map, consuming it.

public fun for_each<K, V>(self: ordered_map::OrderedMap<K, V>, f: |(K, V)|)
Implementation 
public inline fun for_each<K, V>(
    self: OrderedMap<K, V>,
    f: |K, V|
) {
    let (keys, values) = self.to_vec_pair();
    keys.zip(values, |k, v| f(k, v));
}

for_each_ref

Apply the function to a reference of each key-value pair in the map.

Current implementation is O(n * log(n)). After function values will be optimized to O(n).

public fun for_each_ref<K: copy, drop, V>(self: &ordered_map::OrderedMap<K, V>, f: |(&K, &V)|)
Implementation 
public inline fun for_each_ref<K: copy + drop, V>(self: &OrderedMap<K, V>, f: |&K, &V|) {
    // This implementation is innefficient: O(log(n)) for next_key / borrow lookups every time,
    // but is the only one available through the public API.
    if (!self.is_empty()) {
        let (k, v) = self.borrow_front();
        f(k, v);


        let cur_k = self.next_key(k);
        while (cur_k.is_some()) {
            let k = cur_k.destroy_some();
            f(&k, self.borrow(&k));


            cur_k = self.next_key(&k);
        };
    };


    // TODO: if we make iterator api public update to:
    // let iter = self.new_begin_iter();
    // while (!iter.iter_is_end(self)) {
    //     f(iter.iter_borrow_key(self), iter.iter_borrow(self));
    //     iter = iter.iter_next(self);
    // }


    // TODO: once move supports private functions udpate to:
    // vector::for_each_ref(
    //     &self.entries,
    //     |entry| {
    //         f(&entry.key, &entry.value)
    //     }
    // );
}

for_each_ref_friend

public(friend) fun for_each_ref_friend<K: copy, drop, V>(self: &ordered_map::OrderedMap<K, V>, f: |(&K, &V)|)
Implementation 
public(friend) inline fun for_each_ref_friend<K: copy + drop, V>(self: &OrderedMap<K, V>, f: |&K, &V|) {
    let iter = self.new_begin_iter();
    while (!iter.iter_is_end(self)) {
        f(iter.iter_borrow_key(self), iter.iter_borrow(self));
        iter = iter.iter_next(self);
    }
}

for_each_mut

Apply the function to a mutable reference of each key-value pair in the map.

Current implementation is O(n * log(n)). After function values will be optimized to O(n).

public fun for_each_mut<K: copy, drop, V>(self: &mut ordered_map::OrderedMap<K, V>, f: |(&K, &mut V)|)
Implementation 
public inline fun for_each_mut<K: copy + drop, V>(self: &mut OrderedMap<K, V>, f: |&K, &mut V|) {
    // This implementation is innefficient: O(log(n)) for next_key / borrow lookups every time,
    // but is the only one available through the public API.
    if (!self.is_empty()) {
        let (k, _v) = self.borrow_front();


        let k = *k;
        let done = false;
        while (!done) {
            f(&k, self.borrow_mut(&k));


            let cur_k = self.next_key(&k);
            if (cur_k.is_some()) {
                k = cur_k.destroy_some();
            } else {
                done = true;
            }
        };
    };


    // TODO: if we make iterator api public update to:
    // let iter = self.new_begin_iter();
    // while (!iter.iter_is_end(self)) {
    //     let key = *iter.iter_borrow_key(self);
    //     f(key, iter.iter_borrow_mut(self));
    //     iter = iter.iter_next(self);
    // }


    // TODO: once move supports private functions udpate to:
    // vector::for_each_mut(
    //     &mut self.entries,
    //     |entry| {
    //         f(&mut entry.key, &mut entry.value)
    //     }
    // );
}

new_iter

fun new_iter(index: u64): ordered_map::IteratorPtr
Implementation 
inline fun new_iter(index: u64): IteratorPtr {
    IteratorPtr::Position {
        index: index,
    }
}
fun binary_search<K, V>(key: &K, entries: &vector<ordered_map::Entry<K, V>>, start: u64, end: u64): u64
Implementation 
fun binary_search<K, V>(key: &K, entries: &vector<Entry<K, V>>, start: u64, end: u64): u64 {
    let l = start;
    let r = end;
    while (l != r) {
        let mid = l + ((r - l) >> 1);
        let comparison = cmp::compare(&entries.borrow(mid).key, key);
        if (comparison.is_lt()) {
            l = mid + 1;
        } else {
            r = mid;
        };
    };
    l
}

Specification

pragma verify = false;

Enum OrderedMap

The OrderedMap datastructure.

enum OrderedMap<K, V> has copy, drop, store
Variants
SortedVectorMap
Fields
entries: vector<ordered_map::Entry<K, V>>
List of entries, sorted by key.

Enum IteratorPtr

An iterator pointing to a valid position in an ordered map, or to the end.

TODO: Once fields can be (mutable) references, this class will be deprecated.

enum IteratorPtr has copy, drop
Variants
End
Fields
Position
Fields
index: u64
The index of the iterator pointing to.