在稳定的 Rust 1.65 或更早版本中模拟 BTreeMap::pop_last

Question

编者注：从Rust 1.66.0开始，BTreeMap::pop_last已经稳定下来。

---

在稳定的 Rust 1.65 或更早版本中，有没有办法编写相当于BTreeMap::pop_last 的函数？

我能想到的最好的办法是：

fn map_pop_last<K, V>(m: &mut BTreeMap<K, V>) -> Option<(K, V)>
where
    K: Ord + Clone,
{
    let last = m.iter().next_back();
    if let Some((k, _)) = last {
        let k_copy = k.clone();
        return m.remove_entry(&k_copy);
    }
    None
}

它可以工作，但它要求密钥是可克隆的。Rust nightly 中的 BTreeMap::pop_last 没有施加这样的约束。

如果我像这样删除克隆

fn map_pop_last<K, V>(m: &mut BTreeMap<K, V>) -> Option<(K, V)>
where
    K: Ord,
{
    let last = m.iter().next_back();
    if let Some((k, _)) = last {
        return m.remove_entry(k);
    }
    None
}

它导致

error[E0502]: cannot borrow `*m` as mutable because it is also borrowed as immutable
  --> ...
   |
.. |     let last = m.iter().next_back();
   |                -------- immutable borrow occurs here
.. |     if let Some((k, _)) = last {
.. |         return m.remove_entry(k);
   |                ^^------------^^^
   |                | |
   |                | immutable borrow later used by call
   |                mutable borrow occurs here

有没有办法解决这个问题，而不对映射键和值类型施加额外的约束？

Answer 1

有没有办法解决这个问题，而不对映射键和值类型施加额外的约束？

它在安全的Rust中似乎不可行，至少在合理的算法复杂度下不可行。（有关通过重新构建整个地图来实现此目的的解决方案，请参阅 Aiden4 的答案。）

但是，如果您被允许使用 unsafe，并且您有足够的决心想要深入研究它，那么以下代码可以做到这一点：

// Safety: if key uses shared interior mutability, the comparison function
// must not use it. (E.g. it is not allowed to call borrow_mut() on a
// Rc<RefCell<X>> inside the key). It is extremely unlikely that such a
// key exists, but it's possible to write it, so this must be marked unsafe.
unsafe fn map_pop_last<K, V>(m: &mut BTreeMap<K, V>) -> Option<(K, V)>
where
    K: Ord,
{
    // We make a shallow copy of the key in the map, and pass a
    // reference to the copy to BTreeMap::remove_entry(). Since
    // remove_entry() is not dropping the key/value pair (it's returning
    // it), our shallow copy will remain throughout the lifetime of
    // remove_entry(), even if the key contains references.
    let (last_key_ref, _) = m.iter().next_back()?;
    let last_key_copy = ManuallyDrop::new(std::ptr::read(last_key_ref));
    m.remove_entry(&last_key_copy)
}

操场

Answer 2

有没有办法解决这个问题，而不对映射键和值类型施加额外的约束？

您无法在安全 Rust 中有效地做到这一点，但这是可能的：

fn map_pop_last<K, V>(m: &mut BTreeMap<K, V>) -> Option<(K, V)>
where
    K: Ord,
{
    let mut temp = BTreeMap::new();
    std::mem::swap(m, &mut temp);
    let mut iter = temp.into_iter();
    let ret = iter.next_back();
    m.extend(iter);
    ret  
}

操场

这将完全遍历地图，但很安全。