c design with unique_ptr with custom deleter-CodePudding

I am writing a tree data structure. Each node has a fixed size so I use a fixed size allocator for allocating/deallocating Node. This gives me a headache:

struct Node {
  // other attributes ...
  std::array<std::unique_ptr<Node, CustomDeleter>, num_children> children_;
};

Since all allocations/deallocations of Node are managed by my custom Alloc, I can't use std::unique_ptr<Node> for child nodes, I have to ship custom deleter (associated with that allocator) to children.

But Alloc must know the type of Node, because Alloc is a fixed-size allocator for Node, it should be aware of sizeof(Node) and alignof(Node).

But Node must know the type of Alloc, because CustomDeleter cannot be instantiated without Alloc! This is a circular depedency!

Have the C committee never considered about implementing a tree structure when they designed std::unique_ptr<Node, Deleter>? How can I resolve this problem?

ps. I can't use std::allocator<Node> because I should be able to use memory resource other than the default memory resource

CodePudding user response：

You can use Template template arguments:

#include <memory>

template <template <class T> class AllocTemplate>
struct Tree {
  struct Node;
  using Alloc = AllocTemplate<Node>;

  [[no_unique_address]] Alloc alloc_;

  struct Deleter {
    [[no_unique_address]] Alloc alloc_;
    Deleter(const Alloc &alloc) : alloc_{alloc} {}
    template <typename T>
    void operator()(T* ptr) noexcept {
      alloc_.deallocate(ptr, sizeof(T));
    }
  };
  
  struct Node {
    int val_ = 0;
    std::unique_ptr<Node, Deleter> next_;
    Node(Deleter deleter) : next_{nullptr, std::move(deleter)} 
    {}
  };

  using nodeptr = std::unique_ptr<Node, Deleter>;

  nodeptr make_node() {
      auto buf = alloc_.allocate(1);
      auto deleter = Deleter{alloc_};
      Node* node = new(buf) Node(deleter);
      return nodeptr(node, deleter);
  }
};

int main() {
    Tree<std::allocator> tree;
    [[maybe_unused]] auto node = tree.make_node();
}