Come posso implementare Ord quando il confronto dipende da dati che non fanno parte degli articoli confrontati?

Question

Ho una piccola struttura che contiene solo un i32:

struct MyStruct { 
    value: i32, 
} 

Voglio realizzare Ord per immagazzinare MyStruct in una o di qualsiasi altra struttura dati BTreeMap che richiede di avere Ord sui suoi elementi.

Nel mio caso, confrontando due istanze di MyStruct non dipende sui value s in loro, ma chiedendo un'altra struttura di dati (un dizionario), e che la struttura dei dati è unico per ogni istanza del BTreeMap creerò. Quindi idealmente sarebbe simile a questa:

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

Tuttavia questo non sarà possibile, dal momento che un Ord implementazione solo è possibile accedere a due istanze di MyStruct, niente di più.

Una soluzione potrebbe memorizzare un puntatore al dizionario in MyStruct ma è eccessivo. MyStruct dovrebbe essere un semplice wrapper e il puntatore raddoppierà le sue dimensioni. Un'altra soluzione è usare un sistema statico globale, ma neanche questa è una buona soluzione.

In C++ la soluzione sarebbe semplice: la maggior parte degli algoritmi/strutture di dati STL consente di passare un comparatore, dove può essere un oggetto funzione con uno stato. Quindi credo che Rust avrebbe un idioma per abbinarlo in qualche modo, c'è un modo per farlo?

Answer 1

Rust (più specificamente le libcollections di Rust) al momento non ha costrutto simile a comparatore, quindi usare una statica mutabile è probabilmente la soluzione migliore. Questo viene anche utilizzato all'interno di rustc, ad es. lo string interner è statico. Detto questo, il caso d'uso non è esattamente raro, quindi forse, se chiediamo una petizione, Rust otterrà comparatori esterni un giorno.

Answer 2

Ricordo il dibattito sull'opportunità o meno di consentire un comparatore personalizzato, e si è deciso che questo complicava molto l'API quando la maggior parte delle volte si poteva ottenere lo stesso effetto usando un nuovo tipo (involucro) e ridefinire PartialOrd per esso.

Era, in definitiva, un trade-off: pesare la semplicità dell'API rispetto a bisogni insoliti (che sono probabilmente riassunti come accesso a risorse esterne).

---

Nel suo caso specifico, ci sono due soluzioni:

• utilizza l'API modo si intendeva: creare una struttura di involucro contenente sia un'istanza di MyStruct e un riferimento al dizionario, allora definire Ord su quella fascia e di utilizzare questo come chiave nella BTreeMap
• aggirare le API ... in qualche modo

Personalmente suggerirei di iniziare a utilizzare l'API come previsto e misurare, prima di intraprendere la strada del tentativo di aggirarlo.

---

@ker è stato così gentile da fornire le seguenti illustrazione di raggiungere avvolgimento nei commenti (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); 
}