Как я могу реализовать Ord, когда сравнение зависит от данных, не являющихся частью сравниваемых элементов?

У меня есть небольшая структура, содержащая только i32:

struct MyStruct {
   value: i32,
}

Я хочу реализовать Ord для хранения MyStruct в BTreeMap или любой другой структуре данных, которая требует, чтобы у вас были Ord.

В моем случае сравнение двух экземпляров MyStruct не зависит от value в них, но запрашивает другую структуру данных (словарь) и что структура данных уникальна для каждого экземпляра 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 должен быть простой оболочкой, а указатель удваивает размер. Другим решением является использование статического глобального, но это не очень хорошее решение.

В С++ решение было бы простым: большинство алгоритмов STL/структуры данных позволяют передавать компаратор, где он может быть объектом функции с некоторым состоянием. Поэтому я считаю, что у Руста была бы такая идиома, чтобы соответствовать этому как-то, есть ли способ сделать это?

Ответы

Ответ 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);
}

Ответ 2

Rust (более конкретно, Rcol libcollections) в настоящее время не имеет подобной конструкции, поэтому использование изменчивого статика, вероятно, будет вашим лучшим выбором. Это также используется в rustc, например. строка interner статична. С учетом сказанного, прецедент не совсем необычен, поэтому, возможно, если мы будем ходатайствовать об этом, Rust однажды получит внешние компараторы.