How to determine node size of std containers?

Question

I would like to implemented a custom allocator for node-based containers like std::unordered_map or std::list. For that allocator I need to specify the size of the nodes. How do I get this? I know in C++17 at least std::unordered_map has a node_type, but I'm currently bound to C++11

Goodkin

Isn't the allocator only responsible for the memory allocation of the objects you store in the map and not for the nodes? So why do you need the size of the node? – Morgue

No, the allocator is used to allocate the nodes which are the value_type plus some extra info. It also allocates some large arrays. On my machine for using Map = std::unordered_map<uint64_t, uint64_t> I get sizeof(Map::value_type) == 16, but the allocator is actually called to allocate 24 bytes for one entry – Goodkin

Ok, never realized that it changes the template of the allocator to be a node of the given type. But within your custom allocator class, you know the type (and therefore size) of the node due to the template argument, so what is the problem with using this information? Do you need that information before the allocator is constructed? (If you write std::list<uint64_t, Allocator<uint64_t>> the allocator instance created is Allocator<std::_List_node<uint64_t>>). – Morgue

@Morgue The standard containers are actually required to call typename std::allocator_traits<Allocator>::rebind_alloc<Node> to allocate internal objects (nodes) of type Node. – Weksler

@Goodkin Do you want to get the size of the internal node programmatically? Or do you want to tell the implementation to use nodes of a specific size? – Weksler

did you find an answer to that? There's an old question that effectivelly says it's not possible: #22951878 Given that, I don't really see any use for allocator customization – Cephalo

@SergeyKolesnik no, I tried hard but this is not possible. Also each implementation (MSVC, libc++, libstdc++) does it differently, at least for std::unordered_map, so it is impractical to hardcode something. – Goodkin

I had some thought about the case, when you need a pool allocator for an auxiliary container and you know how many elements will be allocated in advance. One can try to implement a statefull allocator that stores number of elements thta will be allocated. Upon the first allocation it would allocated the whole pool using the type size requested by the caller (container). But it is a wild guess and I don't see if it is worth the try. Better to give up on the Standard Library completelly. – Cephalo

@SergeyKolesnik unfortunately that doesn't work generically, e.g. in MSVC they allocate some control structure first for the map, so just using the size of the first allocation doesn't work. I have implemented my pool allocator now a bit differenltly so it supports multiple allocation sizes, up to a given template size. I just have to choose the size large enough, typically sizeof(value_type) + sizeof(void*)*4 works. – Goodkin