C++16种堆栈实现

Sixteen Ways to Stack a Cat Bjarne Stroustrup AT&T Bell Laboratories Murray Hill, New Jersey 07974 ABSTRACT This paper presents a series of examples of how to represent stacks in a program. In doing so it demonstrates some of the fundamental techniques and tradeoffs of data hiding as seen in languages such as C, Modula2, and Ada. Since all the examples are written in C++ it also demonstrates the flexibility of C++’s mechanisms for expressing data hiding and access. 1 Introduction Consider representing a stack of objects of some type in a program. Several issues will affect our design of the stack class: ease of use, run time efficiency, cost of recompilation after a change. We will assume that messing around with the representation is unacceptable so that data hiding for the representa- tion is a must. We will assume that many stacks are necessary. The type of the elements on the stacks is of no interest here so we will simply call it cat. The implementations of the various versions of stacks are left as an exercise for the reader. Please note that the purpose is to illustrate the diversity of data hiding techniques, not to show how best to represent stacks in C++. The techniques shown here apply to a variety of types – most of which are more interesting than stacks – and will be used in conjunction with other techniques. For example, if you actu- ally wanted to build a better stack for C++ you would probably start by making cat a parameter, that is, use templates†. This paper is a fairly lighthearted play with C++ features and techniques. I think it has something to delight and possibly horrify novices and seasoned C++ programmers alike. Most of the techniques shown have serious uses, though. 2 Files as Modules Consider the traditional C notion of a file as a module. First we define the interface as a header file: // stack interface, stack.h: typedef int stack_id; stack_id create_stack(int); void destroy_stack(stack_id); void push_stack(stack_id,cat); cat pop_stack(stack_id); The integer argument to create_stack is the maximum size of the desired stack. We can now use stacks like this: __________________ † See Chapter 14 of Ellis&Stroustrup: The Annotated C++ Reference Manual. Addison Wesley. 1990. - 2 - #include "stack.h" void f(int sz, cat kitty) { stack_id s = create_stack(sz); push_stack(s,kitty); cat c2 = pop_stack(s); destroy_stack(s); } This is rather primitive, though. Stacks are numbered, rather than named; the concept of the address of a stack is ill defined; copying of stacks is undefined; the lifetimes of stacks are exclusively under control of the users; the technique relies on the convention of .h files and on comments to express the concept of a stack; the names of the stack functions are clumsy. From a C++ perspective, the problem is that there are no stack objects defined. These stacks do not obey the general language rules for naming, creation, destruction, access, etc. Instead, little ‘‘cookies’’ (the stack_ids) are passed to functions that manipulate stack representations. Note that in many contexts it would be reasonable not to impose a maximum size on a stack. Not imposing a maximum would allow a noticeable simplification of the stack interface. However, this would decrease the value of the stack example as a vehicle for discussion of general data hiding issues because most types do require arguments to the operations that create objects. 3 Stack Identifiers We can do a little better. First let us make stack_id a genuine type: // stack interface, stack.h: struct stack_id { int i; }; stack_id create_stack(int); void destroy_stack(stack_id); void push_stack(stack_id,cat); cat pop_stack(stack_id); This at least will prevent us from accidentally mixing up stack identifiers and integers: #include "stack.h" void f(int sz, cat kitty) { stack_id s = create_stack(sz); push_stack(s,kitty); cat c2 = pop_stack(sz); // error: stack_id argument expected destroy_stack(s); } This error would not have been caught by the compiler given the first definition of stack_id. These first two versions both have the nice property that the implementation is completely hidden so that it can be changed without requiring recompilation of user code as long as the interface remains unchanged. 4 Modules Now let us use a class to specify this stack module. Doing that will allow us to avoid polluting the glo- bal name space and relying on convention and comments to specify what is and isn’t part of a stack’s inter- face: - 3 - // stack interface, stack.h: class stack { public: struct id { int i; }; static id create(int); static void destroy(id); static void push(id,cat); static cat pop(id); }; We can use this module like this: #include "stack.h" void f(int sz, cat kitty) { stack::id s = stack::create(sz); stack::push(s,kitty); cat c2 = stack::pop(s); stack::destroy(s); } This looks very much like a Modula-2 module. We don’t have a ‘with’ or ‘use’ construct to avoid the repe- tition of ‘‘stack::’’. For example: void f(int sz, cat kitty) { use (stack) { // pseudo code id s = create(sz); push(s,kitty); cat c2 = pop(s); destroy(s); } } However, such a construct for merging name spaces is a syntactic detail and does not always lead to more readable code. Further, an even more radical simplification of the notation is achieved in section 10. Note that static member functions were used to indicate that the member functions do not operate on specific objects of class stack; rather, class stack is only used to provide a name space for stack oper- ations. This will be made explicit below. 5 Modules with Sealed Identifiers To make the correspondence to Modula-2 modules more exact, we need to stop people from messing around with the stack identifiers and stop them from trying to create (C++ style) stack objects: - 4 - // stack interface, stack.h: class stack { public: class id { friend stack; private: int i; }; static id create(int); static void destroy(id); static void push(id,cat); static cat pop(id); private: virtual dummy() = 0; }; The representation of an id is now accessible only to class stack, ‘‘the implementation module for stacks,’’ and class stack is an abstract class so that no objects of class stack can be created: stack x; // error: declaration of object of abstract class stack The use of a pure virtual function to prevent the creation of objects is a bit obscure, but effective. An alternative technique would have been to give stack a private constructor. Naturally, the example of stack usage from section 4 works exactly as before. 6 Packages In the style of Modula-2, we are now passing around ‘‘little cookies’’ (opaque types) used by the imple- mentation module to identify the objects. If we want we can pass around the objects themselves (or point- ers to them) in the style of Ada: // stack interface, stack.h: class stack { public: class rep { friend stack; private: // actual representation of a stack object }; typedef rep* id; static id create(int); static void destroy(id); static void push(id,cat); static cat pop(id); private: virtual dummy() = 0; }; The typedef is redundant, but it allows our user code to remain unchanged: - 5 - #include "stack.h" void f(int sz, cat kitty) { stack::id s = stack::create(sz); stack::push(s,kitty); cat c2 = stack::pop(s); stack::destroy(s); } That rep is very much like an Ada private type. Users can pass it around but not look into it. One disadvantage is that by placing the representation of stacks in the declaration of class stack we force recompilation of user code when that representation changes. This can lead to a major increase in compilation time. Actually, this recompilation isn’t necessary, because the user code and that code’s use of information about the implementation was left unchanged. A reasonably smart dependency analyser could deduce that no recompilation of user code is necessary after even a radical change to the representation. However, a dumb (that is, time stamp on source-file based) dependency analyser will not deduce that and will recompile user code just because the representation was changed. A smart dependency analyser will rely on smaller units of change, on understanding of the semantics of C++, or on both to minimize recompi- lation. Smart dependency analysers are rumored to exist, but they are not widely available. On the positive side, the representation information is now available to the compiler when compiling user code so that genuine local variables can be declared and used: #include "stack.h" void g(int sz, cat kitty) { stack::rep s; stack::push(&s,kitty); cat c2 = stack::pop(&s); } This is unlikely to work without additional code in the implementation, though, unless some mechanism for initializing a stack representation exists. This could be done by adding suitable constructors and destructors to class rep, but it would be more in the spirit of packages to provide an explicit initialization function. It would also be natural to support use reference arguments to eliminate most explicit pointers. // stack interface, stack.h: class stack { public: class rep { friend stack; // actual representation of a stack object }; static rep* create(int); static void destroy(rep&); static void initialize(rep&,int); static void cleanup(rep&); static void push(rep&,cat); static cat pop(rep&); private: virtual dummy() = 0; }; The create() function is now redundant (a user can write one without special help from the class), but I have left it in to cater for code and coding styles that relies on it. If needed, it could be made to return a ref- erence instead of a pointer. - 6 - #include "stack.h" void h(int sz, cat kitty) { stack::rep s; stack::initialize(s,sz); stack::push(s,kitty); cat c2 = stack::pop(s); stack::cleanup(s); } The cleanup() operation is needed because the initialize() operation and/or the push() operation are likely to grab some free store to hold the elements. Unless we want to rely on a garbage col- lector we must clean up or accept a memory leak. Now enough information is available to the compiler to make inlining of operations such as initialize(), push(), and pop() feasible even in an implementation with genuine separate compi- lation. The definitions of the functions we want inlined can simply be placed with the type definition: // stack interface, stack.h: class stack { public: class rep { friend stack; // actual representation of a stack object }; // ... static cat pop(rep& x) { // extract a cat from the representation of stack x // return that cat } // ... }; Inlining and genuine local variables can be essential to make data hiding techniques affordable in appli- cations where run time efficiency is at a premium. 7 Packages with Controlled Representations Alternatively, if we did not want users to allocate reps directly we could control the creation and copy- ing of reps by making these operations private: - 7 - // stack interface, stack.h: class stack { public: class rep { friend stack; // actual representation of a stack object rep(int); // constructor rep(const rep&); // copy constructor void operator=(const rep&); // assignment operator }; static rep* create(int); static void destroy(rep&); static void initialize(rep&,int); static void cleanup(rep&); static void push(rep&,cat); static cat pop(rep&); private: virtual dummy() = 0; }; This ensures that only the stack functions can create reps: stack::rep* stack::create(int i) { rep* p = new rep(i); // fine: create is a member of stack // ... return p; } f() { stack::rep s(10); // error: f() cannot access rep::rep(): private member } Naturally, the example of stack usage from section 6 works exactly as before. 8 Packages with Implicit Indirection If we are not interested in inlining but prefer to minimize recompilation costs even when we don’t have a smart dependency analyser, we can place the representation ‘‘elsewhere:’’ - 8 - // stack interface, stack.h: class stack_rep; class stack { public: typedef stack_rep* id; static id create(int); static void destroy(id); static void push(id,cat); static cat pop(id); private: virtual dummy() = 0; }; This scheme keeps implementation details not only inaccessible to users but also out of sight. With this definition (alone) a user cannot allocate stack_reps. Unfortunately C++ does not allow you to define a class ‘‘elsewhere’’ and have its name local to another class. Consequently, the name stack_rep must be global. The indirection (implied by the use of id) is implicit to the users of stacks and explicit in the imple- mentation of stacks. 9 Simple Minded Types One simple improvement would be to put the operations that create and destroy stack_reps into class stack_rep. Actually, for a C++ programmer it would be natural to put all the operations into the rep and rename it ‘‘stack:’’ // stack interface, stack.h: class stack { // actual representation of a stack object public: typedef stack* id; static id create(int); static void destroy(id); static void initialize(id,int); static void cleanup(id); static void push(id,cat); static cat pop(id); }; so that we can write: #include "stack.h" void f(int sz, cat kitty) { stack s; stack::initialize(&s,sz); stack::push(&s,kitty); cat c2 = stack::pop(&s); stack::cleanup(&s); } The redundant use of the typedef ensures that our original program still compiles: - 9 - #include "stack.h" void g(int sz, cat kitty) { stack* p = stack::create(sz); stack::push(p,kitty); cat c2 = stack::pop(p); stack::destroy(p); } The likely difference between f() and g() is two memory management operations (a new in create and a delete in destroy). 10 Types Now all we have to do is to make the functions non-static and give the constructor and destructor their proper names: // stack interface, stack.h: class stack { // actual representation of a stack object public: stack(int size); ˜stack(); void push(cat); cat pop(); }; We can now use the C++ member access notation: #include "stack.h" void f(int sz, cat kitty) { stack s(sz); s.push(kitty); cat c2 = s.pop(); } Here we rely on the implicit calls of the constructor and destructor to shorten the code. 11 Types with Implicit Indirection If we want the ability to change the representation of a stack without forcing the recompilation of users of a stack we must reintroduce a representation class rep and let stack objects hold only pointers to reps: - 10 - // stack interface, stack.h: class stack { struct rep { // actual representation of a stack object }; rep* p; public: stack(int size); ˜stack(); void push(cat); cat pop(); }; The indirection is invisible to the user. Naturally, to take advantage of this indirection to avoid re-compilation of user code after changes to the implementation we must avoid inline functions in stack. If our dependency analyser is dumb we might have to pace representation class rep ‘‘elsewhere’’ as was done in section 8 above. 12 Multiple Representations In all of the examples above, the binding between the name used to specify the operation to be per- formed (e.g. push) and the function invoked were fixed at compile time. This is not necessary. The fol- lowing examples show different ways to organize this binding. For example, we could have several kinds of stacks with a common user interface: // stack interface, stack.h: class stack { public: virtual void push(cat) = 0; virtual cat pop() = 0; }; Only pure virtual functions are supplied as part of the interface. This allows stacks to be used, but not cre- ated: #include "stack.h" void f(stack& s, cat kitty) { s.push(kitty); cat c2 = s.pop(); } Since no representation is specified in the stack interface, its users are totally insulated from implementa- tion details. We can now provide several distinct implementations of stacks. For example, we can provide a stack implemented using an array - 11 - // array stack interface, astack.h: #include "stack.h" class astack : public stack { // actual representation of a stack object // in this case an array // ... public: astack(int size); ˜astack(); void push(cat); cat pop(); }; and elsewhere a stack implemented using a linked list: // linked list stack interface, lstack.h: #include "stack.h" class lstack : public stack { // actual representation of a stack object // in this case a linked list // ... public: lstack(int size); ˜lstack(); void push(cat); cat pop(); }; We can now create and use stacks: #include "astack.h" #include "lstack.h" void g() { lstack s1(100); astack s2(100); cat ginger; cat blackie; f(s1,ginger); f(s2,snowball); } 13 Changing Operations Occasionally, it is necessary or simply convenient to replace a function binding while a program is run- ning. For example, one might want to replace lstack::push() and lstack::pop() with new and improved versions without terminating and restarting the program. This is fairly easily achieved by taking advantage of the fact that calls of virtual functions are indirect through some sort of table of virtual func- tions (often called the vtbl). The only portable way of doing this requires cooperation from the lstack class; it must have a con- structor that does no work except for setting up the vtbl that all constructors do implicitly: - 12 - class noop {}; lstack::lstack(noop) {} // make an uninitialized lstack Fortunately such a constructor can be added to the program source text without requiring recompilation that might affect the running program that we are trying to update (enhance and repair). Using this extra constructor we define a new class which is identical to lstack except for the rede- fined operations: // modified linked list stack interface, llstack.h: #include "stack.h" class llstack : public lstack { public: llstack(int size) : lstack(size) {} llstack(noop x) : lstack(x) {} void push(cat); cat pop(); }; Given an lstack object we can now update its pointer to its table of virtual functions (its vtbl) thus ensuring that future operations on the object will use the llstack variants of push() and pop(): #include "llstack.h" void g(lstack& s) { noop xx; new(&s) llstack(xx); // turns s into an llstack! } Naturally, we must rely on some form of dynamic linking to make it possible to add g() to a running pro- gram. Most systems provide some such facility. This use of operator new assumes that // place an object at address ‘p’: void* operator new(size_t,void* p) { return p; } has been defined and relies on the llstack::llstack(noop) constructor for suppressing (re)initialization of the data of s and for updating s’s vtbl. This trick allows us to change the vtbl for particular objects without relying on specific properties of an implementation (that is, portably). There is no language protection against misuse of this trick. Changing the vtbl for every object of class lstack in one operation, that is, changing the contents of the vtbl for class lstack rather than simply changing pointers to vtbls in the individual objects, can- not be done portably. However, since that operation will be messy and non-portable I will not give an example of it. 14 Changing Representations A more interesting – and probably more realistic – challenge is to replace both the representation and the operations for an object at run time. For example, convert a stack from an array representation to a linked list representation at run time without affecting its users. To ensure that the cutover from one repre- sentation to another can be done by a single assignment we reintroduce the rep type and make push() and pop() simple forwarding functions to operations on the rep: - 13 - // stack interface, stack.h: class stack { rep* p; public: stack(int size); ˜stack(); rep* get_rep() { return p; } void put_rep(rep* q) { p = q; } void push(cat c) { p->push(c); } cat pop()