ACP: Add `extend_front`, `extend_from_within`, `extend_from_within_front`, `prepend` and `splice` to `VecDeque`

[antonilol]

Proposal

Problem statement

Switching from Vec to VecDeque because efficient push and pop is needed at both ends can cost performance when already using methods like Vec::extend_from_within and Vec::splice. Such methods are not available on VecDeque.

Motivating examples or use cases

This came up in a self growing stack data structure where elements can be pushed and popped (from the back of the stack). In case there are no more items new items are created just in time. One can also get the last n elements (this calls self.grow_to(n), see below) as a slice. This currently uses Vec but I want to use VecDeque here so grow_to does not have to shift all elements. While I use splice here, this is actually a special case where extend_front would be the best. extend_from_within is also used in here, which currently does not exist on VecDeque.

pub(crate) struct Stack {
    elements: Vec<Expr>,
    next_element_id: u16,
}

impl Stack {
    fn grow_to(&mut self, min_len: usize) {
        if self.elements.len() >= min_len {
            return;
        }

        let to_insert = min_len - self.elements.len();
        self.next_element_id += to_insert as u16;
        self.elements.splice(
            0..0,
            (0..to_insert)
                .map(|i| Expr::Stack(StackExpr::new(self.next_element_id - i as u16 - 1))),
        );
    }

    pub fn extend_from_within_back(&mut self, amount: usize, offset: usize) {
        self.grow_to(amount + offset);

        let to = self.len() - offset;
        let from = to - amount;
        self.elements.extend_from_within(from..to);
    }

    // ...
}

Solution sketch

pub struct Splice<...> { ... } // like vec::Splice but for VecDeque

impl<T> VecDeque<T> {
    pub fn prepend(&mut self, other: &mut Self);

    pub fn splice<R, I>(&mut self, range: R, replace_with: I) -> Splice<'_, I::IntoIter, A>
    where
        R: RangeBounds<usize>,
        I: IntoIterator<Item = T>;
}

impl<T: Clone> VecDeque<T> {
    pub fn extend_from_within<R>(&mut self, src: R)
    where
        R: RangeBounds<usize>;

    pub fn extend_from_within_front<R>(&mut self, src: R)
    where
        R: RangeBounds<usize>;
}

Not sure about extend_front yet (asked these questions in rust-lang/rust#146861 before, but they should really be in this ACP):

• extend allows iterators that yield &T where T is Clone, should extend_front do too?
• Does this need a whole new trait like Extend or only a method on VecDeque?
• Should extend_front act like repeated pushes to the front of the queue? This reverses the order of the elements. Doing it different might incur an extra move if the iterator length is not known up front (where do you start placing elements in the buffer?).

Alternatives

All these methods can be written in terms of existing APIs, but may not perform optimally. As an example, extend_from_within can be emulated by cloning the needed elements to a new collection and then using VecDeque::extend. This needs an additional copy and collection. splice also looks costly to emulate, as far as I can tell.

prepend could be written in a separate crate, but that crate would need to reimplement private VecDeque helpers like to_physical_idx. The rest relies on specialization, so would need explicit methods like VecDequeExt::extend_from_within_copy to match the performance.

Links and related work

Feature request: rust-lang/rust#69939
First try at implementing extend_front: rust-lang/rust#146861

What happens now?

This issue contains an API change proposal (or ACP) and is part of the libs-api team feature lifecycle. Once this issue is filed, the libs-api team will review open proposals as capability becomes available. Current response times do not have a clear estimate, but may be up to several months.

Possible responses

The libs team may respond in various different ways. First, the team will consider the problem (this doesn't require any concrete solution or alternatives to have been proposed):

• We think this problem seems worth solving, and the standard library might be the right place to solve it.
• We think that this probably doesn't belong in the standard library.

Second, if there's a concrete solution:

• We think this specific solution looks roughly right, approved, you or someone else should implement this. (Further review will still happen on the subsequent implementation PR.)
• We're not sure this is the right solution, and the alternatives or other materials don't give us enough information to be sure about that. Here are some questions we have that aren't answered, or rough ideas about alternatives we'd want to see discussed.

[Amanieu]

We discussed this in the @rust-lang/libs-api meeting today. We were particularly concerned about the potential confusion around the order in which extend_front inserts elements into the VecDequeue. It is very reasonable for users to want to prepend a slice of items in that order. We therefore decided to use the following naming convention:

• "prepend" preserves the order of elements.
• "extend_front" pushes elements one at a time at the front.

Therefore we would like to see these methods:

impl<T> VecDeque<T> {
    // Preserves order of elements.
    pub fn prepend<I>(&mut self, other: I)
    where
        I: IntoIterator<Item = T>,
        I::Iter: DoubleEndedIterator
    {
        self.extend_front(other.into_iter().rev())
    }

    // Reverses order of elements.
    pub fn extend_front<I>(&mut self, other: I)
    where
        I: IntoIterator<Item = T>;

    pub fn splice<R, I>(&mut self, range: R, replace_with: I) -> Splice<'_, I::IntoIter, A>
    where
        R: RangeBounds<usize>,
        I: IntoIterator<Item = T>;
}

impl<T: Clone> VecDeque<T> {
    pub fn extend_from_within<R>(&mut self, src: R)
    where
        R: RangeBounds<usize>;

    // Preserves order of elements.
    pub fn prepend_from_within<R>(&mut self, src: R)
    where
        R: RangeBounds<usize>;
}

[Amanieu]

This ACP is accepted with the changes above.

Please open a tracking issue and open a PR to rust-lang/rust to add it as an unstable feature. You can close this ACP once the tracking issue has been created.

[antonilol]

Opened tracking issue: rust-lang/rust#146975