Emulate BTreeMap::pop_last in stable Rust 1.65 or older

Question

Editor's note: as of Rust 1.66.0, BTreeMap::pop_last has been stabilized.

---

In stable Rust 1.65 or older, is there a way to write a function equivalent to BTreeMap::pop_last?

The best I could come up with is:

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
}

It works, but it requires that the key is cloneable. BTreeMap::pop_last from Rust nightly imposes no such constraint.

If I remove the cloning like this

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
}

it leads to

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

Is there a way to work around this issue without imposing additional constraints on map key and value types?

Answer 1

Is there a way to work around this issue without imposing additional constraints on map key and value types?

It doesn't appear doable in safe Rust, at least not with reasonable algorithmic complexity. (See Aiden4's answer for a solution that does it by re-building the whole map.)

But if you're allowed to use unsafe, and if you're determined enough that you want to delve into it, this code could do it:

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

Playground