Qubit Collections
Focused Rust collection types for query patterns not directly represented by the standard library.
Overview
Qubit Collections starts with OrderedIndexMap<K, O, V>, a primary-key map
with an independently managed ordered secondary index. It supports fast lookup
by K, earliest-entry and bounded-prefix operations by O, duplicate order
keys with stable attachment order, explicit attached/detached states, bounded
range cursors, and entries that remain in the primary map after leaving the
ordered index. Primary keys are stored once and do not need to be cloneable.
The crate uses hashbrown's raw hash-table abstraction for its private
primary-key index. It does not use slotmap: a compact private
Vec<Option<_>> arena is sufficient because slot identifiers never escape the
map. The crate provides no internal synchronization. A map is Send and
Sync when its components are; wrap shared mutable access in the
synchronization primitive appropriate for its owner.
Available collections
| Category | Type | Import path |
|---|---|---|
| Map | OrderedIndexMap |
qubit_collections::map::OrderedIndexMap |
Complexity
| Operation | Complexity |
|---|---|
| Lookup or value mutation by primary key | Average O(1) |
| Inspect the smallest attached record | O(log n) |
| Insert, replace, remove, attach, detach, or reorder one record | Average/amortized O(log n) |
Detach or extract a range containing k records |
Average/amortized O(k log n) |
| Storage | O(c + a) |
Here, n is the current number of primary records, a is the number of
attached records, and c is the retained capacity scale of primary storage.
Reservations and past peaks can make c much larger than n. Primary storage
retains capacity after removals and clear; its allocation can reflect a
previous peak or explicit reservation rather than the current record count.
Detaching retains the primary record. Dropping the map releases its owned
allocations, while allocator behavior determines whether process memory usage
decreases immediately.
Time bounds assume well-distributed hashes and constant-cost hashing, equality, ordering, cloning, and destruction. Growth costs are amortized across operations. A single insertion can perform linear work when primary storage grows or its hash index is rebuilt under these assumptions; the table is not a per-call latency guarantee. Severe hash collisions can degrade primary-key operations to linear time. Range extraction also performs primary-index removal for each yielded record.
Installation
[]
= "0.2"
Quick start
use OrderedIndexMap;
let mut deadlines = new;
deadlines.insert;
deadlines.insert;
let first = deadlines.first.expect;
assert_eq!;
// Detaching affects only the ordered view and gives direct value access.
let detached = deadlines.detach.expect;
assert_eq!;
drop;
assert_eq!;
assert_eq!;
Index lifecycle
Every insertion starts attached. pop_first, remove, and extract_range
delete complete records. detach and detach_range retain primary records and
return value access without another hash lookup; attach restores ordered
visibility. set_order changes the retained order while preserving the
attachment state. insert replaces an occupied primary key, while try_insert
rejects duplicates and returns the untouched key, order, and value.
get_entry, iter, iter_ordered, range, and first expose a record's key,
order, value, and IndexState. values_ordered is the concise path for
downstream code that only needs values. The primary key and order are not
directly mutable because changing either without rebuilding its index would
violate collection invariants. The same restriction applies to changes made
through interior mutability.
Invalid ranges panic when the start exceeds the end or equal endpoints are
both excluded. Dropping detach_range or extract_range early affects only
records already yielded. Attachment order uses a u64 sequence; exhausting it
panics, while clear resets the sequence allocator.
If user-provided hashing, equality, ordering, cloning, or destruction code panics after a cross-index mutation starts, the map becomes poisoned and rejects later operations. Discard that instance instead of observing a partially updated index.
Testing
# Run tests with the default feature set
# Run tests with all declared features
# Project CI checks
# Check code coverage
License
Copyright (c) 2025 - 2026. Haixing Hu. All rights reserved.
Licensed under the Apache License, Version 2.0. See LICENSE for the full license text.
Contributing
Contributions are welcome. Please follow the Rust API guidelines, keep public
API documentation and tests current, and run ./.infra/bin/align-ci.sh to format code and
./.infra/bin/ci-check.sh to satisfy CI requirements before submitting a pull request.
Author
Haixing Hu - Qubit Co. Ltd.
Repository: https://github.com/qubit-ltd/rs-collections