泛型<编程>：可识别联合(Discriminated Unions)（1）
Andrei Alexandrescu
相信我：不管粗看上去怎么样，如果你想要的是关于编程的文章，你算来对地方了。这里讨论的不是怎样去识别一个联合，这个泛型编程的部分讨论的是可识别联合数据的类型。
可识别联合从概念上说有许多同义词：拆解联合（disjoint union），可变类型（variant type），或者代数类型（algebraic type），不管你怎么叫它们，可识别联合作为数据抽象在各种应用中正变得非常有用。许多语言（大多数是功能语言）在数据结构中非常依赖可识别联合。也许你在不久的将来会在C++中用到可识别联合，因为......
但什么是可识别联合，它能为你做什么？你会很快找到答案甚至更多意外惊喜，但首先，应大家要求，让我对上篇文章做一下补充。
对特别访问（Ad-Hoc Visitation）的特别补充
泛型编程的前一个部分[1]定义了一个模板类叫AdHocVisitor，这个模板类对一个类层次执行不改变原类层次的类似于访问的功能。
AdHocVisitor的语义非常简单，假设你这样实例化：
Typedef AdHocVisitor<cons<TextArea, VectorGraphics,
Bitmap>::type>
DocElementVisitor;
然后，AdHocVisitor的代码能够保证正确的访问：当你调用DocElementVisitor::StartVisit，正确的重载函数Visit(TextArea*)，Visit(VectorGraphics*)，或Visit(Bitmap*)会被自动调用。
AdHocVisitor执行参数类型演绎的机制本质上和if-else链一样，这就是说，代码效果类似于：
If (TextArea* pTextArea = dynamic_cast<TextArea*>(p))
{
Visit(pTextArea);
}
else if VectorGraphics pVectorGraphics =
dynamic_cast<VectorGraphics*>(p))
{
Visit(pVectorGraphics);
}
else if (Bitmap* pBitmap = dynamic_cast<Bitmap*>(p))
{
Visit(pBitmap);
}
else
{
throw "Unknown type passsed";
}
象我上篇文章所解释的，AdHocVisitor采用的方法是对类型串执行模板递归操作来进行分阶段测试，但最终的语义是和上面的if-else语句链一样的。
现在设想后来你定义了一个新的从TextArea继承的FormattedTextArea类。很自然的，你会把这个类型加到DocElementVisitor的定义中，这样你也能访问FormattedTextArea对象：
typedef AdHocVisitor<cons<TextArea, VectorGraphics,
Bitmap, FormattedTextArea>::type>
DocElementVisitorl
当访问DocElementVisitor，增加的dynamic_cast<FormateedTextArea*>测试放在if-else链的最后，这意味着这个测试不可能成功——任何FormateedTextArea“是一个（is-A）”TextArea，所以dynamic_cast<TextArea*>起作用。结果，代码会总是认为FormateedTextArea实际上是一个TextArea并且据此访问它。最后的那个测试不会被执行到，因为会被前面的测试拦截掉。这不是我们想要的。
一个简单的解决是重新排列类型串，让FormattedTextArea在TextArea前面出现：
typedef AdHocVisitor<cons<FormattedTextArea, TextArea,
VectorGraphics, Bitmap>::type>
DocElementVisitor;
一个更漂亮的解决是自动完成这件事情。实际上，Loki有个很好的DerivedToFront类型串来重新排列类型串，它正好能满足你这样的要求。你需要查看Loki的代码[2]或解释[3]来知道原理，但使用上是相当简单的：
typedef DerivedToFront<cons<FormattedTextArea, TextArea,
VectorGraphics, Bitmap>::type>
ShuffledHierarchy;
Typedef AdHocVisitor<shuffledHierarchy::Result>
DocElementVisitor;
这些是相当多的补充。当在写上篇专栏快接近字数限制时，我决定不管这个警告，但是集中讨论类型串，而不是层次访问的一些微妙问题。我这样做时是因为Scott Meyers在一封信里提醒我：
“太多的枝节[...]使读者不能完全吸收你想要说的，因为他们分心了[...]。写作时，我想非常重要的是内容保持集中”
有时候真实生活比最好的电视连续剧还要好玩，因为第一个写信指出上一篇专栏的遗漏正是...Soctt Meyers他自己！第二个人是Uwe Behrens。Scott真的应该获得特别奖励，因为他还知道完整的基于DerivedToFront的解决。显然Uwe没有读过《Modern C++ Design》[3]，否则他会对AdHocVisitor这个方法更有信心。这可以通过他下面评论来看出：
“我过去在我自己的程序中用过类似的机制，包括实现访问模式，在那个过程里，我知道了这个方法的一个严重缺陷。我以惨痛的方式知道这一点（也就是，整夜的调试）。”
总结：坏消息是我在“类型串及应用”[1]一文中没有提及一个重要问题，好消息是，这个问题有个自动化的解决方案[2，3]。非常感谢Scott Meyers和Uwe Behrens。
那么什么是可识别联合？（Discriminated Unions）
好吧，回到主题。已经有一篇关于可识别联合的文章[4]作为这篇你在读的文章的基础。但是那篇文章为范围更小，更专门的读者群写的——所以许多读者来询问更细节的问题。
一个可识别联合是个数据类型，它可以存储类型的有限集合的一个值并提供对那个值类型安全的存取功能。
这里有些关键部分需要特别注意。首先，提供的取值功能必须是类型安全的，这意味着，尽管看上去不错，但过时的C联合不能用在此处，因为它不能提供类型安全的取值——换句话说，它不是可识别的。
Union SomeData
{
int anInteger_;
double aDouble_;
char* aPointer_;
};
编译器只是把三个成员变量存储在重叠的内存中，却不能阻止你象这样非法使用它：
//类似隐式reinterpret_cast
SomeData dt;
dt mPoint_ = "Hello,cruel world of undiscriminated unions";
int weird = dt.aninteger;
第二个需要指出的重点是关于类型集的范围问题。在完整的动态多态和可识别联合之间有重要的区别。你可以把指向基类的指针看作某种联合，因为它可以指向任意从基类继承的对象。但是，这个集合是无界限的——你预先不知道可能的类型集。相反，一个可识别联合只存储可能类型的有限集合，这个集合在定义时可知。当然，这些类型本身仍然可以是多态的。
当介绍联合时，大多数的C和C++书都把它看作本质上低层次的，无趣的工具——“嗨，如果你真的需要节约内存，这里有个小工具给你。”这就是C的联合能给你的一切。但是可识别联合是非常有用的高层次抽象。“泛型编程”的这个部分和下个部分会让你相信这一点的。
可识别联合的用途
当你需要把不同类型的对象（在状态和接口上不同）作为同类型对象方式操作时（多态在处理不同状态但统一接口时非常好），可识别联合就变得有用了。
假设在一个数据类型中存储数据库字段值。数据库字段可以是整型，浮点型，字符串或日期型。这些字段之间除了它们共同在数据库里之外毫无共同之处。如果你想要实现一个能够存储和操作数据库字段的数据结构，你在某个特定时刻需要能够存储数据库的字段类型。这就是variants能用到的地方。
另一个例子是在动态类型语言里存储数据，比如Scheme或Basic语言。一个变量可能是有限的，小的类型集合中的任意一种。
还有一个例子是传给分析器的项目。例如，在句法分析中，你得到的每个词位可能是关键字，可能是标识符，可能是字面常量（整型，浮点型，字符串等等），可能是操作符等等。一个可识别联合是存储这些词汇元素的最好选择。用一个面向对象的方法会出现无意义的操作，比如获得一个关键字的整型值。换句话说，这样的归类方法很糟。
正如我们下面会看到的，只要小心操作，可识别联合比其他方法有巨大的（一位市场人士会说成是“压倒性的”）效率优势。
当前的实现
一个在C和C++里实现可识别联合的明显的方法是用“标记联合”：你存储一个包含着需要的类型的标准的联合和一个整数来显示现在哪个字段有效，考虑DatabaseField例子：
struct DatabaseField
{
enum TypeTag {typeNull, typeInt, typeDouble,
typeString, typeDate }
tag_;
union
{
int fieldInt_;
double fieldDouble_;
char* fieldString_;
Date fielddate_;
};
...
};
不管什么时候你赋给DatabaseField的任何field*成员变量，你需要同时正确地设置tag_成员。相反的，在获取联合的成员变量前，你需要首先查询tag_来获知你查询的DatabaseField里面的精确类型。
这个步骤可以包装在一系列的get/set函数中（GetInt, SetInt, GetString, SetString等等）。问题是，这样的方法笨拙，有限制而且僵硬。你需要手工维护一个三维的关系——类型标识和数据加上get/set函数。除此之外，难道没有一个比笨拙的get/set函数更好点的接口？
实现可识别联合的彻底的面向对象方法非常简单：你从一个公共类中继承所有你需要的可能类型，比如说，DBField。这样你有StringDBField和IntDBField等等。然后，你的可识别联合只是个指向DatabaseField的引用。你使用dynamic_cast（或者在你的面向对象语言调用的对应任意语句）来得到实际类型。
这是一个面向对象不适合的情况。当你的类型有差不多的操作时定义一个类层次才有意义；然而，字符串，双精度浮点，整型和日期型没有多少共同之处。一个类层次不能有效地表达这样的结构。你需要要么依赖类型转换要么自己写繁琐的函数，类似于“给我那个数据的浮点值”。这很显然是糟糕的设计。
一个现代的实现
我们要建立一个可识别联合的实现，它具有工业强度，提供你所需要的几乎所有东西，就象语言本身提供了这些特性。
首先显而易见的是，给定的可识别联合是仅仅关系到类型集合，我们正好能够使用前文介绍过的类型串。这样我们粗略的实现就象这样：
template <class Tlist>
class Variant //可识别联合可能会很长
{
...
};
你能够用一个类型串来实例化Variant
typedef Variant<cons<int, double, String, Date>::type> DatabaseField
在让用户选择支持的类型集基础上，一个好的实现应该提供：
* 值语义：默认的构造和拷贝构造函数，赋值函数和析构函数
* 初始化Varian的构造函数带有类型串的任意类型的值
* 对应于类型串中所有类型的赋值操作符重载函数。
* 类型安全的类型存取机制
* 有swap功能，这在很很多常用法(idioms)中很有用
* 类型转换
最后的但同样重要的是，Variant应该是高效的。不要忘记我们讨论的是能和语言内建
特性相提并论的基础机制。
存储：不单单只是关于效率
那么，你想要怎样在Variant类型中存储实际的值呢？
第一个能想到的设计方案可能是使用一个联合来存储。它正是我们需要的——允许不同类型的变量共享底层内存。加上一个小技巧，我们能够从类型串里取出类型并把它们放入联合中。（你知道联合能够模板化吗？）
template <class Tlist> union ConfigurableUnion;
template <class H, classT>
union ConfigurableUnion< typelist<H, T> >
{
H head_;
ConfigurableUnion<T> tail_;
};
template <class H >
union ConfigurableUnion< typelist<H, null_type> >
{
H head_;
};
ConfigurableUnion是一个你能很好控制需要存储的类型的联合。
然而，一旦你想这样做：
typedef ConfigurableUnion<std::string, int> impossibleType;
编译器会提醒你联合不接受带有构造成员函数和析构成员函数的类型，这导致了对于任何重要的程序ConfigurableUnion都没有用。
第二个想法是单单存储指针而不是直接的类型，并为数据分配自由存储区。这个想法可行，但有两个问题：一个小问题一个大问题（到底哪个大哪个小取决于你的看法是偏向于语言的纯粹性还是偏向于执行效率）
一个问题是这个解决方案不象就地分配内存的联合那样的有效率。使用自由存储区导致时间开销，同时可能有空间开销（由于分配器必须保持维护数据）
另一个更基本的（或没什么太大关系的，取决于你的看法）问题是使用自由存储区变更了Variant提供的对外的意外保证（exception guarantees）。如果就地分配内存，Variant的构造函数只会抛出和传入类型的拷贝构造函数一样类型的意外。特别是，如果你用拷贝不会抛意外的类型来实例化Variant，Variant同样也不会抛意外。Variant能很好地和使用意外的代码协作，不会在意外上有什么偏差。把Variant使用在意外上就象吃饭一样简单。
如果我们用自由存储区分配来设计Variant，它的构造函数会抛出它存储的类型会抛出的意外再加上std::bad_alloc，甚至用“简单”类型比如整型或字符型来实例化也可能抛出意外。这不是好的设计，因为这样放松了Variant可能对它的客户做的保证，以此类推必然也会放松这些客户能够提供的保证。
结论是，Variant最好用就地分配内存。
我们来继续研究这个就地分配内存的主意，我们可以用不指定类型的字符缓存，不是吗？
Template <class Tlist>
Class Variant
{
//计算需要的缓存大小
enum {neededSize = ... };
unsigned char buffer_[neededSize];
};
我们实际上可以非常简单地计算出neededSize。只要用一个递归算法的实现来获得一个类型串中的最大元素：你比对头部和尾部的最大元素（递归算出），然后你选两个中大的那个。
template <class Tlist> struct MaxSize;
template <>
struct MaxSize<null_type>
{
enum { result = 0};
};
template <class Head, class Tail>
struct MaxSize <typelist<Head, Tail> >
{
private:
enum {tailResult = size_t(MaxSize<Tail>::result) };
public:
enum {result = sizeof(Head) > tailResult ?
sizeof(Head) : size_t(tailResult) };
};
正如你看到的，MaxSize用它自身递归来计算内部变量tailResult，然后它取较大的值。停止版本（null typelist）仅仅返回最小的正数——零。
给定MaxSize，我们的Variant定义变为：
template <class Tlist>
class Variant
{
enum { neededSize = MaxSize<Tlist>::result };
unsigned char buffer_[neededSize];
};
如果你听到吓人的巨响，那是因为我们现在的存储实现撞在了墙上：它不能用，更糟的是，它有时能用——和某些类型配合，在某些机器上，在某些编译器中，甚至和月亮的盈亏有关。做好面对艰难险阻的准备——我们正遇到对齐（alignment）问题。
实际上，我们方法的问题在于编译器不知道我们准备放在buffer_内“真实”数据是什么。编译器只知道它必须处理一个字符缓存。
结果是，在现在的大多数计算机体系中，某些数据类型必须存储在内存的一个指定的偏移中，例如典型的四字节整型可能分配在地址为四的倍数的地址上。这不意味着八字节数据必须分配在八倍数的地址上——它们的对齐可能也是四（但是，没有数据会要求对齐大于它自身的大小，因为这会破坏数组存储规则）
对齐概念的理由是内存条，总线和处理器的物理分配。举例来说，某些内存条使用内存总线低位八字节，所以构造它们的内容时不能直接使用高位字节。
如果你试图获得没有正确对齐的数据，会得到几个可能结果中的一个。你可能得到你要的数据，但慢很多，因为处理根本上是用软件重新排列数据来模拟，这本来是硬件来操作的（x86处理器是这样做的）。然而许多其他处理器，当你试图做非法地址访问会立刻终止你的程序。
好消息是，你不用担心对齐：处理器通过对所有数据分配合适的已对齐内存来很好地处理这件事。坏消息是你现在需要自己处理这些，因为buffer_[neededSize]事实上意味着你自己掌握你的命运。
我们怎么保证buffer_正确对齐？这正是联合所做的——它保证了它的最大成员有足够空间并对它的对齐要求最高的成员执行对齐，这正是我们需要的，所以我们的存储实现应该是这样的
union
{
unsigned char buffer_[needeSize];
Align dummy_;
};
我们不会直接用到dummy_它出现只是为了对齐。我们现在只需要正确定义Align类型。我们在下一部分具体讨论。
参考书目
[1] A. Alexandrescu. "Generic<Programming>: Typelists and Applications," C/C++ Users Journal C++ Experts Forum, February 2002, <www.cuj.com/experts/2002/alexandr.htm>.
[2] 你可以从<www.moderncppdesign.com>下载Loki。
[3] A. Alexandrescu. Modern C++ Design (Addison-Wesley Longman, 2001).
[4] A. Alexandrescu. "An Implementation of Discriminated Unions in C++," The 2001 C++ Template Programming Workshop, held in conjunction with OOPSLA 2001, <www.oonumerics.org/tmpw01/alexandrescu.pdf>.
[5] 有消息说下个C++标准的修订版本，被那些密切关注的人昵称为“c++0x”，会支持带构造函数的类型作为联合的成员，但不管怎样，带析构函数的类型不被支持，这是有原因的。既然联合不存放识别标志，当联合离开作用域时编译器怎么知道调用哪个析构函数呢？
Andrei Alexandrescu 是位于西雅图的华盛顿大学的博士生，也是受到好评的《Modern C++ Design》一书的作者。可以通过www.moderncppdesign.com. 来联系他。Andrei同时也是C++研讨会 (<www.gotw.ca/cpp_seminar>).的一名有号召力的讲师。
