CUJ: Standard Library: Container for accommodating pointers

The Standard Librarian: I / O and Function Objects: Containers of Pointers

Matthew austern

http://www.cuj.com/experts/1910/AUStern.htm?topic=Experts

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

Like most things in the standard C run library, standard container classes are used to parameterize: You can create a std :: vector to accommodate int type objects, create a std :: Vector to accommodate the String object, create a std :: Vector to accommodate the user's custom type object. Create a std :: vector , std :: vector or std :: vector is also completely reasonable. It is also important to accommodate pointers.

Unfortunately, although it is a common technology, the container of accommodation pointers is also one of the most common roots of chaos for novices. There is almost no week in the C newsgroup: why this code causes memory leaks:

{

Std :: vector v;

For (int i = 0; i

v.insert (new my_type (i));

...

} // v is Destroyed Here

This memory leak is a bug of the compiler? Std :: vector destructor does not destroy the elements of V?

If you think about how std :: Vector is generally working, and you know the words that don't have a special rule in which the pointer does not have a special rule - that is, MY_TYPE * is just another T. - It is not difficult to understand why vector has such a behavior and why this code has memory leak. However, the behavior of Vector may be surprised by those familiar with the old container library.

This article explains how the behavior of the container that accommodates the pointer is useful, and what is done when the container of the pointer will be useful, and what is done when needed to perform more tasks than the standard container in memory management.

Containers and ownership

Standard containers use value semanties. For example, when you add a variable x to a vector:

v.push_back (x)

You are actually doing an additional copy of X. This statement stores the value of X (a copy) instead of the address of the X. After you add X to a Vector, you can do what you want to do, such as being destroyed to it or let it leave the living domain - without affecting the copy of the Vector. The elements in a container cannot be an element of another container (the elements of the two containers must be different objects, even if these elements happen to equal), and remove one element from the container will destroy this element (although it has the same Another object of the value may exist elsewhere). Finally, the container "has" its element: When a container is destroyed, the elements are destroyed with it.

These features are very similar to the usual buccal array and may be too obvious and not worth mentioning. I lists how similar it is to clearly display containers and arrays. The most common concept that happened when using standard containers is that the container "behind the scene" is more than practical. Value is not always what you need: Sometimes you need to store the address of the object in the container instead of the value of the copy object. You can use the container to implement quotes with the same way as the array: with explicit requirements. You can put any type of object into the container [Note 1], and the pointerself is a very good object. The pointer takes up memory; can be assigned; there is address; there is a value that can be copied. If you need to store the address of the object, use the container of the pointer. No longer writing:

Std :: vector v;

MY_TYPE X;

...

v.push_back (x);

You can write:

Std :: vector v;

MY_TYPE X;

...

v.push_back (& ​​x);

I don't have any changes. You are still being created a std :: Vector ; only T happens to be a pointer type, my_type *. Vector still "has" its elements, but you must understand what these elements are: they are pointers, not what they point to pointers.

The difference between the pointer and the thing that has a pointer refers to it is like a vector and an array or partial variable. If you write:

{

MY_TYPE * P = New my_type;

}

When leaving the code domain, the pointer P will disappear, but it points to the object, * P, does not disappear. If you want to destroy this object and release its memory, you need yourself to complete, explicitly write Delete p or use other equivalents. Similarly, there is no special code in std :: Vector to traverse the entire vector and call each element to call Delete. The element disappears when VECTOR disappears. If you want to have another thing in front of those elements, you must do it yourself.

You may be strange why std :: Vector and other standard containers are not designed to do some special actions for pointers. First of all, of course, there is a simple consistency: understanding that a uniform semantic library is easy to understand that there are many special cases. If there is a special case, it is difficult to draw the boundary line. Are you equivalent to the type of the handle type of Iterator or user-defined? If there is an exception to Vector on a general rule, do you have an exceptional exception to a vector ? How does the container know when using Delete P, when do you use delete [] P?

Second, and more importantly: If std :: vector does automate the object to be directed, the use of the std :: Vector is greatly reduced. After all, if you expect a vector with a series of MY_TYPE objects, you already have vector . Vector is for you to use some different things, when the value of the value and strong ownership is not suitable. When you have an object being referenced by multiple containers, or when you have multiple times in the same container, or when you start to point to a valid object, you can use the container that accommodates the pointer. (They may be NULL pointers, pointing to native memory pointers, or pointers to sub-objects.)

Imagine a special example:

l You are maintaining a task chain list, some tasks are currently active, some hang. You use a std :: list to store all tasks, with a std :: vector to store the task subset of event tasks. l Your program has a string table: std :: Vector , each element P pointing to an array of NULL ends. Depending on how you design your string table, you may use string text, or point to a huge character array - no matter which method, you can't use a loop to traverse the Vector, and call the delete P for each element .

l You are doing I / O Multiplexing and pass a std :: Vector to a function. Input stream is open from elsewhere, it will be closed elsewhere, and maybe one is & std :: cin.

If the container that accommodates the pointer is more handful of DELETE, the above usage is not possible.

Have all the objects pointing

If you have created a container that accommodates pointers, the reason should usually be creating and destroyed from elsewhere. Is there a reason to have a reason to get a container, it has a pointer itself, but also the object pointing? some. I know the only good reason, but it is also very important: polymorphism.

The polymorphism in C is bound to the pointer / reference semantic. If, for example, Task is not just a class, and it is a base class of a inheritance system. If P is a task *, then p may point to a Task object or any object that is derived from Task. When you call a virtual function of Task through the P, the corresponding function will be called in the actual type pointed to P.

Unfortunately, the base class that will be used as a polymorphism means you can't use Vector . The object in the container is a stored value; the elements in Vector must be a Task object, and cannot be a derived class object. (In fact, if you follow the base class of the inheritance system must be an abstract base class advice, then the compiler will not allow you to create a Task object and a Vector object.)

Object-oriented design usually means that you have access to objects between objects being created to objects, you can access objects through pointers or references. If you want to have a set of objects, in addition to the container that accommodates the pointer, you have almost no choice [Note 2]. What is the best way to manage such a container?

If you are using containers that accommodate pointers to have a set of objects, the key is to make sure all objects are destroyed. The most obvious solution may also be the most common, in front of the destruction of the container, travers it, and call the DELETE statement for each element. If you write this loop too much, it is easy to make a packaging:

Template

Class my_vector: private st :: vector

{

Typedef std :: vector base;

PUBLIC:

USING BASE :: Iterator;

USING BASE :: Begin;

USING BASE :: End;

...

PUBLIC:

~ my_vector () {

ITerator I = Begin (); i! = end (); i)

Delete * i;

}

}

