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 |      |      |      |      |
+ ---- + ---- + ---- + ---- + ---- +
||
||

这有助于解释为什么在我们在 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中文网其他相关文章！