data-structures - 是否有 `Entry`的 `BTreeMap`机制允许返回不可变的引用？

Question

是否有Entry的BTreeMap机制可以返回不可变的引用？

请看下面的代码，它实现了一种稀疏向量。本质上，它是一个向量，假定除非特别设置和操作，否则元素为零:

// External libraries
use std::cell::{Ref, RefCell, RefMut};
use std::collections::BTreeMap;

// Stores a sparse vector
#[derive(Debug)]
struct MyVec {
    data: RefCell<BTreeMap<usize, f64>>,
}
impl MyVec {
    // Returns a reference to an element
    pub fn get<'a>(&'a self, i: usize) -> Ref <'a,f64> {
        // Insert a missing element
        let mut data = self.data.replace(BTreeMap::new());
        match data.get(&i) {
            Some(_) => (),
            None => {data.insert(i,0.0); ()}
        }
        self.data.replace(data);

        // Return the element
        Ref::map(self.data.borrow(), |data| data.get(&i).unwrap())
    }

    // Returns a mutable reference to an element
    pub fn get_mut<'a>(&'a self, i: usize) -> RefMut<'a, f64> {
        RefMut::map(self.data.borrow_mut(), |data| data.entry(i).or_insert(0.0))
    }

    // Create a new sparse vector
    pub fn new() -> MyVec {
        MyVec {
            data: RefCell::new(BTreeMap::new()),
        }
    }
}

fn main() {
    // Create a vector
    let x = MyVec::new();
    *x.get_mut(3) = 4.0;
    *x.get_mut(5) += 0.5;
    let x2 = *x.get(2);
    let x3 = *x.get(3);
    println!("x: {:?}, x[2]: {}, x[3]: {}", x, x2, x3);
}

这将返回结果:

x: MyVec { data: RefCell { value: {2: 0.0, 3: 4.0, 5: 0.5} } }, x[2]: 0, x[3]: 4

我的问题是，函数 get需要对 map 进行三个查找。它需要进行一次查找以确定数据是否存在，如果需要，则进行一次查找以插入该条目，如果不存在，则需要进行一次查找以返回数据。这与函数 get_mut形成对比，后者可以对元素进行单次查找，如有必要，插入缺失的零，然后返回可变引用。

如果需要，是否有更好的方法来插入缺少的元素，然后返回对结果的不可变引用？

Answer 1

您可以使用entry中or_insert中具有的get_mut + get链来组合第一次查找和插入。

让我们也摆脱所有'a的生命周期。 Rust推断的生命周期就足够了。

pub fn get(&self, i: usize) -> Ref<'_, f64> {
    self.data.borrow_mut().entry(i).or_insert(0.0);
    Ref::map(self.data.borrow(), |data| data.get(&i).unwrap())
}

(我不确定如何将其简化为单个查询。问题是我们需要可变地借用单元格以插入默认值，但是我们需要在函数结束之前返回可变的借用。如果有一种方法，一次查找就可以完成所有操作，但我无法解决。)

现在让我们谈谈API。返回 Ref和 RefMut的设计不是很好:它表明您的结构使用 RefCell，应该是实现细节。最好从 f64返回 get，从 &mut f64返回 get_mut。

另外， get_mut允许修改数据结构，因此应采用 &mut self。除非结构可变，否则您不应该允许突变。

impl MyVec {
    pub fn get(&self, i: usize) -> f64 {
        *self.data.borrow_mut().entry(i).or_insert(0.0)
    }

    pub fn get_mut(&mut self, i: usize) -> &mut f64 {
        self.data.get_mut().entry(i).or_insert(0.0)
    }
}

let mut x = MyVec::new();
*x.get_mut(3) = 4.0;
*x.get_mut(5) += 0.5;
let x2 = x.get(2);
let x3 = x.get(3);

assert_eq!(x2, 0.0);
assert_eq!(x3, 4.0);
assert_eq!(x.get(5), 0.5);

Playground

请注意，现在已将 x声明为 let mut x，以允许 get_mut调用，并且不再需要取消引用 get调用。另外，由于我们不返回引用，因此我们可以将 get压缩为单个查询(感谢 @loganfsmyth)。

您可能希望 get返回引用，而不是值的副本。不幸的是，很难安全地这样做。只要修改树，这些引用就可以失效。 get_mut可以安全地返回引用，因为一次只能有一个可变的借位。 get不能，因为定期借阅没有这样的限制。