alist

alist is a Rust crate that implements association lists, inspired by Lisp, as a lightweight alternative to HashMap and BTreeMap. The list is backed by a Vec of key-value pairs and keeps insertion order across insertions and removals. It offers bookmarks for efficient repeated lookup and is particularly well-suited for small datasets. Key-based operations scan linearly, so AList should be used only for small inputs and only with keys that meet FastEq's intended contract: compact key types with cheap equality.

Features

• Order Preservation: Keys and values are stored in insertion order across insertions and removals.
• Bookmark API: Reuse a stored position for O(1) lookup when the bookmarked item has not moved; otherwise lookup falls back to a scan and refreshes the bookmark.
• FastEq Keys: Lookup and insertion APIs require FastEq, an Eq marker trait for types with trivial equality comparisons.
• Convenience: Includes iterators for keys, values, and entries, as well as standard collection utilities like retain, clear, and shrink.

When to Use alist

• Small datasets only; key-based lookups, replacement insertions, removals, and entry access are O(n).
• Applications that rely on predictable insertion order.
• Compact keys that implement FastEq, have cheap equality, and 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 choice of K and V part of the performance model:

• Prefer compact keys and values. Large keys or values increase the stride between entries and can reduce cache-line efficiency during scans.
• Prefer keys with trivial equality. Lookup compares keys repeatedly, so an expensive Eq implementation can dominate runtime.
• String does not implement FastEq because string equality is O(n) in the string length. Prefer small identifiers, interned symbols, indices, or other compact keys when using AList.
• If values are large, consider storing an indirection such as Box, Rc, or Arc so scans move across compact pairs.

Installation

Add alist to your Cargo.toml:

cargo add alist

or edit your Cargo.toml manually by adding:

[dependencies]
alist = "0.2"

Examples

Creating an AList and Adding Items

use alist::AList;

let mut alist = AList::new();
alist.insert('a', 42);
alist.insert('b', 99);

assert_eq!(alist.get(&'a'), Some(&42));
assert_eq!(alist.len(), 2);

Using the bookmark API:

use alist::AList;

let mut alist = AList::new();
alist.insert('a', 42);
alist.insert('b', 99);

let mut bookmark = alist.bookmark(&'a').unwrap();

assert_eq!(alist.get(&mut bookmark), Some(&42));

Safety and Coverage

This crate contains no unsafe code.

Contributions

Contributions are always welcome! If you have ideas for new operations or improvements, feel free to open an issue or submit a pull request.

License

This crate is licensed under the MIT License. See LICENSE for more details.