1
`
`GOOGLE-1014
`Google Inc. v. Micrografx LLC
`IPR2014-00532
`
`

`
`C++
`
`Programming
`
`Language
`
`Second Edition
`
`Bjarne Stroustrup
`
`AT&T Bell Laboratories
`
`Murray Hill, New Jersey
`
`A
`77
`
`ADDISON-WESLEY PUBLISHING COMPANY
`
`ewY0r1<
`- Menlo Park, California -
`Reading, Massachusetts
`Don Milis. Ontario - Wokjngham.England - Amsterdam - Bonn
`Sydney - Singapore - Tokyo - Madrid - San Juan - Milan -- Paris
`
`2
`
`

`
`Library of Congress Cataloging-in-Publication Data
`
`Stroustrup, Bjarne.
`The C++ programming language I Bjame Stroustrup. -- 2nd ed.
`p.
`cm.
`Includes bibliographical references and index.
`ISBN 0-201-53992-6
`
`1. C++ (Computer program language)
`plus programming language.
`QA76.73.Cl5S79
`1991
`005. 13‘ 3--dc20
`
`1. Title.
`
`I]. Title: C plus
`
`91-27307
`C[P
`
`1%
`
`Copyright © l99l by AT&T Bell Telephone Laboratories. Incorporated.
`
`Reprinted with corrections June, 1993
`
`All rights reserved. No part of this publication may be reproduced, stored in a retrieval system.
`or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording, or
`otherwise, without the prior written permission of the publisher. Printed in the United States of
`America.
`
`This book was typeset in Times and Courier by the author, using a Linotronic 2[}UP phototype-
`setter and a DEC VA): 8550 running the l{)th edition of the UNIX operating system.
`
`DEC. PDP. and VAX are trademarks of Digital Equipment Corporation. UNIX is a registered
`trademark of AT&T Bell Laboratories.
`
`ll-MA-9'7 96 95 94
`
`3
`
`

`
`Preface
`
`The road goes ever on and on.
`— Bilbo Baggins
`
`As promised in the fil'SI edition of this book, C++ has been evolving to meet the needs
`of its users. This evolution has been guided by the experience of users of widely
`varying backgrounds working in a great range of application areas. The C++ user-
`community has grown a hundredfold during the six years since the first edition of this
`book; many lessons have been learned, and many techniques have been discovered
`and/or validated by experience. Some of these experiences are retlected here.
`
`The primary aim of the language extensions made in the last six years has been to
`enhance C++ as a language for data abstraction and object-oriented programming in
`general and to enhance it as a tool for writing high-quality libraries of user-defined
`types in particular. A “high-quality library," is a library that provides a concept to a
`user in the form of one or more classes that are convenient, safe, and efficient to use.
`
`in this context, safe means that a class provides a specific type-safe interface between
`the users of the library and its providers: e{f_j‘i‘ci'enr means that use of the class does not
`impose significant overheads in run—time or space on the user compared with hand-
`written C code.
`
`through 10 give a
`This book presents the complete C++ language. Chapters I
`tutorial introduction; Chapters l 1 through 13 provide a discussion of design and soft-
`ware development
`issues; and,
`finally,
`the complete C++ reference manual
`is
`included. Naturally, the features added and resolutions made since the original edi-
`
`tion are integral parts of the presentation. They include refined overloading resolu-
`tion, memory management facilities, and access control mechanisms, type—safe link-
`
`age, const and static member functions, abstract classes, multiple inheritance,
`templates, and exception handling.
`C++ is a general-purpose programming language; its core application domain is
`
`4
`
`

