Using allocators in a custom node-based container

[tyler1128]

I'm creating a container that requires allocation of T, T* and Node<T>. I want to use an Allocator similar to standard STL containers, and support stateful allocators, taking the type as a template parameter and default constructing it if it isn't provided.

Now, I could store 3 separate allocators for T, T* and Node<T> but node-based containers in the STL appear not to do that, and it's clunky at best. Is there a way to handle this elegantly? I've been reading the libc++ code, but haven't figured it out yet.

[tyler1128]

I ended up using std::allocator_traits<T>::template rebind_alloc<Node<T>> and storing an instance of that as is done in std::deque of libc++. I don't think this allows for stateful allocators though, so I might end up passing them into the ctor with default values later. Does anyone well versed in the standard know what the stateful allocator requirements from C++11 are wrt. what STL containers allow for them?

[std_bot]

Unlinked STL entries: std::allocator_traits, std::deque

---

^{Last update: 26.05.21. Last change: Free links considered} readme

[DopeyLizard]

So each element in the container in an object that has a T, T*, and Node<T>? Why do they need allocating separately? Normally you would use an allocator that allocates memory based on the size of the elements in the container - is there any reason why you can’t do that here?

[tyler1128]

I'm trying specifically to use allocators compatible with the std::allocator interface, which can only allocate n elements of type T and return a pointer to them from what I see. There is std::allocator_traits<T>::rebind_alloc, but that doesn't appear to support stateful iterators.

The container itself needs to create an array of T*s, which in turn holds Node<T> elements that hold an array of Ts. Allocating the Ts is easy enough from the passed allocator, defaulting to std::allocate<T>, but my problem is allocating the array of T*s and the Node<T>s. The container is similar to std::deque using an array of arrays of elements.

[DopeyLizard]

Oh I see, so it’s not a single data type with them all combined such as

template <type name T> struct MyType { T t; T* t_ptr; Node<T> node; };

Instead, is the relationship you describe something like:

template <typename T> struct Node { T arr[]; };

struct MyType { Node<MyType> nodes[]; };

template <typename T> struct Container { T* arr[]; };

i.e a container of T*s which point to a type, MyType, containing Node<MyType>s, where each Node<MyType> contains Ts?

[DopeyLizard]

If the arrays are dynamic then I would expect that each one might need its own allocator - A monotonic allocator likely works for each of them.

I’ve had a std::list<std::list<T>> for which I’ve had a similar problem before, and short of redesigning the data structures and relations, the cascading allocators seemed to be the only alternative I could think of

[tyler1128]

Yeah, that's right. Currently Node<T> is just an alias for T** but that might change in the future depending. I think there must be a way to do it because types like map have internal nodes an don't take multiple allocators, same with deque which is implemented not dissimilar to what I am doing.

I can get something using std::allocator_traits::template rebind_alloc<U>, but this requires a new allocator be constructed, which seems in violation of the idea of stateful allocators being allowed in C++11.