This skill can work, but it is more limit and requirements than it looks.

The problem is that it is not enough to correct the system. If you have a container that lists all objects that is being destroyed, you'd better make sure that as long as the pointer leaves the object, it is destroyed, and a pointer does not appear twice in the container. When you use Erase () or Clear () to remove pointers, you must be careful, but you also need to be careful of the value of the container and the assignment of Iterator: Items V1 = V2, and V [N] = p This operation is dangerous of. Standard generic algorithm, there are many assignments that will be implemented through Iterator, which is another danger. You obviously can't use generic algorithms such as std :: copy () and std :: replace (), you can't use std :: remove (), std :: remove_if (), and std :: remove_if (), and std: : unique () [Note 3]. Packaging classes such as MY_Vector can solve some of these problems, but not all. It is difficult to see how to prevent users from using assignments in danger, unless you prohibit all assignments - and then, you will not be much like a container.

The problem is that each element must be tracked separately, so perhaps the way is that the packaging pointer is not packaged throughout the container.

The standard runtime defines a class std :: auto_ptr of the pointer package. A Auot_ptr object holds a T * type pointer P, which constructs the object Delete by the object. It seems that this is what we are looking for: a packaging class, its destructor delete a pointer. Naturally, it will be desirable to replace Vector with vector >.

This is a natural idea, but it is wrong. The reason, once again, it is because of the value semantics. The container class assumes that they can copy their own elements. For example, if you have a Vector , then Type Types must behave as the same as a usual value. If T1 is a T type value, you'd better write:

T T2 (T1)

And obtain a copy T2 of T1.

