MultiIndexMap

这是 lun3x/multi_index_map 的一个分支，供临时使用。如果更改合并到上游，可能会被删除。以下是上游crate的Readme。

在crates.io上也可用。

Rust库，用于存储需要通过结构体字段的多个不同索引进行访问的struct。受C++/Boost Multi-index Containers 启发，但为更符合Rust API风格而重新设计。

当前实现支持

• 使用来自 rustc-hash 的 FxHashMap 进行哈希索引。
• 使用来自 std::collections 的 BTreeMap 进行排序索引。
• 唯一和非唯一索引。
• 未索引字段。
• 每个索引字段的迭代器。
• 底层存储的迭代器。

性能特征

唯一索引

• 哈希索引检索是常数时间。（FxHashMap + Slab）。
• 排序索引检索是对数时间。（BTreeMap + Slab）。
• 遍历哈希索引与FxHashMap相同，但每个元素还需要从底层存储中进行检索。
• 遍历有序索引与BTreeMap相同，但每个元素还需要从底层存储中进行检索。
• 遍历底层存储与Slab相同，因此是连续内存，但可能有空槽。
• 插入、删除和修改的复杂度随着索引字段数量的增加而增加。在这些操作中，必须更新所有索引，因此它们较慢。
• 通过不安全mut方法修改未索引字段的时间与常规检索时间相同。
• 违反唯一性的插入或修改将导致 panic。

非唯一索引

• 哈希索引检索仍然是常数时间，与元素总数相关，但与匹配元素数量线性相关。（FxHashMap + (Slab * num_matches)）。
• 排序索引检索仍然是与元素总数相关的对数时间，但与匹配元素数量线性相关。（BTreeMap + (Slab * num_matches)）。
• 在非唯一索引的相等范围内进行迭代很快，因为匹配的元素在内存中连续存储。否则，迭代与唯一索引相同。

如何使用

此包提供了一个 derive 宏 MultiIndexMap，当应用于表示元素的 struct 时，将生成一个用于存储和访问这些元素的映射。使用注解来指定要索引的字段。目前支持 hashed_unique、hashed_non_unique、ordered_unique 和 ordered_non_unique。元素必须实现 Clone。

示例

use multi_index_map::MultiIndexMap;

#[derive(MultiIndexMap, Clone, Debug)]
struct Order {
    #[multi_index(hashed_unique)]
    order_id: u32,
    #[multi_index(ordered_unique)]
    timestamp: u64,
    #[multi_index(hashed_non_unique)]
    trader_name: String,
}

fn main() {
    let order1 = Order {
        order_id: 1,
        timestamp: 1656145181,
        trader_name: "JohnDoe".into(),
    };

    let order2 = Order {
        order_id: 2,
        timestamp: 1656145182,
        trader_name: "JohnDoe".into(),
    };

    let mut map = MultiIndexOrderMap::default();

    map.insert(order1);
    map.insert(order2);

    let orders = map.get_by_trader_name(&"JohnDoe".to_string());
    assert_eq!(orders.len(), 2);
    println!("Found 2 orders for JohnDoe: [{orders:?}]");

    let order1_ref = map.get_by_order_id(&1).unwrap();
    assert_eq!(order1_ref.timestamp, 1656145181);

    let order2_ref = map
        .modify_by_order_id(&2, |o| {
            o.timestamp = 1656145183;
            o.order_id = 42;
        })
        .unwrap();
    assert_eq!(order2_ref.timestamp, 1656145183);
    assert_eq!(order2_ref.order_id, 42);
    assert_eq!(order2_ref.trader_name, "JohnDoe".to_string());

    let orders = map.get_by_trader_name(&"JohnDoe".to_string());
    assert_eq!(orders.len(), 2);
    println!("Found 2 orders for JohnDoe: [{orders:?}]");

    let orders = map.remove_by_trader_name(&"JohnDoe".to_string());
    for (_idx, order) in map.iter() {
        assert_eq!(order.trader_name, "JohnDoe");
    }
    assert_eq!(orders.len(), 2);

    // See examples and tests directories for more in depth usage.
}

