I then mention that for other use cases, you can maintain a capacity field only in the part of the code where you need this.
Whether this is the right design for everybody, I do not know, but so far it is what I prefer for myself.
I then mention that for other use cases, you can maintain a capacity field only in the part of the code where you need this.
Whether this is the right design for everybody, I do not know, but so far it is what I prefer for myself.
However one possible issue is if someone pushes and pops repeated just at the boundary where f increases in value. To address that you would have to use more advanced techniques, and I think "cheat" by inspecting internal structures of the allocator.
Edit: malloc_usable_size could be used for this purpose I think.
I try do this here (this code is not tested and may not be up-to-date): https://github.com/uecker/noplate/blob/main/src/vec.h#L30
The issue with the boundary is what I meant with hysteresis in the article.
In all my current code where I tried it makes no noticeable difference, and I am not a fan of premature optimization. But then, I could always switch to the alternative API.
One valid reason might be that I can't rely on realloc not be poor, but then I would rather use my own special allocation function. Other valid reasons would be to have very precise control or certain guarantees, but then I would prefer a different interface. In any case, I do not think that this logic belongs into my vector. But it is also possible that I change my mind on this...
It can't preallocate, so when adding many items it will make many expensive realloc calls that could have been avoided. Though you could have an interface that allows pushing or popping many items at once to make up for it, but this is less convenient.
You can currently forgo shrinking on pop but you can't if mixing popping and pushing. You need to know the capacity for that, otherwise it may actually shrink on a consequent push. This could incur many expensive reallocs if used similarly to a stack.
Even the cheap realloc calls will cost more than checking an int in code that's likely small, inlined, and with its data in one cache line (number of items and capacity next to each other in one struct, which are also next to the first item). The realloc function is probably dynamically linked, more complex, and has to access additional data.
If you don't want to add more memory overhead to the vector, consider just using two ints and it won't be any larger, that's enough unless a vector should be many gigabytes. Otherwise if you think that's not enough and feel like leaning into the complexity instead, use bit fields or bit twiddling to split up one 64 bit int into say, 56+8 bit ints. Let the smaller int track additional capacity rather than total capacity and also use that to solve your hysteresis problem. Well, or just use two 64 bit ints, but what's the fun in that?
But realloc also does overallocate a little bit, and for large blocks it would remap the pages. The inlining argument makes sense though. (Edit: Pushing and then popping a billion integers takes about 2 seconds with std::vector<int>, 10 with vec(int) and realloc each time, and 4.3 seconds with a simple preallocation logic that does not require a capacity on my laptop. Having a call to "rand" in it already adds more overhead.).