`
`In addition, C++ is successfully used in
`systems programming in the broadest sense.
`many application areas that are not covered by this label.
`Implementations of C++
`exist from some of the most modest microcomputers to the largest supercomputers
`and for almost all operating systems. Consequently. this book describes the C++ lan-
`guage itself without trying to explain a particular implementation, programming envi-_
`ronment, or library.
`
`This book presents many examples of classes that, though useful, should be classi-
`fied as “toys." This style of exposition allows general principles and useful tech-
`niques to stand out more clearly than they would in a fully elaborated program, where
`they would be buried in details. Most of the useful classes presented here, such as
`linked lists, arrays, character strings. matrices, graphics classes, associative arrays,
`etc., are available in “bulletproof” and/or “goldplated” versions from a wide variety
`of commercial and non-commercial sources. Many of these “industrial strength"
`classes and libraries are actually direct and indirect descendants of the toy versions
`found here.
`
`This edition provides a greater emphasis on tutorial aspects than did the first edi-
`tion of this book. However, the presentation is still aimed squarely at experienced
`programmers and endeavors not to insult their intelligence or experience. The discus-
`sion of design issues has been greatly expanded to reflect the demand for information
`beyond the description of language features and their immediate use. Technical detail
`and precision have also been increased. The reference manual,
`in particular, repre-
`sents many years of work in this direction. The intent has been to provide a book
`with a depth sufficient to make more than one reading rewarding to most program-
`mers.
`In other words, this book presents the C++ language, its fundamental princi-
`ples, and the key techniques needed to apply it. Enjoy!
`
`Acknowledgments
`In addition to the people mentioned in the acknowledgements section in the preface to
`the first edition, I would like to thank Al Aho, Steve Buroff, Jim Coplien, Ted Gold-
`stein, Tony Hansen, Lorraine Juhl, Peter Iuhl. Brian Kernighan, Andrew Koenig, Bill
`Leggett. Warren Montgomery, Mike Mowbray, Rob Murray, Jonathan Shopiro, Mike
`Vilot. and Peter Weinberger for commenting on draft chapters of this second edition.
`Many people influenced the development of C++ from 1985 to 1991.
`I can mention
`only a few: Andrew Koenig, Brian Kernighan, Doug Mcllroy, and Jonathan Shopiro.
`Also thanks to the many participants of the “external reviews" of the reference man-
`ual drafts and to the people who suffered through the first year of X3] 16.
`
`Murray Hill, New Jersey
`
`Bjame Strousn-up
`
`5
`
`

`
`Preface to the first Edition
`
`Language shapes the way we think.
`and determines what we can think about
`
`— B.L.Whor_-f
`
`C++ is a general purpose programming language designed to make programming
`more enjoyable for the serious programmer. Except for minor details, C++ is a super-
`set of the C programming language.
`In addition to the facilities provided by C, C++
`provides flexible and efficient facilities for defining new types. A programmer can
`partition an application into manageable pieces by defining new types that closely
`match the concepts of the application. This technique for program construction is
`often called data abstraction. Objects of some user-defined types contain type infor-
`mation. Such objects can be used conveniently and safely in contexts in which their
`type cannot be determined at compile time. Programs using objects of such types are
`often called object based. When used well, these techniques result in shorter, easier
`to understand, and easier to maintain programs.
`
`The key concept in C++ is class. A class is a user-defined type. Classes provide
`data hiding, guaranteed initialization of data, implicit type conversion for user—defined
`types, dynamic typing, user-controlled memory management, and mechanisms for
`overloading operators. C++ provides much better facilities for type checking and for
`expressing modularity than C does.
`It also contains improvements that are not
`directly related to classes, including symbolic constants, inline substitution of func-
`tions, default function arguments, overloaded function names, free store management
`operators, and a reference type. C++ retains C’s ability to deal efficiently with the
`fundamental objects of the hardware (bits, bytes, words, addresses, etc.). This allows
`the user—defined types to be implemented with a pleasing degree of efficiency.
`C++ and its standard libraries are designed for portability. The current implemen-
`tation will run on most systems that support C. C libraries can be used from a C++
`
`6
`
`

