从 Ref<'a, BTreeSet<T>> 高效地获取 Vec<Ref<'a, T>>

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
}

A running example

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

即使使用 &'a BTreeSet<T> 和 &'a T 而不是 Ref<'a, BTreeSet<T>> 和 Ref<'a, T> 执行此操作也需要 O(n)（因为我们只需要收集引用在数组中迭代）。下面是使用普通引用的方法示例。

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

A running example

我的问题是：
鉴于 Ref<'a, BTreeSet<T>> 有没有办法在 O(n) 时间复杂度内获得 Vec<Ref<'a, T>>？

Answer 1

最简单的方法是引用 Ref 而不是 Ref:

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

Playground link

这样，Ref 可以比函数的寿命更长，这意味着您可以 return 借用 Ref 的引用，而无需处理临时借用。

请注意，这意味着您可以只使用 &'a BTreeSet<T> 而不必使用 Ref，因此您的 original code with references works.

从 Ref<'a, BTreeSet<T>> 高效地获取 Vec<Ref<'a, T>>

Efficiently get Vec<Ref<'a, T>> from Ref<'a, BTreeSet<T>>

rust

reference

time-complexity

refcell