lib.rs:

使静态容器动态化

有时从预定的数据集构建某些数据结构比在构建后实现一种更新此数据结构的方法要容易得多。

例如，当数据已知时，构建一个完全平衡的搜索树是微不足道的，但保持其平衡在添加/删除一些元素后就不那么容易了。

此 crate 为数据结构没有合理插入方法的情况提供了一种经济的解决方案。

示例

假设您有一个排序向量

struct SortedVec<T> {
    vec: Vec<T>
}

impl<T: Ord> FromIterator<T> for SortedVec<T> {
    fn from_iter<I>(iter: I) -> Self where
        I: IntoIterator<Item=T>
    {
        let mut vec: Vec<_> = iter.into_iter().collect();

        vec.sort();

        SortedVec { vec }
    }
}

这几乎是许多用例的完美数据结构，但每个插入的平均时间复杂度是数组的线性。

此 crate 提供了一个结构 Dynamic

use dynamization::Dynamic;

type DynamicSortedVec<T> = Dynamic<SortedVec<T>>;

该功能将存储数据分组到不同大小的独立单元中。单元的大小选择是为了使单个元素的插入平均为对数。

使Dynamic工作所需做的唯一一件事是实现Static特征

use dynamization::Static;

impl<T: Ord> Static for SortedVec<T> {
    fn len(&self) -> usize { 
        self.vec.len() 
    }

    fn merge_with(self, other: Self) -> Self {
        // Only for documentation purposes: two sorted arrays can be merged 
        // much more efficiently than sorting the concatenation result!
        self.vec.into_iter().chain(other.vec).collect()
    }
}

现在DynamicSortedVec有了add_unit方法。

还可以实现可选的特征Singleton，以使insert方法可用

use dynamization::Singleton;

impl<T> Singleton for SortedVec<T> {
    type Item = T;
    
    fn singleton(item: Self::Item) -> Self {
        SortedVec { vec: vec![item] }
    }
}

现在您可以使用DynamicSortedVec作为一个相当高效的通用数据结构

let mut foo = DynamicSortedVec::new();
for x in vec![(1, "one"), (5, "five"), (4, "four"), (3, "tree"), (6, "six")] {
    foo.insert(x);
}

// Each query now must be implemented in terms of partial containers:
foo.units_mut().filter_map(|unit| {
    unit.vec
        .binary_search_by_key(&3, |pair| pair.0)
        .ok()
        .map(move |index| &mut unit.vec[index])
}).for_each(|three| {
    assert_eq!(three, &(3, "tree"));
    three.1 = "three";
});

// A dynamic structure can be "freezed" with .try_collect():
assert_eq!(foo.try_collect().unwrap().vec, vec![
    (1, "one"),
    (3, "three"),
    (4, "four"),
    (5, "five"),
    (6, "six"),
]);