pop_if or Entry/Peek-like API for Vec and VecDeque

[avandesa]

Proposal

Problem statement

With the methods available on Vec and VecDeque, it is not possible to inspect a value at a given index (or at the front or back of the collection) and then modify or remove the value without at least one unwrap. An API similar to HashMap::entry or BinaryHeap::peek_mut would enable users to access an element and modify or remove it if it exists, or insert it if not.

Motivation, use-cases

Using the methods currently available on a Vec, here is how one would remove the last element if it fulfills a certain condition:

fn pop_if_even(v: &mut Vec<u32>) {
    if v.last().map(|item| *item % 2 == 0).unwrap_or(false) {
        let _popped = v.pop().unwrap(); // will never panic
        // do something with the popped value
    }
}

In the body of the if statement, we pop the value that we just inspected, but are forced to call unwrap even though there will always be a value present, since we just checked that the value fulfilled a condition. Having to call unwrap or expect on what will always be a Some is inelegant, and may require users to disable a lint rule.

More fundamentally, this pattern requires accessing the collection multiple times, when it could be seen as a single operation. Another use-case that has the same issue is modifying a value if it exists or inserting a new one if the collection is empty:

fn modify_or_insert(v: &mut Vec<u32>) {
    if let Some(last) = v.last_mut() {
        last *= 2;
    } else {
        v.push(0);
    }
}

There's nothing problematic about this snippet, but, like the first example, it could also benefit from an abstraction over the last value in a collection.

Solution sketches

Vec::pop_if

The initial, and simplest, suggestion is a Vec::pop_if method, which would remove the last element in the vec if there is at least one element and the element fulfilled a given predicate:

impl<T> Vec<T> {
    pub fn pop_if<F>(&mut self, predicate: F) -> Option<T>
        where F: FnOnce(&mut T) -> bool;
}

This solution fulfills the requirements of the first example. We can now conditionally remove an item with just one method call and no unwrapping:

fn pop_if_even_pop_if(v: &mut Vec<u32>) {
    if let Some(popped) = v.pop_if(|item| *item % 2 == 0) {
        // do something with the popped value
    }
}

A VecDeque would have similar pop_back_if and pop_front_if methods. remove_if and swap_remove_if could also be analogues to Vec::remove and Vec::swap_remove, respectively.

Peek

A slightly more complex but more powerful solution would be something simlar to BinaryHeap::peek_mut:

impl<T> Vec<T> {
    fn peek_mut(&mut self) -> Option<PeekMut<'_, T>>;
}

struct PeekMut<'a, T> { /* trim */ }

impl<'a, T> PeekMut<'a, T> {
    fn pop(self) -> T;
}

// impl `Deref` and `DerefMut` for `PeekMut`

The first example above would become this:

fn pop_if_even_peek(v: &mut Vec<u32>) {
    let Some(peek) = v.peek() else { return };
    if *peek % 2 == 0 {
        peek.pop();
    }
}

It would not have an effect on the modify_or_insert example.

We just have one method call on the collection itself, and no more unwrapping. We would also be able to perform more complex logic on the value without stuffing it into a closure.

This API also has a notable difference from the fn-based pop-if API: it separates the steps of checking whether the collection has an element (by calling peek) from accesing the element itself (by invoking Deref, calling pop, etc). In this way, it's more generic and flexible than pop_if, allowing more complex access patterns.

VecDeque would have similar peek_back and peek_front methods, though whether those would need separate structs depends on how it's implemented.

Entry

Another possible solution is an API analagous to HashMap::entry. Users request a specific index, and get an enum indicating whether that index is in-bounds for the collection or if it is the first empty index. If the index is valid, then users can edit the value. Otherwise, they can insert a value at the given index or into an empty collection.

