You have a solution that is probably good enough.

This is little more than a recurring idea that I've yet to use, but could be used for this.

When writing a library to deal with relatively small 'value types' -- n-bit integers are a prefect example -- the time-costs and memory overheads of malloc()/free()(¹) can be a substantial part of the aggregate costs of using the type. Indeed, C++11 attempts to deal with another part of this -- avoiding the process of allocating a new instance, copying the value of an old instance (transformed by the current operation) into the new instance and then discarding the old instance -- by the implementation of 'move semantics'. But that's a separate issue.

((¹)Compiler malloc/free are bad enough, but Perl's is horrible. Leastwise on Windows.)

A good solution to this is create a pool of the value types and manage them yourself. As the allocations are all fixed sized, the pool can be managed as a simple array of values with pointer to the next free; and each unused value pointing to the next free.

That gives 0 per-value memory overhead; 1 dereference and a fixup per allocation; and worst case a short pointer chain for free. It can also give good cache locality. And, guaranteed alignment! (An alternative implementation that uses a bitmap rather free-chain can be even more efficient.)

On Windows this idea is made very simple by using VirtualAllocEx()(²) to reserve a chunk of virtual memory space, that lives completely outside the sight of the CRT (heap), that can be grown and shrunk in-place in system page sized chunks.

So, you reserve (say) 1GB virtual memory(³), but only allocate the first page (4k). That's enough for an array of 256 128-bit integers, but if you need more, you can efficiently, dynamically extend that array to accommodate 67 million more, without any need to copy or move any of the existing values.

((²) I don't know/can't find the equivalent system function for *nix. I thought for a while valloc() might be it; but that seems to have been deprecated and replaced by a call that has all sort of silly restrictions (must be compatible with the standard free() in order to be posix complaint.))

((³) You might need to be a little more conservative on 32-bit systems; but on 64-bit there is ~16 million times as much address space available as any of the current crop of processors can actually address, so there is no penalty for spreading ourselves around a bit.)