Using std::initializer_list to create a tree?

Question

What I have is something like:

struct ExprTreeNode {
   char c;
   std::vector< int > i;
};

ExprTreeNode tn { '+', { 1, 2, 3, 4 } };

What I want to write is something like:

MyTree t1 { '+', { 1, 2, { '*', { 3, 4, 5 } } } };
MyTree t2 { '*', { { '+', { 77, 88, 99, 111 } }, { '-', { 44, 33 } } } };

I'm free to define the MyTree class (and possible helper classes) - but it should be something tree-ish - like operator as a TreeNode content and a container (e.g. a std::vector) holding the subnodes.

In C++ is it possible to use such an initializer_list to initialize a tree-like structure? (If it is possible, a hint how to do this would be nice.)

Answer 1

The following might work for you:

struct ExprTreeNode {
    bool is_value;
    int i;
    char c;
    std::vector< ExprTreeNode > v;

    ExprTreeNode( int i_ ) : is_value( true ), i( i_ ) {}
    ExprTreeNode( char c_, std::initializer_list< ExprTreeNode > v_ )
      : is_value( false ), c( c_ ), v( v_ ) {}
};

ExprTreeNode tn { '+', { 1, 2, { '*', { 3, 4 } } } };

(in practice you might want to combine i and c)

Here's a live example.

---

Update: As it was pointed out in another Q/A where I used a similar technique, the above is undefined behaviour as I am using std::vector<ExprTreeNode> as a member and at that point, ExprTreeNode is not a complete type. The following should fix it:

struct ExprTreeNode {
    int value_;
    char op_;
    std::shared_ptr< void > subnodes_;

    ExprTreeNode( int v ) : value_( v ) {}
    ExprTreeNode( char op, std::initializer_list< ExprTreeNode > subnodes );

    void print() const;
};

typedef std::vector< ExprTreeNode > Nodes;

ExprTreeNode::ExprTreeNode( char op, std::initializer_list< ExprTreeNode > l )
  : op_(op), subnodes_(std::make_shared<Nodes>(l))
{}

This uses the shared_ptr also as a flag for leaf/non-leaf and if you want to use it, you need to cast it first:

void ExprTreeNode::print() const
{
   if( !subnodes_ ) {
      std::cout << value_;
   }
   else {
      std::cout << op_ << " ( ";
      for( const auto& e : *std::static_pointer_cast<Nodes>(subnodes_) ) {
         e.print(); std::cout << " ";
      }
      std::cout << ")";
   }
}

Here's the updated live example.