The C++ standard only gives a few directives in this area:

Complete details can be found in the C++ standard, look in [20.4 Memory].

The easiest way of fulfilling the requirements is to call operator new each time a container needs memory, and to call operator delete each time the container releases memory. This method may be slower than caching the allocations and re-using previously-allocated memory, but has the advantage of working correctly across a wide variety of hardware and operating systems, including large clusters. The __gnu_cxx::new_allocator implements the simple operator new and operator delete semantics, while __gnu_cxx::malloc_allocator implements much the same thing, only with the C language functions std::malloc and free.

Another approach is to use intelligence within the allocator class to cache allocations. This extra machinery can take a variety of forms: a bitmap index, an index into an exponentially increasing power-of-two-sized buckets, or simpler fixed-size pooling cache. The cache is shared among all the containers in the program: when your program's std::vector<int> gets cut in half and frees a bunch of its storage, that memory can be reused by the private std::list<WonkyWidget> brought in from a KDE library that you linked against. And operators new and delete are not always called to pass the memory on, either, which is a speed bonus. Examples of allocators that use these techniques are __gnu_cxx::bitmap_allocator, __gnu_cxx::pool_allocator, and __gnu_cxx::__mt_alloc.

Depending on the implementation techniques used, the underlying operating system, and compilation environment, scaling caching allocators can be tricky. In particular, order-of-destruction and order-of-creation for memory pools may be difficult to pin down with certainty, which may create problems when used with plugins or loading and unloading shared objects in memory. As such, using caching allocators on systems that do not support abi::__cxa_atexit is not recommended.

You can specify different memory management schemes on a per-container basis, by overriding the default Allocator template parameter. For example, an easy (but non-portable) method of specifying that only malloc or free should be used instead of the default node allocator is:

    std::list <int, __gnu_cxx::malloc_allocator<int> >  malloc_list;

Likewise, a debugging form of whichever allocator is currently in use:

    std::deque <int, __gnu_cxx::debug_allocator<std::allocator<int> > >  debug_deque;
      

Writing a portable C++ allocator would dictate that the interface would look much like the one specified for allocator. Additional member functions, but not subtractions, would be permissible.

Probably the best place to start would be to copy one of the extension allocators: say a simple one like new_allocator.

Several other allocators are provided as part of this implementation. The location of the extension allocators and their names have changed, but in all cases, functionality is equivalent. Starting with gcc-3.4, all extension allocators are standard style. Before this point, SGI style was the norm. Because of this, the number of template arguments also changed. Here's a simple chart to track the changes.

More details on each of these extension allocators follows.

Explaining all of the fun and delicious things that can happen with misuse of the auto_ptr class template (called AP here) would take some time. Suffice it to say that the use of AP safely in the presence of copying has some subtleties.

The AP class is a really nifty idea for a smart pointer, but it is one of the dumbest of all the smart pointers -- and that's fine.

AP is not meant to be a supersmart solution to all resource leaks everywhere. Neither is it meant to be an effective form of garbage collection (although it can help, a little bit). And it can notbe used for arrays!

AP is meant to prevent nasty leaks in the presence of exceptions. That's all. This code is AP-friendly:

    // Not a recommend naming scheme, but good for web-based FAQs.
    typedef std::auto_ptr<MyClass>  APMC;

    extern function_taking_MyClass_pointer (MyClass*);
    extern some_throwable_function ();

    void func (int data)
    {
	APMC  ap (new MyClass(data));

	some_throwable_function();   // this will throw an exception

	function_taking_MyClass_pointer (ap.get());
    }
   

When an exception gets thrown, the instance of MyClass that's been created on the heap will be delete'd as the stack is unwound past func().

Changing that code as follows is not AP-friendly:

	APMC  ap (new MyClass[22]);
   

You will get the same problems as you would without the use of AP:

	char*  array = new char[10];       // array new...
	...
	delete array;                      // ...but single-object delete
   

AP cannot tell whether the pointer you've passed at creation points to one or many things. If it points to many things, you are about to die. AP is trivial to write, however, so you could write your own auto_array_ptr for that situation (in fact, this has been done many times; check the mailing lists, Usenet, Boost, etc).

All of the containers described in the standard library require their contained types to have, among other things, a copy constructor like this:

    struct My_Type
    {
	My_Type (My_Type const&);
    };
   

Note the const keyword; the object being copied shouldn't change. The template class auto_ptr (called AP here) does not meet this requirement. Creating a new AP by copying an existing one transfers ownership of the pointed-to object, which means that the AP being copied must change, which in turn means that the copy ctors of AP do not take const objects.

The resulting rule is simple: Never ever use a container of auto_ptr objects. The standard says that “undefined” behavior is the result, but it is guaranteed to be messy.

To prevent you from doing this to yourself, the concept checks built in to this implementation will issue an error if you try to compile code like this:

    #include <vector>
    #include <memory>

    void f()
    {
	std::vector< std::auto_ptr<int> >   vec_ap_int;
    }
   

Should you try this with the checks enabled, you will see an error.

The standard deliberately doesn't require a reference-counted implementation, allowing other techniques such as a circular-linked-list.

The shared_ptr code is kindly donated to GCC by the Boost project and the original authors of the code. The basic design and algorithms are from Boost, the notes below describe details specific to the GCC implementation. Names have been uglified in this implementation, but the design should be recognisable to anyone familiar with the Boost 1.32 shared_ptr.

The basic design is an abstract base class, _Sp_counted_base that does the reference-counting and calls virtual functions when the count drops to zero. Derived classes override those functions to destroy resources in a context where the correct dynamic type is known. This is an application of the technique known as type erasure.

The original authors of the Boost shared_ptr, which is really nice code to work with, Peter Dimov in particular for his help and invaluable advice on thread safety. Phillip Jordan and Paolo Carlini for the lock policy implementation.