ACP: Add extend_front, extend_from_within, extend_from_within_front, prepend and splice to VecDeque (original) (raw)

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, 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 VecDeque { 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 { pub fn extend_from_within(&mut self, src: R) where R: RangeBounds;

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):

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.

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):

Second, if there's a concrete solution: