8. Libraries

Life can only be understood backwards, but it must be lived forwards.

– Søren Kierkegaard

Library design tradeoffs — aims of library design — language support for libraries — early C++ libraries — the stream I/O library — concurrency support — foundation libraries — persistence and databases — numeric libraries — specialized libraries — a standard C++ library.

Since no language can support every desirable feature and because even accepted extensions take time to implement and deploy, people ought to always consider libraries as a first choice. Designing libraries is more often than not the most constructive outlet for enthusiasm for new facilities. Only if the library route is genuinely infeasible should the language extension route be followed.

We are obviously faced with an opportunity, but can we manage the resulting diversity? I think we can. The diversity reflects the diversity of needs in the C++ community. A library supporting high-performance scientific computation has different constraints from a library supporting interactive graphics, and both have different needs from a library that supplies low-level data structures to builders of other libraries.

C++ evolved to enable this diversity of library architectures and some of the newer C++ features are designed to ease the coexistence of libraries.

What tradeoffs are there? When answering that question people often focus on language features: Should I use inline functions? virtual functions? multiple inheritance? single-rooted hierarchies? abstract classes? overloaded operators? That is the wrong focus. These language features exist to support more fundamental tradeoffs: Should the design

– Emphasize run-time efficiency?

– Minimize recompilation after a change?

– Maximize portability across platforms?

– Enable users to extend the basic library?

– Allow use without source code available?

– Blend in with existing notations and styles?

– Be usable from code not written in C++?

– Be usable by novices?

Given answers to these kinds of questions, the answers to the language-level questions will follow. Modern libraries often provide a variety of classes to allow users to make such tradeoffs. For example, a library may provide a very simple and efficient string class. In addition, it can also supply a higher-level string class with more facilities and more opportunities for user-modification of its behavior (§8.3).

The basic structure of C++ encourages a strongly-typed style of programming. In C++, a class is a type. The rules of inheritance, the abstract class mechanism, and the template mechanism combine to encourage users to manipulate objects strictly in accordance with the interfaces they present to their users. To put it more crudely: Don’t break the type system with casts. Casts are necessary for many low-level activities and occasionally for mapping from higher-level to lower-level interfaces, but a library that requires its end users to do extensive casting is imposing an undue and usually unnecessary burden on them. C’s printf family of functions, void* pointers, unions, and other low-level features are best kept out of library interfaces because they imply holes in the library’s type system.

For years, C++ has been evolving towards a situation where the language provides sufficient facilities to cope with the basic problems that arise when a user tries to use two independently-designed libraries. To complement, library providers are beginning to consider multiple library use when they design libraries.

Namespaces address the basic problem of different libraries using the same name (§17.2). Exception handling provides the basis for a common model of error handling (§16). Templates (§15) provide a mechanism for defining containers and algorithms independent of individual types; such types can then be supplied by users or by other libraries. Constructors and destructors provide a common model for initialization and cleanup of objects (§2.11). Abstract classes provide a mechanism for defining interfaces independently of the classes they interface to (§13.2.2). Run-time type information provides a mechanism for recovering type information that was lost when an object was passed to a library and passed back with less specific type information (as a base class) (§14.2.1). Naturally, this is just one use of these language facilities, but viewing them as supports for composition of programs out of independently developed libraries can be enlightening.

Consider multiple inheritance (§12.1) in this light: Smalltalk-inspired libraries often rely on a single “universal” root class. If you have two of those you could be out of luck, but if the libraries were written for distinct application domains, the simplest form of multiple inheritance sometimes helps:

Click here to view code image

class GDB_root :
      public GraphicsObject,
      public DataBaseObject {};

A problem that cannot be solved that easily arises when the two “universal” base classes both provide some basic service. For example, both may provide a run-time type identification mechanism and an object I/O mechanism. Some such problems are best solved by factoring out the common facility into a standard library or a language feature. Others can be handled by providing functionality in the new common root. However, merging “universal” libraries will never be easy. The best solution is for library providers to realize that they don’t own the whole world and never will, and that it is in their interest to design their libraries accordingly.