impl<T> Vec<T> {
    /// Returns:
    /// * `Some<Entry::Occupied>` if `index < self.len()`
    /// * `Some<Entry::Vacant>` if `index == self.len()`
    /// * `None` if index > self.len()
    fn entry(&'a mut self, index: usize) -> Option<Entry<'a, T>>;
    /// Returns:
    /// * `Entry::Occupied` if there is at least one element
    /// * `Entry::Vacant` otherwise
    fn back_entry(&'a mut self) -> Entry<'a, T>;
    fn front_entry(&'a mut self) -> Entry<'a, T>;
}

enum Entry<'a, T> {
    Occupied(OccupiedEntry<'a, T>),
    Vacant(VacantEntry<'a, T>),
}

struct OccupiedEntry<'a, T> { /* trim */ }

struct VacantEntry<'a, T> { /* trim */ }

impl<'a, T> Entry<'a, T> {
    // Modify the value if present
    fn and_modify<F>(self, f: F) -> Self
        where F: FnOnce(&mut T);
    // Insert a value if not present
    fn or_insert(self, val: T) -> &mut T;
    // or_insert_with, or_default
}

impl<'a, T> Occupied<'a, T> {
    // Replace the value and return the old one
    fn replace(&mut self, val: T) -> T;
    // Remove the value with `Vec::remove`
    fn remove(self) -> T;
}

// impl `Deref` and `DerefMut` for `OccupiedEntry` or have `get` and `get_mut` methods

impl<'a, T> VacantEntry<'a, T> {
    // Insert a value
    fn push(self, val: T) -> &mut T;
}

Using this API, the given example would look like this (and like with Peek, would be simplified by if-let chains):

fn pop_if_even_entry(v: &mut Vec<u32>) {
    if let Entry::Occupied(entry) = v.back_entry() {
        if *entry % 2 == 0 {
            entry.remove();
        }
    }
}

However, it would also enable more complex usage:

fn halve_or_remove_or_init(v: &mut Vec<u32>) {
    match v.back_entry() {
        Entry::Occupied(occupied) => {
            if *entry % 2 == 0 {
                *entry /= 2;
            } else {
                entry.remove();
            }
        }
        Entry::Vacant(vacant) => {
            entry.push(0);
        }
    }
}

This Entry API has the same advantage over the pop_if method that Peek does, while also allowing users to access an arbitrary index in the collection rather than just the first or last elements. It also enables the use of a more fluent API for the modify_or_insert example:

fn modify_or_insert_entry(v: &mut Vec<u32>) {
    v.back_entry()
        .and_modify(|val| val *= 2)
        .or_insert(0);
}

However, this API can be significantly more complex to implement and use, and it's unclear whether arbitrary index access in this way adds significant value. One possibility is to restrict this API to only access the front or back of a collection (i.e., remove fn entry(index) -> Option<_>), making this very similar to the Peek API but with functionality to modify and replace values rather than just remove them.

Finally, it is worth noting that Peek and Entry are not mutually exclusive to the pop_if method. pop_if fulfills a rather specific use case, while Peek/Entry are abstractions over the same access pattern that pop_if would follow.

Links and related work

Zulip topic with the initial discussion

std::collections::hash_map::Entry

std::collections::binary_heap::PeekMut

[pitaj]

fn pop_if_even_peek(v: &mut Vec<u32>) {
    if let Some(peek) = v.peek() {
        if *v % 2 == 0 {
            v.pop();
        }
    }
}

I think *v and v.pop() should both refer to peek instead of v. (And you misspelled "Occupied" a few times.)

Also I'd note that your Entry API here seems to work with Deref, but the map ones do not.

[avandesa]

Thank you, fixed!

[EFanZh]

Related: rust-lang/rfcs#3082.

[joshtriplett]

Vec::peek should be called Vec::peek_mut. And pop_if should provide a &mut to the closure.

Other than that, 👍 to both pop_if and peek_mut.

[pitaj]

Would it be best to have the pop_if closure take a mutable reference instead? That would avoid the infamous retain_mut issue.

impl<T> Vec<T> {
    pub fn pop_if<F>(&mut self, predicate: F) -> Option<T>
        where F: FnOnce(&mut T) -> bool;
        //               ^^^
}

[joshtriplett]

@pitaj Yes, that's what I was proposing in #208 (comment) ; possibly our messages raced. :)

[pitaj]

Oh they didn't race, I just totally skipped over that portion of your comment. Woops

[avandesa]

Thank you both for your feedback, I've updated, the proposal.

• pop_if takes a mutable reference
• Peek becomes PeekMut

Should I remove the Entry section as well?

What would the next steps be to move this forward? Thanks!

[m-ou-se]

Feel free to open a tracking issue and open a PR to rust-lang/rust to add pop_if as an unstable feature.

And the same thing for peek/peek_mut. (Do add the naming as an unresolved question please, so we don't forget to think about peek vs peek_mut before stabilization.)