`
`vi
`
`Preface to the first Edition
`
`program, and most tools that support programming in C can be used with C++.
`This book is primarily intended to help serious programmers learn the language
`and use it for nontrivial projects.
`It provides a complete description of C++, many
`complete examples, and many more program fragments.
`
`Acknowledgments
`C++ could never have matured without the constant use. suggestions, and constructive
`criticism of many friends and colleagues.
`In particular, Toni Cargill. Jim Coplien, Stu
`Feldman, Sandy Fraser, Steve Johnson, Brian Kemighan, Bart Locanthi, Doug Mell-
`roy, Dennis Ritchie, Larry Rosler, Jerry Schwarz. and Jon Shopiro provided important
`ideas for development of the language. Dave Presotto wrote the current implementa-
`tion of the stream HO library.
`In addition, hundreds of people contributed to the development of C++ and its
`compiler by sending me suggestions for improvements, descriptions of problems they
`had encountered, and compiler errors.
`I can mention only a few: Gary Bishop,
`Andrew Hume, Tom Karzes, Victor Milenkovic, Rob Murray, Leonie Rose, Brian
`Schmult, and Gary Walker.
`Many people have also helped with the production of this book, in particular, Jon
`Bentley, Laura Eaves, Brian Kemighan, Ted Kowalski, Steve Mahaney. Jon Shopiro,
`and the participants in the C++ course held at Bell Labs, Columbus, Ohio, June 26—27,
`1985.
`
`Murray Hill, New Jersey
`
`Bjarne Srrousrrup
`
`7
`
`

`
`Contents
`
`Acknowledgments
`
`Preface to First Edition
`
`Acknowledgments
`
`Contents
`
`Notes to the Reader
`
`The Structure of ThisBook
`
`Implementation Notes
`Exercises
`
`Design Notes ............................................................................. ..
`Historical Note
`C and -C++
`
`Efficiency and Structure ....
`Philosophical Note
`Thinking, about Programming in C++ ....................................... ..
`Rules ofThumb
`
`.................................................... ..
`
`Note to C Programmers
`References
`
`-:5—oqooooo\o~.e.L»mro~
`
`8
`
`

`
`A Tour of C++
`
`introduction ............................................................................... ..
`1.1
`1.2 Programming Paradigms
`1.3 "A Better C" ............................................................................ ..
`1.4 Support for Data Abstraction .................................................... ..
`1.5 Support for Object-Oriented Progrtnnming .............................. ..
`1.6 Limits to Perfection .................................................................. ..
`
`Declarations and Constants
`
`2.] Declarations .............................................................................. ..
`2.2 Names
`2.3 Types ......................................................................................... ..
`2.4 Literals ...................................................................................... ..
`2.5 Named Constants ...................................................................... ..
`2.6 Saving Space ............................................................................. ..
`2.7 Exercises ................................................................................... ..
`
`Expressions and Statements
`
`13
`
`13
`14
`22
`30
`36
`4]
`
`43
`
`43
`48
`48
`64
`68
`
`73
`
`75
`
`75
`3.1 A Desk Calculator ..................................................................... ..
`3.2 OperatorSummary 88
`3.3 Statement Summary .................................................................. ..
`100
`3.4 Comments and Indentation ....................................................... ..
`104
`3.5 Exercises ................................................................................... ..
`106
`
`Functions and Files
`
`109
`
`4.1 Introduction 109
`4.2 Linkage ..................................................................................... ..
`111}
`4.3 Header Files
`112
`4.4 Linkage to Non-C++ Code ........................................................ ..
`1 19
`4.5 How to Make a Library ............................................................. ..
`121
`4.6 Functions ................................................................................... ..
`123
`4.7 Macros ....................................................................................... ..
`138
`4.8 Exercises ................................................................................... ..
`140
`
`5.1 1ntroductionandOverview
`5.2 Classes and Members ................................................................ ..
`
`143
`
`143
`144
`
`9
`
`

`
`5,3 Interfaces and Implementations
`5.4 Minor Class Features
`5.5 Construction and Destruction ................................................... ..
`5.6 Exercises
`
`Derived Classes
`
`6.1 Introduction and Overview ....................................................... ..
`6.2 Derived Classes ......................................................................... ..
`6.3 Abstract Classes
`
`6,4 A Complete Program ................................................................ ..
`6,5 Multiple Inheritance .................................................................. _.
`6.6 Access Control .......................................................................... ..
`6.7 Free Store .................................................................................. ..
`6.8 Exercises ................................................................................... ..
`
`Operator Overloading
`
`ix
`
`153
`161
`170
`178
`
`131
`
`181
`182
`191
`
`193
`201
`211
`215
`222
`
`2.25
`
`7.1 Introduction 225
`
`7.2 Operator Functions 226
`7.3 User-defined Type Conversion
`229
`7.4 Literals ...................................................................................... ..
`236
`
`236
`7.5 Large Objects ............................................................................ ..
`237
`7.6 Assignment and Initialization ................................................... ..
`240
`7.7 Subscripting .............................................................................. ..
`7.8 FunctionCall 242
`
`7.9 Dereferencing ............................................................................ ..
`7.11) Increment and Deerement ......................................................... ..
`
`244
`246
`
`248
`7.11 A String Class
`7.12 Friends andMembers 251
`7.13 Caveat
`252
`7.14 Exercises
`253
`
`Templates
`
`255
`
`8.1 Introduction ............................................................................... ..
`
`255
`
`256
`8.2 A Simple Template ................................................................... ..
`259
`8.3 List Templates ........................................................................... ..
`8.4 Function Templates 270
`8.5 Template Function Overloading Resolution
`277
`8.6 Template Arguments
`279
`8.7 Derivation and Templates ......................................................... ..
`281
`
`10
`
`

`
`8.8 An AssociativeArray
`8.9 Exercises ................................................................................... ..
`
`Exception Handling
`
`291
`
`293
`
`293
`9.1 Error Handling .......................................................................... ..
`297
`9.2 Discrimination of Exceptions ................................................... ..
`9.3 Naming ofExceptions 300
`9.4 Resource Acquisition
`308
`9.5 Exceptions that are not Errors
`315
`9.6 Interface Specifications ............................................................. ..
`317
`9.7 Uncaught Exceptions ................................................................ ..
`320
`9.8 Error—Handling Alternatives
`321
`9.9 Exercises
`324
`
`Streams
`
`325
`
`10.1 Introduction 325
`
`10.3 Input .......................................................................................... ..
`10.4 Formatting
`10.5 Files and Streams
`10.6 C lnput;'Output
`10.7 Exercises ................................................................................... ..
`
`Design and Development
`
`330
`337
`350
`356
`358
`
`361
`
`361
`11.1 Introduction ............................................................................... ..
`364
`11.2 Aims and Means
`367
`11.3 The Development Process
`11.4 Management 382
`11.5 Rules ofThumb ........................................................................ ..
`387
`11.6 Annotated Bibliography ............................................................ ..
`388
`
`Design and C++
`
`12.1 Design and Programming Language ......................................... ..
`12.2 Classes
`12.3 Components
`12.4 Interfaces and Implementations
`12.5 Rules of Thumb ........................................................................ ..
`
`39]
`
`391
`402
`422
`425
`42?
`
`11
`
`

