When pushing element to a vector, an exponential expansion logic is used to have constant-time amortized pushes.
However, in some situation you desire dynamic allocation, yet you know in advance that there's a limit of the possible number of elements.
For example, when making recursive depth-visit iterative one uses an explicit stack. The length of the visit path is usually much smaller than the number of vertices, so it makes sense to have a dynamic stack growing as needed, but the stack will never be longer than the number of vertices. For path lengths beyond half the number of vertices, it is likely the vector will be expanded beyond need.
I was wondering what would be the easiest way to implement a feature like that. Note that we cannot use something like bounded-vec because the upper limit is a constant.
Of course one can have a bounded_push method that checks whether there is enough capacity, and if not performes a reserve_exact of, say, twice the current len minimized with the upper bound. The downside is that this solution forces an expansion logic on Vec, which is not a good thing.
Messing up with Vec's internal does not seem doable either.
I'd wrap vec in a newtype with the custom reserve-as-needed logic in it, as you described. Another option is to use an extension trait, where you can add methods to vec that do what you need wrt custom expansion.
But I wonder if this is really neccessary. Have you measured, and determined the amount of overallocated memory by vec to be a problem serious enough to warrant a custom implementation like this?
Edit: sorry, I didn't see at first that you mentioned reserve_exact. Then I suppose your bounded push in an extension trait could be useful. Still, I would personally just call either of these methods once I know the expected length.
Let me repeat: there is no expected length. There is a maximum length we know we won't surpass, but in general the vector will be much shorter. with_capacity does exactly what we don't want to do—waste a lot of space when the vector will be actually shorter.
The newtype does not solve the problem of bypassing Vec's internal expansion logic, which we would like to preserve.
I don't see how that's possible without some new method to access std Vec's expansion logic, i.e., do the calculation of the new capacity without actually allocating. To preserve std Vec's expansion logic if it changes over time, the std Vec methods must be called. Yet that would violate the max capacity you want to enforce. Even if there were a crate that has a non-const bound (bounded-collections may allow this, but I can't quite tell), it would not be able to preserve the std Vec's expansion logic.
I mean if you have already reserved a controlled amount of extra capacity with reserve_exact before pushing, be it the maximum or less, it shouldn't reserve even more. Except for what the allocator adds, of course. A newtype could enforce this.
The absolute easiest thing to do is create the Vec with capacity that is a binary logarithm of this maximum capacity that you will not surpass.
For example, if this maximum is 10,000 elements, Vec::with_capacity(10_000 / 16) will reserve capacity for 625 elements and it will grow to 10,000 over 4 reallocs. But it will probably not grow to 20,000 due to your local constraint. This is a dumb example, but it illustrates the idea.
The much-more-effort solution is modeling a configurable capacity growth policy for standard library collections and pushing it through to stabilization. I don't think it's an unreasonable thing to want, but it is certainly uncommon. You may encounter some resistance simply due to this fact.
I could do that, but if they somehow change the Vec reallocation policy it will not work anymore (e.g., Go slices have a very complicated reallocation method that changes the multiplicative factor as the array grows).
Yeah, it depends on implementation details of the collection. That's an unfortunate downside. At least for now, Vec's amortized growth strategy is "double whatever the current capacity is".
Adjust your algorithm to match, by looking and the std Vec source and copying the algorithm if necessary so you can predict expanded capacity. This is unlikely, and at least it can be managed.
The alternative is to enhance std, as mentioned above or even perhaps to add a BoundedVec. As I said, without changes to std, logically there can be no other true solution, given your requirements.
So there is a cheap workaround, and an expensive true solution.
If you're willing to relax your requirements, you could explicitly implement the exponential expansion yourself, so there is no danger that changes to std Vec would impact you. This is a cheap solution, but doesn't meet your stated requirements.
If you want to control the resizing strategy use reserve_exact. If you want to use Vec's default resizing strategy use reserve. To push an item without triggering any resizing either check the capacity beforehand or use push_within_capacity.
Together those pieces give you the manual control from which you can build whatever behavior you want.
You will have to wrap the Vec (or &mut Vec) in your own newtype, and implement your own push that checks the capacity(), and uses (try_)reserve_exact() to grow using your custom rules.
You can use a new type and inplement a push_bounded() method that checks the vector length and capacity and decides if to let the vector expand naturally (capacity/2 < max) or use reserve_exact to allocate to the maximum permitted capacity. Yes, the capacity/2 is because you know the allocation policy but I don't see any way to do this without that bit of knowledge.
With the strategy everybody is talking about you will still have 2x memory overhead in the worst case because you may need to move the data from an n-1 capacity to n capacity, for a total of 2n-1 allocated at the same time (or 3n if you account for memory fragmentation)
You can avoid that with a double indirection in the data structure, where you allocate the data in fragments of size sqrt(n) and never move them.
What exactly do you want it to look like? Simultaneously not relying on implementation, not making your own and influencing it in strictly defined way? It looks like it is only achievable if Vec would gain a parameter for reallocating policy, which is either a new generic or a new struct member, and both are, obviously, not implementable for alloc::vec::Vec.