Change VecDeque::new() to not use any allocation

[bluss]

Allocation free empty collections are very useful, for example for algorithms where a large portion of its cases don't need to store any elements.

[Gankra]

👍 as long as it can be done without significantly affecting perf.

[ticki]

Maybe new_empty() or new_no_alloc()?

[bluss]

@ticki I don't think it needs a new method for it. Main issue is that I don't see an easy way to make a no allocation VecDeque into a valid state that we can handle without more complicated conditionals to check capacity. I didn't spend too long time trying to implement it, though.

👎 I'd rather not. This violates RAII, IMO, and you can just use Option<VecDeque<T>> if not allocating until the last moment is necessary.

Changing my mind because I didn't know about the behaviour with Vec::new.

[bluss]

How does it violate RAII? It would only bring VecDeque into the behavior that Vec already has. Vec::new() does not allocate.

[huonw]

@Undeterminant, hm, I'm missing the connection between not allocating and RAII, e.g. Vec is extremely RAII-y but Vec::new() doesn't allocate. Using Option has non-trivial overhead (mainly for the programmer, but also at runtime), so that doesn't seem like a particularly nice solution.

[ranma42]

It looks like most methods go though the computation of len()... has anybody already tried using head and len instead of head and tail to evaluate if the code worsen (in readability and/or performance)?

Now that you mention it, you're right. I was under the assumption that all of these containers allocated on creation.

[Gankra]

This is completely out of cache, but I recall that head + len was indeed an inferior representation. Happy to be wrong, 'course.

[Gankra]

Note that rust-lang/rust#30426 "regresses" BTreeMap to behave like VecDeque.

[bluss]

I don't think that's correct? In the present code, BtreeMap::new calls Node::make_leaf_root(6), which allocates.

[Gankra]

@bluss Ah, I was just going off the PR's description. I've long since forgot such details :)

[Centril]

Closing in favor of rust-lang/rust#68990.