`
`Design of Libraries
`
`13.1 Introduction ............................................................................... ..
`
`13.2 Concrete Types ......................................................................... ..
`13.3 Abstract Types .......................................................................... ..
`13.4 Node Classes ............................................................................. ..
`
`13.5 Run—tirne Type Information
`13.6 Fat Interfaces ............................................................................. ..
`
`13.7 Application Frameworks ........................................................... ..
`13.8 Interface Classes
`13.9 Handle Classes .......................................................................... ..
`
`13.10 Memory Management ............................................................... ..
`13.11 Exercises ................................................................................... ..
`
`Reference Manual
`
`121 Introduction ............................................................................... ..
`
`r.2 Lexical Conventions ................................................................. ..
`
`r.3 Basic Concepts
`r.4 Standard Conversions ............................................................... ..
`
`r.5 Expressions ............................................................................... ..
`L26 Statements ................................................................................. ..
`r.7 Declarations .............................................................................. ..
`
`L8 Declarators ................................................................................ ..
`r.9 Classes ...................................................................................... ..
`r.l0 Derived Classes ......................................................................... ..
`
`r.l1 Member Access Control
`
`........................................................... ..
`
`r.l2 Special Member Functions
`r.13 Overloading
`
`r.l4 Templates
`L15 Exception Handling
`r.I6 Preprocessing ............................................................................ ..
`L17 Appendix A: Grammar Summary ............................................. ..
`1218 Appendix B: Compatibility
`
`ANSUISO Resolutions
`
`Index
`
`12
`
`

