CUJ: Standard Library: Container for incomplete type

The Standard Librarian: Containers of Incomplete Types

Matt austern

http://www.cuj.com/experts/2002/AUSTERN.HTM?topic=experts

-------------------------------------------------- ------------------------------

In 1997, on the eve of the C standard, the Standardization Commission received an inquiry: Is it possible to create a standard container with an incomplete type? The committee spent a while to understand this problem. This is what it means, why do you want to do this? The committee finally solved the problem and responded. (Just let you not have to jump to the end, answering is "no".) But the problem itself is more interested than answering: it pointed out a useful, unanpricted programming skills. The standard runtime is not directly supporting this technique, but both can coexist.

Incomplete type

We have used incomplete types to "Note 1] in the form of very familiar declaration. If you declare a class T, you can even use it in a certain way before it is defined. (More specifically, it is before its definition body: A class is still in its definition). You can use the T * type pointer and T & Type reference; you can write the signature containing such a pointer or referenced function; you can even declare a T type of Extern object. What you can't do is: You can't use a pointer, you can't define the T type variable, you can't write new T, you can't inherit from T, and sizeof () cannot be used.

This is not just random. All of this is derived from this fact, such as the C standard pointed out in a footnote: "The size and layout of the unfained object type is unknown." If a type is incomplete, you can't do anything you need to know Its size or layout. How do you create such an object when you don't know how T type objects? statement:

Class T;

Tell the compiler T is a CLSS or STRUCT. (It is said that t is an alias of the built-in type or other class.) This is enough to let the compiler know how to handle T., but not enough to create a T object: Compiler should assign such an object assignment How much memory? How should it lay out? Similarly, the operation of the pointer is meaningless, because the expression of P = 1 requires the compiler to know the size of the object points to which P is pointed.

