Avoid using cast in tree structure

Question

We are considering a design that requires casting which does not feel right. Obviously googled the issue but have not found an answer. Would appreciate advice on how to avoid the need for casting. Here is a stripped down example (please execuse any typos, this has not been compiled).

struct NodeBase
{
   enum class type
   {
     value,
     aggregate
   };
   type m_type;
};

struct NodeAggregate : public NodeBase
{
   std::vector<NodeBase*> m_list;
};

struct NodeValue : public NodeBase
{
   std::string m_key;
   std::string m_value;
};

The above classes can be used to create a tree structure with multiple levels.

The 'difficulty' is to develop an algorithm that traverses this structure without casting. The type variable in the base class shall identify the correct type and will reduce the number of cast to a single but it does not avoid casting.

What would be an alternative design for this issue?

Appreciate any comments.

Answer 1

struct NodeBase;

struct NodeAggregate {
  std::vector<std::unique_ptr<NodeBase>> children;
  ~NodeAggregate();
};

struct NodeValue {
  std::string key, value;
};

struct NodeBase {
  boost::variant<NodeAggregate, NodeValue> m;
};

inline NodeAggregate::~NodeAggregate() = default;

the variant supports visiting, which is a type-safe pseudo static-cast.

This also eliminates all needless indirection.

Answer 2

The pattern that you seem to be re-implementing is called tagged union, or variant, which is typically paired with the visitor pattern. Instead of rolling your own, I recommend using an existing implementation.

But also consider alternative implementations:

• Use homogeneous nodes. Let every node be able to store both child list, and data. That way you only need one type of node and no casting is necessary. If only leaves can have data, then you can implement that limitation in the algorithms, instead of the data structure.

  struct Node
  {
       std::vector<Node*> m_list;
       std::string m_key;
       std::string m_value;
  };
  

• Or use virtual functions:

  struct NodeBase
  {
      virtual       bool  is_leaf()            = 0;
      virtual const range children()     const = 0;
      virtual       range children()           = 0;
      virtual const std::string* key()   const = 0;
      virtual       std::string* key()         = 0; // if the tree is not sorted by key
      virtual const std::string* value() const = 0;
      virtual       std::string* value()       = 0;
      virtual ~NodeBase() {}
  };
  

  The leaf and branch nodes can implement the functions differently. Leaf can always return an empty range, while branch can return null key and value. Alternatively, they can require the user to use is_leaf, and throw an exception if wrong type of function is called.

  Instead of returning access to the vector directly, I used a range type, that should be a pair of iterators, which allows you to encapsulate the choice of the underlying container.

In all of these designs, you can templetize the key and value types for better generality.

Answer 3

I think you want the Visitor pattern. For example:

struct NodeAggregate;
struct NodeValue;

struct Visitor
{
    virtual void visit(NodeAggregate &aggregate) = 0;
    virtual void visit(NodeValue &value) = 0;
};

struct NodeBase
{
    virtual void accept(Visitor &visitor) = 0;
};

struct NodeAggregate : public NodeBase
{
    std::vector<NodeBase*> m_list;

    void accept(Visitor &visitor) override
    {
        visitor.visit(*this);

        for(auto base : m_list)
        {
            base->accept(visitor);
        }
    }
};

struct NodeValue : public NodeBase
{
    std::string m_key;
    std::string m_value;

    void accept(Visitor &visitor) override
    {
        visitor.visit(*this);
    }
};

struct WriteToConsoleVisitor : Visitor
{
    void visit(NodeAggregate &aggregate) override
    {
        std::cout << "got an aggregate" << std::endl;
    }

    void visit(NodeValue &value) override
    {
        std::cout << "got a value. key = " << value.m_key << ", value = " << value.m_value << std::endl;
    }
};

The trick here is to have a visitor class that has a visit method for each node type in the system, and to have each node type have an accept method that takes the visitor and passes itself into the visitor. This is a way of implementing a technique called double dispatch in single dispatch languages like C++.

Answer 4

If you have several node types consider to use Visitor Pattern to traverse through all tree nodes without casting:

#include <iostream>
#include <memory>
#include <string>

class Aggregate;
class ConcreteNode1;
class ConcreteNode2;

class Visitor {
public:
  virtual void Visit(ConcreteNode1& node) = 0;
  virtual void Visit(ConcreteNode2& node) = 0;
  virtual void Start(Aggregate& aggregate) = 0;
  virtual void Finish(Aggregate& aggregate) = 0;
};

class Node {
  friend class Aggregate;
public:
  Node() : parent_(nullptr) {}
  virtual ~Node() = default;
  virtual void Accept(Visitor& visitor) = 0;
private:
  void SetParent(Aggregate* parent) {
    parent_ = parent;
  }
  Aggregate* parent_;
};

class Aggregate : public Node {
public:
  void Add(std::shared_ptr<Node> node) {
    node->SetParent(this);
    nodes_.push_back(std::move(node));
  }
  virtual void Accept(Visitor& visitor) override {
    visitor.Start(*this);
    for (auto node : nodes_) {
      node->Accept(visitor);
    }
    visitor.Finish(*this);
  }
private:
  std::vector<std::shared_ptr<Node>> nodes_;
};

class ConcreteNode1 : public Node {
public:
  ConcreteNode1(int data) : data_(data) {}
  virtual void Accept(Visitor& visitor) override {
    visitor.Visit(*this);
  }
  int GetData() const { return data_; }
private:
  int data_;
};

class ConcreteNode2 : public Node {
public:
  ConcreteNode2(std::string name) : name_(std::move(name)) {}
  virtual void Accept(Visitor& visitor) override {
    visitor.Visit(*this);
  }
  const std::string& GetName() const { return name_; }
private:
  std::string name_;
};

int main()
{
  class SimpleVisitor : public Visitor {
    virtual void Visit(ConcreteNode1& node) override {
      std::cout << "ConcreteNode1: " << node.GetData() << std::endl;
    }
    virtual void Visit(ConcreteNode2& node) override {
      std::cout << "ConcreteNode2: " << node.GetName() << std::endl;
    }
    virtual void Start(Aggregate& aggregate) override {
      std::cout << "Start Aggregate\n";
    }
    virtual void Finish(Aggregate& aggregate) override {
      std::cout << "Finish Aggregate\n";
    }
  } visitor;
  auto root = std::make_shared<Aggregate>();
  root->Add(std::make_shared<ConcreteNode1>(1));
  {
    auto subtree = std::make_shared<Aggregate>();
    subtree->Add(std::make_shared<ConcreteNode1>(2));
    subtree->Add(std::make_shared<ConcreteNode2>("test1"));
    root->Add(subtree);
  }
  root->Add(std::make_shared<ConcreteNode2>("test2"));

  /// traverse through all nodes
  root->Accept(visitor);
}