当比较取决于数据而不是比较项目的一部分时,如何实现Ord？

Question

我有一个只包含以下内容的小结构i32:

struct MyStruct {
   value: i32,
}

我想实现Ord,以便存储MyStruct一个BTreeMap或任何其他需要您拥有Ord其元素的数据结构.

在我的例子中,比较两个实例MyStruct并不依赖value于它们中的s,而是要求另一个数据结构(字典),并且该数据结构对于BTreeMap我将创建的每个实例都是唯一的.理想情况下,它看起来像这样:

impl Ord for MyStruct {
    fn cmp(&self, other: &Self, dict: &Dictionary) -> Ordering {
        dict.lookup(self.value).cmp(dict.lookup(other.value))
    }
}

然而,这是不可能的,因为Ord实现只能访问两个实例MyStruct,仅此而已.

一种解决方案是存储指向字典的指针,MyStruct但这样做太过分了.MyStruct应该是一个简单的包装器,指针会增加一倍.另一个解决方案是使用静态全局,但这也不是一个好的解决方案.

在C++中,解决方案很简单:大多数STL算法/数据结构允许您传递比较器,它可以是具有某种状态的函数对象.所以我相信Rust会有一个成语来以某种方式匹配它,有什么方法可以实现这一点吗？

Answer 1

我记得关于是否允许自定义比较器是否值得讨论的争论,并且当大多数时候通过使用新的(包装)类型并且重新定义它时,决定使API复杂化很多PartialOrd. .

这最终是一种权衡:权衡API简单性与异常需求(可能总结为访问外部资源).

在您的具体情况下,有两种解决方案:

• 按照预期的方式使用API​​:创建一个包含MyStruct字典的实例和引用的包装器结构,然后Ord在该包装器上定义并将其用作键中的键.BTreeMap
• 以某种方式规避API ......

我个人建议在开始试图规避它之前,先按照预期使用API​​并进行测量.

@ker非常友好地提供了以下关于在评论中实现包装的说明(游乐场版本):

#[derive(Eq, PartialEq, Debug)]
struct MyStruct {
   value: i32,
}

#[derive(Debug)]
struct MyStructAsKey<'a> {
    inner: MyStruct,
    dict: &'a Dictionary,
}

impl<'a> Eq for MyStructAsKey<'a> {}

impl<'a> PartialEq for MyStructAsKey<'a> {
    fn eq(&self, other: &Self) -> bool {
        self.inner == other.inner && self.dict as *const _ as usize == other.dict as *const _ as usize
    }
}

impl<'a> Ord for MyStructAsKey<'a> {
    fn cmp(&self, other: &Self) -> ::std::cmp::Ordering {
        self.dict.lookup(&self.inner).cmp(&other.dict.lookup(&other.inner))
    }
}

impl<'a> PartialOrd for MyStructAsKey<'a> {
    fn partial_cmp(&self, other: &Self) -> Option<::std::cmp::Ordering> {
        Some(self.dict.lookup(&self.inner).cmp(&other.dict.lookup(&other.inner)))
    }
}

#[derive(Default, Debug)]
struct Dictionary(::std::cell::RefCell<::std::collections::HashMap<i32, u64>>);

impl Dictionary {
    fn ord_key<'a>(&'a self, ms: MyStruct) -> MyStructAsKey<'a> {
        MyStructAsKey {
            inner: ms,
            dict: self,
        }
    }
    fn lookup(&self, key: &MyStruct) -> u64 {
        self.0.borrow()[&key.value]
    }
    fn create(&self, value: u64) -> MyStruct {
        let mut map = self.0.borrow_mut();
        let n = map.len();
        assert!(n as i32 as usize == n);
        let n = n as i32;
        map.insert(n, value);
        MyStruct {
            value: n,
        }
    }
}

fn main() {
    let dict = Dictionary::default();
    let a = dict.create(99);
    let b = dict.create(42);
    let mut set = ::std::collections::BTreeSet::new();
    set.insert(dict.ord_key(a));
    set.insert(dict.ord_key(b));
    println!("{:#?}", set);
    let c = dict.create(1000);
    let d = dict.create(0);
    set.insert(dict.ord_key(c));
    set.insert(dict.ord_key(d));
    println!("{:#?}", set);
}

Answer 2

Rust(更具体地说是Rust的libcollections)目前没有类似比较器的构造,所以使用可变静态可能是你最好的选择.这也用在内rustc,例如字符串内部是静态的.话虽如此,用例并不完全不常见,所以也许如果我们请求它,Rust有一天会得到外部比较器.