In the form, press the C standard, T, to be Assignable and CopyConstructible. The pointer meets these requirements - you can get a copy of the pointer - but Auto_Ptr is not satisfied. The selling point of Auto_PTR is its right to maintain strong, so it is not allowed to copy. There is something on the form of a copy constructor, but the "copy constructor" of Auto_PTR actually does not copy. If T1 is a std :: auto_ptr , and you write:

Std :: auto_ptr t2 (t1)

Then T2 will not be a copy of T1. Not a copy, but a transfer of ownership - T2 gets the value of T1, and T1 is changed to a NULL pointer. Auto_PTR's object is fragile: You can only change its value when you look at it.

In some implementation, when you try to create a Vector >, you will get a compile period error. This is still a lucky; if you are not fortunate, things look very well until the running period is unpredictable. In summary, the standard container class cannot work with the copy constructor does not perform a copy of the copy. This is not the design purpose of Auto_Ptr, and standard [Note 4] even pointed out that "the container in the standard running library with auto_ptr will get undefined behavior." When you need an abnormal security mechanism, you should use Auto_PTR to Exit the code space when the DELETE pointer; Auto_Ptr is named due to the simulated automatic variable. You should not try to use Auto_Ptr to manage pointers in the container class; it is not feasible. Replace Auto_PTR, you should use a different "smart pointer", reference to the counting pointer class. Pointer tracking with reference counts how many pointer points to the same object. When you construct a copy of a reference count pointer, count plus 1; when you destroy a reference count pointer, count reduction. When the count becomes 0, the object referred to by the pointer is automatically destroyed.

Pointer clauses that write a reference count are not particularly difficult, but it is not almost nothing. It doesn't have to do it; Fortunately, the use of reference count does not mean you need to write a reference count of your own references; several such classes already exist and free to use. For example, you can use Boost's Shared_PTR class [Note 5]. I expect Shared_PTR or other similar things will become an integral part of the C standard's next revision.

Of course, the reference count is only a special garbage collection. Like all forms of garbage recycling, it automatically destroys the object you no longer need. The main advantage of reference counting pointers is that they are easy to join existing systems: SHARE_PTR This mechanism is just a small separate class, which you can use in a part in a larger system. On the other hand, the reference count is a minimal effect of garbage collection (assignment and copy of each pointer require some related complex processing), the most flexible form (when two data structures have mutual pointers, You have to be careful). Other forms of garbage collection work is equally good in C programs. In particular, Boehm Conservative Garbage Collector [Note 6] is free, portable and is well tested.

If you use a conservative garbage collector, you only need to link it to the program. You don't need to use any special pointer packaging classes; just allocate memory instead of careless delete it. Special, if you create a vector , you know that the object you point to, as long as the vector still exists, it will not be dropped by Delete (the garbage collector will never destroy the object to the object), and you also know They will drop DELETE at some time after the vector is destroyed (unless otherwise referred to the program).

The advantages of garbage recovery - whether the reference count or conserved garbage collector, or other method - is it completely uncertainty of the living life of the object: You don't need to master which part of a certain time program This object is referenced. On the other hand, the disadvantage of garbage collection is also this! Sometimes you do know the survival of the object, or at least know that the object should not continue after a particular state of the program. For example, you may have a complex analysis tree; maybe it fills a polymorphic object, maybe it is too complicated and unable to grasp each node alone, but you can determine that you will no longer need them after the analysis is Any one.

From manual management Vetor to Vector > to the conserved garbage collector, we gradually abandoned the view of a set of objects; the premise of garbage collection is that the object's "ownership" is irrelevant. . In a sense, it solves this problem by throwing away the "ownership" problem. If your program does have a statement that is clearly defined, then you may have a reason to desire to destroy a set of objects at the end of a state. Instead of garbage collection, another alternative method is to allocate an object through an Arena (WQ Note: Dictionary for "Arena, Stage", the translation is not good, not translated) to allocate objects: maintain a list of objects, so that you can destroy once All objects.

You may want to know how great this technology and the technology mentioned above (traversing containers and calling Destory () for each element ()). Is there a substantive difference? If not, let me spend so dangerous and restrictions, what do you say?