Memory management presents yet another set of problems for library designers in general and users of multiple libraries in particular (§10.7).

The early work with container classes such as list and array was severely hampered by the lack of support for a way of expressing parameterized types (§9.2.3). In the absence of proper language support, we had to make do with macros. The best that can be said for the C preprocessor’s macro facilities is that they allowed us to gain experience with parameterized types and support individual and small group use.

Much of the work on designing classes was done in cooperation with Jonathan Shopiro who in 1983 produced list and string classes that saw wide use within AT&T and are the basis for the classes currently found in the “Standard Components” library that was developed in Bell Labs and sold by USL. The design of these early libraries interacted directly with the design of the language and in particular with the design of the overloading mechanisms.

The key aim of these early string and list libraries was to provide relatively simple classes that could be used as building blocks in applications and in more ambitious libraries. Typically, the alternative was hand-written code using C and C++ language facilities directly, so efficiency in time and space was considered crucial. For this reason, there was a premium on self-contained classes rather than hierarchies, on the inlining of time-critical operations, and on classes that could be used in traditional programs without major redesign or retraining of programmers. In particular, no attempts were made to enable users to modify the operation of these classes by overriding virtual functions in derived classes. If a user wanted a more general and modifiable class, it could be written with the “standard” class as a building block. For example:

Click here to view code image

class String { // simple and efficient
    // ...
};

class My_string { // general and adaptable
    String rep;
    // ...
public:
    // ...
    virtual void append(const String&);
    virtual void append(const My_string&);
    // ...
} ;

To introduce stream I/O, this example was considered:

fprintf(stderr,"x = %s ",x);

Because fprintf() relies on unchecked arguments that are handled according to the format string at run time this is not type safe and [Stroustrup,1985]

“had x been a user-defined type like complex there would have been no way of specifying the output format of x in the convenient way used for types “known to printf()” (for example, %s and %d). The programmer would typically have defined a separate function for printing complex numbers and then written something like this:

Click here to view code image

fprintf(stderr,"x = ");
put_complex(stderr,x);
fprintf(stderr," ");

This is inelegant. It would have been a major annoyance in C++ programs that use many user-defined types to represent entities that are interesting/critical to an application.

Type-security and uniform treatment can be achieved by using a single overloaded function name for a set of output functions. For example:

Click here to view code image

put(stderr,"x = ");
put(stderr,x);
put(stderr," ");

The type of the argument determines which “put function” will be invoked for each argument. However, this is too verbose. The C++ solution, using an output stream for which << has been defined as a “put to” operator, looks like this:

cerr << "x = " << x << " ";

where cerr is the standard error output stream (equivalent to the C stderr). So, if x is an int with the value 123, this statement would print

x = 123

followed by a newline onto the standard error output stream.

This style can be used as long as x is of a type for which operator << is defined, and a user can trivially define operator << for a new type. So, if x is of the user-defined type complex with the value (1,2.4), the statement above will print

x = (1,2.4)

on cerr.

The stream I/O facility is implemented exclusively using language features available to every C++ programmer. Like C, C++ does not have any I/O facilities built into the language. The stream I/O facility is provided in a library and contains no extra-linguistic magic.”

The idea of providing an output operator rather than a named output function was suggested by Doug McIlroy by analogy with the I/O redirection operators in the UNIX shell (>, >>, I, etc.). This requires operators that return their left-hand operand for use by further operations:

“An operator<< function returns a reference to the ostream it was called for so that another ostream can be applied to it. For example:

cerr << "x = " << x;

where x is an int, will be interpreted as

Click here to view code image

(cerr.operator<<("x = ")) . operator<< (x) ;

In particular, this implies that when several items are printed by a single output statement, they will be printed in the expected order: left to right.”

Had an ordinary, named function been chosen the user would have been forced to write code like that last example. Several operators were considered for input and output operations:

“The assignment operator was a candidate for both input and output, but it binds the wrong way. That is, cout=a=b would be interpreted as cout= (a=b), and most people seemed to prefer the input operator to be different from the output operator.