`
`Templates
`
`l’0m' quote heir.
`
`— B.Strousrrup
`
`This Chapter introduces the template concept that allows container classes,
`such as lists and associative arrays, to be simply defined and implemented
`without loss of static type checking or run—time efficiency. Similarly, tem-
`plates allow generic functions, such as sort (l, to be defined once for a
`family of types. A family of list classes is defined as an example of tem-
`plates and their interaction with other language features. Some variants of
`a sort ()
`function template is presented to demonstrate techniques for
`using templates to compose code from semi-independent parts. Finally, a
`simple associative array template is defined and used in a couple of small
`example programs.
`
`8.1 Introduction
`
`One of the most useful kinds of classes is the container class, that is, a class that holds
`
`objects of some (other) type. Lists. arrays. associative arrays, and sets are container
`
`classes. Specifying a container of objects of a single known type can be done with the
`facilities described in Chapters 5 and 7. For example §5.3.2 defined a set of ints.
`However, container classes have the interesting property that the type of objects they
`contain is of little interest to the definer of a container class. but of crucial importance
`to the user of a particular container. Thus we want to have the type of the contained
`object be an argument to a container class: The definer specifies the container class in
`tenns of that argument, and the users specify what the type -of contained objects is to
`be for each particular container (each object of the container class). The Vector
`template in §l.4.3 was an example of this.
`
`13
`
`

