CODEWITHSUNDEEP
rust
Andrei Matveiakin
Andrei Matveiakin

Reputation: 1818

Emulate BTreeMap::pop_last in stable Rust 1.65 or older

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?

Upvotes: 21

Views: 1119

Answers (3)

user4815162342
user4815162342

Reputation: 154911

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

Upvotes: 10

Niklas Mohrin
Niklas Mohrin

Reputation: 1918

We can even be sure that it is not possible to mutate the map in-place with the current offer of interfaces in safe Rust (version 1.59, at the time of writing):

To extract the key, we need to look the keys of the map. "Look at" implies borrowing here. This gives us a &K reference that also borrows the entire map.

Now, a problem arises: To call any of these remove* methods, we need to mutably borrow the map again, which we cannot do since we still hold the reference to the key that we are about to extract - these lifetimes overlap and it won't compile.

Another approach could be to try to get hold of the Entry, but to get one through the .entry method, we need have an owned K too.

Upvotes: 2

Aiden4
Aiden4

Reputation: 2654

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

You can't do it efficiently in safe rust, but it is possible:

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  
}

playground

This will do a full traversal of the map but is safe.

Upvotes: 5

Related Questions