The operators < and > were tried, but the meanings “less than” and “greater than” were so firmly implanted in people’s minds that the new I/O statements were for all practical purposes unreadable (this does not appear to be the case for << and >>). Apart from that, '<' is just above ',' on most keyboards and people were writing expressions like this:

cout < x , y , z;

It is not easy to give good error messages for this.”

Actually, now we could overload comma (§11.5.5) to give the desired meaning, but that was not possible in C++ as defined in 1984 and would require messy duplication of output operators.

The c in the names of the standard I/O streams cout, cin, etc., stands for character:; they were designed for character-oriented I/O.

In connection with Release 2.0, Jerry Schwarz reimplemented and partially redesigned the streams library to serve a larger class of applications and to be more efficient for file I/O [Schwarz, 1989]. A significant improvement was the use of Andrew Koenig’s idea of manipulators [Koenig,1991] [Stroustrup,1991] to control formatting details such as the precision used for floating point output and the base of integers. For example:

Click here to view code image

int i = 1234;

cout << i << ' '            // decimal by default: 1234
     << hex << i << ' '     // hexadecimal: 4d2
     << oct << i << ';    // octal: 2322

Experience with streams was a major reason for the change to the basic type system and to the overloading rules to allow char values to be treated as characters rather than small integers the way they are in C (§11.2.1). For example:

char ch = 'b';
cout << 'a' << ch;

would in Release 1.0 output a string of digits reflecting the integer values of the characters a and b, whereas Release 2.0 outputs ab as one would expect.

The iostreams shipped with Release 2.0 of Cfront became the model for iostream implementations shipped by other suppliers and for the iostream library that is part of the upcoming standard (§8.5).

Multi-processor systems are becoming more common, but so are amazingly fast single-processors. This implies the need for at least two forms of concurrency: multi-threading within a single processor, and multi-processing with several processors. In addition, networking (both WAN and LAN) imposes its own demands and special-purpose architectures abound. Because of this diversity, I recommend parallelism be represented by libraries within C++ rather than as a general language feature. Such a feature, say something like Ada’s tasks, would be inconvenient for almost all users.

It is possible to design concurrency support libraries that approach built-in concurrency support both in convenience and efficiency. By relying on libraries, you can support a variety of concurrency models, though, and thus serve the users that need those different models better than can be done by a single built-in concurrency model. I expect this will be the direction taken by most people and that the portability problems that arise when several concurrency-support libraries are used within the community can be dealt with by a thin layer of interface classes.

Examples of concurrency support libraries can be found in [Stroustrup, 1980b], [Shopiro,1987], [Faust, 1990], and [Parrington,1990]. Examples of language extensions supporting some form of concurrency are Concurrent C++ [Gehani,1988], Compositional C++ [Chandy,1993], and Micro C++ [Buhr,1992]. In addition, proprietary threads and lightweight process packages abound.

Click here to view code image

#include <task.h>
#include <iostream.h>
class Int_message : public object {
    int i;
public :
    Int_message(int n) : i(n) {}
    int val() { return i; }
} ;

The task system queues carry messages of classes derived from class object. The use of the name object proves that this is a very old library. In a modern program, I would also have wrapped the queues in templates to provide type safety, but here I retained the style of the early task library uses. Using the task library queues for carrying single integers is a bit overblown, but it is easy and the queues ensure proper synchronizations of put () s and get () s from different tasks. The use of the queues illustrates how information can be carried around in a simulation or in a system that doesn’t rely on shared memory.

Click here to view code image

class sieve : public task {
    qtail* dest;
public :
    sieve(int prime, qhead* source);
} ;

A class derived from task will run in parallel with other such tasks. The real work is done in the task’s constructors or in code called from those. In this example, each sieve is a task. A sieve gets a number from an input queue and checks if that number is divisible by the prime number represented by the sieve. If not, the sieve passes the number along to the next sieve. If there isn’t a next sieve, we have found a new prime number and can create a new sieve to represent it:

Click here to view code image

