Make VecDeque::new const, add guarantee for O(1) Vec<T> -> VecDeque<T> conversion

[Sp00ph]

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.

Links and related work

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.

[Sp00ph]

I forgot to mention it, but obviously this would also include VecDeque::new_in becoming const.

[scottmcm]

As a bonus if the O(1) conversion happens, we could delegate VecDeque: FromIterator to Vec: FromIterator, getting a bunch of optimization for free (by not needing to reimplement them on VecDeque) and potentially saving a bunch of monomorphization work too (since collecting an iterator into either container type can reuse the same code).

(Could even spell it impl<I, T> FromIterator<I> for VecDeque<T> where Vec<T>: FromIterator<I> and never again worry about keeping them in sync.)

[Sp00ph]

I've actually tried this before (in my original deque implementation, not in stdlib code), and it was noticably slower than the manual implementation. I'm not exactly sure why that is, maybe I just did something wrong or forgot to mark it #[inline] or something.

[Sp00ph]

The relevant PR got merged, so I don't think there's any more blockers for this ACP now.

[scottmcm]

I'd love to have this. It'd be amazing to change the answer for "how do I remove a bunch of things from the front of a Vec?" to change from "well, let me tell you about a bunch options with into_iter and drain and ..." to "It's O(1) to convert it to a VecDeque, so just do that -- you can always convert it back again for just the unavoidable data movement cost anyway if you still need a Vec".

[dtolnay]

Seconded

[scottmcm]

An additional fun thing this will let us do: collect a vec::IntoIter<T> into a VecDeque<T> in O(1).

@Sp00ph with the second here, I think you're clear to open a PR with these changes -- the constifying and the documentation promises. You can r? it to dtolnay to kick off the FCP to get full-team consensus and have it mentioned in TWiR so the broader community will have time to raise any potential worried that hadn't previously been identified.

[Sp00ph]

@scottmcm I probably need to add #[rustc_const_stable] to VecDeque::new then right? What about VecDeque::new_in, considering that's still a nightly only API? Also, do I just set feature = "none" or make up a feature name, or is there a more involved process?

[scottmcm]

Oh, right. Probably the official way is you first make a doesn't-need-FCP change to make it unstably const, for which you'd open a tracking issue using the template in https://github.com/rust-lang/rust/issues/new/choose. And yes, you just make up the tracking issue name.

Then the FCP-needing PR would change it from rustc_const_unstable to rustc_const_stable.

(I'd be tempted to just go straight to stable, since it's not some complicated new compile-time functionality, but I don't know if just having an ACP is enough for that. Up to libs-api how strict they'd want to be.)

[Sp00ph]

So what's the best approach then in your opinion? Should I wait until I get confirmation from the libs-api team about whether I can go straight to stable? Or should I just open a PR going straight to stable and then fall back to the full process in case that PR gets rejected?

[scottmcm]

My default answer is do whatever's easier, and then if libs-api says to do something else do that 🙃

[dtolnay]

Let's pick up the discussion in the 3 PRs. Thank you @Sp00ph!

• Make VecDeque::new const rust#105127
• Make VecDeque::new_in unstably const rust#105126
• Add O(1) Vec -> VecDeque conversion guarantee rust#105128