rust - 如何在BinaryHeap的比较函数中使用外部数据结构？

Question

我正在尝试使用BinaryHeap，其中cmp函数需要在要比较的两件事外部使用HashMap。
阅读 How can I implement Ord when the comparison depends on data not part of the compared items?的答案后，我尝试通过将要比较的值与还存储对所需数据结构的引用的结构进行包装来做类似的事情:

use std::cmp::Ordering;
use std::collections::BinaryHeap;
use std::collections::HashMap;

#[derive(Copy, Clone, PartialEq, Eq, Hash)]
struct Foo {
    x: u8,
}

struct Bar {
    foos: Vec<Foo>,
}

impl<'a> Bar {
    pub fn new(size: u8) -> Bar {
        let mut bar = Bar {
            foos: Vec::with_capacity(size as usize),
        };

        for i in 0..size {
            bar.foos.push(Foo { x: i })
        }

        bar
    }

    pub fn func(&self) {
        #[derive(Eq, PartialEq)]
        struct FooWrapper<'a> {
            foo: &'a Foo,
            val_map: &'a HashMap<&'a Foo, u16>,
        }

        impl<'a> Ord for FooWrapper<'a> {
            fn cmp(&self, other: &FooWrapper) -> Ordering {
                let val_a = self.val_map[self.foo];
                let val_b = other.val_map[other.foo];
                val_b.cmp(&val_a).then_with(|| self.foo.x.cmp(&other.foo.x))
            }
        }

        impl<'a> PartialOrd for FooWrapper<'a> {
            fn partial_cmp(&self, other: &FooWrapper) -> Option<Ordering> {
                Some(self.cmp(other))
            }
        }

        let mut val_map = HashMap::new();
        val_map.insert(&self.foos[0], 5);
        val_map.insert(&self.foos[1], 2);
        val_map.insert(&self.foos[2], 3);

        let mut heap = BinaryHeap::new();
        heap.push(FooWrapper {
            foo: &self.foos[0],
            val_map: &val_map,
        });

        while !heap.is_empty() {
            let _f = heap.pop().unwrap().foo;
            //
            // Some other stuff
            //
            val_map.insert(&self.foos[0], 3);
        }
    }
}

fn main() {
    let bar = Bar::new(3);
    bar.func();
}

这导致错误:

error[E0502]: cannot borrow `val_map` as mutable because it is also borrowed as immutable
  --> src/main.rs:64:13
   |
56 |             val_map: &val_map,
   |                      -------- immutable borrow occurs here
...
59 |         while !heap.is_empty() {
   |                ---- immutable borrow later used here
...
64 |             val_map.insert(&self.foos[0], 3);
   |             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ mutable borrow occurs here

似乎 while !heap.is_empty() {会导致问题，因为没有该行我看不到此错误，但是找不到解决方法。
然后，我尝试使包装器中存储的 HashMap引用可变:

#[derive(Eq, PartialEq)]
struct FooWrapper<'a> {
    foo: &'a Foo,
    val_map: &'a mut HashMap<&'a Foo, u16>,
}

heap.push(FooWrapper {
    foo: &self.foos[0],
    val_map: &mut val_map,
});

结果是:

error[E0308]: mismatched types
  --> src/main.rs:44:31
   |
44 |                 Some(self.cmp(other))
   |                               ^^^^^ lifetime mismatch
   |
   = note: expected reference `&Bar::func::FooWrapper<'a>`
              found reference `&Bar::func::FooWrapper<'_>`
note: the anonymous lifetime #3 defined on the method body at 43:13...
  --> src/main.rs:43:13
   |
43 | /             fn partial_cmp(&self, other: &FooWrapper) -> Option<Ordering> {
44 | |                 Some(self.cmp(other))
45 | |             }
   | |_____________^
note: ...does not necessarily outlive the lifetime `'a` as defined on the impl at 42:14
  --> src/main.rs:42:14
   |
42 |         impl<'a> PartialOrd for FooWrapper<'a> {
   |              ^^

error[E0308]: mismatched types
  --> src/main.rs:44:31
   |
44 |                 Some(self.cmp(other))
   |                               ^^^^^ lifetime mismatch
   |
   = note: expected reference `&Bar::func::FooWrapper<'a>`
              found reference `&Bar::func::FooWrapper<'_>`
note: the lifetime `'a` as defined on the impl at 42:14...
  --> src/main.rs:42:14
   |
42 |         impl<'a> PartialOrd for FooWrapper<'a> {
   |              ^^
note: ...does not necessarily outlive the anonymous lifetime #3 defined on the method body at 43:13
  --> src/main.rs:43:13
   |
43 | /             fn partial_cmp(&self, other: &FooWrapper) -> Option<Ordering> {
44 | |                 Some(self.cmp(other))
45 | |             }
   | |_____________^

有没有办法使这项工作可行，或者有替代的途径？

Answer 1

我不知道那怎么工作。 IIUC，您在将项目添加到堆之后，更改了定义项目顺序的哈希映射。但是，如果顺序更改，则在重新组织以考虑新顺序之前，该堆将不再是堆。我不知道任何允许即时进行此类重组的通用堆实现，因此您可能需要自己进行滚动。
话虽这么说，并且考虑到重组成本，您最好将值存储在Vec中，并对最小值进行线性搜索:

use std::collections::HashMap;

#[derive(Copy, Clone, PartialEq, Eq, Hash)]
struct Foo {
    x: u8,
}

struct Bar {
    foos: Vec<Foo>,
}

impl<'a> Bar {
    pub fn new(size: u8) -> Bar {
        let mut bar = Bar {
            foos: Vec::with_capacity(size as usize),
        };

        for i in 0..size {
            bar.foos.push(Foo { x: i })
        }

        bar
    }

    pub fn func(&self) {
        let mut val_map = HashMap::new();
        val_map.insert(&self.foos[0], 5);
        val_map.insert(&self.foos[1], 2);
        val_map.insert(&self.foos[2], 3);

        let mut workset: Vec<_> = self.foos.iter().collect();

        while !workset.is_empty() {
            // Look for the "minimum" item
            let i = workset.iter().skip (1).enumerate().fold (0, |best, (k, x)| {
                if val_map[x] < val_map[workset[best]] { k } else { best }
            });
            let _f = workset.swap_remove (i);
            
            //
            // Some other stuff
            //
            val_map.insert(&self.foos[0], 3);
        }
    }
}

fn main() {
    let bar = Bar::new(3);
    bar.func();
}

Playground