How to use STL-compliant allocators for heterogeneous memory allocations

Question

I'm trying to implement a class that's followed in memory by an array of some arbitrary type:

template<class T>
class Buf
{
    size_t n;
    int refs;
    explicit Buf(size_t n) : n(n) { }
    // other declarations are here as appropriate

    // Followed in memory by:
    // T items[n];
};

This would be easy with operator new:

template<class T>
Buf<T> *make_buf(size_t n)
{
    // Assume the caller will take care of constructing the array elements
    return new(operator new(sizeof(Buf<T>) + sizeof(T) * n)) Buf<T>(n);
}

template<class T>
void free_buf(Buf<T> *p)
{
    // Assume the caller has taken care of destroying the array elements
    p->~Buf<T>();
    return operator delete(p);
}

template<class T>
T *get_buf_array(Buf<T> *p)
{
    return reinterpret_cast<T *>(reinterpret_cast<char *>(p) + sizeof(Buf<T>));
}

But now, how do I implement this using some standard-compliant allocator SomeAllocator?

Is it guaranteed that SomeAllocator::rebind<char>::other::allocate will return memory suitably aligned for any type of object? If so, am I otherwise safe to just use an allocator of some char type? If not, do I have any alternatives, or is this task impossible with allocators in general? (In the worst case I suppose I could cast the pointers to uintptr_t and align them manually, but I'm wondering if there's a better way.)

Answer 1

I was thinking the solution could be by creating a notional early array.

+-----------+
|Buf<T>     |
+-------+---+---+-------+-------+
|T[0]   | T[1]  |T[2]   |  T[3]...
+-------+-------+-------+-------+

With the non-overlapping T[2], T[3], ... being the required array of T.

template<class T>
class Buf
{
    size_t n;
    int refs;
    explicit Buf(size_t n) : n(n) { }
    // other declarations are here as appropriate

    // Followed in memory by:
    // T items[n];
};

The number of ruined elements would be :-

const size_t lead = ( sizeof(Buf<T>) + sizeof(T) - 1) / sizeof(T);

Finally the raw memory of i can be accessed by

(reinterpret_cast<T*>( this ) )[ i + lead ];

Answer 2

I'm afraid you're making unwarranted assumptions about what the C++ standard requires. What you're trying to do may not be generically possible.

The default allocator (new or malloc) is required to return a pointer to a block of memory that is suitably aligned for any complete object type with a fundamental alignment requirement. The size must be at least as large as the requested size. Custom allocators have different requirements, depending on what they allocate. An allocator for one type is not guaranteed to return storage suitably aligned for another. Of course, if you are the one implementing a custom allocator, you can make sure it returns what you need.

The compiler is required to satisfy some constraints about memory layout, but it will not guarantee that something is placed in memory immediately after something else. There could be padding bytes insert to meet alignment requirements.

The recent C++ standards provide quite a bit of support for handling alignments. There is probably an answer for you in there somewhere. I suspect that underlying this are some requirements you haven't told us about. Perhaps there is another way to go about it.

Answer 3

I think that standard compliant allocator you stl compliant? Since you don't require your allocator to be used with an stl data structure it is not really necessary to meet it's requirements even though you may as well do so as I think it is a neat way of doing it and in which case you may implement you buffer by using an std::vector with your custom stl style allocator as a template parameter. With regards to alignment guarantees of operator new and operator new[] I suggest you have a look at:

Is there any guarantee of alignment of address return by C++'s new operation?.

If your alignment concerns are for primitive types such as doubles etc. you are pretty much covered by std::align as you can see in http://en.cppreference.com/w/cpp/memory/align.

However if you have stranger/larger alignment requirements such as aligning every element to cache lines etc. or T is a type with a size where sizeof(T)mod alignment != 0 you may have problems when allocating arrays of T's. In such cases even if the first element of the array is aligned to meet the requirement it doesn't mean that all the subsequent elements will be aligned as well.

Answer 4

Constrain the alignment by rebinding the allocator to a specialization of std::aligned_storage.

typedef std::aligned_storage_t< 1, std::max( alignof (Buf<T>), alignof (T) ) >
        unit_type; // lowest-common-denominator type for aligned allocation

std::size_t unit_count // number of unit_type array elements needed
    = ( sizeof (Buf<T>) + sizeof (T) * n // = actual used storage
           + sizeof (unit_type) - 1 )    //   + alignment padding
      / sizeof (unit_type);              // divided by element size

typedef typename std::allocator_traits< SomeAllocator >::rebind_alloc< unit_type >
        rebound;

rebound a( alloc_parm ); // Retain this somewhere if statefulness is allowed.
ptr = std::allocator_traits< rebound >::allocate( a, unit_count );

(Remember, all allocator access goes through allocator_traits!)