qubit-collections 0.2.6

Custom collection types for specialized access and traversal patterns
Documentation

Qubit Collections

Rust CI Coverage Crates.io Rust License 中文文档

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

[dependencies]
qubit-collections = "0.2"

Quick start

use qubit_collections::map::OrderedIndexMap;

let mut deadlines = OrderedIndexMap::new();
deadlines.insert("later", 20, "second");
deadlines.insert("earlier", 10, "first");

let first = deadlines.first().expect("an attached deadline exists");
assert_eq!(&"earlier", first.key());

// Detaching affects only the ordered view and gives direct value access.
let detached = deadlines.detach("earlier").expect("record is attached");
assert_eq!(&"first", detached.value());
drop(detached);
assert_eq!(Some(&"first"), deadlines.get("earlier"));
assert_eq!(
    vec![&"second"],
    deadlines.values_ordered().collect::<Vec<_>>(),
);

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
cargo test

# Run tests with all declared features
cargo test --all-features

# Project CI checks
./.infra/bin/ci-check.sh

# Check code coverage
./.infra/bin/coverage.sh

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