当比较依赖于不属于比较项目的数据时，如何实现 Ord? [英] How can I implement Ord when the comparison depends on data not part of the compared items?

问题描述

我有一个只包含一个 i32 的小结构:

I have a small struct containing only an i32:

struct MyStruct {
   value: i32,
}

我想实现 Ord 以便将 MyStruct 存储在 BTreeMap 或任何其他需要 的数据结构中Ord 在其元素上.

I want to implement Ord in order to store MyStruct in a BTreeMap or any other data structure that requires you to have Ord on its elements.

就我而言，比较 MyStruct 的两个实例不依赖于其中的 value ，而是询问另一个数据结构(字典)，以及该数据结构对于我将创建的 BTreeMap 的每个实例都是唯一的.所以理想情况下它看起来像这样:

In my case, comparing two instances of MyStruct does not depend on the values in them, but asking another data structure (a dictionary), and that data structure is unique for each instance of the BTreeMap I will create. So ideally it would look like this:

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

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

However this won't be possible, since an Ord implementation only can access two instances of MyStruct, nothing more.

一种解决方案是将指向字典的指针存储在 MyStruct 中，但这太过分了.MyStruct 应该是一个简单的包装器，指针的大小会加倍.另一种解决方案是使用静态全局变量，但这也不是一个好的解决方案.

One solution would be storing a pointer to the dictionary in MyStruct but that's overkill. MyStruct is supposed to be a simple wrapper and the pointer would double its size. Another solution is to use a static global, but that's not a good solution either.

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

In C++ the solution would be easy: Most STL algorithms/data structures let you pass a comparator, where it can be a function object with some state. So I believe Rust would have an idiom to match this somehow, is there any way to accomplish this?

推荐答案

我记得关于允许自定义比较器是否值得的争论，并且决定这会使 API 变得非常复杂，当大多数时候可以通过使用新的(包装)类型并为其重新定义 PartialOrd 来实现相同的效果.

I remember the debate over whether allowing a custom comparator was worth it or not, and it was decided that this complicated the API a lot when most of the times one could achieve the same effect by using a new (wrapping) type and redefine PartialOrd for it.

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

It was, ultimately, a trade-off: weighing API simplicity versus unusual needs (which are probably summed up as access to external resources).

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

In your specific case, there are two solutions:

• 按照预期的方式使用 API:创建一个包含 MyStruct 实例和对字典的引用的包装器结构，然后在该包装器上定义 Ord 并使用它作为 BTreeMap
中的键
• 以某种方式绕过 API...

• use the API the way it was intended: create a wrapper structure containing both an instance of MyStruct and a reference to the dictionary, then define Ord on that wrapper and use this as key in the BTreeMap
• circumvent the API... somehow

我个人建议先按预期使用 API，然后再尝试规避它.

I would personally advise starting with using the API as intended, and measure, before going down the road of trying to circumvent it.

@ker 非常友好地提供了以下实现注释包装的示例(游乐场版本):

@ker was kind enough to provide the following illustration of achieving wrapping in comments (playground version):

#[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);
}

这篇关于当比较依赖于不属于比较项目的数据时，如何实现 Ord?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！