MultiIndexMap

同时在crates.io上可用。

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

当前实现支持

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

性能特征

唯一索引

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

非唯一索引

• 哈希索引检索仍然是常数时间，但与元素总数有关，而与匹配元素的数量有关，为线性时间。（FxHashMap + (Slab * num_matches)）
• 排序索引检索的总元素数仍然是对数时间复杂度，但与匹配元素的数量线性相关。（BTreeMap + (Slab * num_matches)）。
• 任何非唯一索引的相等范围都存储为BTreeSet，在检索所有匹配元素以及遍历整个索引时，必须遍历其长度。

如何使用

• 这个crate提供了一个 derive 宏 MultiIndexMap，将其应用于表示元素的struct时，将生成一个用于存储和访问这些元素的映射。
• 注释用于指定要索引的字段。目前支持 hashed_unique、hashed_non_unique、ordered_unique 和 ordered_non_unique。
• 所有索引字段的类型必须实现 Clone。
• 可选地，可以使用 multi_index_derive 来在生成的 MultiIndexMap 上派生特征，例如 #[multi_index_derive(Clone, Debug)] 更多详情请参阅 examples/main.rs。

示例

use multi_index_map::MultiIndexMap;

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

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

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

    let mut map = MultiIndexOrderMap::default();

    map.try_insert(order1).unwrap();
    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 order2_ref = map
        .update_by_order_id(&42, |filled: &mut bool, volume: &mut u64| {
            *filled = true;
            *volume = 0;
        })
        .unwrap();
    assert_eq!(order2_ref.filled, true);
    assert_eq!(order2_ref.volume, 0);

    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);

    println!("{map:?}");

    // 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。

• 在插入元素时，我们将其添加到后端存储，然后向每个查找表添加元素，指向后端存储中的索引。
• 在检索给定键的元素时，我们在查找表中查找键，然后从后端存储中检索该索引处的项。
• 在删除给定键的元素时，我们执行相同的操作，但在返回元素之前，我们必须从所有其他查找表中删除键。
• 在遍历索引时，我们使用查找表的默认迭代器，然后简单地从后端存储中检索给定索引处的元素。
• 在更新未索引的字段时，我们通过给定的键查找元素，然后对未索引的字段应用闭包以就地修改。然后返回修改后的元素（s）的引用。如果键不匹配，则不会应用闭包，并返回 Option::None。
• 在修改元素的索引字段时，我们执行相同的过程，但闭包接收整个元素的可变引用。可以修改任何字段，无论是索引还是未索引的。然后必须更新所有查找表以反映索引字段的变化，因此这比未索引更新要慢。

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, BTreeSet<usize>>,
}

struct MultiIndexOrderMapOrderIdIter<'a> {
    ...
}

struct MultiIndexOrderMapTimestampIter<'a> {
    ...
}

struct MultiIndexOrderMapTraderNameIter<'a> {
    ...
}

impl MultiIndexOrderMap {
    fn try_insert(&mut self, elem: Order) -> Result<&Order, MultiIndexMapError<Order>>;
    fn insert(&mut self, elem: Order) -> &Order;
    
    fn len(&self) -> usize;
    fn is_empty(&self) -> bool;
    fn clear(&mut self);
    
    fn get_by_order_id(&self, key: &u32) -> Option<&Order>;
    fn get_by_timestamp(&self, key: &u64) -> Option<&Order>;
    fn get_by_trader_name(&self, key: &String) -> Vec<&Order>;

    fn update_by_order_id(&mut self, key: &u32, f: impl FnOnce(&mut bool, &mut u64)) -> Option<&Order>;
    fn update_by_timestamp(&mut self, key: &u64, f: impl FnOnce(&mut bool, &mut u64)) -> Option<&Order>;
    fn update_by_trader_name(&mut self, key: &String, f: impl FnMut(&mut bool, &mut u64)) -> Vec<&Order>;
    
    fn modify_by_order_id(&mut self, key: &u32, f: impl FnOnce(&mut Order)) -> Option<&Order>;
    fn modify_by_timestamp(&mut self, key: &u64, f: impl FnOnce(&mut Order)) -> Option<&Order>;
    fn modify_by_trader_name(&mut self, key: &String, f: impl FnMut(&mut Order)) -> Vec<&Order>;
    
    fn remove_by_order_id(&mut self, key: &u32) -> Option<Order>;
    fn remove_by_timestamp(&mut self, key: &u64) -> Option<Order>;
    fn remove_by_trader_name(&mut self, key: &String) -> 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 中的巧妙技巧。