C 中的不相交聯合

目前還不清楚如何在 C 中表達此 Haskell 類型：

data Tree = Leaf Int | Inner Tree Tree

與 Haskell 和 Rust 等語言不同，C 缺乏對
的內建支持 不相交的聯合。然而，如果我們願意做一些額外的輸入，它確實提供了代表它們所需的所有成分。

首先要認識到的是，不相交的並集包括：

• 許多不同的變體
• 每個都有一些與之關聯的數據。

在我們的二元樹範例中，我們有兩個變體：「葉子」和「內部」。葉變數儲存單一整數（其資料），內部變數儲存兩棵樹（代表其左子樹和右子樹）。

我們可以使用具有兩個字段的結構在 C 中表示這樣的動物：

1. “類型標籤”，通常是整數，指示所表示的變體。
2. data 字段，用於儲存與變體相關的資料。

使用枚舉定義不同的變體類型標籤很方便：

enum tree_type {
        TREE_LEAF,
        TREE_INNER,
};

儲存資料怎麼樣？這就是工會存在要解決的問題類型。

工會

聯合只是一塊能夠儲存多種不同類型資料的記憶體。例如，這是一個可以儲存 32 位元 int 或 5 個字元數組的聯合。

union int_or_chars {
        int num;
        char letters[5];
};

類型為 union int_or_chars 的變數可以在任何特定時間保存 int 或 5 個字元的陣列（但不能同時儲存）：

union int_or_chars quux;

// We can store an int:
quux.num = 42;
printf("quux.num = %d\n", quux.num);
// => quux.num = 42

// Or 5 chars:
quux.letters[0] = 'a';
quux.letters[1] = 'b';
quux.letters[2] = 'c';
quux.letters[3] = 'd';
quux.letters[4] = 0;
printf("quux.letters = %s\n", quux.letters);
// => quux.letters = abcd

// But not both. The memory is "shared", so the chars saved above are
// now being interpreted as an int:
printf("quux.num = %x\n", quux.num);
// quux.num = 64636261

return 0;

像 union int_or_chars 這樣的聯合擁有足夠大的記憶體區塊可供使用，可以容納其最大的成員。這是顯示其工作原理的示意圖：

+ ---- + ---- + ---- + ---- + ---- +
| byte |      |      |      |      |
+ ---- + ---- + ---- + ---- + ---- +
|<--   int uses these 4  -->|
|<--  array of chars uses all 5 -->|

這有助於解釋為什麼在我們在 quux 中儲存字元數組後列印 quux.num 會導致「垃圾」：它不是垃圾，而是字串「abcd」被解釋為整數。 （在我的機器上，quux.num 以十六進位列印為64636261。字元「a」的ASCII 值為0x61，「b」的值為0x62，「c」為0x63，「d」為0x64。由於我的處理器是小端字節序，所以順序顛倒了。

關於聯合的最後一點，您可能會對 sizeof 報告的大小感到驚訝：

printf("%ld\n", sizeof(union int_or_chars));
// => 8

在我的機器上，類型 union int_or_chars 的大小為 8 個位元組，而不是我們預期的 5 個位元組。由於我的處理器架構規定的對齊要求，已添加一些填充。

返回二元樹

我們現在準備繼續將二元樹類型從 Haskell 轉換為 C。我們已經定義了一個枚舉來表示變體的類型。現在我們需要一個聯合來儲存其資料：

union tree_data {
        int leaf;
        struct inner_data inner;
};

其中 struct inner_data 是包含「內部」變體的左右子級的結構：

struct inner_data {
        struct tree *left;
        struct tree *right;
};

請注意，「內部」變體維護

指向其左子節點和右子節點的指標。間接是必要的，因為否則結構樹將沒有固定的大小。

這些部分就位後，我們就可以定義我們的樹類型了：

enum tree_type {
        TREE_LEAF,
        TREE_INNER,
};

struct tree;
struct inner_data {
        struct tree *left;
        struct tree *right;
};

union tree_data {
        int leaf;
        struct inner_data inner;
};

// A representation of a binary tree.
struct tree {
        enum tree_type type;
        union tree_data data;
};

和樹玩耍

讓我們寫一些函式來建構樹：

// Construct a leaf node.
struct tree *leaf(int value) {
        struct tree *t = malloc(sizeof(*t));
        t->type = TREE_LEAF;
        t->data.leaf = value;
        return t;
}

// Construct an inner node.
struct tree *inner(struct tree *left, struct tree *right) {
        struct tree *t = malloc(sizeof(*t));
        t->type = TREE_INNER;
        t->data.inner.left = left;
        t->data.inner.right = right;
        return t;
}

並列印它們：

void print_tree(struct tree *t) {
        switch (t->type) {
        case TREE_LEAF:
                printf("%d", t->data.leaf);
                return;
        case TREE_INNER:
                printf("(");
                print_tree(t->data.inner.left);
                printf(" ");
                print_tree(t->data.inner.right);
                printf(")");
                return;
        }
}

這使我們能夠翻譯 Haskell 表達式：

Inner (Inner (Leaf 1) (Leaf 2)) (Leaf 3)

轉換成 C 為：

inner(inner(leaf(1), leaf(2)), leaf(3));

例如：

struct tree *t = inner(inner(leaf(1), leaf(2)), leaf(3));
print_tree(t);
// => ((1 2) 3)

作為一個稍微有趣的例子，我們來翻譯這個深度優先搜尋函數：

-- Check if a value is in a tree.
search :: Int -> Tree -> Bool
search v (Leaf w) = v == w
search v (Inner l r) = search v l || search v r

使用我們的樹型：

// Check if a value is in a tree.
int search(int value, struct tree *t) {
        switch (t->type) {
        case TREE_LEAF:
                return t->data.leaf == value;
        case TREE_INNER:
                return (
                        search(value, t->data.inner.left) ||
                        search(value, t->data.inner.right)
                );
        }
}

這當然更冗長，但翻譯過程很簡單（編譯器大概可以為我們做這種事......）。

權衡

我們最後稍微題外話一下替代表示中涉及的權衡。具體來說，假設不是：

union tree_data {
        int leaf;
        struct inner_data inner;
};

我們使用：

union tree_data {
        int leaf;
        struct inner_data *inner;
        //                ^ The difference.
};

在第一種情況下，聯合體包含一個結構體inner_data，而在第二種情況下，它儲存一個指向該結構體的

指標。因此，第一個聯合體稍大一些，為 16 字節，而我的機器上的指標版本為 8 個位元組。不幸的是，受影響的不僅僅是內部節點：葉節點使用相同的 16 位元組聯合，但僅儲存單一（4 位元組）int。感覺有點浪費。

然而，這並不是故事的全部。每次訪問內部節點的左子節點和右子節點時，我們都會為額外的間接尋址付出代價：讀取不一定便宜，特別是在指向的記憶體未快取的情況下。

我懷疑這裡提出的主要方法在大多數情況下是一個更好的起點，並且嘗試削減一些字節（白色導致額外的讀取）是不值得的，直到它成為現實。

以上是C 中的不相交聯合的詳細內容。更多資訊請關注PHP中文網其他相關文章！