The difference is small, but it is very important: Arena stores an object set for the purpose of delete in the future, and there is no other purpose. It can be implemented in the form of a standard container, but it does not expose the container interface. You encountered problems on Vector because you can remove elements, copy override elements, and use generic algorithms. Arena is a strong ownership agreement. The ARENA container contains one and only a pointer for each object it managed, and it has all of these objects; it does not allow you to remove, copy, override or use the pointer to which it is contained in the selection. To use objects in Arena, you need to store the pointer to them elsewhere - in the container, in the tree, or in any suitable data structure. Use rights and ownership completely separated.

Arena is a universal idea. Arena may be simply a container, just remember that you don't use unsafe member functions, or it can be a packaging class to try to run safer. Many such packaging classes have been written out [Note 7]. Listing 1 is a simplified example of an Arena class that uses an implementation skill to make it else to use a different ARENA class for each pointer type. For example, you may write:

Arena a;

...

Std :: vector v;

v.push_back (a.create (3));

...

A.DESTROY_ALL ();

We almost returned to the starting point: using a VECTOR that accommodates pointers, the object points to the object is owned and managed.

to sum up

The pointer is very common in the C program, and the standard container is the same; without surprising, their compositions, accommodating pointer containers are also common.

The biggest difficulty of novices is the ownership problem when accommodating the container of the pointer: When should you point to the object pointing to? Most of the technologies that handle containers that house pointers can be attempted to a principle: if you have a container that accommodates pointers, the object to which you point to it should be owned by other places.

l If the non-polymorphic object set (type MY_TYPE) is being processed, you should store the value of the object into a container, such as list or deque . If needed, you also use the second container to store pointers to those objects.

l Do not try to put auto_ptr into a standard container.

l If there is a set of polymorphic objects, you need to manage them with containers that accommodate pointers. (However, those pointers can be packaged in some Handle class or smart pointer class.) When the object survival is not predict, or when it is not important, the easiest method is to use garbage recycling. Two simplest choices for garbage collection are references to count pointers and conserved garbage collectors. Which is the best choice for you depends on the availability of the tool. l If you have a set of polymorphic objects, and you need to control their living expectations, the easiest way is to use Arena. A simple ARENA class example is shown in Listing 1.

Listing 1: a Simple Arena Class

#include

Class arena {

Private:

Struct Holder {

Virtual ~ Holder () {}

}

Template

Struct Obj_holder: Public Holder {

T Obj;

Template

Obj_holder (arg1 arg1)

: Obj (arg1) {}

}

Std :: Vector Owned;

Private:

ARENA (Const Arena);

Void Operator = (Const Arena);

PUBLIC:

Arena () {}

~ arena () {

DESTROY_ALL ();

}

Template

T * Create (arg1 arg1) {

Obj_holder * p = new obj_holder (arg1);

OWNED.PUSH_BACK (P);

Return & P-> OBJ;

}

Void destroy_all () {

Std :: vector :: size_type i = 0;

While (I

Delete OWNED [I];

i;

}

OwNed.clear ();

}

}

Note

[1] Well, Almost Any: There is the rescussed later - on the objects you put in a container. Most Reasonable Types Conform To Those Restrictions; Pointers Certainly DO.

[2] There is one sense in which you have a choice:. You can simulate value semantics by hiding polymorphic pointers inside a non-polymorphic wrapper class See, for example, James Coplien, Advanced C Programming Styles and Idioms (Addison-Wesley, 1991), for a discussion of this "envelope and letter" idiom. See also chapter 14 of Andrew Koenig and Barbara Moo's Accelerated C (Addison-Wesley, 2000), for a family of generic handle classes. However, while the envelope-and -letter idiom is useful, it is also fairly heavyweight and it will affect many aspects of your design. Unless you have other reasons for using an envelope-and-letter design, it would be silly to turn to it just for the sake of container classes. [3] See Harald Nowak, "A remove_if for vector ," C / C Users Journal, July 2001, for an explanation of the problems with remove and remove_if, and for a technique that avoids them. However, THIS TECHNIQUE Does Not Generalize to Unique.

[4] 0.4.5, Paragraph 3.

[5] .

[6] Hans-J. Boehm, "A Garbage Collector for C and C ," .

[7] See, For Example, Andrew Koenig, "Allocating C Objects in Clusters," Journal of Object-Oriented Programming, 6 (3), 1993.