STL extensions

Although the STL containers may provide all the functionality you?ll ever need, they are not complete. For example, the standard implementations of set and map use trees, and although these are reasonably fast, they may not be fast enough for your needs. In the C++ Standards Committee it was generally agreed that hashed implementations of set and map should have been included in Standard C++; however, there was not enough time to add these components, and thus they were left out .

Fortunately, alternatives are freely available. One of the nice things about the STL is that it establishes a basic model for creating STL-like classes, so anything built using the same model is easy to understand if you are already familiar with the STL.

The SGI STL from Silicon Graphics is one of the most robust implementations of the STL and can be used to replace your compiler?s STL if that is found wanting. In addition, SGI has added a number of extensions including hash_set, hash_multiset, hash_map, hash_multimap, slist (a singly linked list), and rope (a variant of string optimized for very large strings and fast concatenation and substring operations).

Let?s consider a performance comparison between a tree-based map and the SGI hash_map. To keep things simple, the mappings will be from int to int:

The performance test we ran showed a speed improvement of roughly 4:1 for the hash_map over the map in all operations (and as expected, find( ) is slightly faster than operator[ ] for lookups for both types of map). If a profiler shows a bottleneck in your map, consider a hash_map.

Non-STL containers

There are two ?non-STL? containers in the standard library: bitset and valarray . We say ?non-STL? because neither of these containers fulfills all the requirements of STL containers. The bitset container, which we covered earlier in this tutorial, packs bits into integers and does not allow direct addressing of its members. The valarray template class is a vector-like container that is optimized for efficient numeric computation. Neither container provides iterators. Although you can populate a valarray with nonnumeric data, it has mathematical functions that only operate with numeric data, such as sin, cos, tan, and so on. Most of valarray?s functions and operators operate on a valarray as a whole, as the following example illustrates.

The valarray class provides a constructor that takes an array of the target type and the count of elements in the array to be used to initialize the new valarray. The shift( ) member function shifts each valarray element one position to the left (or to the right, if its argument is negative) and fills in holes with the default value for the type (zero in this case). There is also a cshift( ) member function that does a circular shift (or ?rotate?). All mathematical operators and functions are overloaded to operate on valarrays, and binary operators require valarray arguments of the same type and size. The apply( ) member function, like the transform( ) algorithm, applies a function to each element, but the result is collected into a result valarray. The relational operators return suitably sized instances of valarray<BOOL> that indicate the result of element-by-element comparisons, such as with eq above. Most operations return a new result array, but a few, such as min( ), max( ), and sum( ), return a single scalar value for obvious reasons.
The most interesting thing you can do with valarrays is reference subsets of their elements, not only for extracting information, but for updating it. A subset of a valarray is called a slice, and certain operators use slices to do their work. The following sample program uses slices.

A slice object takes three arguments: the starting index, the number of elements to extract, and the ?stride,? which is the gap between elements of interest. Slices can be used as indexes into an existing valarray, and a new valarray containing the extracted elements is returned. A valarray of bool, such as is returned by the expression v > 6, can be used as an index into another valarray; the elements corresponding to the true slots are extracted. As you can see, you can also use slices and masks as indexes on the left side of an assignment. A gslice object (for ?generalized slice?) is like a slice, except that the counts and strides are themselves arrays, which allows you to interpret a valarray as a multidimensional array. The example above extracts a 2 by 3 array from v, where the numbers start at zero and the numbers for the first dimension are found six slots apart in v, and the others two apart, which effectively extracts the matrix
1 3 5
7 9 11