The Standard Librarian: Containers of Incomplete Types
Matt Austern
http://www.cuj.com/experts/2002/austern.htm?topic=experts
--------------------------------------------------------------------------------
在1997年，C++标准完成前夕，标准化委员会收到了一个询问：用不完全的类型创建标准容器是可能的吗？委员会花了好一会儿才理解这个问题。这样的事情意谓着什么，究竟为什么会想这样做？委员会最终解决了问题并给予了回答。(仅仅为了让你不必跳到最后面，回答是“No”。)但问题本身比回答更令人感兴趣：它指出了一个有用的，未经广泛讨论的编程技巧。标准运行库并不直接支持这个技巧，但两者可以共存。
不完全的类型
我们都用过不完全的类型，以很熟悉的向前申明的形式[注1]。如果你申明了一个类T，你甚至能在它被定义之前以受一定限制的方式使用它。(更确切地说，是在它的定义体结束之前：一个类在它的定义里面还是不完全的)。你能使用T*类型的指针和T&类型的引用；你能写签名中包含这样的指针或引用的函数；你甚至能申明一个T类型的extern的对象。你不能做的是：不能使用指针的运算，不能定义T类型的变量，不能写new T，不能从T进行继承，也不能使用sizeof()。
这不是随便列出来的。所有这些都是从这个事实推导的，如C++标准在一个脚注中指出的：“未完全定义的对象类型的大小和布局是未知的。”如果一个类型是不完全的，你不能做任何需要知道它的大小或布局的事情。你如何在不知道T类型的对象应该多大时创建这样一个对象？声明：
class T;
告诉编译器T是一个clss或struct。(其反面，是说T是内建类型或其它class的别名。)这足以让编译器知道该如何处理T的指针或引用，但不足以创建一个T的对象：编译器应该为这样一个对象分配多少内存？它应该如何布局其字段？同样地，指针标的运算是没有意义的，因为p += 1这样的表达式要求编译器知道p所指向的对象的大小。
为什么你想拥有指向一个只被前置申明了的类型的指针？经典的例子是（Kernighan和Ritchie[注2]称为“自引用结构self-referential structures”）：一个类包含一个指向它自己的指针，象链表或树的节点。举例来说：
struct int_list_node {
int value;
int_list_node* next;
};
在类的定义体里面，int_list_node自身是一个不完全类型：它一直是不完整的，直到编译器看到了全部的定义体。如果next是int_list_node类型的，就非法了(一个类怎么能包含它自己的一个实例？)，但是指向int_list_node的指针或引用就没问题。
自然，自引用结构不是不完全类型的唯一用处。如果你的设计中含有指向对方实例的多个类时，或含有互为友元的紧耦合类时，这是必须的：
class int_list;
struct int_list_node;
class int_list {
friend class int_list_node;
...
};
struct int_list_node {
friend class int_list;
...
};
这个例子说明了不完全类型的一个重要的方面：在一个文件某处是不完全的类型可以在稍后被完成。在此处，int_list在它的前向申明出现后是不完全类型，但在它的完整定义体之后是一个完全类型。
最后，前向申明可以被用作数据隐藏的一个技巧，以将实现与接口分离[注3]。你可以在头文件中提供一个“不透明类型”my_class的前向申明，然后申明一个函数接口以提供所需要的操作。(你可以选择在别处暴露完整的类定义体，或者也许完全不暴露)。自然地，头文件中的函数的模样有些限制。你可以写：
my_class& clone(const my_class&);
但不可以写：
int illegal_function(my_class);
或:
my_class illegal_function();
你不能以值传递的方式传入或返回不完全类型，就象不能定义一个不完全类型的变量一样。当然，限制同样加在成员函数上，就象加在独立函数上的一样。正如你不能写上面的illegal_function()，你也不能写：
struct illegal_class {
my_class f();
};
不完全类型和模板
理解不完全类型对模板的影响，最好从这个经验法则出发：当你看到一个类模板X<T>的时候，设想它就是一个普通类型，并且每次看到T时，就用某些特定类型替代它。如果你用一个不完全类型来代替T并且得到了一个合法的类的话，那么你就可以确定X<T>可以用不完全类型实例化。于是，举例来说，你能将我们上面看见的list_node类写成一个模板：
template <class T>
struct list_node {
T value;
list_node<T>* next;
};
不完全类型是list_node<T>而不是T本身。你能将不完全类型定义为模板的实参？当然能！C++标准[注4]甚至明确地这么说了。你不能用一个不完全类型实例化list_node(那是非法的；我们已经有了一个T类型的成员变量)，但是那是因为list_node的特殊，而不是因为对模板有任何特别限制。这样做没有任何问题：
template <class T>
struct ptr_list_node {
T* ptr_value;
ptr_list_node<T>* next;
};
class my_class;
ptr_list_node<my_class> p;
用类my_class实例化ptr_list_node是合法的，即使我们拥有的只是my_class的一个前向申明；拥有ptr_list_node<my_class>类型的变量也是合法的。对这一点，在list_node或ptr_list_node这样的模板与int_list_node这样的普通类之间并没有实质性的不同。
然而，联合使用前向申明和模板确实引入了在非模板类中没有的新问题。
比如，考虑这个类：
template <class T>
struct X {
T f() {
T tmp;
return tmp;
}
};
这看起来非常象上面的illegal_class的例子。我们有一个成员函数f()，它返回一个T类型的值，并且我们有一个T类型的局部变量。明显，这是在T为不完全类型时不能做的，所以你可能认为如果只有my_class的前向申明的话，写X<my_class>是非法的。然而，实际上，这没有错。为什么？
这是一个技术问题，但很简单：一个函数模板不会进行错误检查(除了琐细的语法错误)，除非它被实例化，并且成员函数除非被使用否则不被实例化。调用X<my_class>().f()是非法的(你以对不完全类型非法的方式使用了my_class)，但只写X<my_class>是没问题的；它不触发任何会造成问题的东西的实例化。
当然，这不是个非常令人感兴趣的例子：X<my_class>只具有一个无法使用的成员函数。然而，它确实提醒我们应该注意事物被被实例化的精巧位置。当我们混用模板和不完全类型时，有两个关键点：不完全类型被完成的点 (也就是我们看到类的定义体而不是只是前向申明的点)，和实例化点。在两者之间，有趣的事情可能发生。比如，你可能实例化X<my_class>，然后定义my_class，只有在此之后才会实例化X<my_class>::f()。
template <class T>
struct X {
T f() {
T tmp;
return tmp;
}
};
class my_class;
X<my_class> x;
class my_class {
...
};
你为什么会期望这样的定义链？这有一个重要的理由：它能让你在my_class自己的定义体内部使用X<my_class>。你能够拥有一个X<my_class>类型的成员变量，并且你甚至能从X<my_class>进行继承。这可能看起来是循环的，并且非常象my_class正在从它自身进行继承，但它并不比int_list_node这样拥有指向自己的指针的类更循环。链中的每一步都是合法的：X是按可以用不完全类型实例化的方式来写的，而且我们当然能自由地在稍后定义完全类型。
我们接近了现实中的事情。实践中，你当然可能不必为前向申明烦恼：你可以立即定义my_class并在其中使用 X<my_class>。(在类的定义体里面，编译器总是行动得好像它已经看到了正被定义的类的一个前向申明。) Barton和Nackman [注5]展示了如何对结构基类和策略基类使用这个技巧：
class ComplexFloat :
public FieldCategory<ComplexFloat>
{
...
};
基类封装了所有数学域模型共用的东西。基类和派生类是相互依赖的：FieldCategory需要从ComplexFloat获得operator*=()这样的函数，然后，它将pow()和repeat()之类的函数提供给ComplexFloat。
标准容器
我们已经偏离原来的问题了。我们已经谈论了不完全类型与模板，但没有提到标准容器。标准并没有以“curiously recurring template pattern”的形式定义它们，而这个技巧正是以这种形式出现的[注6]。于是，不完全类型的容器是从哪来的呢？
我们已经看到几种形式的通过前置申明得到的近乎循环的东西，但还有一种我们还没看到。int_list_node这样的类含义一个指针指向另外一个int_list_node，但这不是非常具有柔性。首先，我们可能想拥有一个节点指向另外N个节点而不是只一个。（许多应用程序包含树状结构，其一个节点可能有任意个子节点－－比如，考虑一下XML。）其次，指针语义可能不很方便[注7]（WQ注，标准STL容器总是值语义的，以避免麻烦的所有权与生命期问题）。明显，我们不能定义一个类X，它包含一个X的对象数组－－就算我们可以，数组也不能可变大小。但我们可能这样代替吗？
struct tree_node {
int value;
std::vector<tree_node> children;
};
从外部表现看，很像这个类的每个对象包含N个相同的其它实例。这是故意的：vector这样的STL容器接近于内建的数组。一个节点的第i个子成员就是n.children[i]，并且因为子成员是tree_node对象而不仅是指针。我们能只用一行就拷贝整个子树：
tree_node n2 = n1;
不用担心内存约定或显式的深拷贝。它看起来是循环的，但循环的表象并不必然违法；正如我们已经看到的，不是看起来循环的东西都真的是循环的。所有必需的是：定义一个vector<T>而T是一个不完全类型是可能的。
当标准化委员会最初认识到这是一个未决问题时，tree_node的例子是我试的第一个测试。我不知道该期望什么；我当然知道实现这个特别的std::vector的版本的人(我)从没想过这样的可能性。令我吃惊的是，它能工作！立即，我们开始考虑更可能发生的程序－－比如，Greg Colvin，用于实现有限元状态机，其每个state对象包含一个std::map<int, state>：
struct state {
int value;
std::map<int, state> next;
};
唉，状态机是第一个表明这个问题不象我们所期望得那样简单的征兆。这个状态机编译失败，并且，在片刻的思考之后，我们认识到不该费心尝试的－－应该显然任何类似的东西都不能工作的。然后，随着更多的测试，我们发现，即使是tree_node这样的例子都不能工作在所有STL实作上。最终，怎么看都是太暗淡太难以接受；标准化委员会认为没有任何其它选择，除了说STL容器不能与不完全类型合作。额外地，我们也申请了对标准运行库的其余部分也禁止这么做。在T或Char还没被定义时，拥有std::complex<T>或std::basic_istream<Char>有意义吗？几乎肯定没有意义。
C++标准[注8]说不允许用一个不完全类型实例化标准运行库中的模板：“后果未知……如果在实例化模板元件时不完全类型被作为实参（WQ注，附原文：the effects are undefined ... if an incomplete type is used as a template argument when instantiating a template component）”。某些实作允许在某些情况下这么做，但那只是意外。(记住，“未定义行为”含盖了所有可能－－包括它可能如你所期望的那样工作。)
回顾一下，在那个技术已经被更好地理解之后，那一个决定仍然看起来是基本正确的。是的，在某些情况下是可能实作一些标准容器以能用不完全类型实例化的－－但同样很清楚，在其它情况下这样做很难或不可能。完全是运气，我们所尝试的第一个测试，使用std::vector，碰巧是容易的情况之一。
很容易明白，定义std::map<K,V>而K或V是不完全类型，是相当无希望的。毕竟，std::map<K, V>的value_type（存储在容器中的对象的类型）是std::pair<const K, V>。而pair<T1, T2>有一个T1类型的成员变量和一个T2类型的成员变量。你不能拥有不完全类型的成员变量，而实例化map<K,V>必然需要实例化pair<const K,V>。
其它标准容器怎么说，比如list或set？在这儿，我们进入了实现细节；很难明确证明实例化std::list<T>或std::set<T>是不可能的。但很容易明白它为什么不工作于这些容器的现有实作，并且允许它工作的实作为什么绝不会直截了当。这些容器通常以节点的形式实现的；比如，set的节点看起来可能有点象这样：
template <class V>
struct rb_tree_node {
V value;
rb_tree_node *parent, *left, *right;
bool color;
};
当然，问题是成员变量value：它意味着我们不能用不完全类型实例化rb_tree_node，于是也就意味着（如果set是按这种方式实现的，）我们不能用不完全类型实例化set。可能以其它方式实现set而绕过这个限制吗？可能的。但，据我所知，还没人尝试过－－恐怕以后也不会有人尝试，因为绕开限制的可行方法会造成set变大或变慢或同时两者。
对于vector，还有其它方法。C++标准没有规定vector<T>应该如何实现，但对于这里的情况，可行的实现是允许T为不完全类型的实现。对std::vector的直截了当写法类似于这样：
template <class T, class Allocator>
class vector {
...
private:
Allocator a;
T* buffer;
typename Allocator::size_type buffer_size;
typename Allocator::size_type buffer_capacity;
};
这其中没有任何东西要求T是完全类型；一个前向申明就足够了。并且没有明显的变更(从Allocator进行继承，使用三个指针而不是一个指针加两个整数，等等)会影响这一点。的确，当为本文再次测试tree_node时，它在我试过的前三个编译器上通过了[注9]
总结
我们处在何处？循环的tree_node这样的设计对某些用途是非常好的，但如我们已经看到的，我们不能拥有它：它被C++标准明确禁止。但是这并不必然意谓着标准程序库对这个设计是没有用处的。重要的主意是表面上循环的设计（类X包含一个作为成员变量的容器，而此容器的value_type是X）：它是在一个类自包含时的次好方案。C++标准说你不被允许使用任何标准容器类，但标准容器不是唯一的选择。C++标准定义了容器的接口，而不只是一组不相干的类，而任何满足那个接口的容器类都与list和set这样的预定义类同样好地适合运行库的架构。
在C++的未来修订版中，放松在用不完全类型实例化标准运行库模板上的限制可能会有意义。很清楚，常规的禁令应该继续存在－－用不完全类型实例化模板是个麻烦的事情，而标准运行库中太多的类对此没有意义。但也许应该以个案方式被放松，而vector看起来正是这样的特例的一个很好的候选者：它是一个标准容器类，而有很好理由用一个不完全类型实例化它，并且标准运行库的实现者想让它能工作。时至今日，事实上，实现者不得不故意禁止它！
注
[1] Actually, there are two other kinds of incomplete types: arrays whose size is unknown, and void, which behaves like an incomplete type that can't ever be completed. See ?.9, paragraph 6, of the C++ Standard. However, the most important kind of incomplete type is a class that has been declared but not yet defined; it's the only kind that I'll discuss.
[2] B. W. Kernighan and D. M. Ritchie. The C Programming Language, First Edition (Prentice-Hall, 1978). I meant it when I said that this was "the classic example"!
[3] This is a well-known technique for managing dependencies in large programs. See, for example, J. Lakos's Large Scale C++ Design (Addison-Wesley, 1996). One classic example of this technique is the familiar C stdio library.
[4] ?4.3.1, paragraph 2.
[5] J. J. Barton and L. R. Nackman. Scientific and Engineering C++ (Addison-Wesley, 1994.)
[6] J. O. Coplien. "A Curiously Recurring Template Pattern," February 1995, <http://creport.com>.
[7] See my column "The Standard Librarian: Containers of Pointers," C/C++ Users Journal Experts Forum, <www.cuj.com/experts/1910/austern.htm>.
[8] ?7.4.3.6, paragraph 2; this is the part of the Standard that discusses general requirements that the standard library places on user components.
[9] The three compilers I tried were g++ 2.95, Microsoft Visual C++ 7.0, and Borland C++ 5.5.1. Why did these results differ from the ones I got four years ago? I suspect it's because of changes in the compilers, not in the library implementations; some older compilers failed to obey the rule that an unused member function of a class template shouldn't be instantiated.
