rust - 高效获取 Vec> 来自 Ref<'a, BTreeSet>

Question

我有一个Ref<'a, BTreeSet<T>>，我想将其内容的引用作为Vec<Ref<'a, T>>.
一种方法是：

fn get_refs<'a, T: Ord>(btree: Ref<'a, BTreeSet<T>>) -> Vec<Ref<'a, T>> {
    let mut result = Vec::new();
    for e in btree.iter() {
        result.push(Ref::map(Ref::clone(&btree), |t| t.get(&e).unwrap()))
    }
    result
}

一个运行的例子

现在让n为 的大小btree。
因为从二叉树中获取值需要O(log(n))并且因为遍历二叉树需要O(n)这种方法具有时间复杂度O(n log(n))。

&'a BTreeSet<T>即使用and&'a T代替Ref<'a, BTreeSet<T>>and这样做（因为我们只Ref<'a, T>需要O(n)收集在数组中迭代的引用）。使用普通引用的方法示例如下。

fn get_refs<'a, T: Ord>(btree: &'a BTreeSet<T>) -> Vec<&'a T> {
    btree.iter().collect()
}

一个运行的例子

我的问题是：
有Ref<'a, BTreeSet<T>>没有办法提高Vec<Ref<'a, T>>时间O(n)复杂度？

Answer 1

最简单的方法是引用 aRef而不是 a Ref：

fn get_refs<'a, T>(btree: &'a Ref<BTreeSet<T>>) -> Vec<&'a T> {
    btree.iter().collect()
}

游乐场链接

这样，theRef可以比函数的生命周期更长，这意味着您可以返回借用 the 的引用，而Ref无需处理借用临时数据。

请注意，这意味着您可以只使用&'a BTreeSet<T>而不使用Refs，因此您的原始代码与引用有效。