Get template to work well with unique_ptr to interfaces in C++

Question

First of all, there's no such built in concept as "interface". By interface in C++, I really mean some abstract base class that looks like:

struct ITreeNode
{
   ... // some pure virtual functions
};

Then we can have concrete structs that implement the interface, such as:

struct BinaryTreeNode : public ITreeNode
{
   BinaryTreeNode* LeftChild;
   BinaryTreeNode* RightChild;

// plus the overriden functions
};

It makes good sense: ITreeNode is an interface; not every implementation has Left & Right children - only BinaryTreeNode does.

To make things widely reusable, I want to write a template. So the ITreeNode needs to be ITreeNode<T>, and BinaryTreeNode needs to be BinaryTreeNode<T>, like this:

template<typename T>
struct BinaryTreeNode : public ITreeNode<T>
{
};

To make things even better, let's use unique pointer(smart point is more common, but I know the solution - dynamic_pointer_cast).

template<typename T>
struct BinaryTreeNode : public ITreeNode<T>
{
   typedef std::shared_ptr<BinaryTreeNode<T>> SharedPtr;
   typedef std::unique_ptr<BinaryTreeNode<T>> UniquePtr;
   // ... other stuff
};

Likewise,

template<typename T>
struct ITreeNode
{
   typedef std::shared_ptr<ITreeNode<T>> SharedPtr;
   typedef std::unique_ptr<ITreeNode<T>> UniquePtr;
};

It's all good, until this point: Let's assume now we need to write a class BinaryTree.

There's a function insert that takes a value T and insert it into the root node using some algorithm(naturally it will be recursive).

In order to make the function testable, mockable and follow good practice, the arguments need to be interface, rather than concrete classes. (Let's say this is a rigid rule that cannot be broken.)

template<typename T>
void BinaryTree<T>::Insert(const T& value, typename ITreeNode<T>::UniquePtr& ptr)
{
   Insert(value, ptr->Left); // Boooooom, exploded
   // ...
}

Here's the problem: Left is not a field of ITreeNode! And worst of all, you cannot cast a unique_ptr<Base> to unique_ptr<Derived>!

What's the best practice for a scenario like this?

Thanks a lot!

Answer 1

Ok, over-engineering it is! But note that, for the most part, such low level data structures benefit HUGELY from transparency and simple memory layouts. Placing the level of abstraction above the container can give significant performance boosts.

template<class T>
struct ITreeNode {
  virtual void insert( T const & ) = 0;
  virtual void insert( T      && ) = 0;

  virtual T const* get() const = 0;
  virtual T      * get()       = 0;
  // etc
  virtual ~ITreeNode() {}
};

template<class T>
struct IBinaryTreeNode : ITreeNode<T> {
  virtual IBinaryTreeNode<T> const* left()  const = 0;
  virtual IBinaryTreeNode<T> const* right() const = 0;

  virtual std::unique_ptr<IBinaryTreeNode<T>>& left()  = 0;
  virtual std::unique_ptr<IBinaryTreeNode<T>>& right() = 0;

  virtual void replace(T const &) = 0;
  virtual void replace(T      &&) = 0;
};

template<class T>
struct BinaryTreeNode : IBinaryTreeNode<T> {
  // can be replaced to mock child creation:
  std::function<std::unique_ptr<IBinaryTreeNode<T>>()> factory
    = {[]{return std::make_unique<BinaryTreeNode<T>>();} };

  // left and right kids:
  std::unique_ptr<IBinaryTreeNode<T>> pleft;
  std::unique_ptr<IBinaryTreeNode<T>> pright;

  // data.  I'm allowing it to be empty:
  std::unique_ptr<T> data;

  template<class U>
  void insert_helper( U&& t ) {
    if (!get()) {
      replace(std::forward<U>(t));
    } else if (t < *get()) {
      if (!left()) left() = factory();
      assert(left());
      left()->insert(std::forward<U>(t));
    } else {
      if (!right()) right() = factory();
      assert(right());
      right()->insert(std::forward<U>(t));
    }
  }
  // not final methods, allowing for balancing:
  virtual void insert( T const&t ) override { // NOT final
    return insert_helper(t);
  }
  virtual void insert( T &&t ) override { // NOT final
    return insert_helper(std::move(t));
  }
  // can be empty, so returns pointers not references:
  T const* get() const override final {
    return data.get();
  }
  T      * get()       override final {
    return data.get();
  }
  // short, could probably skip:
  template<class U>
  void replace_helper( U&& t ) {
    data = std::make_unique<T>(std::forward<U>(t));
  }
  // only left as customization points if you want.
  // could do this directly:
  virtual void replace(T const & t) override final {
    replace_helper(t);
  }
  virtual void replace(T      && t) override final  {
    replace_helper(std::move(t));
  }
  // Returns pointers, because no business how we store it in a const
  // object:
  virtual IBinaryTreeNode<T> const* left()  const final override {
    return pleft.get();
  }
  virtual IBinaryTreeNode<T> const* right() const final override {
    return pright.get();
  }
  // returns references to storage, because can be replaced:
  // (could implement as getter/setter, but IBinaryTreeNode<T> is
  // "almost" an implementation class, some leaking is ok)
  virtual std::unique_ptr<IBinaryTreeNode<T>>& left() final override {
    return pleft;
  }
  virtual std::unique_ptr<IBinaryTreeNode<T>>& right() final override {
    return pright;
  }
};