maplike

Rust traits for abstract containers and operations over them.

With this library, you can write code that is generic over various built-in, standard library, and third-party containers, including collections, and primitives. You can have the same code work on both on BTreeMap and HashMap, and in many cases also on Vec, VecDeque, Option, Box, Rc, Arc and more.

See the Supported containers section for a complete list of supported containers.

Basically, this is Python's collections.abc, but in Rust, and with traits not only for different kinds of containers, but also for each operation. Essentially, every container, including non-collections, is treated as if it was a map. If it is not really a map, then it is treated as if its key type was usize, even when there can be at most only one element. Hence the crate name, maplike.

The traits are implemented for many containers from std and third-party crates. See the Traits section for a list of all available traits.

This library is maintained and champaigned (aka. dogfooded) by the authors, who use has it as a dependency for

• undoredo, a versatile crate for implementing Undo/Redo and non-linear history tree using sparse deltas (diffs), snapshots, or commands on arbitrary data structures;
• multi_bimap, a crate implementing many-to-many bidirectional map using two antiparallel internal containers chosen by the user;
• rstared, a simple Rust decorator to add a passively listening R-tree (rstar::RTree) to many standard library and third-party collection types.
• dcel, a crate that implements the half-edge data structure (aka. doubly connected edge list, DCEL) generically over its underlying containers.

This crate is compatible with no_std and serde and contains no unsafe code. MSRV is 1.92.

If you are looking for abstract number traits instead of or in addition to abstract container traits, also check out another crate of ours, numlike.

Usage

Adding dependency

First, add maplike as a dependency to your Cargo.toml:

[dependencies]
maplike = { version = "0.15.0", features = ["derive"] }

The derive feature flag is only needed if you want to derive the Keyed trait using derive macro #[derive(Keyed)].

Usage examples

maplike's container and collection traits allow you to write functions that are generic over many different collection types. A single collection trait like Get is enough to abstract over Vecs, arrays, and maps alike.

use std::collections::{BTreeMap, HashMap};

use maplike::ops::Get;

// Generic over any collection implementing the `Get` trait.
fn get_second_element<C: Get<usize>>(collection: &C) -> Option<&C::Value> {
    collection.get(&1)
}

// `get_second_element()` works for `Vec`s, arrays, `BTreeMap`s, `HashMap`s with
// the very same code.
assert_eq!(get_second_element(&vec![10, 20, 30]), Some(&20));
assert_eq!(get_second_element(&[10, 20, 30]), Some(&20));
assert_eq!(get_second_element(&BTreeMap::from([(0, 10), (1, 20)])), Some(&20));
assert_eq!(get_second_element(&HashMap::from([(0, 10), (1, 20)])), Some(&20));

An abstract container trait can bundle together several traits for container methods together in one short bound. For example, Veclike joins together (Get, Set, Push, Pop, Clear, Len, and Index), thus allowing for code that is generic over Vec, VecDeque, smallvec::SmallVec, tinyvec::ArrayVec, and tinyvec::TinyVec.

use maplike::abc::{Keyed, Veclike};
use maplike::ops::{Clear, Push};

// This function is generic over any `Veclike` collection. The `Veclike` bound
// provides `.clear()`, `.push()` and many other methods at once.
fn replace_all<C: Veclike<usize, Value = i32>>(collection: &mut C, values: &[i32]) {
    collection.clear();
    for &value in values {
        collection.push(value);
    }
}

// `replace_all()` now works for any `Veclike` collection.

// Works on `Vec`,
let mut vec = Vec::new();
replace_all(&mut vec, &[1, 2, 3]);
assert_eq!(vec, [1, 2, 3]);
replace_all(&mut vec, &[4, 5, 6]);
assert_eq!(vec, [4, 5, 6]);

#[cfg(feature = "smallvec")]
{
    use smallvec::SmallVec;

    // Works on `smallvec::SmallVec`.
    let mut small_vec: SmallVec<[i32; 8]> = SmallVec::new();
    replace_all(&mut small_vec, &[7, 8, 9]);
    assert_eq!(small_vec.as_slice(), [7, 8, 9]);
}

#[cfg(feature = "tinyvec")]
{
    use tinyvec::{ArrayVec, TinyVec};

    // Works on `tinyvec::ArrayVec`.
    let mut tiny_array_vec: ArrayVec<[i32; 8]> = ArrayVec::new();
    replace_all(&mut tiny_array_vec, &[7, 8, 9]);
    assert_eq!(tiny_array_vec.as_slice(), [7, 8, 9]);

    // Works on `tinyvec::TinyVec`.
    let mut tiny_vec: TinyVec<[i32; 8]> = TinyVec::new();
    replace_all(&mut tiny_vec, &[10, 11, 12]);
    assert_eq!(tiny_vec.as_slice(), [10, 11, 12]);
}

