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

Question

I have a Ref<'a, BTreeSet<T>> and I would like to get the references of its content as Vec<Ref<'a, T>>.
One method to do this is:

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

Now let n be the size of btree.
Because getting a value from a binary tree takes O(log(n)) and because iterating through a binary tree takes O(n) this method has time complexity O(n log(n)).

Even though doing this in with &'a BTreeSet<T> and &'a T instead of Ref<'a, BTreeSet<T>> and Ref<'a, T> takes O(n) (Because we only need to collect the references iterated in an array). An example of the method using plain references is the following.

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

A running example

My question is:
Given Ref<'a, BTreeSet<T>> is there a way to get Vec<Ref<'a, T>> in O(n) time complexity?

Answer 1

The easiest way is to take a reference to a Ref instead of a Ref:

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

Playground link

This way, the Ref can live longer than the life of your function, which means you can return references that borrow the Ref without dealing with borrowing a temporary.

Note that this means you can just work with &'a BTreeSet<T> instead and not even have to work with Refs, so your original code with references works.