# Extensions

Here we will make an attempt at describing the non-Standard extensions to the library. Some of these are from SGI's STL, some of these are GNU's, and some just seemed to appear on the doorstep.

Before you leap in and use these, be aware of two things:

1. Non-Standard means exactly that. The behavior, and the very existence, of these extensions may change with little or no warning. (Ideally, the really good ones will appear in the next revision of C++.) Also, other platforms, other compilers, other versions of g++ or libstdc++-v3 may not recognize these names, or treat them differently, or...
2. You should know how to access these headers properly.

# Contents

- Ropes and trees and hashes, oh my!
- Added members
- Allocators

## Ropes and trees and hashes, oh my!

The SGI headers

         <bvector>
         <hash_map>
         <hash_set>
         <rope>
         <slist>
         <tree>

are all here; `<bvector>` exposes the old bit_vector class that was used before specialization of vector<bool> was available. `<hash_map>` and `<hash_set>` are discussed further below. `<rope>` is the SGI specialization for large strings ("rope," "large strings," get it? love those SGI folks). `<slist>` is a singly-linked list, for when the doubly-linked `list<>` is too much space overhead, and `<tree>` exposes the red-black tree classes used in the implementation of the standard maps and sets.

Okay, about those hashing classes... I'm going to foist most of the work off onto SGI's own site.

Each of the associative containers map, multimap, set, and multiset have a counterpart which uses a hashing function to do the arranging, instead of a strict weak ordering function. The classes take as one of their template parameters a function object that will return the hash value; by default, an instantiation of hash. You should specialize this functor for your class, or define your own, before trying to use one of the hashing classes.

The hashing classes support all the usual associative container functions, as well as some extra constructors specifying the number of buckets, etc.

Why would you want to use a hashing class instead of the "normal" implementations? Matt Austern writes:

> [W]ith a well chosen hash function, hash tables generally provide much better average-case performance than binary search trees, and much worse worst-case performance. So if your implementation has hash_map, if you don't mind using nonstandard components, and if you aren't scared about the possibility of pathological cases, you'll probably get better performance from hash_map.

(Side note: for those of you wondering, "Why wasn't a hash table included in the Standard in the first #!$@ place?" I'll give a quick answer: it was proposed, but too late and in too unorganized a fashion. Some sort of hashing will undoubtably be included in a future Standard.

Return to top of page or to the FAQ.

## Added members

Some of the classes in the Standard Library have additional publicly-available members. Of those, some are intended purely for the implementors, for example, additional typedefs. Those won't be described here (or anywhere else). This list will grow slowly, since we expect it to be rare -- most extensions will be self-contained.

- `filebuf`s have another ctor with this signature:
  `basic_filebuf(int __fd, const char* __name, ios_base::openmode __mode);`
  This comes in very handy in a number of places, such as attaching Unix sockets, pipes, and anything else which uses file descriptors, into the IOStream buffering classes. The three arguments are as follows:
  `int __fd,` // open file descriptor
  `const char* __name,`
  `ios_base::openmode __mode` // same as the other openmode uses

Return to top of page or to the FAQ.

## Allocators

This will be blank for a while. It will describe all of the different memory allocators, most inherited from SGI's code. Input is solicited.

Return to top of page or to the FAQ.

Comments and suggestions are welcome, and may be sent to Phil Edwards or Gabriel Dos Reis.
$Id: howto.html,v 1.4 2000/12/03 23:47:49 jsm28 Exp $