vector-map

vector-map is a lightweight, no_std Rust crate that implements the familiar map and set APIs on top of a plain vector. Its VecMap<K, V> stores keys and values in two parallel Vecs and locates entries with a linear scan, which — thanks to cache-friendly, branch-predictable iteration over contiguous memory — is frequently faster than a HashMap for small collections.

Because it relies on equality rather than hashing or ordering, VecMap works with key types that are neither Hash nor Ord, requiring only PartialEq. The crate also ships a VecSet<T> built on the same foundation, optional Serde support, and a benchmark suite comparing it against linear_map.

What You Get

• A VecMap<K, V> type exposing the standard map API — get, insert, remove, contains_key, iterators, and indexing
• A VecSet<T> with set-algebra operators (union, intersection, difference, symmetric difference)
• no_std support, depending only on alloc, so it runs in embedded and constrained targets
• Optional Serde serialization behind the serde_impl feature flag
• A Criterion-style benchmark comparing performance against the linear_map crate

Common Use Cases

• Storing small maps (up to a few hundred entries) where linear search outperforms hashing
• Keying a map by types that implement only PartialEq and cannot be hashed or ordered
• Embedded or no_std projects that need a map without pulling in a hashing dependency
• Expressing map intent in code while avoiding the overhead of a full HashMap

Under The Hood

Architecture - VecMap<K, V> is a struct of two parallel vectors, keys: Vec<K> and values: Vec<V>, kept in lockstep so index i pairs keys[i] with values[i]. Lookups route through a private position helper that linearly scans keys for a PartialEq match, and get/get_mut/insert/remove all build on it; removal swaps the last element into the vacated slot, trading ordering guarantees for O(1) deletion. VecSet<T> in src/set.rs is a thin wrapper over VecMap<T, ()>. Defined in src/lib.rs.

Tech Stack - Pure Rust targeting the 2018 edition, declared #![no_std] and pulling in only alloc for Vec. The single optional runtime dependency is serde (behind the serde_impl feature); dev-dependencies are linear-map and rand for comparative benchmarks. Cargo feature flags gate Serde, nightly paths, contract checks, and slice exposure.

Code Quality - The code is compact and idiomatic, using generic bounds (Q: PartialEq<K>) to allow borrowed-key lookups and core::mem::swap for in-place value replacement. Inline unit tests live in src/lib.rs, doctests document VecSet construction, and a benchmark in benches/bench.rs validates the performance premise against linear_map.

API Design - The public surface deliberately mirrors std::collections::HashMap, so new, with_capacity, get, insert, remove, iter, and indexing behave as expected, easing adoption. The relaxed PartialEq-only bound is the key ergonomic win, and unsafe internals are cordoned off behind an opt-in feature to discourage misuse.