4 个版本
| 0.1.3 | 2023年1月31日 |
|---|---|
| 0.1.2 | 2021年3月2日 |
| 0.1.1 | 2021年2月28日 |
| 0.1.0 | 2021年2月28日 |
在 数据结构 中排名 #918
每月下载量 84,646
用于 23 个crate（4 直接使用）
26KB
393 行
assoc
将向量视为 关联数组。
示例
use assoc::AssocExt;
let mut map = vec![("a", 1), ("b", 2)];
map.entry("c").or_insert(3);
assert_eq!(map.get(&"c"), Some(&3));
assert_eq!(map.entry("c").or_insert(4), &3);
lib.rs:
AssocExt 是一个特质扩展，允许您将 [Vec] 当作映射使用。它提供了查询、添加和删除键值对的API，以及一个 Entry API。它对键没有其他约束，除了 PartialEq。
use assoc::AssocExt;
#[derive(PartialEq, Debug)]
enum MyKey {
A,
B,
C,
}
let mut map = vec![(MyKey::A, 1), (MyKey::B, 2)];
map.entry(MyKey::C).or_insert(3);
assert_eq!(map.get(&MyKey::C), Some(&3));
map.entry(MyKey::A).and_modify(|e| *e += 1).or_insert(9);
assert_eq!(map.get(&MyKey::A), Some(&2));
为什么？
std::collections 提供了两个映射：HashMap 和 BTreeMap。 HashMap 要求其键实现 Hash 和 [Eq]，而 BTreeMap 要求其键实现 [Ord] 和 [Eq]。 Hash 和 Ord 使映射数据结构的实现更高效；然而，它们对于通用映射数据结构不是必需的。当处理无法实现 Hash 或 Ord 的键时， std::collections 会有所不足。
例如，以下代码片段无法编译，因为 MyKey 没有实现 Hash
use std::collections::HashMap;
#[derive(PartialEq, Eq, Debug)]
enum MyKey {
A,
B,
C,
}
let map = vec![(MyKey::A, 1), (MyKey::B, 2)]
.into_iter()
.collect::<HashMap<MyKey, u64>>();
性能
通过 AssocExt 将 Vec 作为通用映射数据结构使用会带来查找效率低下的缺点。由于 AssocExt 无法依赖于键是否可哈希或可比较，所有需要查找的操作都会在底层向量上执行线性搜索。查询键 k 会引发与 k 的 O(N) 相等比较。
涉及频繁调整大小的流程应考虑使用 Vec 与 AssocExt，因为它在重新分配时利用了空间局部性。经验表明，当执行增长到约50个元素的操作时，Vec 比HashMap和BTreeMap更快。对于更大的映射，线性搜索的成本开始占主导地位。不出所料，Vec 比HashMap和BTreeMap具有更低的内存占用。
Entry API 消除了多次连续查找的需要（例如，检查键是否存在，如果不存在则添加键）。调用 AssocExt::entry 需要一个初始的线性搜索，然后在原地修改后提供常数时间访问。
PartialEq 与 Eq
Eq严格来说，映射的键应该实现 Eq，这也是为什么这个crate还提供了一个 AssocStrictExt 的原因。这个特质扩展的行为类似于 AssocExt，但要求 K: Eq。
当处理包含浮点数值的键时，这是一个值得注意的区别。由于 f32::NAN != f32::NAN，映射无法更新包含 f32::NAN 的键的现有条目。
use assoc::AssocExt;
let mut v = vec![(1.0, "a")];
v.entry(f32::NAN).or_insert("b");
v.entry(f32::NAN).or_insert("c");
assert_eq!(format!("{:?}", v), r#"[(1.0, "a"), (NaN, "b"), (NaN, "c")]"#);
在映射中使用浮点数作为键通常是一个代码味道，但对于不会遇到NaNs的使用场景，AssocExt 是一个很好的选择。