sortedvec

文档

一个纯 Rust 库，它公开宏，用于在 Ord 键上生成数据结构，比常规的 Vec 更快地查找 (O(log(n)) 与 O(n))，并且比哈希表更简单、更节省内存。它非常适合小型查找表，其中插入和删除操作很少。

注意： sortedvec 仍然是实验性的，其接口可能会更改。

示例

use sortedvec::sortedvec;

sortedvec! {
    struct SortedVec {
        fn derive_key(x: &u32) -> u32 { *x }
    }
}

let unsorted = vec![3, 5, 0, 10, 7, 1];
let sorted = SortedVec::from(unsorted.clone());

// linear search (slow!)
let unsorted_contains_six: Option<_> = unsorted.iter().find(|&x| *x == 6);
assert!(unsorted_contains_six.is_none());

// binary search (fast!)
let sorted_contains_six: Option<_> = sorted.find(&6);
assert!(sorted_contains_six.is_none());

基准测试

下表显示了在标准库的 HashMap、SortedVec 和 Vec 中，字符串和整数键的查找如何扩展。

变更日志

• 0.5.0:
  • sortedvec_slicekey! 宏的引入。
  • position 方法的引入。
  • 通过将它们与数据结构相关联，解决了键派生函数命名冲突。这将键派生名称固定为 derive_key。这是一个 重大更改。
• 0.4.1：第一个公共版本。