如何使用默认值为 HashMap 编写安全包装 [英] How to write a safe wrap for HashMap with default value

问题描述

我使用默认值为 HashMap 实现了一个包装，我想知道它是否安全.

I implemented a wrap for HashMap with default values and I would like to know if it's safe.

当 get 被调用时，内部映射可能会被调整大小，并且先前对值的引用(通过 get 获得)将指向无效地址.我试图使用计算机科学中的所有问题都可以通过另一个间接级别来解决"的想法来解决这个问题(巴特勒兰普森).我想知道这个技巧是否使这段代码安全.

When get is called, the internal map may be resized and previous references to values (obtained with get) would be pointing to invalid address. I tried to solve this problem using the idea that "all problems in computer science can be solved by another level of indirection" (Butler Lampson). I would like to know if this trick makes this code safe.

use std::cell::UnsafeCell;
use std::collections::HashMap;
use std::hash::Hash;

pub struct DefaultHashMap<I: Hash + Eq, T: Clone> {
    default: T,
    map: UnsafeCell<HashMap<I, Box<T>>>,
}

impl<I: Hash + Eq, T: Clone> DefaultHashMap<I, T> {
    pub fn new(default: T) -> Self {
        DefaultHashMap {
            default: default,
            map: UnsafeCell::new(HashMap::new()),
        }
    }

    pub fn get_mut(&mut self, v: I) -> &mut T {
        let m = unsafe { &mut *self.map.get() };
        m.entry(v).or_insert_with(|| Box::new(self.default.clone()))
    }

    pub fn get(&self, v: I) -> &T {
        let m = unsafe { &mut *self.map.get() };
        m.entry(v).or_insert_with(|| Box::new(self.default.clone()))
    }
}

#[test]
fn test() {
    let mut m = DefaultHashMap::new(10usize);
    *m.get_mut(4) = 40;
    let a = m.get(4);
    for i in 1..1024 {
        m.get(i);
    }
    assert_eq!(a, m.get(4));
    assert_eq!(40, *m.get(4));
}

(游乐场)

推荐答案

既然你不能¹ 改变从 get 返回的值，我只想返回一个对值缺失时的默认值.但是，当您调用 get_mut 时，您可以将该值添加到映射中，并将引用返回到新添加的值.

Since you cannot¹ mutate the value returned from get, I'd just return a reference to the default value when the value is missing. When you call get_mut however, you can then add the value to the map and return the reference to the newly-added value.

这样做的好处是不需要任何 unsafe 代码.

This has the nice benefit of not needing any unsafe code.

use std::{borrow::Borrow, collections::HashMap, hash::Hash};

pub struct DefaultHashMap<K, V> {
    default: V,
    map: HashMap<K, V>,
}

impl<K, V> DefaultHashMap<K, V>
where
    K: Hash + Eq,
    V: Clone,
{
    pub fn new(default: V) -> Self {
        DefaultHashMap {
            default,
            map: HashMap::new(),
        }
    }

    pub fn get_mut(&mut self, v: K) -> &mut V {
        let def = &self.default;
        self.map.entry(v).or_insert_with(|| def.clone())
    }

    pub fn get<B>(&self, v: B) -> &V
    where
        B: Borrow<K>,
    {
        self.map.get(v.borrow()).unwrap_or(&self.default)
    }
}

#[test]
fn test() {
    let mut m = DefaultHashMap::new(10usize);
    *m.get_mut(4) = 40;
    let a = m.get(4);
    for i in 1..1024 {
        m.get(i);
    }
    assert_eq!(a, m.get(4));
    assert_eq!(40, *m.get(4));
}

<小时>

[1]:从技术上讲，如果您的默认值包含内部可变性，这将有不同的行为.在这种情况下，对默认值的修改将应用于整个集合.如果这是一个问题，您需要使用更接近原始的解决方案.

---

[1]: Technically this will have different behavior if your default value contains internal mutability. In that case, modifications to the default value would apply across the collection. If that's a concern, you'd need to use a solution closer to your original.

这篇关于如何使用默认值为 HashMap 编写安全包装的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！