C++で大規模で複雑な定数データ構造をエンコードする方法

Question

以前は、gccのC99-style compound-literal extensionをC++に使用して、コード内にネストされた定数データ構造をエンコードしました。ここでは例です：

#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"; 
} 

アイデアが必要な場合を除きメモリにゼロ初期費用で、これらの合理的に大規模な一定の構造物の静的記憶域期間を使用していない、とページ何に確かに必要です。

これはclangの最近のバージョンでは動作しなくなりました。最新のOS Xはclccを 'gcc'という名前でバンドルしています。だから私は別の解決策が必要です。

C++でこれに最も適した標準準拠のイディオムは何ですか？

特にこれらの構造内のすべてのオブジェクトを作成するコストを支払う必要はありません。そのようなことが避けられれば、それは素晴らしいことです。

Answer 1

C++ 11 uniform initialization構文は動作するはずです：

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

そうでない場合は、単に引数として名前とサブツリーを取るコンストラクタを作ります。

---

あなたは構造が動的に割り当てることにしたくない場合は、それ自体で各構造を作成する必要があり、その後、例えば使用してそれらを一緒にリンクします

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

大規模で複雑なタイプが再帰的でない場合は、単純にconstexprタイプと一意の初期化をトリックなしで使用することができます。それは木だとあなただけ（サイズは無限であるように）そのような再帰的な型を持つことができないので

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

struct A { 
    B b; 
    C c; 
}; 

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

はしかし、トリックが必要です。私が考えることができる2つのアプローチがあります。まず、無限の再帰を避けるために、ポインタや参照を使用します。

ポインタを使用すると、静的オブジェクトを作成しポインタを取得する方法が必要になります。私はC++には単一の式でこれを行うことができるものはないと思うので、ツリー内の各ノードの宣言が必要になります。これは便利ではありません。

参考文献では、（参考文献自体が危険なハッキングなしでnullableではないので）ヌルノードを表現する方法が必要です。ここでは、この単純な実装です：

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); 
} 

再帰を回避するための第2のアプローチは、すべての異なるツリー構造のためのさまざまな種類を生成するためのテンプレートを使用することです。

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);  
} 

リーフノードがTree<null_tree_t, null_tree_t>を入力している。この方法で、葉ノードの左の子を持つツリーがTree< Tree<null_tree_t, null_tree_t>, null_tree_t>で、葉ノードの右の子を持つ左の子を持つツリーは次のとおりです。

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

等