在稳定的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 night的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

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

它在safeRust中似乎不可行，至少在算法复杂度合理的情况下不可行。(请参阅Aiden4的答案，了解通过重建整个地图来实现这一点的解决方案。(

但是，如果你被允许使用不安全的，如果你下定决心想深入研究它，这个代码可以做到：

// 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

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

在安全锈蚀中你不能有效地做到这一点，但有可能：

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  
}

操场

这将对地图进行完全遍历，但是安全的。

Answer 3

我们甚至可以确定，使用安全Rust(撰写本文时为1.59版本(中当前提供的接口，不可能对映射进行适当的更改：

要提取关键点，我们需要查看地图的关键点"看看"；意味着在这里借款。这为我们提供了一个&K参考，它也借用了整个地图。

现在，一个问题出现了：要调用这些remove*方法中的任何一个，我们需要再次可变地借用映射，这是我们无法做到的，因为我们仍然持有对即将提取的密钥的引用-这些寿命重叠，它不会编译。

另一种方法可以是尝试获取Entry，但要通过.entry方法获取，我们也需要拥有一个K。