其他功能

• 泛型：映射键和集合元素可以是实现Ord和Default特质的任何类型。
• 任意可变：可以插入和删除元素，映射值可以修改。安全。

使用方法

SgMap非穷举，#![no_std] API 示例（对于std::collections::BTreeMap几乎相同）

use scapegoat::SgMap;
use tinyvec::{array_vec, ArrayVec};

// This const is an argument to each generic constructor below.
// So we'll use *only the bare minimum* memory for 5 elements.
// - Stack RAM usage can be precisely controlled: per map instance (constructor call-site).
// - To save executable RAM/ROM (monomorphization!), stick to a global capacity like this.
const CAPACITY: usize = 5;

let mut example = SgMap::<_, _, CAPACITY>::new(); // BTreeMap::new()
let mut static_str = "your friend the";

// Insert "dynamically" (as if heap)
example.insert(3, "the");
example.insert(2, "don't blame");
example.insert(1, "Please");

// Fallible insert variant
assert!(example.try_insert(4, "borrow checker").is_ok());

// Ordered reference iterator
assert!(example
    .iter()
    .map(|(_, v)| *v)
    .collect::<ArrayVec<[&str; CAPACITY]>>()
    .iter()
    .eq(["Please","don't blame","the","borrow checker"].iter()));

// Container indexing
assert_eq!(example[&3], "the");

// Head removal
let please_tuple = example.pop_first().unwrap();
assert_eq!(please_tuple, (1, "Please"));

// By-predicate removal
example.retain(|_, v| !v.contains("a"));

// Extension
let iterable = array_vec![
    [(isize, &str); CAPACITY] =>
    (1337, "safety!"), (0, "Leverage"), (100, "for")
];
example.extend(iterable.into_iter());

// Value mutation
if let Some(three_val) = example.get_mut(&3) {
    *three_val = &mut static_str;
}

// New message :)
assert!(example
    .into_values()
    .collect::<ArrayVec<[&str; CAPACITY]>>()
    .iter()
    .eq(["Leverage","your friend the","borrow checker","for","safety!"].iter()));

更多示例在这里。

堆栈容量：重要上下文

根据上述内容，const泛型类型参数决定了集合容量。因此，也决定了堆栈使用。这种使用是固定的

use core::mem::size_of_val;
use scapegoat::SgMap;

let small_map: SgMap<u64, u64, 100> = SgMap::new(); // 100 item capacity
let big_map: SgMap<u64, u64, 2_048> = SgMap::new(); // 2,048 item capacity

#[cfg(target_pointer_width = "64")]
#[cfg(not(feature = "low_mem_insert"))]
#[cfg(not(feature = "fast_rebalance"))]
{
    assert_eq!(size_of_val(&small_map), 2_680); // 2.7 KB
    assert_eq!(size_of_val(&big_map), 53_328);  // 53.3 KB
}

支持的最大容量是65_535（例如，0xffff或u16::MAX）项目。请注意

• 对于嵌入式平台，堆栈大小限制（受可用RAM限制）在制造商的数据表中指示。
• 在Linux上，主线程的默认堆栈限制为8MB，新生的线程为2MB（除非重写）。
• 在任意操作系统上运行cargo test，除非设置环境变量RUST_MIN_STACK，否则限制为2MB。

警告：尽管栈使用量是恒定的（无递归），但如果N（常量泛型容量）和/或存储的项目类型（泛型）过大，则在运行时可能会发生栈溢出。注意栈溢出与缓冲区溢出（Rust可以防止）是不同的。无论如何，您必须测试以确保您不会超过目标平台的栈大小限制。Rust只支持x86/x64上的栈探测，尽管已经提出了针对其他架构的创意链接解决方案。

有关高级配置选项，请参阅此处文档。

可信依赖项

此库有三个依赖项，每个依赖项都没有自己的依赖项（例如，总共有三个依赖项）。

• tinyvec - #![no_std]，#![forbid(unsafe_code)]是Vec的替代方案。
• micromath - #![no_std]，#![forbid(unsafe_code)]浮点近似。
• smallnum - #![no_std]，#![forbid(unsafe_code)]整数抽象。

由于此库及其所有依赖项都#![forbid(unsafe_code)]，因此不会将第三方unsafe代码引入到您的项目中。这最大限度地提高了内存安全的静态保证（通过Rust的类型系统强制执行）。除内存安全之外的鲁棒性和正确性属性通过差异模糊测试动态验证。

其他注意事项

总体目标

此项目是安全、便携式数据结构设计的一个练习。目标是向嵌入式开发者提供熟悉、易于使用的API，这些系统在其他情况下没有动态集合的奢侈。不会牺牲安全性。

scapegoat的速度或成熟度不如标准库的BTreeMap/BTreeSet（通过cargo bench进行基准测试）。标准库已经针对缓存性能进行了大量优化。此库针对低、仅栈的内存占用进行了优化。它提供

• 最佳兼容性：API 大部分是 BTreeMap 和 BTreeSet 的子集，因此它基本上可以作为 #![no_std] 系统的“即插即用”替代品。如果您需要的 API 还未得到支持，请 提交一个问题。

• 动态验证：使用 基于覆盖率、结构感知、差异模糊测试 来证明此实现在逻辑上是等价的，并且具有相同的可靠性。

• 可调性能：一个 单个浮点数值 优化了 insert、get 和 remove 操作类的相对性能。并且可以在运行时更改。

算法复杂度

空间复杂度始终为 O(n)。

内存占用演示

• 代码大小演示 - 调用 SgMap<usize, usize, 1024> 以及 insert、get 和 remove：x86-64 二进制文件的 14.2KB。注意：您可能需要使用超过 3 个函数，这将导致更多可执行代码被包含在内。

• 堆栈空间演示 - SgMap<u8, u8, 128>：存储成本为 1.3KB。注意：运行时需要更多的堆栈空间进行维护（例如，重新平衡）。

许可和贡献

遵循 MIT 许可协议。欢迎 贡献！