Crate alist 

alist

alist provides an insertion-ordered association list backed by a Vec.

The crate is no_std and uses alloc for owned storage.

This implementation is backed by a Vec of key-value pairs, preserving insertion order across insertions and removals and enabling optimized bookmark lookups in O(1) when the bookmarked item has not moved.

What is an Association List?

An association list (alist) is a collection of key-value pairs. It provides a lightweight alternative to hash-based and tree-based maps for simple mapping or dictionary-like functionality, especially when the dataset is small and iteration order matters.

Like HashMap, this implementation does not allow multiple values for the same key: inserting a duplicate key overwrites the existing value while preserving the key’s original insertion position.

Association lists can avoid hashing and ordering overhead for small datasets, but key-based operations scan linearly and degrade as the dataset grows. Use AList only for small inputs and only when keys satisfy FastEq’s intended contract: compact key types with cheap equality.

This crate mitigates repeated lookup costs by leveraging stored positions through the Bookmark API.

Items in the alist are stored in insertion order. Removing an item shifts later items left while preserving their relative order. Bookmarks account for that by validating and refreshing their stored position.

A bookmark is a record of the item’s position in the internal vector. If the item is still at that position, access is O(1). If it has moved, a linear search is performed, with a worst-case complexity of O(n), and the bookmark is refreshed.

Lookup Arguments

Lookup methods accept borrowed keys for one-off access. Methods such as AList::get, AList::get_mut, and AList::contains_key also accept mutable bookmarks so the cached position can be refreshed when needed. Removal methods accept borrowed keys or owned bookmarks; a bookmark is consumed when used for removal because removing the entry invalidates the cached position.

These features make alist a viable alternative to HashMap or BTreeMap in scenarios where:

• Data removal is infrequent.
• The dataset is small.
• Keys implement FastEq but do not need to implement Hash or Ord.

Choosing Key and Value Types

AList stores (K, V) pairs contiguously and performs linear scans for key lookup. This makes the size of K and V important: large keys or values increase the stride between entries and can reduce cache-line efficiency while scanning. Prefer compact keys and values, or store large values behind an indirection such as Box, Rc, or Arc.

Key equality also matters. Lookup compares keys repeatedly, so AList requires FastEq to keep lookup APIs focused on key types with cheap equality. String does not implement FastEq because its Eq implementation is O(n) in the string length. Prefer small identifiers, interned symbols, indices, or other compact keys when possible.

Key Features:

• Order Preservation: Items are stored in insertion order across insertions and removals.
• Optimized Retrieval: Bookmarks support O(1) access while their stored positions remain valid.
• Simplicity: A straightforward design that avoids the overhead of hash-based collections while providing robust functionality.

Example in Rust:

use alist::AList;

let mut alist = AList::new();
alist.insert('a', "value1");
alist.insert('b', "value2");

// Linear lookup
if let Some(value) = alist.get(&'a') {
    println!("Found: {}", value);
}

// Fast lookup
let mut k2 = alist.bookmark(&'b').unwrap();
assert_eq!(alist.get(&mut k2), Some(&"value2"));

// Overwriting a value
alist.insert('a', "new_value");
assert_eq!(alist.get(&'a'), Some(&"new_value"));

Macros

alist

Creates an AList from key-value pairs.

Structs

AList

An association list implementation backed by a Vec of key-value pairs.

Bookmark

A cached lookup handle for a key in an AList.

IntoIter

Owning iterator over key-value pairs in insertion order.

IntoKeys

Owning iterator over keys in insertion order.

IntoValues

Owning iterator over values in insertion order.

Iter

Iterator over borrowed key-value pairs in insertion order.

IterMut

Iterator over borrowed keys and mutable values in insertion order.

Keys

Iterator over borrowed keys in insertion order.

OccupiedEntry

A view into an occupied entry in an AList.

VacantEntry

A view into a vacant entry in an AList.

Values

Iterator over borrowed values in insertion order.

ValuesMut

Iterator over mutable value references in insertion order.

Enums

Entry

A view into a single key position in an AList.

Traits

FastEq

Marker trait for key types with trivial equality comparisons.