Lib.rs

› 数据结构
#vec #hash-set #unique-identifier #hash-table #set #identifiable #orderset

identified_vec

类似于HashSet，但保留插入顺序且无需在元素类型上要求Hash

作者：Alexander Cyon

8个版本

0.1.11 2023年12月22日
0.1.10 2023年12月21日

#741 在 数据结构


用于 identified_vec_macros

MIT 许可证

82KB
982 行

identified_vec

Code Coverage Crates.io Documentation Rust

一组唯一的可识别元素，保留了插入顺序，灵感来源于Pointfree的Swift Identified Collections。

与标准Vec类似，IdentifiedVec按照用户指定的顺序维护其元素。然而，与Vec不同，IdentifiedVec引入了唯一标识元素的能力，使用哈希表确保没有两个元素具有相同的身份，并有效地查找对应特定标识符的元素。

IdentifiedVec在需要通过稳定的标识符高效访问唯一元素时，是Vec的有用替代品。它也是BTreeSet的有用替代品，其中Ord特质的要求可能过于严格；它也是HashSet的有用替代品，其中Hash特质的要求可能过于严格。

您可以使用任何实现了Identifiable特质的元素类型来创建标识符向量。

示例

extern crate identified_vec;
use identified_vec::{IsIdentifiedVec, IdentifiedVec, Identifiable, IdentifiedVecOf};
use std::cell::RefCell;

#[derive(Eq, PartialEq, Clone, Debug)]
struct User {
    id: &'static str,
    name: RefCell<&'static str>,
}

impl User {
    fn new(id: &'static str, name: &'static str) -> Self {
        Self {
            id,
            name: RefCell::new(name),
        }
    }
    fn name(&self) -> &'static str {
        *self.name.borrow()
    }
}

Identifiable

impl Identifiable for User {
    type ID = &'static str;
    fn id(&self) -> Self::ID {
        self.id
    }
}

from_iter

let mut users = IdentifiedVecOf::<User>::from_iter([
    User::new("u_42", "Satoshi Nakamoto"),
    User::new("u_1337", "Leia Skywalker"),
]);

assert_eq!(
    users.get(&"u_42").map(|u| u.name()),
    Some("Satoshi Nakamoto")
);

assert_eq!(
    users.get_at_index(1).map(|u| u.name()),
    Some("Leia Skywalker")
);

append & elements()

users.append(User::new("u_237", "Alan Turing"));
assert_eq!(
    users.elements(),
    [
        User::new("u_42", "Satoshi Nakamoto"),
        User::new("u_1337", "Leia Skywalker"),
        User::new("u_237", "Alan Turing"),
    ]
    .iter()
    .collect::<Vec<&User>>()
);

// Element with same ID is not appended:
users.append(User::new("u_42", "Tom Mervolo Dolder"));
assert_eq!(
    users.elements(),
    [
        User::new("u_42", "Satoshi Nakamoto"),
        User::new("u_1337", "Leia Skywalker"),
        User::new("u_237", "Alan Turing"),
    ]
    .iter()
    .collect::<Vec<&User>>()
);

update_or_insert

// Element with same ID replaces existing if an `update_*` method is used:
// e.g. `update_or_insert`:
users.update_or_insert(User::new("u_42", "Tom Mervolo Dolder"), 0);
assert_eq!(
    users.elements(),
    [
        User::new("u_42", "Tom Mervolo Dolder"),
        User::new("u_1337", "Leia Skywalker"),
        User::new("u_237", "Alan Turing"),
    ]
    .iter()
    .collect::<Vec<&User>>()
);

update_or_append

// or `update_or_append`
users.update_or_append(User::new("u_237", "Marie Curie"));
assert_eq!(
    users.elements(),
    [
        User::new("u_42", "Tom Mervolo Dolder"),
        User::new("u_1337", "Leia Skywalker"),
        User::new("u_237", "Marie Curie"),
    ]
    .iter()
    .collect::<Vec<&User>>()
);

或者，您还可以提供一个闭包来描述元素的标识

let numbers = IdentifiedVec::<u32, u32>::new_identifying_element(|e| *e);

动机

标准集合中没有哪一个BTreeSet和HashSet保留插入顺序，Vec保留了插入顺序，但是允许重复。因此，如果您想要一个保留插入顺序的唯一元素集合（类似于Set），则IdentifiedVec符合您的需求。更好的是，元素无需实现Hash或Ord。

标志

此crate具有以下Cargo功能

  • serde：为 IdentifiedVecOf 类型启用 serde 序列化支持（其中 Element 实现 Identifiable 特性）。
  • id_prim：为原始类型获取 Identifiable 特性的实现：i8，.., i128， u8， ..., u128 和 bool（不是很有用，仅允许在 IdentifiedVecOf 中存储两个元素，但谁又能评判是非呢。）

实现细节

一个已标识的向量由一个保持插入顺序的 Vec 的 ID 和一个 HashMap 的 id-元素对组成，用于在给定 ID 的情况下以常数时间查找元素。

许可证

在 MIT 许可证下授权（LICENSE-MIT 或 https://opensource.org/licenses/MIT）

依赖项

~250–760KB
~18K SLoC