Efficient and interoperable software components
Matt is a member of the technical staff at Silicon Graphics. Matt is coauthor, along with Alexander Stepanov and Hans Boehm, of the SGI STL. He is currently working on a book about the STL, to be published by Addison-Wesley. Matt can be contacted at [email protected].
The C++ community was introduced to generic programming in 1994, when Hewlett-Packard released a demonstration implementation of the Standard Template Library (STL). The STL was subsequently adopted as part of the C++ Standard Library. Late in 1996, Silicon Graphics released (and made freely available at http://www.sgi.com/Technology/STL/) a new version of the Standard Template Library.
Although the STL is often thought of as a library of container classes, that is not the most appropriate starting point for understanding it. The STL is, more than anything else, a collection of generic algorithms combined with the support apparatus that the algorithms require. It is possible to understand most of the structure of the STL by examining a single algorithm in depth.
Algorithms
The crucial insight that underlies the STL is that most of the fundamental algorithms of computer science are, in fact, abstract. That is, the precise details of data structures are usually irrelevant when describing a fundamental algorithm: What matters are certain abstract properties of the data. If these properties are precisely specified, then the algorithm can be written so that it is as general as possible -- it can operate on every type and every structure for which the operation itself could sensibly be defined. Most importantly, a generic algorithm can be written so that it is no less efficient than if it had been written for one specific data structure.
Consider a linear search, for example. Given a range of elements, we are to find the first element that is equal to a particular value.
The basic outline of the algorithm is immediately obvious: Step through the range, from beginning to end, testing each element to see if it is equal to the desired value. If it is, then return; if not, advance to the next element. If there is no next element, then return some indication of failure.
This general description leaves some details of the interface unspecified. If you are searching for a particular int in an array of ints, then find1 (see Listing One is one plausible implementation. The first argument, first, points to the beginning of the array, and the second argument, last, points one element past the end of the array. The third argument, value, is the value to be searched for. The return value is a pointer to the first element that is equal to value; if there is no such element, then the return value is last.
This interface relies on a C/C++ "past-the-end" pointer. That is, if A is an array with n elements, then A+n is a valid pointer even though it does not actually point to anything. (The elements of A are A[0] through A[n-1].) Because of this rule, you can specify ranges in the asymmetric form [first, last), meaning everything from first up to, but not including, last. This rule makes it possible for find1 to use last as an indicator of failure, and it makes it possible for find1 (and other algorithms) to treat empty ranges the same way as nonempty ranges. A function like find1 is useful, and most of us have written something of the sort. The trouble, though, is precisely that most of us have had to write something of the sort. The Standard C Library contains a function, strchr, that is similar to find1. strchr, though, can only be used to find an element in an array of char, just as find1 can only be used to find an element in an array of ints. strchr can't be used for the related problem of finding an element in an array of unsigned chars.
The STL generalizes find1 to find; see Listing Two. This is no longer C, but C++. Superficially, find looks similar to find1. And, in fact, if find's first two arguments are of type int* and the third is of type int, then find and find1 are equivalent.
This generic version of find uses C++'s template mechanism: The formal generic types InputIterator and T represent whatever types find was called with, just as the variables first, last, and T represent the values that find was called with. Pursuing this analogy further: If you call a function twice, its arguments need not have the same values both times. Similarly, if you call find twice, you need not call it with the same types both times. The C++ compiler will automatically create as many instances of find as necessary.
This process of template instantiation takes place at compile time; it does not involve any run-time dispatching, and it does not incur any run-time overhead. If you call find once with arguments of type int* and once with arguments of type char*, then it is as if you had written two versions of find and included both of them in your program.
Iterators
find is clearly more general than find1: find1's first two arguments must be of type int*, while find's first two arguments may be of any pointer type. However, find is more general than may immediately be apparent. In C, operators like * are defined only for a fixed set of built-in types: If x is of type struct X, then in C, an expression like *x is meaningless. In C++, however, this restriction has been removed. In C++, you can overload operators on user-defined types. The expression *x is a syntactic convenience, equivalent to calling an ordinary function. (Specifically, it is equivalent to calling a member function named X::operator*().)
C++'s Iostream library is the most familiar example of operator overloading: The expression cout << x means to write the value of x to a stream. Operator overloading also enables "smart pointer" classes -- objects that are similar to pointers but that have some additional or alternate functionality.
find, then, may be used not only with pointers, but also with any type that "looks like" a pointer -- any type that provides the same sort of operations that pointers do. It may, for example, be used to find an element in a linked list of nodes: All that is necessary is a class that has a single data member, a pointer p to the current node, and a member function operator++() that performs the operation p = p->next. If operator++() is declared to be inline, then using find should be no less efficient than writing a loop and stepping through the list by hand.
What is significant about find -- what makes it a truly generic algorithm -- is that it does not assume any specific representation for the data it operates on: It only relies on an interface for stepping through and examining elements. This interface could have involved functions with names like get(), set(), and next(). In the STL, however, the interface was instead chosen to be that of pointer operations, partly for the sake of familiarity, but, more importantly, to make it possible to use find with ordinary, unmodified pointers. Even in an age of fancy classes and data structures, pointers still matter!
At this point, however, all this talk about the interface that find uses has been vague. Unless you are specific about an interface, it is useless to say that you are programming to that interface. The interface is implicit in Listing Two, and in Figure 1 it is made explicit.
All of the requirements in Figure 1, except the fourth, deal specifically with the type InputIterator. The fourth expresses a relationship between the two types InputIterator and T. This suggests a different way of expressing find's type requirements: dividing them into the requirements on InputIterator, the requirements on T, and the requirements that involve both template parameters.
The requirement on T is simply that equality is defined on objects of type T. The requirements on InputIterator, however, are more interesting. Figure 1 only describes four requirements on the type InputIterator. That is, find does not rely on the entire set of pointer operations, but only on an extremely restricted and stylized subset.
This interface is significant because find is not the only algorithm that relies on it; restrictive as it is, it is sufficient for many different algorithms. We call this set of requirements a "concept" -- in this case, the "Input Iterator" concept. If a type satisfies all of these requirements, we say it is a "model" of that concept.
The STL defines other Iterator concepts in addition to Input Iterator: It is possible to express find solely in terms of the operations listed in the Input Iterator requirements, but other algorithms, such as sort, cannot be expressed in terms of such a minimal set of operations. Sorting a range of elements requires being able to modify the element that an iterator points to, and it requires arbitrary access to elements, instead of purely sequential access; that is, it requires operations like *p = x and *(p + n). The Input Iterator concept includes neither of those operations, but a different iterator concept -- Random Access Iterator -- includes both.
The relationship between Input Iterator and Random Access Iterator is essentially hierarchical: If a type I is a model of Random Access Iterator, then it must also be a model of Input Iterator. This is not the hierarchy of class inheritance, however, since neither Input Iterator nor Random Access Iterator is a class. It is a hierarchy of concepts, and we use the term "refinement" to describe it.
In addition to these two Iterator concepts, the STL includes: Forward Iterator, a refinement of Input Iterator and Output Iterator; Bidirectional Iterator, a refinement of Forward Iterator; and Random Access Iterator, a refinement of Bidirectional Iterator.
Containers
Generic algorithms naturally lead to the iterator concepts; the next step is to provide a set of types that model those concepts. We already have iterators that traverse built-in C arrays -- pointers. An obvious generalization is to provide additional data structures, then provide iterators that traverse those new data structures.
The STL defines several concepts that describe data-structure requirements, the most general of which is Container. All STL Container classes are models of Container, so, as in the case of Iterators, the basic Container concept provides as minimal an interface as possible.
All STL containers do two basic things. First, they contain elements. Containers always "own" the objects they contain, just as C arrays do. When an array is destroyed, all of the elements in the array are also destroyed; the same is true of any type that models Container. Second, an STL Container provides iterators that point to its elements. Algorithms access those Iterators using the member functions begin() and end(). If X is a model of Container and x is of type X, then an algorithm that proceeds from x.begin() up to (but not including) x.end() will pass through each of x's elements exactly once.
In principle, the Container interface need not include anything more than that. For convenience, however, it is actually slightly richer. For example, it also includes the member function size(). Strictly speaking, size() is redundant, since the size of a container x is just the distance between the iterators x.begin() and x.end().
Container is a very general concept: Almost any user-defined data structure that contains a homogeneous collection of objects can be defined so that it models Container. All of the container classes in the STL, however, are models of either Sequence or Associative Container, both of which are refinements of Container.
A Sequence is a dynamically sized Container: It permits insertion, modification, and erasure of elements at any position, and it automatically performs any necessary memory management. An Associative Container is also dynamically sized, but it does not permit unrestricted insertion and erasure. Instead, it provides an efficient mechanism for finding an element in terms of some key.
Both Sequences and Associative Containers are familiar ideas (although possibly under different names) from other programming languages and other C++ libraries. STL Containers differ from their predecessors, however, in two ways. First, Containers are models of generic concepts; this makes it possible to write an algorithm solely in terms of (say) the Sequence interface, without needing to know whether the algorithm's argument is a vector or a deque.
Second, and more important, STL Containers provide only a minimal set of operations for manipulating their elements. The operation of a linear search, for example, is not a member function. Instead, it has been factored out into the stand-alone algorithm find. This means that there is no need to rewrite a linear search for every new container class: The existing STL algorithm find will work with any class that conforms to the Container interface and that provides iterators that conform to the Input Iterator interface.
It is the idea of writing algorithms in terms of concepts, rather than as member functions of Container classes, that enables interoperability between existing components and new components.
Function Objects and Adapters
Many algorithms can be written solely in terms of containers and iterators. Sometimes, however, this is still not enough for full generality. Again, consider the problem of a linear search. While the algorithm find can be used to find the first integer in a range that is equal to 18, it can't be used to find the first integer that is less than zero. The most general statement of the problem of linear search is finding the first element that satisfies some condition; find, however, only deals with the special case where that condition happens to be equality.
find is parameterized by the type of the object being searched for, and by the way that these objects are organized into a range. The way to make it more general is to parameterize it, additionally, by the condition we are searching for.
In C, you would make one of find's arguments a function pointer, but in C++ (see Listing Three) there is a better way. The template parameter Predicate represents a new concept. Predicate is a model of Predicate, a kind of "function object" -- any object that can be called as if it were a function (specifically, anything for which the function call operation, operator()(), is defined. operator()(), like other operators, can be overloaded).
How can you use find_if to find the first negative element in a vector<int>? The most obvious way is to write a function negative that takes a single element of type int and returns a bool. This function would be used as: find_if(V.begin(), V.end(), negative);.
The third argument is of type bool (*)(int), which is a model of Predicate. Using find_if in this manner is straightforward, but unnecessarily cumbersome: It is always better to reuse code than to rewrite it, and using an algorithm shouldn't require writing special-purpose "glue" functions.
The STL includes several predefined Function Objects; one is the template struct less<T>, which takes two arguments of type T and returns true if the first argument is less than the second. This is not the sort of Function Object we need (find_if requires a function object that takes a single argument), but it can be used as follows: find_if(V.begin(), V.end(), bind2nd(less<int>(), 0));.
bind2nd is an example of an adapter: something that converts one interface to another. In this case, bind2nd's first argument is a Function Object that takes two arguments, and bind2nd's return value is a Function Object that takes a single argument. The return value is a Function Object F with the property that F(n) is equivalent to less<int>()(n,0).
The notion of converting one interface into another applies to many sorts of interfaces, not just Function Objects. In addition to Function-Object adapters, the STL also includes Iterator adapters and Container adapters.
Documenting the STL
The STL is organized around concepts: The most important property of any type, whether it is an Iterator, Container, or Function Object, is how it fits in to the STL's conceptual hierarchy. Similarly, one of the most important properties of any STL algorithm is the set of the permissible types of its arguments. This is especially important when writing new algorithms and data structures, since the STL guarantees interoperability of components if, and only if, the types model the appropriate concepts.
Imagine a language that supports concepts directly. In this hypothetical language, just as a variable is declared to be of some specified type, a type could be declared to be a model of some specified concept. This language isn't C++, though. There is no way to declare, in C++, that a concept name like InputIterator stands for a specific set of requirements: The template parameters in Listing Three are named InputIterator and Predicate, but these names are not special to the compiler. The compiler has no way of knowing that a template parameter must satisfy the InputIterator requirements just because it is called InputIterator.
Concepts are just as real a part of the STL as classes, but they cannot be expressed within the C++ language. Since concepts can exist solely as part of the documentation, the documentation must, to some extent, take the place of code. This places unusual burdens on the documentation. An example of how to document a generic library is the hypertext documentation included with the SGI Standard Template Library (available at http://www.sgi.com/Technology/STL/).
The documentation of each generic algorithm and generic class describes which concept each template parameter must model. The page that documents find_if, for example, says that its template parameters must be models of, respectively, Input Iterator and Predicate, and it has hyperlinks to the pages that document those two concepts.
Fundamentally, documenting a concept means describing the properties that a type must have if it is to be a model of the concept; the central part of this description is a list of valid expressions involving that type. This list must also describe any other types that are mentioned in these expressions. If X is a model of Input Iterator, for example, then some of the expressions in the Input Iterator requirements involve not just X but also X's value type. Finally, since STL concepts form a hierarchy, each concept's documentation also specifies which concept or concepts it is a refinement of.
Algorithmic Improvements
The reference manual for the original "STL" (A.A. Stepanov and M. Lee, "The Standard Template Library." Hewlett-Packard technical report HPL-95-11(R.1), 1995) describes 67 generic algorithms. The SGI STL documents three algorithms, uninitialized_copy, uninitialized_fill, and uninitialized_fill_n, that were present but undocumented in the HP implementation. It also adds five completely new algorithms: iota, is_sorted, is_heap, random_sample, and random_sample_n.
The first three of these new algorithms are simple, but nevertheless useful: iota fills a range with consecutively ascending numbers, and is_sorted and is_heap test, respectively, whether a range is sorted in ascending order and whether it satisfies the heap condition. The latter is particularly important because the STL contains several algorithms that operate only on valid heaps: is_heap makes it possible to verify that a range satisfies these algorithms' preconditions.
The algorithms random_sample and random_sample_n are complementary to the algorithm random_shuffle from the original STL. random_shuffle randomly rearranges a range of elements. This is a common operation. Another common operation, however, is selecting an unbiased sample of m elements from an input range of N elements. One way to obtain an unbiased sample is to permute the input range with random_shuffle, then copy the first m elements. However, this method isn't always possible (what if the input range is immutable?). Even when it is possible, it is extremely wasteful. random_sample and random_sample_n implement unbiased random selection directly and efficiently.
In addition to the new algorithms, the SGI STL contains a major improvement in the sort algorithm. The original STL implemented sort in terms of quicksort. This was a reasonable choice: Quicksort is widely used, and it is one of the best general-purpose sorting algorithms. Quicksort's average run time is O(N log N). In this it is not unusual (heapsort and mergesort, for example, are also O(N log N)), but quicksort can be implemented with an extremely simple inner loop, and is thus significantly faster than other O(N log N) methods.
Despite this, quicksort has a serious flaw: It is fast on average, but its worst-case behavior is poor. For certain input sequences, quicksort becomes quadratic -- its average complexity is O(N log N), but its worst-case complexity is O(N2). Naïve implementations of quicksort, in fact, are quadratic when the input range is already sorted -- an important special case. The original HP implementation used the "median of three" improvement, which means that it exhibited quadratic behavior for different (and presumably less common) input sequences, but the danger of quadratic behavior was still present.
The SGI STL implements sort in terms of "Introsort," rather than quicksort. Introsort, developed by D.R. Musser, is similar to quicksort. It has an equally simple inner loop, and is as fast as quicksort for almost all input sequences; it is never more than a few percent slower. Introsort, however, has the property that its complexity is always O(N log N). Unlike quicksort, introsort is suitable for applications where it is important to have a guaranteed upper bound on complexity.
Several other algorithms, including copy and lexicographical_compare, have been tuned for better performance. By far the most important algorithmic improvement, however, is the new implementation of sort.
New Container Classes
The original STL had seven Container classes: vector, list, deque, set, map, multiset, and multimap. The first three of these are Sequences, and the latter four are Associative Containers.
While it is correct to call set, map, multiset, and multimap Associative Containers (all four classes are models of the concept Associative Container), it is also misleading. They are actually a special kind of Associative Container: They are all models of the concept Sorted Associative Container, which is a refinement of Associative Container. Every Associative Container associates values with keys, and provides an efficient way of finding a value given its key. Sorted Associative Containers, however, have the additional property that their elements are always sorted by key in ascending order.
Sorted Associative Containers are useful, and the invariant of ascending order is sometimes important. Associative Containers that are not sorted, however, are also useful, and their absence from the original STL was a serious omission. The SGI STL has four additional Container classes -- hash_set, hash_map, hash_multiset, and hash_multimap -- that are models of Associative Container, but not of Sorted Associative Container.
The new Associative Containers are based on hash tables. The hash function (a function object) is a template parameter; the default is the function object hash<T>, which is defined for all integral types and for char*. Listing Four shows how a hash table can be used.
The main reason for using a hash_map instead of a map is efficiency. The performance of hash tables depends on the hash function; with a reasonable choice of hash function, a hash_map is, on average, several times faster than a map.
Another major omission from the original STL was singly linked lists. The STL class list is doubly linked: Each node has a link both to its successor and its predecessor. Again, there is no denying that doubly linked lists are useful. Because list is doubly linked, list's iterators are models of Bidirectional Iterator -- they can be decremented as well as incremented. This makes list more flexible than if it were singly linked, since some algorithms require the ability to step backwards.
As every Lisp programmer knows, however, singly linked lists are perfectly adequate for many purposes. And in those cases where a singly linked list is adequate, using a doubly linked list is a mistake. Doubly linked lists use more memory than singly linked lists (one additional pointer per node), and operations that modify the list structure are slower. Inserting or erasing a node in a doubly linked list requires twice as many pointer assignments as performing the same operation in a singly linked list.
Both singly and doubly linked lists are important data structures. The SGI STL includes both the doubly linked list class list and the singly linked list class slist.
Thread Safety
Threads are not part of the C++ language: The draft C++ standard says nothing at all about threads or concurrency. Nevertheless, most modern C++ programs run in multithreaded environments; multiprocessor systems, where each thread could potentially run on a different CPU, are becoming common. (This is an especially important issue for SGI, since most of SGI's recent products are multiprocessor systems.)
The danger inherent in multithreaded programs is that a data structure can be put in an inconsistent state if two different threads try to modify it simultaneously. The solution is well known: If any data structure is shared between two threads, then each thread must acquire a lock before it modifies the data and must release the lock afterward. As far as the STL is concerned, the question is simply how much of this synchronization mechanism should be implemented in library code and how much should be left to the user.
One option that seems attractive is to have the library handle all concurrency issues automatically, and to leave nothing at all to the user. So, for example, two threads could both insert elements into the same map, and the library would automatically perform the necessary locking and serialization so that no two insertions happened simultaneously.
It's entirely possible to write such a library; the only problem is that nobody would want it. First, even in multithreaded programs, many Containers simply don't need to be shared between threads. A particular vector might, for example, store information that only a single thread needs to access. In an implementation that automatically managed concurrency, however, there would be overhead associated with every use of each Container, regardless of whether that Container is actually shared. This overhead is substantial: Every member function, including trivial one-line inline member functions, would have to acquire and release a lock. Since lock acquisition is expensive on most operating systems, this could lead to programs that run an order of magnitude slower.
Second, even for programs that do need to share Containers between threads, automatic locking by Containers' member functions is the wrong way to do it. The problems are apparent even in a simple example like V[1]=V[0];. If the library did automatic locking, then it would acquire a lock for V, read the value in V[0], release the lock, acquire a new lock, write the value in to V[1], and then release the second lock. This is both inefficient and unreliable because it acquires two locks instead of one, and unreliable because V might be modified in between the release of the first lock and the acquisition of the second.
It is impossible for a library to guarantee that programs that use it will manage concurrency correctly; a thread-safe library is one that makes it possible for users to write thread-safe programs. That is, if a program is written so that no thread tries to use an STL Container object at the same moment that another thread is modifying it, then the library must guarantee that the program will behave correctly.
This is not as trivial a condition as it might seem. It means that the implementation of STL Containers must not involve any objects that are shared between two different containers, unless those shared objects are protected by explicit locking within the library. The HP STL does not satisfy this condition: It contains unprotected shared data, and it is therefore not thread safe. In several places, this use of shared memory is unnecessary.
First, three of the STL algorithms (stable_sort, stable_partition, and inplace_merge) require temporary auxiliary storage; the HP STL used a single global buffer for auxiliary storage, which meant that all three of these algorithms were unreliable in multithreaded programs. In the SGI STL, that global buffer has been replaced by dynamically allocated memory; this has no measurable effect on the speed of those algorithms, but makes it possible to use them safely in multithreaded programs.
Second, the STL's Sorted Associative Containers (set, map, multiset, and multimap) are implemented in terms of red-black trees. Red-black trees need some way to represent a nonexistent node -- the child of a node that has no children. The most straightforward representation (the one found in both the HP STL and Introduction to Algorithms, by T.H. Cormen, C.E. Leiserson, and R.L. Rivest, MIT Press, 1990) is to use a special sentinel node. This representation makes the code that rebalances trees somewhat simpler than it would be otherwise. Unfortunately, it also means that the red-black trees in the HP STL are not thread safe. This sentinel node is shared between every tree of the same type, and the rebalancing code uses the sentinel to store temporary bookkeeping information. Two different trees, running in two different threads, could interfere with each other disastrously.
The SGI STL eliminates this possibility by replacing the sentinel node with a null pointer. This requires modifications to all of the operations that rebalance the tree, and the new code is more complicated than the old. As it happens, though, the new code also turns out to be slightly faster.
Finally, there is one important area where shared data cannot be avoided -- memory allocation.
Memory Allocation
C++ programs that use many small dynamically allocated objects should not allocate them by calling new for each object. Consider, for example, the STL Container list. A list consists of many list nodes, each of which points to its predecessor and to its successor. As Listing Five shows, list requires a new node for each new element; this new node is returned by list's private member function get_node. How should get_node be implemented?
It would be inefficient to call new each time a new node is requested. It would waste space, since the run-time system must keep track of each chunk of memory allocated by new, and it would be unnecessarily slow, since new is typically an expensive operation. The solution to this problem has been known for years, and is discussed, among other places, in The C++ Programming Language, Second Edition, by Bjarne Stroustrup (Addison-Wesley, 1991). A program that needs to allocate many small nodes should manage its own specialized memory pool: It should use new or malloc only to obtain large chunks of memory, and should allocate the nodes from that pool rather than directly from the heap. Most STL implementations use some variation of this optimization. The details, however, are crucial both for thread safety and for efficient memory usage. The important issues are how many memory pools there are, and which part of the library is responsible for maintaining them and obtaining nodes from them.
One possibility would be for each list object to maintain its own memory pool. A list might, for example, automatically allocate enough space for a thousand nodes as it is created. The advantages of this scheme are obvious: It is simple, fast, and, since it involves no data shared between multiple objects, is inherently thread safe. The disadvantage is equally obvious: It wastes an enormous amount of memory, since every list, even one with very few elements, must maintain a large pool.
A more realistic implementation is for the list class, rather than each list object, to maintain a memory pool. Every object of class list<int> shares one pool of nodes, every object of class list<double> shares another pool, and so on. Listing Six shows the implementation of get_node using this scheme. get_node returns a node from the pool, unless the pool is empty; if it is empty, then get_node calls add_new_buffer, which uses a "page allocator" to obtain a new block of memory. The page allocator, in turn, calls new or malloc.
The page-allocator scheme is adequate, and is, in fact, used in the original HP implementation of the STL. However, it suffers from two defects. First, it can lead to memory fragmentation. A program with many different instantiations of Container templates will waste a great deal of memory. Second, the implementation of get_node in Listing Six is not thread safe, since every object of type list<T> shares the same pool. Modifying it to be thread safe wouldn't be particularly straightforward, especially since the equivalent function in every other Container class would also have to be modified.
Fundamentally, both of these defects result from the fact that the process of allocating a new node is divided between the list's page allocator and the list itself. The solution, then, is to replace the page allocator with a "node allocator" -- an allocator that both obtains blocks of memory from the operating system, and manages pools of nodes. As Listing Seven shows, using node allocators is far less complicated than using page allocators. The implementation of get_node in Listing Seven does nothing more than request a new node from the allocator.
The node-allocator scheme clearly prevents memory fragmentation. The pool of free nodes is maintained by the allocator, rather than by the list, so the pool is shared between every Container class that uses the allocator. There is a single pool, rather than one for every Container type.
Thread safety is still an issue, since node allocators do not eliminate shared data: Every Container must be able to access the pool of free nodes. This access, however, is always through the node allocator. The free-memory pool is the only shared data in the library, and only the node allocator accesses the pool directly, so no library component (other than the node allocator) need concern itself with acquiring and releasing locks.
Finally, since only the allocator explicitly manages concurrency, it is possible to provide an elegant way for programs with only a single thread to avoid the overhead of thread safety. Container classes are parameterized by their allocators -- one of a Container's template parameters is its allocator type. The default allocator is thread safe, but the library also contains a faster allocator, single_client_alloc, that is suitable for single-threaded programs.
The Future
The STL is not merely a collection of containers and algorithms, but a conceptual framework for fundamental algorithms and data structures. Extensibility has always been a central design goal of the STL. The SGI Standard Template Library is a crucial first step toward this goal, and serves as a model for extending the STL. But there are still entire categories of fundamental algorithms that have not yet been addressed. Some of the most important omissions are graph algorithms, pattern matching, multidimensional data structures, and persistence.
SGI will continue to extend and enhance the STL, and will serve as a clearinghouse for suitable components that others wish to contribute. The STL will not merely be a static body of code, but will be a growing collection of efficient and interoperable software components.
Listing One
int* find1(int* first, int* last, int value) {
while (first != last && *first != value)
++first;
return first;
}
Listing Two
template <class InputIterator, class T> InputIterator find(InputIterator first, InputIterator last, const T& value)
{
while (first != last && *first != value)
++first;
return first;
}
Listing Three
template <class InputIterator, class Predicate> InputIterator find_if(InputIterator first,InputIterator last,Predicate pred)
{
while (first != last && !pred(*first))
++first;
return first;
}
Listing Four
#include <hash_map.h> #include <stdio.h>
struct eqstr {
bool operator()(const char* s1, const char* s2) const {
return strcmp(s1, s2) == 0;
}
};
int main()
{
hash_map<char*, int, hash<char*>, eqstr> days;
days["January"] = 31;
days["February"] = 28;
days["March"] = 31;
days["April"] = 30;
days["May"] = 31;
days["June"] = 30;
printf("%s has %d days\n", "March", days["March"]);
return 0;
}
Listing Five
iterator insert(iterator position, const T& x) { link_type tmp = get_node();
construct(&((*tmp ).dat a), x);
(*tmp).next = position.node;
(*tmp).prev = (*position.node).prev;
(*(link_type((*position.node).prev))).next = tmp;
(*position.node).prev = tmp;
++length;
return tmp;
}
Listing Six
link_type get_node() { link_type tmp = free_list;
return free_list
? (free_list = (link_type)(free_l ist- >next ), tmp)
: (next_avail == last ? (add_new_buffer(), next_avail++)
: next_avail++); }
Listing Seven
link_type get_node() { return list_node_allocator::allocate( );
}
DDJ
Copyright © 1997, Dr. Dobb's Journal