如何大型複雜的，恆定的數據結構編碼在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"; 
} 

的想法是使用靜態存儲持續時間爲這些相當大的結構不變，零成本的初始化，的確需要除非無需任何頁面到內存中。

這不再是最新版本鐺的作品，然而，最新的OS X被命名爲「海灣合作委員會」項下捆綁鐺。所以我需要不同的解決方案。

是什麼在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}}; 

然而，因爲它是一棵樹，你不能只是有一個遞歸式一樣，（因爲規模將是無限的），技巧是必要的。我可以想到兩種方法。首先是使用指針或引用來避免無限遞歸。

的指針，你需要創建靜態對象和獲取指針到他們的一種方式。我不認爲C++有什麼可以讓你在單一表達式中做到這一點，所以這需要樹中每個節點的聲明，這是不方便的。

有了引用，你需要一些方法來表示一個空節點（因爲引用本身不是空的，沒有危險的黑客）。這裏有一個簡單的實現這個：

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

第二種方法避免遞歸是使用模板來生成不同類型的每個不同的樹結構。

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> 

等等