Requirements on standard library allocator pointer types

Question

I am trying to write a quadtree sparse matrix class. In short, a quadtree_matrix<T> is either the zero matrix or a quadruple (ne, nw, se, sw) of quadtree_matrix<T>.

I'd like eventually to test different allocation schemes since this will probably impact the performance of linear algebra operations. So I will also template quadtree_matrix on a standard allocator type, so that I can reuse existing allocators.

I will have to allocate two different kind of data: either a T, or a node, which contains four pointers (to either T or node). For all the algorithms I will consider, I know for sure what kind of data to expect because I know what are the sizes of the submatrices I am facing at any point of the algorithm (I don't even need to store these sizes).

I will of course be using two different allocators: this is ok, since allocator types provide the rebind template and a template copy constructor (and are intended to be used as value types, as the get_allocator members of standard containers suggest by returning a copy).

The problem is that allocator member functions use a certain pointer type, which is not required to be a vanilla pointer. Some allocators (boost interprocess allocators) use this feature extensively.

If the allocator pointer types were garden variety pointers, I would have no problems: at the very least, I could use pointers to void and reinterpret_cast them to the right type (either node* or T*). I could also use a union (probably better).

As far as I know, there is no requirement on the PODness of the allocator::pointer types. They are only required to be random access iterators.

Now, my question is:

Given an allocator class template A<T> (or its equivalent A::rebind<T>::other), is there any guarantee on:

1. The ability to static cast A<T>::pointer to A<U>::pointer provided U is an accessible base of T ?
2. The ability to static cast A<T>::pointer to A<U>::pointer provided T is an accessible base of U and the "runtime type" (whatever this means in this context) of the castee is U ?
3. The type A<void>::pointer (if this makes sense) ?

Or is there a solution to my problem I didn't think about ?

Answer 1

From the tables in 20.1.5/2 it clearly indicates that the type of A<T>::pointer must be "pointer to T". Since those pointer types are normally convertible your 1 and 2 are true. It follows then that A<void>::pointer must be void*.

EDIT: There's also explicit wording in 20.1.5/4 (it applies to what standard containers may assume about allocators):

The typedef members pointer, const_pointer, size_type, and difference_type are required to be T*,T const*, size_t, and ptrdiff_t, respectively.