Rebinding in a custom STL allocator with pre-allocated block

Question

I'm going to build a custom allocator, preallocating a big block (array) for storing N elements of some class T, and then just increase an index inside the array to service allocation requests.

Since I don't want any initialization for the elements in the pre-allocated block, something like this won't work:

T buffer[N];

because in this case T's constructor will be called for the N elements of the block.

Since my understanding is that std::aligned_storage doesn't call T's constructor, I thought of using std::aligned_storage, something like this:

std::aligned_storage<
    N * sizeof(T),
    std::alignment_of<T>::value 
>::type buffer;

T* base = static_cast<T*>( static_cast<void*>(&buffer) );

And then the allocator can just increment the base pointer when an allocation for a T is requested (until (base+N)), and T can be constructed in place (with placement new) when needed.

I'd like to use this scheme to define a custom allocator for STL containers. However, it seems to me that there could be a problem here for rebinding. In fact, if my understanding is correct, an STL allocator should support rebinding from a type T to a type U, e.g. because containers like std::list<T> (or other node-based containers like std::map) use allocators to allocate nodes that are not actually of type T, but of different type U (containing T and other "header" overhead information for the node). So, would the aforementioned std::aligned_storage approach work well for rebinding? Or (as I think) a correct alignment for Ts does not imply a correct alignment for another different type U?

How could this problem be solved?

How could I define the aforementioned buffer to make it work also for rebinding to some different type U?

Should this problem be attacked from a different perspective? If so, what?

Answer 1

You are on the right track.

One irritating details is that copies of allocators must compare equal, even converting (rebound) copies. Comparing equal means they can deallocate each other's pointers. So a container such as std::list<int> will rebind your_alloc<int> to your_alloc<node<int>> and then construct a your_alloc<node<int>> using a your_alloc<int>. And technically your your_alloc<node<int>> has to deallocate a pointer allocated by your_alloc<int>.

Here is my attempt to meet this requirement. Feel free to copy/modify/abuse this code. My intent is to educate, not become the world's allocator supplier (which wouldn't exactly be lucrative anyway :-)).

This example takes a slightly different approach to alignment: I happen to know that on my platform of interest (OS X, iOS) that malloc returns 16 byte aligned memory, and so that's all my custom allocator needs to return. You could change that number to whatever is appropriate for your system.

This hardwiring of alignment means that a single pool can safely supply several allocator<int> and allocator<node<int>>, as they are all 16-byte aligned (and that's enough). And it also means that copies, even converted copies, can detect when the pointer is pointing into the buffer, since copies all share the same buffer.

Said slightly differently, the C++ committee has effectively specified that allocators are reference types: copies are equivalent and point to the same memory pool.

You can get away with cheating, using memory pools actually embedded into the allocator, but only with some containers on some implementations, and you can't back that up with a quote from the standard.