Làm thế nào để mã hóa cấu trúc dữ liệu phức tạp, liên tục lớn trong C++

Question

Trước đây, tôi đã sử dụng g23's C99-style compound-literal extension tới C++ để mã hóa cấu trúc dữ liệu không đổi lồng nhau trong mã. Dưới đây là một ví dụ:

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

Ý tưởng là để sử dụng thời gian lưu trữ tĩnh cho các cấu trúc liên tục một cách hợp lý lớn, với chi phí khởi tạo không, và thực sự không cần phải trang bất cứ điều gì vào bộ nhớ trừ khi cần thiết.

Điều này không còn hoạt động trong phiên bản mới nhất của tiếng kêu, tuy nhiên, và OS X mới nhất là gói clang dưới tên 'gcc'. Vì vậy, tôi cần một giải pháp khác.

Thành ngữ phù hợp tiêu chuẩn tốt nhất cho điều này trong C++ là gì?

Tôi không đặc biệt muốn trả chi phí xây dựng tất cả các đối tượng trong các cấu trúc này, vì vậy nếu điều đó có thể tránh được, nó sẽ là tuyệt vời.

Answer 1

C++ 11 uniform initialization cú pháp nên làm việc:

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

Nếu không, chỉ cần đảm một constructor lấy tên và subtrees như các đối số.

---

Nếu bạn không muốn cấu trúc được phân bổ động, bạn phải tạo từng cấu trúc và sau đó liên kết chúng với nhau bằng cách sử dụng ví dụ: địa chỉ-của nhà điều hành:

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

Nếu lớn, loại phức tạp đã không đệ quy bạn chỉ có thể sử dụng constexpr loại và khởi tạo thống nhất với không có thủ đoạn.

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

struct A { 
    B b; 
    C c; 
}; 

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

Tuy nhiên, vì đó là cây và bạn không thể có loại đệ quy như vậy (vì kích thước sẽ là vô hạn), cần phải thực hiện các thủ thuật. Có hai cách tiếp cận mà tôi có thể nghĩ đến. Đầu tiên là sử dụng con trỏ hoặc tài liệu tham khảo để tránh đệ quy vô hạn.

Với con trỏ, bạn sẽ cần một cách tạo đối tượng tĩnh và nhận con trỏ đến chúng. Tôi không nghĩ rằng C + + có bất cứ điều gì cho phép bạn làm điều này trong một biểu thức duy nhất, do đó sẽ yêu cầu khai báo cho mỗi nút trong cây, mà không phải là thuận tiện.

Với tài liệu tham khảo bạn cần một số cách để thể hiện một nút rỗng (vì tham chiếu không tự vô hiệu nếu không có hacks nguy hiểm). Dưới đây là cách triển khai đơn giản này:

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

Cách tiếp cận thứ hai để tránh đệ quy là sử dụng mẫu để tạo các loại khác nhau cho mỗi cấu trúc cây khác nhau.

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

Bằng cách này một nút lá đã gõ Tree<null_tree_t, null_tree_t>, một cái cây với một con trái đó là một nút lá là Tree< Tree<null_tree_t, null_tree_t>, null_tree_t>, một cái cây với một con bên trái có một đứa trẻ ngay đó là một nút lá là:

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

Vv