`
`256
`
`Templates
`
`Chapter 8
`
`This chapter first presents the notion of a template class by examining a simple
`stack template. Then a more complete and realistic example of a couple of related
`list templates is presented. Function templates and the rules for what can be a func-
`tion template argument are stated. Finally, an associative array template is presented.
`
`8.2 A Simple Template
`
`A class template specifies how individual classes can be constructed much as a class
`declaration specifies how individual objects can be constructed. We can define a
`stack of elements of an arbitrary type:
`
`template<class T)
`class stack {
`
`[ V = p = new TIsz=s];
`etacktint s)
`‘stack[)
`{ delete[] v;
`}
`
`}
`
`{ *p++ = a:
`void push(T a)
`T popt)
`{ return *——p;
`}
`
`}
`
`int size() const
`
`{ return p—v;
`
`}
`
`}:
`
`All run—time error checking has been left out for simplicity. Apart from that. the
`example is complete and realistic.
`The template <cl ass T> prefix specifies that a template is being declared and
`that an argument T of type type will be used in the declaration. After its introduction,
`T is used exactly like other type names. The scope of T extends to the end of the clec~
`laration that template <class T> prefixes. Note that template<c.l.ass T>
`says that T is a type name; it need not actually be the name of a class. For so below,
`T turns out to be char.
`
`The name of a class template followed by a type bracketed by < > is the name of a
`class (as defined by the template) and can be used exactly like other class names. For
`example:
`
`stack<char> sc(100);
`
`// stack of characters
`
`defines an object so ofa class stack<c:har>.
`Except for the special syntax of its name, stack<char> works exactly as if it
`had been defined:
`
`14
`
`

`
`Section 8.2
`
`A Simple Tempiate
`
`257
`
`class stack_char {
`char* v;
`
`char* p;
`int 52;
`public:
`[ V = p = new char[sz=s];
`etack_char(int s)
`“stack”char()
`[ delete[] v;
`}
`
`}
`
`{ *p++ = a;
`void push(char a)
`char popl)
`{ return *——p;
`}
`
`}
`
`int size() const
`
`{ return p—v;
`
`}
`
`1;
`
`One can think of a template as a clever kind of macro that obeys the scope, naming,
`and type rules of C++. That would be an oversimplification, but it is an oversimplifi-
`cation that might help avoid some gross misunderstandings.
`In particular, use of a
`template need not imply any run-time mechanisms beyond what is used for an equiva-
`lent “hand-written" class, nor does it necessarily imply any savings in the amount of
`code generated.
`
`[L is usually a good idea to debug a particular class, such as stacl-t_char, before
`turning it into a template such as stack<T>. Similarly, when trying to understand a
`template it is often useful to imagine its behavior for a particular type such as int or
`shape* before trying to comprehend the template in its full generality.
`Given the class template declaration, stacks can now be defined and used like
`this:
`
`stack<shape*> ssp[200);
`stack<Point> sp{400):
`
`// stack of pointers to shapes
`// stack of Points
`
`void f(stack<complex>& sc)
`
`// ‘reference to stack
`// of complex’ argument
`
`sc.push(complex(l.2l);
`complex 2 = 2.5*Sc.pop();
`
`// pointer to stack of ints
`stack<int>*p = 0:
`p = new stack<int>(8D0}: // Stack of ints
`// on the free store
`
`for (int i = 0;
`p—>push(i);
`sp.push(Point(i,i+400});
`
`i<400;
`
`i++)
`
`{
`
`} /
`
`1’
`
`{
`
`}
`
`Because the stack member functions were all
`
`inline.
`
`the only function calls
`
`15
`
`

`
`258
`
`Templates
`
`Chapter 8
`
`generated for this example were the ones generated for free store allocation and
`deallocation.
`
`Template functions need not be inline; stack could equally well have been
`defined:
`
`template<class T> class stack {
`
`stack(int);
`“stack();
`
`void push('I');
`T poptl;
`
`int size{) const;
`
`};
`
`In that case, definitions of the stack member function must be provided somewhere
`exactly as for non—template class member functions. Such functions are themselves
`parameterized by the type argument to their template class; thus these functions are
`defined by function templates. When defined outside the template class, this must be
`explicit. For example:
`
`template<class T> void stack<T>::push{T a)
`{
`
`*p++ = ar-
`
`}
`
`ternplate<c:lasS :I'> stack<T>::stack(int s)
`{
`
`v = p = new T[sz=s];
`
`}
`
`Note that within the scope of st;-1ck<T> qualification with <T> is redundant so that
`stack<T>: :stack is the name for the constructor.
`It is the impIementation’s job — not the programmer’s — to ensure that versions of
`template functions are generated for each argument type to the template. Thus for the
`example above, the implementation would generate definitions for the constructors
`for staok<shape*>, stack<Point>, and stack<int>, the destructors for
`stack-<shape*>
`and
`stack<Point>,
`the
`push {)
`functions
`for
`stac:k<complex>, stack<int>, stack<Point>, and the pop () function for
`stack<complex>. The generated functions will be perfectly ordinary member
`functions. For example:
`
`void stack<complex>: :push(complex a)
`
`{ *p++ = a:
`
`}
`
`differs from “ordinary member functions” only in the syntax for the class name.
`
`16
`
`

`
`Section 8.2
`
`A Simple Template
`
`259
`
`Just as there can be only one function defining a class member function in a pro-
`gram. there can be only one function template defining a class template member func-
`tion in a program. When a function definition is needed for a class template member
`function for a particular type.
`it is the itnplementation‘s job to find the template for
`the member function and generate the appropriate version. An implementation may
`require the programmer to help find template source by following some convention.
`It is important to write templates so that they have as few dependencies on global
`information as possible. The reason is that a template will be used to generate func-
`tions and classes based on unknown types and in unknown contexts. Almost any sub-
`tle context dependency will surface as a debugging problem to a programmer who is
`unlikely to be the original author of the template. The rule of avoiding references to
`global names as far as possible should be taken extra seriously in template design.
`
`8.3 List Templates
`
`When writing a realistic collection class, one often needs to deal with relationships
`between the classes involved in the implementation, with memory management
`issues, and with the need to iterate over a collection.
`It is also common to design sev-
`eral related classes together (§l2.2). As an example, we will present a family of
`singly linked list classes and templates.
`
`8.3.1 An Intrusive List
`
`First, we will build a simple list that relies on a link field in objects put onto the list.
`Later, we use that list as a building block for a more general list that does not require
`a link field in objects put onto it. The class declarations with only their public func-
`tions will be presented first; the implementation will be presented in the next section.
`The idea is to avoid obscuring the design points with implementation details.
`First we define a type slink, that is, a link in a singly linked list:
`
`struct slink [
`slink* next;
`}
`slink()
`{ next=O;
`slink(slink* pl
`{ next = p;
`
`}
`
`}:
`
`We can now define a class that can contain objects of any class derived from slink:
`
`class slist_base {
`//'
`...
`public:
`int inserttslink*):
`int appendtslinlrf);
`slink* getllr
`//
`
`// add at head of list
`// add at tail of list
`// remove and return head of list
`
`17
`
`

`
`260
`
`Templates
`
`Chapter 8
`
`This class is intrusive because it can be used only if the elements provide the slink
`as a handle for slist_base to use. The name slist__base indicates that the
`class will be used as a base for singly linked list classes. As ever, when one designs a
`family of related entities there is a problem selecting names for the various members
`of the family. Since class names cannot be overloaded the way function names can,
`we cannot use overloading to reduce the name proliferation.
`An slist_base can be used like this:
`
`void f()
`{
`
`slist_base slb;
`s1b.insert(new slink);
`// ...
`
`slink* p = slb.get();
`// ...
`
`delete p;
`
`}
`
`However, because slinks don't carry information (beyond their identity), this is not
`very interesting. To use a slist_base, one needs to derive a useful class from
`slink. In a compiler one might have a name node that needs to be on a list:
`
`class name : public slink [
`//
`
`};
`
`void ftconst char* 3)
`{
`
`slist_base slb;
`slb.insert{new name(s));
`// .
`.
`.
`
`name* p = (name*)slb.get(};
`// ...
`
`delete p:
`
`}
`
`This works, but because slist_base is defined in terms of slinks and not
`names,
`it
`is necessary to use an explicit cast to convert the sl:i_nk* returned by
`slist_base: :get ()
`into a name*. This is inelegant.
`In a large program with
`many lists and many classes derived from slink, it
`is also error prone. What we
`would like is a type—safe version of slist_base:
`
`template<class T>
`
`class Islist : private slist_base {
`public:
`
`{ slist_base::insert{a);
`void insert{T* a}
`T* getll
`{ return (T*) slist_base::get():
`// ...
`
`}
`
`}
`
`}:
`
`18
`
`

