alt Hacker Newscapacity isn't stored at all. Instead, it's computed on demand when the length of the vec is either zero or a power of two.
Brilliant insight. This is the first time I've seen this observation in over 3 decades of working with C.
Replies
Really? It's been done plenty and I thought was quite common knowledge. Some of the <stdbit.h> provided functions are basically for this purpose.
stdc_bit_ceil(len) gets the smallest power of 2 not less than len, which is our capacity. This is usually implemented with a clz instruction.
stdc_has_single_bit(len) determines if it's a power of 2 - typically implemented with a popcount instruction (popcount(len)==1).
The approach isn't used in older (90s and earlier) texts because hardware support for popcount/clz wasn't commonplace and the cost to do it in software wasn't worth it, but it is mentioned in some texts.
It doesn’t really work though for generic vectors. If you support not just vec_push but vec_pop as well, then you really do need to store capacity separately or else call realloc way more often than you normally need to.