Defining your own allocator is a relatively simple process. The Standard C++ Library describes a particular interface, consisting of types and functions. An allocator that conforms to the standard must match the syntactic requirements for these member functions and types. The Standard C++ Library also specifies a portion of the semantics for the allocator type.
The Standard C++ Library allocator interface relies heavily on member templates. As of this writing, many compilers do not yet support both member function templates and member class templates. This makes it impossible to implement a standard allocator. Rogue Wave's implementation of the Standard C++ Library provides an alternative allocator interface that provides most of the power of the standard interface, without requiring unavailable compiler features. This interface differs significantly from the standard interface, and will not work with other vendors' versions of the Standard C++ Library.
We recommend that when you define an allocator and implement containers, you provide both the standard interface and the Rogue Wave interface. This will allow you to use allocators now, and to take advantage of the standard once it becomes available on your compiler.
The remainder of this chapter describes the requirements for the Standard C++ Library allocator, the requirements for Rogue Wave's alternative allocator, and some techniques that specify how to support both interfaces in the same code base.
An allocator that conforms to the Standard C++ Library allocator specification must have the following interface. The example uses my_allocator as a place holder for your own allocator name:
template <class T>
class my_allocator
{
typedef implementation_defined size_type;
typedef implementation_defined difference_type
typedef implementation_defined pointer;
typedef implementation_defined const_pointer;
typedef implementation_defined reference;
typedef implementation_defined const_reference;
typedef implementation_defined value_type;
template <class U>
struct rebind { typedef allocator<U> other; };
Each of the pointer types in this interface must have a conversion to void*. It must be possible to use the resulting void* as a this value in a constructor or destructor and in conversions to B<void>::pointer, for appropriate B, for use by B::deallocate().
The rebind member allows a container to construct an allocator for some arbitrary type out of the allocator type provided as a template parameter. For instance, the list container gets an allocator<T> by default, but a list may well need to allocate list_nodes as well as T's. The container can construct an allocator for list_nodes out of the allocator for T, which is the template parameter Allocator in this case, as follows:
Allocator::rebind<list_node>::other list_node_allocator;
Here is a description of the member functions that a Standard C++ Library allocator must provide:
my_allocator(); template <class U> my_allocator(const my_allocator<U>&); template <class U> operator=(const my_allocator<U>&); ~my_allocator();
Constructors and destructor.
pointer address(reference r) const;
Returns the address of r as a pointer type. This function and the following function are used to convert references to pointers.
const_pointer address(const_reference r)
const;
Returns the address of r as a const_pointer type.
pointer allocate(size_type n, const_pointer hint=0);
Allocates storage for n values of T. Uses the value of hint to optimize storage placement, if possible.
void deallocate(pointer);
Deallocates storage obtained by a call to allocate.
size_type max_size();
Returns the largest possible storage available through a call to allocate.
void construct(pointer p, const T& val);
Constructs an object of type T at the location of p, using the value of u in the call to the constructor for T. The effect is:
new((void*)p) T(u);
void destroy(pointer p);
Calls the destructor on the value pointed to by p. The effect is:
((T*)p)->~T()
Here is a description of the non-member functions that a Standard C++ Library allocator must provide:
template <class T> my_allocator::pointer operator new(my_allocator::size_type, my_allocator&);
Allocates space for a single object of type T using my_allocator::allocate. The effect is:
new((void*)x.template allocate<T>(1)) T;
template <class T, class U>
bool
operator==(const my_allocator<T>& a,
const my_allocator<U>& b);
Returns true if allocators b and a can be safely interchanged. Safely interchanged means that b could be used to deallocate storage obtained through a, and vice versa.
template <class T, class U>
bool
operator!=(const my_allocator<T>& a,
const my_allocator<U>& b);
Returns !(a == b).
Rogue Wave provides an alternative allocator interface for those compilers that do not support both class templates and member function templates.
In this interface, the class allocator_interface provides all types and typed functions. Memory is allocated as raw bytes using the class provide by the Allocator template parameter. Functions within allocator_interface cast appropriately before returning pointer values. Because multiple allocator_interface objects can attach to a single allocator, one allocator can allocate all storage for a container, regardless of how many types are involved. The one real restriction is that pointers and references are hard-coded as type T* and T&. (Note that in the standard interface they are implementation_defined.). If your compiler supports partial specialization instead of member templates, you can use it to get around even this restriction by specializing allocator_interface on just the allocator type.
To implement an allocator based on the alternative interface, supply the class labeled my_allocator below:
//
// Alternative allocator uses an interface class
// (allocator_interface)
// to get type safety.
//
template <class T>
class my_allocator
{
public:
typedef implementation_defined size_type;
typedef implementation_defined difference_type;
typedef implementation_defined pointer;
typedef implementation_defined const_pointer;
typedef implementation_defined reference;
typedef implementation_defined const_reference;
typedef implementation_defined value_type;
my_allocator();
~my_allocator();
void * allocate (size_type n, void * = 0);
void deallocate (void* p);
size_type max_size (size_type size) const
};
We've also included a listing of the full implementation of the allocator_interface class, to show how a standard container will use your class. Chapter 16 provides a full description of how the containers use the alternative interface.
template <class Allocator,class T>
class allocator_interface
{
public:
typedef Allocator allocator_type;
typedef T* pointer;
typedef const T* const_pointer;
typedef T& reference;
typedef const T& const_reference;
typedef T value_type;
typedef typename Allocator::size_type size_type;
typedef typename Allocator::difference_type difference_type;
protected: allocator_type* alloc_;
public:
allocator_interface() : alloc_(0) { ; }
allocator_interface(Allocator* a) : alloc_(a) { ; }
void alloc(Allocator* a)
{
alloc_ = a;
}
pointer address (T& x)
{
return static_cast<pointer>(&x);
}
size_type max_size () const
{
return alloc_->max_size(sizeof(T));
}
pointer allocate(size_type n, pointer = 0)
{
return static_cast<pointer>(alloc_->allocate(n*sizeof(T)));
}
void deallocate(pointer p)
{
alloc_->deallocate(p);
}
void construct(pointer p, const T& val)
{
new (p) T(val);
}
void destroy(T* p)
{
((T*)p)->~T();
}
};
class allocator_interface<my_allocator,void>
{
public:
typedef void* pointer;
typedef const void* const_pointer;
};
// // allocator globals // void * operator new(size_t N, my_allocator& a); inline void * operator new[](size_t N, my_allocator& a); inline bool operator==(const my_allocator&, const my_allocator&);
Rogue Wave strongly recommends that you implement containers that support both the Standard C++ Library allocator interface, and our alternative interface. By supporting both interfaces, you can use allocators now, and take advantage of the standard once it becomes available on your compiler.
In order to implement both versions of the allocator interface, your containers must have some mechanism for determining whether the standard interface is available. Rogue Wave provides the macro _RWSTD_ALLOCATOR in stdcomp.h to define whether or not the standard allocator is available. If _RWSTD_ALLOCATOR evaluates to true, your compiler is capable of handling Standard C++ Library allocators; otherwise, you must use the alternative.
The first place that you use _RWSTD_ALLOCATOR is when determining which typenames the container must use to reflect the interface. To do this, place the equivalent of the following code in your container class definition:
#ifdef RWSTD_ALLOCATOR
typedef typename Allocator::rebind<T>::other::reference
reference;
typedef typename
Allocator::rebind<T>::other::const_reference
const_reference;
typedef typename Allocator::rebind<node>::other::pointer
link_type;
typedef Allocator::rebind<T>::other value_allocator;
typedef Allocator::rebind<node>::other node_allocator;
#else
typedef typename
allocator_interface<Allocator,T>::reference reference;
typedef typename
allocator_interface<Allocator,T>::const_reference
const_reference;
typedef typename
allocator_interface<Allocator,node>::pointer link_type;
Allocator alloc;
typedef allocator_interface<Allocator,T> value_allocator;
typedef allocator_interface<Allocator,node>
node_allocator;
#endif
Notice that we use rebind even for the types associated with T. This is safest since it ensures that the container will work even if the allocator is instantiated with a different type for the allocator template parameter, for example, vector<int, allocator<void> >. This makes our containers more robust. Note also that we provide two allocator types: value_allocator and node_allocator. You will need to assemble actual allocators inside your container, probably as they're needed. In our example, the mechanism for calling allocator::allocate for T's looks like this, regardless which interface is being used:
value_allocator(alloc)::allocate();
In this call we construct an appropriate allocator using its template copy constructor and then call allocate on that allocator. One result of this use of the allocator is that any state held by an allocator had better be passed through the copy constructor by reference, so that it is maintained in the one allocator object that we keep around, which is the one passed into the constructor for the container.