`
`Section 8.3.1
`
`An Intrusive List
`
`261
`
`The cast inside Islist: zget ()
`
`is perfectly reasonable and safe because class
`
`Islist ensures that every object on the list really is of type T or of a type derived
`from T. Note that s1ist_base is a private base class of Islist. We do not
`want users accidentally messing around with the unsafe implementation details.
`The name Islist stands for “intrusive singly linked list." This template can be
`used like this:
`
`void ftconst char* 5)
`{
`
`Islist<name> ilst;
`ilst.inseIt(new namelsl);
`//
`name* p = ilst.get();
`//
`
`delete p;
`
`}
`
`Attempted misuses are caught at compile time:
`
`class expr
`//
`
`l:
`
`: public slink {
`
`void gtexpr* e)
`i
`
`I3liet<name> ilstr
`ilst.inseIt(e): // error: Islist<na.me>::inserttl
`// expects a name*
`
`//
`
`}
`
`There are several important things to note about the example so far. First. the scheme
`is type safe (barring silly mistakes in the very limited context of the access functions
`in Islist). Second, type safety is achieved without the expenditure of time or
`space because the access functions in Islist are trivial
`iniine functions. Third,
`because all the real work is done by the — yet to be presented — implementation of
`slist—_bas-e, there is no replication of code, and the source code of the implemen-
`tation (the slist_base functions) need not be available to a user. This is consid-
`ered commercially important by some.
`[I also provides a separation between an inter-
`face and its
`implementation so that
`reimplenientation without
`requiring re—
`compilation of user code becomes possible. Finally, a simple intrusive list is close to
`
`In other words, this strategy has near optimal properties of
`optimal in time and space.
`time, space, data hiding, and type checking while providing great flexibility and econ-
`omy of expression.
`is derived from
`However, an object can be on an Islist only provided it
`slink. This implies that we cannot have an Islist of ints, that we cannot have
`
`a list of some previously defined type that is not based on slink, and that having an
`object on two Islists takes some work (§6.5.1).
`
`19
`
`

`
`262
`
`Templates
`
`Chapter 8
`
`8.3.2 A Non-intrusive List
`
`After our "digression” into the building and use of intrusive lists, we can proceed to
`building a non-intrusive list, that is, a list that does not require its elements to provide
`facilities to help the implementation of the list class. Because we no longer can
`assume that an object on the list has link field, the list implementation will have to
`provide one:
`
`template<class T>
`struct Tlink : public slink {
`T info:
`
`Tlinktconst T& a)
`
`:
`
`info(a)
`
`{
`
`}
`
`l;
`
`A Tlink<T> holds a copy of an object of type T in addition to the link field pro-
`vided by its base class slink. Note that the use of the initializer info (a) , rather
`than the assignment info=a. is essential for efficient operation for types with non-
`trivial copy constructors and assignment operators (§7.l1). For such a type — say
`St ring — defining the constructor,
`
`Tlinldconst Ts a)
`
`[
`
`info = a;
`
`}
`
`would have caused a default St ring to be constructed and then assigned to.
`Given this link class and the Islist class, the definition of the non-intrusive list
`is almost trivial:
`
`template<class T>