内部实现

上面的示例将生成以下 MultiIndexMap 和相关的迭代器。Order 存储在 Slab 中，在连续的内存中，这允许快速查找和快速迭代。为每个索引字段创建一个查找表，将索引键映射到 Slab 中的索引。这些的确切类型取决于注解。对于 hashed_unique 和 hashed_non_unique，使用 FxHashMap，对于 ordered_unique 和 ordered_non_unique，使用 BTreeMap。

• 在插入元素时，将其添加到后端存储中，然后将指向后端存储中索引的元素添加到每个查找表中。
• 在检索给定键的元素时，我们在查找表中查找键，然后检索后端存储中该索引处的项目。
• 在删除给定键的元素时，我们做同样的事情，但在返回元素之前必须从所有其他查找表中删除键。
• 在遍历索引时，我们使用查找表的默认迭代器，然后简单地从后端存储中检索给定索引处的元素。
• 在修改元素时，我们通过给定的键查找元素，然后应用闭包以原地修改元素。然后我们返回修改后元素的引用。然后必须更新所有查找表以反映索引字段的变化。如果我们只想修改未索引的字段，则直接修改该字段要快得多。这就是为什么提供了 unsafe 方法。这些方法可以用来快速修改未索引的字段，但不能用来修改索引字段。

struct MultiIndexOrderMap {
    _store: slab::Slab<Order>,
    _order_id_index: rustc_hash::FxHashMap<u32, usize>,
    _timestamp_index: std::collections::BTreeMap<u64, usize>,
    _trader_name_index: rustc_hash::FxHashMap<String, Vec<usize>>,
}

struct MultiIndexOrderMapOrderIdIter<'a> {
    ...
}

struct MultiIndexOrderMapTimestampIter<'a> {
    ...
}

struct MultiIndexOrderMapTraderNameIter<'a> {
    ...
}

impl MultiIndexOrderMap {
    fn insert(&mut self, elem: Order);
    
    fn len(&self) -> usize;
    fn is_empty(&self) -> bool;
    fn clear(&mut self);
    
    fn get_by_order_id(&self) -> Option<&Order>;
    fn get_by_timestamp(&self) -> Option<&Order>;
    fn get_by_trader_name(&self) -> Vec<&Order>;
    
    unsafe fn get_mut_by_order_id(&mut self) -> Option<&mut Order>;
    unsafe fn get_mut_by_timestamp(&mut self) -> Option<&mut Order>;
    unsafe fn get_mut_by_trader_name(&mut self) -> Vec<&mut Order>;
    
    fn modify_by_order_id(&mut self, f: impl FnOnce(&mut Order)) -> Option<&Order>;
    fn modify_by_timestamp(&mut self, f: impl FnOnce(&mut Order)) -> Option<&Order>;
    
    fn remove_by_order_id(&mut self) -> Option<Order>;
    fn remove_by_timestamp(&mut self) -> Option<Order>;
    fn remove_by_trader_name(&mut self) -> Vec<Order>;
    
    fn iter(&self) -> slab::Iter<Order>;
    unsafe fn iter_mut(&mut self) -> slab::IterMut<Order>;
    
    fn iter_by_order_id(&self) -> MultiIndexOrderMapOrderIdIter;
    fn iter_by_timestamp(&self) -> MultiIndexOrderMapTimestampIter;
    fn iter_by_trader_name(&self) -> MultiIndexOrderMapTraderNameIter;
}

依赖项

有关每个依赖项的信息，请参阅 Cargo.toml。

未来工作

• 允许用户指定要使用的哈希函数，而不是始终使用 FxHashMap。
• 对于具有整数索引的小表，向量-映射风格的查找表可能非常快。
• 在插入重复的唯一索引时允许覆盖行为，返回被覆盖元素的 Vec。
• 实现 boost::multi_index_containers 中使用的 巧妙技巧 以提高性能。