Repository navigation
Implement an inline-only growable (bounded) 'vector' #16998
Description
Activity
The full general form (rust-lang/rfcs#197 + integer in type system) would also be a solution to the problem of initializing a
[T, ..N]incrementally, as you could just build up a fixed capacity vector and then unwrap it.I think this is sort of a dupe of #16522
Yeah, definitely related, but not quite a dupe, that
SmallVec:- is unbounded, as it promotes to heap allocation beyond the limit;
- is larger than necessary for this (the
ptrandcapacitywords are unnecessary... even auintlength is unnecessary in many circumstances, I'm suren < 256in most cases, andlength: u8works there) - does unnecessary work (branching to decide on inline vs. heap when indexing etc.)
- reduces use-cases, this one can be used in environments without allocation.
(And as @Kimundi points out, this could be used as a low-overhead way to initialise fixed length arrays.)
👍 Yep, this would be way simpler than smallvec. Definitely needs integer type params, though. iirc there's a couple closed RFCs for this (can't for the life of me find them now).
@huonw Would you be interested in working on an RFC for this? (post 1.0, presumably)
Definitely needs integer type params
Only for the generic version; if this is needed/really wanted now, we can take the same approach as servo's smallvec and just hardcode the sizes required (e.g. have a macro that creates them).
(This is what my last paragraph refers to. :) )
Would you be interested in working on an RFC for this? (post 1.0, presumably)
Not at the moment, sorry.
hardcoded sizes make me sad 😢 (especially since BTree itself just wants this)
The BTree only needs a generic version of this type if the BTree is generic over integer types itself, and clearly if the latter happens we will be able to generalise this, so non-hardcoded sizes are an independent issue (at least, if this is an internal 'implementation detail'/
#[experimental]item insidecollections).Yes, sorry. I was simply referring to the fact that ideally B should be configurable in some static fashion.
So, it seems like default type parameters mean that we could go forward with a fixed-size variant and then seamlessly make it extensible in the future.
@nikomatsakis Not if we're providing a family of structs like InlineVec1, InlineVec2, InlineVec4, ...
However if this is just a purely internal thing, I suppose it could just be tailored to whatever BTree wants, and we can call it a day.
On Fri, Sep 05, 2014 at 08:10:06AM -0700, Alexis Beingessner wrote:
@nikomatsakis Not if we're providing a family of methods like InlineVec1, InlineVec2, InlineVec4, ...
Why not? Those wind up as aliases to InlineVec<1>, InlineVec<2>
etc. But I confess I was thinking that we just make InlineVec, tie it
N=32 or whaever we want, and then start working on an RFC for integer
generics to appear ASAP after 1.0 :)Hm, that also sounds like a reasonable approach, though pinpointing the exact default number of elements we want might be hard to do up front :)
I'm pulling a massive triage effort to get us ready for 1.0. As part of this, I'm moving stuff that's wishlist-like to the RFCs repo, as that's where major new things should get discussed/prioritized.
This issue has been moved to the RFCs repo: rust-lang/rfcs#863
Something like
[T, .. n]but with alengthfield (and the correct destructor), so it's valid to store anywhere from 0 uptonTs in it. This can haveTs dynamically pushed and popped, but attempting to push more thannwould be an error. I.e.(The error could either be
fail!or aResult<(), ...>return value.)This is useful for data structures like 2-4-trees, B-trees etc., where they have internal nodes that store a sequence of keys with variable, but bounded, length. At the moment the only safe way to encode this is either a heap allocation (
Vec) or with[Option<T>, .. n]where the "length" is modeled by storing[Some(x_1), Some(x_2), ..., Some(x_length), None, ..., None](this leads to a lot ofunwrapand unnecessary branches).rust-lang/rfcs#197 is related, to make the destructors work right. For full generality we would need integer type params, but we can certainly have an internal abstraction of this form in
collections(for use in btree etc.) with the lengths required hard-coded, and generalise/publish it later.