qubit-collections 0.2.4

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 O(log n)
Detach or extract a range containing k records O(k log n)
Storage O(n)

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