libs-team (original) (raw)

Proposal

Problem statement

Unlike almost all std collections, VecDeque<T> does not have a const fn new(). Also, there is currently no way to convert a Vec<T> into a VecDeque<T> without potentially reallocating.

Motivation, use-cases

The Rust std collections generally allocate lazily, allowing the constructor to be basically free and making almost all of the constructors const fns. Specifically, {Vec, LinkedList, BinaryHeap}::new are already const fn on stable, and {BTreeMap, BTreeSet}::new will become const fn with Rust 1.66. The fact that VecDeque::new isn't marked const seems like an unfortunate implementation detail, which will hopefully be able to be changed if this PR gets merged.

Since the current VecDeque<T> implementation is constrained to power-of-2 sizes only, converting a Vec<T> into a VecDeque<T> may have to reallocate the entire buffer. By guaranteeing that this conversion be O(1), it allows users to freely convert between Vec<T> and VecDeque<T> without ever reallocating and makes it trivial to e.g. turn an existing Vec<T> into a FIFO queue.

Solution sketches

If the VecDeque rewrite gets merged, all that would remain would be to mark VecDeque::new as a const fn, and to add a doc comment to the impl From<Vec<T>> for VecDeque<T> {...} stating that the conversion is guaranteed to be O(1) and to not reallocate. If the PR doesn't get merged, this ACP would probably need to be dropped until some other VecDeque<T> rewrite makes the changes possible.

rust-lang/rust#102991 (VecDeque rewrite PR)

What happens now?

This issue is part of the libs-api team API change proposal process. Once this issue is filed the libs-api team will review open proposals in its weekly meeting. You should receive feedback within a week or two.