Crate maplike 

maplike

This crate provides traits for common operations over map-like, set-like, and vec-like data structures: get, set, insert, remove, push, pop, clear, len.

Supported collections

Standard library

Rust’s standard library collections are supported via built-in convenience implementations:

• HashMap, gated by the std feature (enabled by default);
• HashSet, gated by the std feature (enabled by default);
• BTreeMap, not feature-gated;
• BTreeSet, not feature-gated;
• Vec, not feature-gated, but does not support stable removal.

Third-party types

In addition to the standard library, maplike has built-in feature-gated convenience implementations for data structures from certain external crates:

• bidimap::BiBTreeMap, gated by the bidimap feature flag, and bidimap::BiHashMap, which is also gated by the std feature flag. bidimap is a maintained fork of the currently unmaintained bimap crate;
• rstar::RTree, gated by the rstar feature flag;
• rstared::RTreed, gated by the rstared feature flag;
• stable_vec::StableVec, gated by the stable-vec feature flag;
• thunderdome::Arena, gated by the thunderdome feature flag.

For examples, see examples directory of the undoredo crate.

Unsupported collections

Standard library’s VecDeque is unsupported.

Among stable vector data structures, Slab, SlotMap, generational-arena cannot be supported because they lack interfaces for insertion at an arbitrary key.

Technical sidenotes

Unlike maps and sets, not all stable vector data structures allow insertion and removal at arbitrary indexes regardless of whether they are vacant, occupied or out of bounds. For StableVec, we managed to implement inserting at out-of-bound indexes by changing the length before insertion using the .reserve_for() method. For thunderdome::Arena, we insert at arbitrary key directly via the .insert_at() method. Collections for which we could not achieve this are documented in the section below.

For Slab, an interface to insert at an arbitrary key is missing apparently because the freelist Slab uses to keep track of its vacant indexes is only singly-linked, not doubly-linked. Inserting an element at an arbitrary vacant index would require removing that index from the freelist. But since there is no backwards link available at a given key, doing so would require traversing the freelist from the beginning to find the position of the previous node, which would incur an overly slow O(n) time cost.

Traits

Arraylike

A keyed collection with get, set, len operations.

Assign

Replace self with a new value.

Clear

Remove all elements from the collection.

Container

Base trait for keyed collections, without any operations defined yet.

Get

Returns a reference to the value corresponding to the key.

GetByLeft

Returns a reference to the right value corresponding to the given left value in a bidirectional map.

GetByRight

Returns a reference to the left value corresponding to the given right value in a bidirectional map.

Insert

Insert a new key-value pair into the collection at an arbitrary key.

IntoIter

Consume the collection and yield owned key-value pairs.

Len

Returns the length of the collection.

Maplike

A keyed collection with get, set, insert, remove, clear operations.

Modify

Modify the value under key with a closure.

Pop

Remove the last element of the collection, returning it.

Push

Insert a value into the collection without specifying a key, returning the key that was automatically generated.

Remove

Remove an element under a key from the collection, returning the value at the key if the key was previously in the map. Other keys are not invalidated.

RemoveByLeft

Remove the left and right values from pair corresponding to the given left value in a bidirectional map.

RemoveByRight

Remove the left and right values from pair corresponding to the given right value in a bidirectional map.

Scalarlike

A single assignable value.

Set

Set the value of an already existing element under a key.

Setlike

A map-like keyed collection whose value is the unit type, thus behaving like a set.

Veclike

An array-like keyed collection with additional push, pop, clear operations.

Derive Macros

Assignderive

Containerderive