Why do you want to have a pointer to a type that is only a premium? Classic example is (kernighan and Ritchie [Note 2] called "Self-reference Self-Referenceial Structure": A class contains a node that pointing its own pointer, icon list or tree. for example:

Struct int_list_node {

Int value;

INT_LIST_NODE * NEXT;

}

In the definition body of the class, int_list_node itself is an incomplete type: it has been incomplete until the compiler sees all of the definitions. If Next is an int_list_node type, it is illegal (how can a class contain one of its own instances?), But pointing to int_list_node pointer or reference is no problem.

Naturally, the self-citing structure is not unique use of incomplete type. This is a must::

Class Int_List;

Struct int_list_node;

Class int_list {friend class int_list_node;

...

}

Struct int_list_node {

Friend class int_list;

...

}

This example shows an important aspect of an incomplete type: an incomplete type at a file can be done later. Here, INT_LIST is incomplete type after its forward decision, but it is a full type after it's a complete definition body.

Finally, the forward statement can be used as a technique hidden in data to separate the interface [Note 3]. You can provide an "opaque type" my_class in the header file and then declare a function interface to provide the required operation. (You can choose to expose the complete class definition body else, or may not expose it at all. Naturally, the appearance of the function in the header file is subjective. You can write:

MY_CLASS & Clone (const my_class&);

But you can't write:

INT ILLEGAL_FUNCTION (MY_CLASS);

or:

MY_CLASS ILLEGAL_FUNCTION ();

You can't pass or return incomplete types in a value password, just like a variable that cannot be defined. Of course, the limitation is equally added to the member function, just like adding in a stand-alone function. As you can't write the above Illegal_Function (), you can't write:

Struct Illegal_class {

MY_CLASS F ();

}

Incomplete type and template

Understand the influence of the incomplete type on the template, the best from this experience method: When you see a class template x , imagine that it is a normal type, and use some Specific types replace it. If you use an incomplete type instead of T and get a legitimate class, you can determine that x can be instantiated with incomplete type. So, for example, you can write the list_node classes we see above as a template:

Template

Struct List_node {

T value;

List_node * next;

}

Incomplete type is LIST_NODE instead of T itself. Can you define incomplete types as a template? Of course! C standard [Note 4] even clearly said. You can't instantiate List_node in an incomplete type (that is illegal; we already have a T type member variable), but that is because of the special restrictions on List_Node, not because there is any special restriction on the template. Do not do this:

Template

Struct PTR_LIST_NODE {

T * pTR_Value;

PTR_LIST_NODE * Next;

}

Class my_class;

PTR_LIST_NODE p;

Instant PTR_LIST_NODE is legally used in class MY_CLASS, even if we have only a forward decision of MY_CLASS; a variable of PTR_LIST_NODE is also legal. This is different from the common class such as the template such as List_Node or PTR_List_Node and INT_LIST_NODE.

However, the joint use pre-deciphery and template did introduce new issues in the non-template class.

For example, consider this class:

Template

Struct x {

T f () {

T TMP;

Return TMP;

}

}; This looks very much like an example of Illegal_class above. We have a member function f () that returns a T type value and we have a T type local variable. Obviously, this is not done when T is incomplete type, so you may think that if only my_class's forward declaration, write x is illegal. However, in fact, this is not wrong. why?

This is a technical problem, but it is very simple: a function template does not check (except for trivial syntax errors) unless it is instantiated, and the member function is not instantiated unite. Call x (). F () is illegal (you use my_class in a way to incomplete type, but only write x is no problem; it does not trigger something that will cause problems Instantiation.

Of course, this is not a very interesting example: x has only one member function that cannot be used. However, it does remind us that we should pay attention to the exquisite location of things being instantiated. When we mix templates and incomplete types, there are two key points: the incomplete type is completed (that is, we see the definition of the class rather than just the point of the forward declaration), and instantiate points. Between the two, interesting things may happen. For example, you may instantiate x , then define my_class, only X :: f () will only be instant thereafter.

Template

Struct x {

T f () {

T TMP;

Return TMP;

}

}

Class my_class;

X x;

Class my_class {

...

}

Why do you expect such a definition chain? This has an important reason: it allows you to use x inside my_class its own definition. You can have a member variable of x type, and you can even inherit from x . This may look cycle, and very like MY_CLASS is inheriting from itself, but it is not more cyclic to the class that points to your own pointer than INT_LIST_NODE. Every step in the chain is legal: x is written in a way that can be instantiated with an incomplete type, and we can certainly freely define a full type later.

We are close to the real thing. In practice, you certainly don't have to have trouble before: You can immediately define my_class and use x . (In the definition body of the class, the compiler always acts as if it has seen a forward declaration of the class being defined.) Barton and Nackman [Note 5] show how to use structural base classes and policy base classes This trick:

Class ComplexFloat:

Public Fieldcategory

{

...

}

The base class encapsulates all mathematical domain models shared. Base classes and derived classes are interdependence: FieldCategory needs to get Operator * = () from ComplexFloat, then supplies POW () and repeat () to ComplexFloat.

Standard container

We have deviated from the original problem. We have talked about incomplete types and templates, but did not mention standard containers. The standard did not define them in the form of "Curiously Recurring Template Pattern", and this skill is in this form of [Note 6]. So, where is the incomplete type of container?

We have seen several forms of nearly looped things through the predecessor, but there is still a kind of we haven't seen it yet. INT_LIST_NODE This type of class meaning a pointer points to another int_list_node, but this is not very flexible. First, we might want to have a node pointing to the other n nodes instead of only one. (Many applications include a tree structure, and one node may have any child nodes - for example, consider XML.) Second, the pointer can not be very convenient [Note 7] (WQ Note, Standard STL container is always value semantic To avoid troublesome ownership and life problems). Obviously, we can't define a class x, which contains an an array of X-like - even if we can, the array cannot be variable. But can we replace this? Struct Tree_Node {

Int value;

Std :: Vector Children;

}

From an external performance, it is very similar to each object of this class contains n identical other instances. This is intentional: the STL container such as Vector is close to the built-in array. The i-i member of a node is N.Children [i], and because the child member is a Tree_Node object, not only the pointer. We can copy the entire subtree with only one line:

Tree_node n2 = n1;

Don't worry about memory conventions or explicit deep copies. It looks cyclic, but the expression of the loop does not necessarily illegally; as we have seen, it is really a cycle. All required is: Define a Vector and T is an incomplete type.

When the standardization committee originally realized this is an outstanding issue, Tree_Node's example is the first test I tried. I don't know what to expect; I certainly know the version of the version of this special std :: vector (I) never thought about this possibility. What is surprised, it works! Immediately, we have begun to consider a more likely to happen, for example, Greg Colvin, for implementing a finite element state, and each State object contains a std :: map :

Struct state {

Int value;

Std :: Map next;

}

Hey, the state machine is the first to indicate that this problem is not as simple as what we expect. This state machine compiles, and after a moment, we realize that you should not try it - it should be obvious that anything like is not working. Then, with more tests, we found that even the examples such as Tree_Node cannot work on all STLs. In the end, it is too dark to accept it too dark; the Standardization Committee believes that there is no other choice, except that the STL container cannot cooperate with incomplete types. Additionally, we also apply for the rest of the standard runtime. Is there std :: complex or std :: basic_istream meaningful when t or char is not defined? It is almost certainly no meaning.

C standard [Note 8] said that the template in the standard run library is not allowed: "The consequence is unknown ... If the incomplete type is incomplete type when instantiation template components (WQ note, with the original: the Effects are undefined ... if an incomplete type ies used as a template argument means "". Some of the actual allowed to do this in some cases, but that is just an accident. (Remember, "Undefined Behavior" covers all possible - including it might as you expect.) Review, after that technology has been better understood, then the decision still looks basic correct. Yes, in some cases, some standard containers may be implemented in an incomplete type - but it is also very clear, in other cases it is difficult or impossible. It is completely luck, the first test we try, use std :: Vector, happening is easy.

It is easy to understand, define std :: Map and k or v is incomplete type, which is quite unwitten. After all, std :: map value_type (the type of object stored in the container) is std :: pair . PAIR has a T1 type member variable and a T2 type member variable. You can't have an incomplete type member variable, and instantiate MAP inevitably needs to instantiate PAIR .

How do other standard containers say, such as List or SET? Here, we entered the implementation details; it is difficult to clearly prove that instantiate std :: List or std :: set is impossible. But it is easy to understand why it does not work in the existing work of these containers, and why does it allow it to work? These containers are usually implemented in the form of a node; for example, the nodes of the SET look like this:

Template

Struct rb_tree_node {

V value;

RB_TREE_NODE * PARENT, * LEFT, * RIGHT;

Bool color;

}

Of course, the problem is that the member variable value: It means that we cannot instantiate RB_Tree_Node with incomplete types, so it means (if set is implemented in this way,) We cannot instantiate the SET in an incomplete type. Can I update this limit in other ways? possible. However, according to I know, no one has tried - I am afraid that there will be no one will try, because the feasible method of winding restrictions will cause SET to become large or slower or both.

For Vector, there are other methods. The C standard does not specify how VECTOR should be implemented, but for the situation here, the feasible implementation is to allow T as an incomplete type implementation. For the straight cross-cutting of std :: vector, the write method is similar to this:

Template

Class vector {

...

Private:

Allocator A;

T * buffer;

TypeName Allocator :: Size_Type Buffer_size;

TypeName Allocator :: Size_Type Buffer_capacity;

}

There is no thing that requires T is a complete type; ahead is sufficient. And there is no obvious change (inheriting from allocator, using three pointers instead of a pointer plus two integers, etc.) will affect this. Indeed, when it tested Tree_Node again, it passed [Note 9] on the top three compilers I tried.

Where is what we are? The design of the loop Tree_Node is very good for some purposes, but as we have seen, we can't have it: it is clearly prohibited by the C standard. But this does not necessarily mean that the standard library is no use of this design. Important ideas is the design on the surface (class x contains a container as a member variable, and the value_type of this container is x): It is a secondary program in a class. The C standard says that you are not allowed to use any standard container classes, but the standard container is not the only choice. The C standard defines the interface of the container, not just a group of unconcerable classes, and any container class satisfying the interface is equally well to the schema of the running library with the predefined classes such as List and Set.

In the Future Revision of C , relax in the restriction on the standard Runbelry template with incomplete types may be meaningful. Clearly, conventional ban should continue to exist - instantiation templates with incomplete type is a trouble, and there are no significant differences in the standard runtime library. However, it may be relaxed in a case, and Vector looks a good candidate in such a special case: it is a standard container class, and there is a good reason to instantiate it with an incomplete type, and standard run The implementation of the library wants to work. Today, in fact, the implementation has to deliberate it!

Note

[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 not ever be completed See .9, paragraph 6, of the C Standard.?. HOWEVER, THE MOSTANTANT 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, Firstice-Hall, 1978). I Meant Ithen 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] JO Coplien. "A curiously recurring template pattern," february 1995, . [7] See my column "The Standard Librarian: Containers of Pointers," C / C users Journals Forum forum , .

[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.