时间戳

首页 > 解决方案 > 如何在 BinaryHeap 的比较函数中使用外部数据结构？

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

问题描述

我正在尝试使用一个函数BinaryHeap，该cmp函数需要使用HashMap被比较的两件事的外部。

在阅读了当比较依赖于数据而不是比较项目的一部分时如何实现 Ord的答案后？，我尝试通过将要比较的值与一个结构进行比较来做类似的事情，该结构还存储对所需数据结构的引用：

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 | |             }
   | |_____________^

有没有办法使这项工作，或替代路径？

标签： rust

解决方案

I don't see how that could work. IIUC, you change the hash map that defines the order of your items after you have added the items to the heap. But if the order changes, then the heap is no longer a heap until it is reorganized to take into account the new order. I don't know of any general-purpose heap implementation that allows such reorganizing on the fly, so you'd probably need to roll your own.

That being said, and given the reorganizing costs, you're probably better off storing your values in a Vec and doing a linear search for the min:

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

推荐阅读