sieve::sieve(int prime, qhead* source) : dest(O)
{
    cout << "prime " << prime << ' ';
    for(;;) {
        Int_message* p = (Int_message*) source->get();
        int n = p->val();
        if (n%prime) {
            if (dest) {
                dest->put(p);
                continue;
            }

            // prime found: make new sieve
            dest = new qtail;
            new sieve(n,dest->head());
        }
        delete p;
    }
}

A message is created on the free store and deleted by whichever sieve consumes that message. The tasks run under the control of a scheduler; that is, the task system differs from a pure co-routine system in which the transfer of control between coroutines is explicit.

To complete the program we need a main() to create the first sieve:

Click here to view code image

int main()
{
    int n = 2;
    qtail* q = new qtail;
    new sieve(n,q->head());  // make first sieve
    for(;;) {
        q->put(new Int_message(++n));
        thistask->delay(1);  // give sieves a chance to run
    }
}

This program will run until it has completely consumed some system resource. I have not bothered to program it to die gracefully. This is not an efficient way of calculating primes. It consumes one task and many task context switches per prime. This program could be run as a simulation using a single processor and address space shared between all tasks or as a genuine concurrent program using many processors. I tested it as a simulation with 10,000 primes/tasks on a DEC VAX. For an even more amazing variant of Eratosthenes’ sieve in C++ see [Sethi, 1989].

Click here to view code image

class Lock {
    //...
public :
    Lock(Real_lock&);  // grab lock
    ~Lock();           // release lock
};

void my_fct()
{
    Lock lck(q21ock); // grab lock associated with q2
    // use q2
}

Releasing the lock in the destructor simplifies code and makes it more reliable. In particular, this style interacts nicely with exceptions (§16.5). Using this style of locking, key data structures and policies can be made independent of concurrency details.

The libraries mentioned here are classified as “other libraries” because they did not affect the development of C++ significantly. This is not a judgment on their technical merit or importance to users. In fact, a library builder can often serve users best by being careful and conservative with the set of language features used. This is one way of maximizing library portability.

A vertical foundation library, on the other hand, aims at providing a complete set of services for a given environment such as the X Window System, MS Windows, MacApp, or a set of such environments. Vertical foundation libraries typically provide the basic classes found in a horizontal foundation library, but their emphasis is on classes for exploiting key features of the chosen environment. To this end, classes supporting interactive user-interfaces and graphics often dominate. Interfaces to specific databases can also be an integral part of such a library. Often, the classes of a vertical library are welded into a common framework in such a way that it becomes difficult to use part of the library in isolation.

My personal preference is to keep the horizontal and vertical aspects of a foundation library independent to maintain simplicity and choice. Other concerns, both technical and commercial, tug in the direction of integration.

The most significant early foundation libraries were Keith Gorlen’s NIH class library [Gorlen,1990], which provided a Smalltalk-like set of classes, and Mark Linton’s Interviews library [Linton, 1987], which made using the X Window System convenient from C++. GNU C++ (G++) comes with a library designed by Doug Lea that is distinguished by effective use of abstract base classes [Lea, 1993]. The USL Standards Components [Carroll, 1993] provide a set of efficient concrete types for data structures and Unix support used mainly in industry. Rogue Wave sells a library called Tools++, which originated in a set of foundation classes written by Thomas Keffer and Bruce Eckel at the University of Washington starting in 1987 [Kef-fer,1993]. Glockenspiel has for years supplied libraries for various commercial uses [Dearle, 1990]. Rational ships a C++ version of The Booch Components that was originally designed for and implemented in Ada by Grady Booch. Grady Booch and Mike Vilot designed and implemented the C++ version. The Ada version is 125,000 non-commented source lines compared to the C++ version’s 10,000 lines – inheritance combined with templates can be a very powerful mechanism for organizing libraries without loss of performance or clarity [Booch, 1993].

Both the NIH library and the GNU library provide basic object I/O mechanisms. POET is an example of a commercial C++ persistence library. There are about a dozen object-oriented databases intended for use with C++ and also implemented in C++. ObjectStore, ONTOS [Cattell,1991], and Versant are examples.