// NOTE: `arrayvec::ArrayVec` and `arrayvec::ArrayString` are not `Veclike`
// because they do not implement `Index`.

Traits

Operations

This crate provides traits for common operations over map-like, set-like, array-like, and vec-like data structures: .with_one(), .assign(), .contains_key(), .get(), .set(), .modify(), .insert(), .remove(), .swap_remove(), .push(), .pop(), .put(), .clear(), .len(), .resize(), .values(), .into_values(), .iter(), and .into_iter().

For bidirectional maps, there are also variants of the get and remove operations by left and right key: .get_by_left(), .get_by_right(), .remove_by_left(), .remove_by_right().

Entry API

We provide generic Entry API for types that have an Entry API: HashMap, BTreeMap, and indexmap::IndexMap.

Containers

For brevity and convenience, we also provide Container, Keyed, Scalarlike, Maplike, Setlike, Arraylike, and Veclike abstract container traits that join together traits of multiple operations.

Supported containers

Standard library

Rust's standard library containers 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, gated by the alloc feature (enabled by default);
• BTreeSet, gated by the alloc feature (enabled by default);
• Vec, gated by the alloc feature (enabled by default);
• VecDeque, gated by the alloc feature (enabled by default);
• Box, gated by the alloc feature (enabled by default);
• Rc and its weak pointer, std::rc::Weak, both gated by the alloc feature (enabled by default);
• Arc, and its weak pointer, std::sync::Weak, both gated by the std feature (enabled by default);
• Option, not feature-gated;

Primitives

All Rust's scalar types (i8, i16, i32, i64, i128, isize, u8, u16, u32, u64, u128, usize, f32, f64, char, bool, ()) are supported and treated as single-element, usize-keyed maps.

Rust's compound types (arrays, tuples, slices) are supported and treated as usize-keyed maps.

maplike's types

maplike provides and supports its own generic type, One, for a collection that always has only one element. Think Option, but without None. Or Box, but without pointer indirection, behaving like a collection despite holding a value not reference, allocated on the stack.

Wrap your value in this type if you need to treat it as a single-element, usize-keyed map and your type does not happen to be a Rust primitive.

Third-party types

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

• bidimap::BiBTreeMap, gated by the bidimap feature flag, and bidimap::BiHashMap, which is additionally gated by the std feature flag. bidimap is a maintained fork of the currently unmaintained bimap crate;
• indexmap::IndexMap and indexmap::IndexSet, gated by the indexmap feature flag;
• rstar::RTree, gated by the rstar feature flag;
• slab::Slab, gated by the slab feature flag (Insert is not implemented; see Technical sidenotes);
• slotmap::SlotMap, slotmap::DenseSlotMap, and slotmap::SecondaryMap, gated by the slotmap feature flag (Insert is not implemented for SlotMap or DenseSlotMap; see Technical sidenotes), and also slotmap::SparseSecondaryMap, which is additionally gated by the std feature flag; slotmap::HopSlotMap is not implemented because it's deprecated;
• stable_vec::StableVec, gated by the stable-vec feature flag;
• thunderdome::Arena, gated by the thunderdome feature flag;
• arrayvec::ArrayVec and arrayvec::ArrayString, gated by the arrayvec feature flag (individual vec-like traits, but not Veclike, because arrayvec types do not implement Index);
• smallvec::SmallVec, gated by the smallvec feature flag;
• thin_vec::ThinVec, gated by the thin-vec feature flag (individual vec-like traits, but not Veclike, because ThinVec does not implement Index);
• tinyvec::ArrayVec, and tinyvec::TinyVec, gated by the tinyvec feature flag;
• geometry types from geo/geo-types, gated by the geo feature flag: Coord, Point, Line, Rect, Triangle, Polygon, and Geometry are treated as single-element, usize-keyed maps; LineString, MultiPoint, MultiLineString, MultiPolygon, and GeometryCollection are treated as usize-keyed vec-like maps of their elements;

For some examples of practical use, see the examples directory of the undoredo crate.

Unsupported containers

Among stable vector data structures, generational-arena is not supported because it lacks an interface 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.

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 a slow O(n) time cost.

For SlotMap and DenseSlotMap, keys are generated by the map on insertion and cannot be chosen by the caller, so there is likewise no way to insert at an arbitrary key.

Because of that, we do not implement Insert for Slab, SlotMap, or DenseSlotMap, unlike other traits (and therefore they are also not Maplike).