Standard Template Library Programmer's Guide

What kinds of applications beyond the standard class libraries are best served by STL ?

I have hopes that STL will introduce a style of programming called generic programming. I believe that this style is applicable to any kind of application, that is, trying to write algorithms and data structures in the most generic way. Specifying families or categories of such structures satisfying common semantic requirements is a universal paradigm applicable to anything. It will take a long time before the technology is understood and developed. STL is a starting point for this type of programming.

Eventually we will have standard catalogs of generic components with well-defined interfaces, with well-defined complexities. Programmers will stop programming at the micro level. You will never need to write a binary search routine again. Even now, STL provides several binary search algorithms written in the most generic way. Anything that is binary-searchable can be searched by those algorithms. The minimum requirements that the algorithm assumes are the only requirements that the code uses. I hope that the same thing will happen for all software components. We will have standard catalogs and people will stop writing these things.

That was Doug McIlroy's dream when he published a famous paper talking about component factories in 1969. STL is an example of the programming technology which will enable such component factories. Of course, a major effort is needed, not just research effort, but industrial effort to provide programmers with such catalogs, to have tools which will allow people to find the components they need, and to glue the components together, and to verify that their complexity assumptions are met.

STL does not implement a persistent object container model. The map and multimap containers are particularly good candidates for persistent storage containers as inverted indexes into persistent object databases. Have you done any work in that direction or can you comment an such implementations?

This point was noticed by many people. STL does not implement persistence for a good reason. STL is as large as was conceivable at that time. I don't think that any larger set of components would have passed through the standards committee. But persistence is something that several people thought about. During the design of STL and especially during the design of the allocator component, Bjarne observed that allocators, which encapsulate memory models, could be used to encapsulate a persistent memory model. The insight was Bjarne's, and it is an important and interesting insight. Several object database companies are looking at that. In October 1994 I attended a meeting of the Object Database Management Group. I gave a talk on STL, and there was strong interest there to make the containers within their emerging interface to conform to STL. They were not looking at the allocators as such. Some of the members of the Group are, however, investigating whether allocators can be used to implement persistency. I expect that there will be persistent object stores with STL-conforming interfaces fitting into the STL framework within the next year.

Set, multiset, map, and multimap are implemented with a red-black tree data structure. Have you experimented with other structures such as B*trees?

I don't think that would be quite right for in-memory data structures, but this is something that needs to be done. The same interfaces defined by STL need to be implemented with other data structures---skip lists, splay trees, half-balanced trees, and so on. It's a major research activity that needs to be done because STL provides us with a framework where we can compare the performance of these structures. The interface is fixed. The basic complexity requirements are fixed. Now we can have meaningful experiments comparing different data structures to each other. There were a lot of people from the data structure community coming up with all kinds of data structures for that kind of interface. I hope that they would implement them as generic data structures within the STL framework.

Are compiler vendors working with you to implement STL into their products?

Yes. I get a lot of calls from compiler vendors. Pete Becker of Borland was extremely helpful. He helped by writing some code so that we could implement allocators for all the memory models of Borland compilers. Symantec is going to release an STL implementation for their Macintosh compiler. Edison Design Group has been very helpful. We have had a lot of support from most compiler vendors.

STL includes templates that support memory models of 16-bit MS-DOS compilers. With the current emphasis on 32-bit, flat model compilers and operating systems, do you think that the memory-model orientation will continue to be valid?

Irrespective of Intel architecture, memory model is an object, which encapsulates the information about what is a pointer, what are the integer size and difference types associated with this pointer, what is the reference type associated with this pointer, and so on. Abstracting that is important if we introduce other kinds of memory such as persistent memory, shared memory, and so on. A nice feature of STL is that the only place that mentions the machine-related types in STL — something that refers to real pointer, real reference — is encapsulated within roughly 16 lines of code. Everything else, all the containers, all the algorithms, are built abstractly without mentioning anything which relates to the machine. From the point of view of portability, all the machine-specific things which relate to the notion of address, pointer, and so on, are encapsulated within a tiny, well-understood mechanism. Allocators, however, are not essential to STL, not as essential as the decomposition of fundamental data structures and algorithms.

The ANSI/ISO C Standards committee treated platform-specific issues such as memory models as implementation details and did not attempt to codify them. Will the C++ committee be taking a different view of these issues? If so, why?

I think that STL is ahead of the C++ standard from the point of view of memory models. But there is a significant difference between C and C++. C++ has constructors and operator new, which deal with memory model and which are part of the language. It might be important now to look at generalizing things like operator new to be able to take allocators the way STL containers take allocators. It is not as important now as it was before STL was accepted, because STL data structures will eliminate the majority of the needs for using new. Most people should not allocate arrays because STL does an effective job in doing so. I never need to use new in my code, and I pay great attention to efficiency. The code tends to be more efficient than if I were to use new. With the acceptance of STL, new will sort of fade away. STL also solves the problem of deleting because, for example, in the case of a vector, the destructor will destroy it on the exit from the block. You don't need to worry about releasing the storage as you do when you use new. STL can dramatically minimize the demand for garbage collection. Disciplined use of containers allows you to do whatever you need to do without automatic memory management. The STL constructors and destructors do allocation properly.

The C++ Standard Library subcommittee is defining standard namespaces and conventions for exception handling. Will STL classes have namespaces and throw exceptions?

Yes they will. Members of the committee are dealing with that, and they are doing a great job.

How different from the current STL definition will the eventual standard definition be? Will the committee influence changes or is the design under tighter control?