Crate alist

alist

alist is a Rust crate for working with association lists, a simple data structure inspired by Lisp.

This implementation is backed by a Vec of key-value pairs, preserving the order of insertions and enabling optimized retrieval of items in O(1) under certain conditions.

What is an Association List?

An association list (alist) is a collection of key-value pairs. It provides a lightweight alternative to hash-based data structures for simple mappings or dictionary-like functionality, especially in contexts where order and immutability are crucial.

Like HashMap, this implementation does not allow multiple values for the same key, inserting a duplicate key overwrites the existing value.

Association lists often outperform hashmaps when working with small datasets, but their performance tends to degrade as the dataset grows larger.

This crate mitigates the typical performance drawbacks of association lists on larger datasets by leveraging the stable ordering of items in the list through the Bookmark API.

Items in the alist are stored in insertion order, which only changes when an element is removed. This property allows the creation of a “bookmark” for an item, significantly improving retrieval times.

A bookmark is essentially a record of the item’s position in the internal vector. If the item has not been moved, access to it is O(1). If the item has been moved, a linear search is performed, with a worst-case complexity of O(n).

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

• Data removal is infrequent.
• The dataset is small.
• The data type does not implement Hash or Ord, as this crate only requires items to implement Eq.

Key Features:

• Order Preservation: Items are stored in insertion order, which can be essential for certain applications.
• Optimized Retrieval: By leveraging the sequential nature of the underlying Vec, the implementation supports an optimization for retrieving items in O(1).
• 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("key1", "value1");
alist.insert("key2", "value2");

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

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

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

Macros

alist

Structs

AList

A association list (alist) implementation, backed by a Vec of key-value pairs.

Bookmark

IntoIter

IntoKeys

IntoValues

Iter

IterMut

Keys

OccupiedEntry

VacantEntry

Values

ValuesMut

Enums

Entry