How to encode large complex, constant data structures in C++

Question

In the past, I've used gcc's C99-style compound-literal extension to C++ to encode nested constant data structures in code. Here's an example:

#include <iostream>
using namespace std;

struct Tree {
    const char *name;
    const Tree *left;
    const Tree *right;
};

const Tree *const tree = (Tree []) {
    "top", // name
    (Tree[]) {
        "left",
        0,
        0
    },
    (Tree[]) {
        "right",
        0,
        0
    }
};

static void dump(const Tree *tree) {
    if (!tree) {
        cout << "null";
        return;
    }

    cout << tree->name << "(";
    dump(tree->left);
    cout << ", ";
    dump(tree->right);
    cout << ")";
}

int main(void) {
    dump(tree);
    cout << "\n";
}

The idea is to use static storage duration for these reasonably large constant structures, with zero initialization cost, and indeed no need to page anything into memory unless needed.

This no longer works in recent version of clang, however, and the latest OS X is bundling clang under the name 'gcc'. So I need a different solution.

What's the best standard-conforming idiom for this in C++?

I don't particularly want to pay the cost of constructing all the objects in these structures, so if that can be avoided, it would be great.

Answer 1

C++11 uniform initialization syntax should work:

const Tree* const tree = new Tree{"top",
    new Tree{"left", nullptr, nullptr},
    new Tree{"right", nullptr, nullptr}
};

Otherwise, just make a constructor taking the name and subtrees as arguments.

---

If you don't want the structures to be dynamically allocated, you have to create each structure by itself, and then link them together using e.g. the address-of operator:

namespace
{
    const Tree leftTree{"left", nullptr, nullptr};
    const Tree rightTree{"right", nullptr, nullptr};
    const Tree topTree{"top", &leftTree, &rightTree};
}

const Tree* const tree = &topTree;

Answer 2

If the the large, complex type weren't recursive you could simply use constexpr types and uniform initialization with no tricks.

struct B { int i; };
struct C { double d; };

struct A {
  B b;
  C c;
};

constexpr A {B{1},C{3.2}};

However, since it's a tree and you can't just have a recursive type like that (as the size would be infinite), tricks are necessary. There are two approaches I can think of. First is to use pointers or references so as to avoid infinite recursion.

With pointers you would need a way of creating static objects and getting pointers to them. I don't think C++ has anything that lets you do this in a single expression, so that would require declarations for each node in the tree, which is not convenient.

With references you'd need some way to represent a null node (since references aren't themselves nullable without dangerous hacks). Here's a simple implementation of this:

struct Tree {
    const char *name;
    Tree const &left;
    Tree const &right;
};

constexpr Tree Null{nullptr,Null,Null};

void print_tree(Tree const &t) {
  if (&t == &Null) {
    std::cout << "()";
    return;
  }
  std::cout << '(' << t.name << ", ";
  print_tree(t.left);
  std::cout << ", ";
  print_tree(t.right);
  std::cout << ")";
}

constexpr Tree a {"a",
                  Tree{"b",
                       Null,
                       Tree{"d",Null,Null}},
                  Tree{"c",Null,Null}};

int main() {
  print_tree(a);
}

A second approach to avoiding the recursion is to use a template to generate different types for every different tree structure.

template<typename LTree, typename RTree>
struct Tree {
    const char *name;
    LTree left;
    RTree right;
};

struct null_tree_t {};
constexpr null_tree_t null_tree{};

template<typename RTree>
struct Tree<null_tree_t, RTree> {
    const char *name;
    RTree right;
};

template<typename LTree>
struct Tree<LTree, null_tree_t> {
    const char *name;
    LTree left;
};

template<>
struct Tree<null_tree_t, null_tree_t> {
    const char *name;
};

// C++14 return type deduction
template<typename LTree, typename RTree>
constexpr auto make_tree(const char *name, LTree ltree, RTree rtree) {
    return Tree<LTree, RTree>{name, ltree, rtree};
}

template<typename LTree>
constexpr auto make_tree(const char *name, LTree ltree) {
    return Tree<LTree, null_tree_t>{name, ltree};
}

template<typename RTree>
constexpr auto make_tree(const char *name, null_tree_t, RTree rtree) {
    return Tree<null_tree_t, RTree>{name, rtree};
}

constexpr auto make_tree(const char *name) {
    return Tree<null_tree_t, null_tree_t>{name};
}

template<typename LTree, typename RTree>
void print(Tree<LTree, RTree> const &tree) {
  std::cout << '{' << tree.name << ", ";
  print(tree.left);
  std::cout << ", ";
  print(tree.right);
  std::cout << '}';
}

template<typename LTree>
void print(Tree<LTree, null_tree_t> const &tree) {
  std::cout << '{' << tree.name << ", ";
  print(tree.left);
  std::cout << ", {}}";
}

template<typename RTree>
void print(Tree<null_tree_t, RTree> const &tree) {
  std::cout << '{' << tree.name << ", {}, ";
  print(tree.right);
  std::cout << "}";
}

void print(Tree<null_tree_t, null_tree_t> const &tree) {
  std::cout << '{' << tree.name << "}";
}

constexpr auto a = make_tree("a",
                             make_tree("b",
                                       null_tree,
                                       make_tree("d")),
                             make_tree("c"));

int main() {
  print(a);    
}

This way a leaf node has type Tree<null_tree_t, null_tree_t>, a tree with a left child that's a leaf node is Tree< Tree<null_tree_t, null_tree_t>, null_tree_t>, a tree with a left child that has a right child that's a leaf node is:

Tree<
  Tree<
    null_tree_t,
    Tree<
      null_tree_t,
      null_tree_t>>,
  null_tree_t>

Etc.