Click here to view code image

void Decompose(const double delt, SymTensor& V,
                       Tensor& R, const Tensor& L)
{
  Symtensor D = Sym(L);
  AntiTensor W = Anti(L);
  Vector z = Dual(V*D);
  Vector omega = Dual(W) – 2.0*lnverse(V-Tr(V)*One)*z;
  AntiTensor Omega = 0.5*Dual(omega);

  R = Inverse(One-O.5*delt*Omega) * (One+0.5*delt*Omega)*R;
  V += delt*Sym(L*V-V*Omega);
}

According to [Budge, 1992], “This code is transparent and its underlying class libraries are versatile and easy to maintain. A physicist familiar with the polar decomposition algorithm can make immediate sense of this code fragment without the need for additional documentation.”

Here is an example of a simulation of a circuit switched network [Eick,1991]:

Click here to view code image

#include <simlib.h>

int trunks[] = { /* ... */ };
double load[] ={/*...*/};
class LBA : public Policy { /* ... */ };


main()
{
  Sim sim;                               // event scheduler

  sim.network(new Network(trunks));      // create the network
  sim.traffic(new Traffic(load,3.0));    // traffic matrix
  sim.policy(new LBA);                   // Lba routing policy

  sim.run(180);  // simulate 180 minutes

  cout<<sim;    // output results
}

The classes involved are either SIMLIB library classes or classes that the user has derived from SIMLIB to define the network, load, and policy for this particular analysis.

As in the physics example in the previous section, the code makes perfect sense if and only if you are an expert in the field. In this case, however, the field is so narrow that the library serves only people in a highly specialized application area.

Many specialized libraries, such as libraries that support graphics and visualization, are actually quite general, but this book is not the place to try to enumerate C++ libraries or even to try for a complete classification. The variety of C++ libraries is mind-boggling.

First of all, the key libraries now in almost universal use must be standardized. This means that the exact interface between C++ and the C standard libraries must be specified and the iostreams library must be specified. In addition, the basic language support must be specified. That is, we must specify functions such as :: operator new(size_t) and set_new_handler(), which support the new operator (§10.6), terminate() and unexpected(), which support exception handling (§16.9), and classes type_info, bad_cast, and bad_typeid, which support run-time type information (§14.2).

Next, the committee must see if it can respond to the common demand for “more useful and standard classes,” such as string without getting into a mess of design by committee and without competing with the C++ library industry. Any libraries beyond the C libraries and iostreams accepted by the committee must be in the nature of building blocks rather than more ambitious frameworks. The key role of a standard library is to ease communication between separately-developed, more ambitious libraries.

With this in mind, the committee has accepted a string class and a wide character wstring class and is trying to unify these into a general string of anything template. It also accepted an array class, dynarray [Stal, 1993], a template class bits<N> for fixed-sized sets of bits, and a class bitstring for sets of bits for which the size can be changed. In addition, the committee has accepted complex number classes (grandchildren of my original complex class; see §3.3) and looked at vector classes intended to support numeric/scientific computation. Because the set of standard classes, their specifications, and even their names are still vigorously debated, F11 refrain from giving details and examples.

I would like to see list and associative array (map) templates in the standard library (§9.2.3). However, as with Release 1.0, these classes may be lost to the urgency of completing the core language in a timely fashion†.

† Here, I have the great pleasure of eating my words! The committee did raise to the occation and approved a splendid library of containers, iterators, and fundamental algorithms designed by Alex Stepanov. This library, often called the STL, is an elegant, efficient, formally sound, and well-tested framework for containers and their use (Alexander Stepanov and Meng Lee: The Standard Template Library, HP Labs Techinical Report HPL-94-34 (R. 1), August, 1994. Mike Vilot:, The C++ Report, October 94). Naturally, the STL includes map and list classes, and subsumes the dynarray, bits, and bitstring classes mentioned above. In addition, the committee approved vector classes to support numeric/scientific computation based on a proposal from Ken Budge from Sandia Labs.