You still fail to understand what being part of multiple data structures means. Shared pointers, separate container to check occupancy, suggesting making a con

You still fail to understand what being part of multiple data structures means. Shared pointers, separate container to check occupancy, suggesting making a container of pointers, all these things suggest you have no idea how to do hybrid data structures. The nodes contain the data along with multiple pointers in them to chain them to various data structures they are part of (trees, lists, hash tables etc.). The object in question contains state that is several cache lines long. You cannot just put the nodes inside your buckets as you don't get to control where the nodes are and cannot invalidate the other data structures. Though I suppose it's a possibility if you know ahead of time how many nodes you're going to need, but then in that case you may be able to go for perfect hashing to begin with (unless you're building some kind of fixed-size cache). A given object for example can be part of several hash maps, based on the various pieces of state it is useful to index by. In practice you'd use a pool to allocate all your nodes in blocks. There is no per-node overhead for this allocation strategy.