Allocators were introduced in Section 3.4. They represent a special memory model and are an abstraction used to translate the need to use memory into a raw call for memory. This chapter describes allocators in detail.
For the application programmer, using different allocators should be no problem. You simply have to pass the allocator as a template argument. For example, the following statements create different containers and strings using the special allocator MyAlloc<>:
// a vector with special allocator std::vector<int,MyAlloc<int> > v; // an int/float map with special allocator std::map<int,float,less<int>, MyAlloc<std::pair<const int,float> > > m; // a string with special allocator std::basic_string<char,std::char_traits<char>,MyAlloc<char> > s;
If you use your own allocator, it probably is a good idea to make some type definitions. For example:
// special string type that uses special allocator typedef std::basic_string<char,std::char_traits<char>, MyAlloc<char> > xstring; // special string/string map type that uses special allocator typedef std::map<xstring,xstring,less<xstring>, MyAlloc<std::pair<const xstring,xstring> > > xmap; // create object of this type xmap mymap;
When you use objects with other than the default allocator, you'll see no difference. However, beware that you don't mix elements with different allocators; otherwise, the behavior is undefined. You can check whether two allocators use the same memory model by using operator ==. If it returns true, you can deallocate storage allocated from one allocator via the other. To access the allocator, all types that are parameterized by an allocator provide the member function get_allocator(). For example:
if (mymap.get_allocator() == s.get_allocator()) {
//OK, mymap and s use the same or interchangeable allocators
...
}This section describes the use of allocators from the viewpoint of people who use allocators to implement containers and other components that are able to handle different allocators. This section is based, with permission, partly on Section 19.4 of Bjarne Stroustrup's The C++ Programming Language, 3rd edition.
Allocators provide an interface to allocate, create, destroy, and deallocate objects (Table 15.1). With allocators, containers and algorithms can be parameterized by the way the elements are stored. For example, you could implement allocators that use shared memory or that map the elements to a persistent database.
Table 15.1. Fundamental Allocator Operations
| Expression | Effect |
|---|---|
a.allocate(num)
| Allocates memory for num elements
|
a.construct(p)
| Initializes the element to which p refers
|
a.destroy(p)
| Destroys the element to which p refers
|
a.deallocate(p,num)
| Deallocates memory for num elements to which p refers
|
As an example, let's look at a naive implementation of a vector. A vector gets its allocator as a template or a constructor argument and stores it somewhere internally:
namespace std {
template <class T,
class Allocator = allocator<T> >
class vector {
...
private:
Allocator alloc; //allocator
T* elems; //array of elements
size_type numElems; //number of elements
size_type sizeElems; //size of memory for the elements
...
public:
//constructors
explicit vector(const Allocator& = Allocator());
explicit vector(size_type num, const T& val = T(),
const Allocator& = Allocator());
template <class InputIterator>
vector(InputIterator beg, InputIterator end,
const Allocator& = Allocator());
vector(const vector<T,Allocator>& v);
...
};
}The second constructor that initializes the vector by num elements of value val could be implemented as follows:
namespace std {
template <class T, class Allocator>
vector<T,Allocator>::vector(size_type num, const T& val,
const Allocator& a)
: alloc(a) //initialize allocator
{
//allocate memory
sizeElems = numElems = num;
elems = alloc.allocate(num);
//initialize elements
for (size_type i=0; i<num; ++i) {
//initialize ith element
alloc.construct(&elems[i],val);
}
}
}Table 15.2. Convenience Functions for Uninitialized Memory
| Expression | Effect |
|---|---|
uninitialized_fill(beg,end,val)
| Initializes [beg, end) with val
|
uninitialized_fill_n(beg,num,val)
| Initializes num elements starting from beg with val
|
uninitialized_copy(beg,end,mem)
| Initialize elements starting from mem with the elements of [beg,end)
|
However, for the initialization of uninitialized memory the C++ standard library provides some convenience functions (Table 15.2). Using these functions, the implementation of the constructor becomes even simpler:
namespace std {
template <class T, class Allocator>
vector<T,Allocator>::vector(size_type num, const T& val,
const Allocator& a)
: alloc(a) //initialize allocator
{
//allocate memory
sizeElems = numElems = num;
elems = alloc.allocate(num);
//initialize elements
uninitialized_fill_n(elems, num, val);
}
}The member function reserve(), which reserves more memory without changing the number of elements (see page 149), could be implemented as follows:
namespace std {
template <class T, class Allocator>
void vector<T,Allocator>::reserve(size_type size)
{
//reserve() never shrinks the memory
if (size <= sizeElems) {
return;
}
//allocate new memory for size elements
T* newmem = alloc.allocate (size);
//copy old elements into new memory
uninitialized_copy(elems,elems+numElems,newmem);
//destroy old elements
for (size_type i=0; i<numElems; ++i) {
alloc.destroy(&elems [i]);
}
//deallocate old memory
alloc.deallocate(elems,sizeElems);
//so, now we have our elements in the new memory
sizeElems = size;
elems = newmem;
}
}In addition, class raw_storage_iterator is provided to iterate over uninitialized memory to initialize it. Therefore, you can use any algorithms with a raw_storage_iterator to initialize memory with the values that are the result of that algorithm.
For example, the following statement initializes the storage to which elems refers by the values in range [x.begin(),x.end()):
copy (x.begin(), x.end(), //source raw_storage_iterator<T*,T>(elems)); //destination
The first template argument (T*, here) has to be an output iterator for the type of the elements. The second template argument (T, here) has to be the type of the elements.
In code you might also find the get_temporary_buffer() and return_temporary_buffer(). They are provided to handle uninitialized memory that is provided for short, temporary use inside a function. Note that get_temporary_buffer() might return less memory than expected. Therefore, get_temporary_buffer() returns a pair containing the address of the memory and the size of the memory (in element units). Here is an example of how to use it:
void f()
{
//allocate memory for num elements of type MyType
pair<MyType*,std;;ptrdiff_t> p = get_temporary_buffer<MyType>(num);
if (p.second == 0) {
//could not allocate any memory for elements
...
}
else if (p.second < num) {
//could not allocate enough memory for num elements
//however, don't forget to deallocate it
...
}
//do your processing
...
//free temporarily allocated memory, if any
if (p.first != 0) {
return_temporary_buffer(p.first);
}
}However, it is rather complicated to write exception-safe code with get_temporary_buffer() and return_temporary_buffer(), so they are usually no longer used in library implementations.
The default allocator is declared as follows:
namespace std {
template <class T>
class allocator {
public:
//type definitions
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef T* pointer;
typedef const T* const_pointer;
typedef T& reference;
typedef const T& const_reference;
typedef T value_type;
//rebind allocator to type U
template <class U>
struct rebind {
typedef allocator<U> other;
};
//return address of values
pointer address(reference value) const;
const_pointer address(const_reference value) const;
//constructors and destructor
allocator() throw();
allocator(const allocator&) throw();
template <class U>
allocator(const allocator<U>&) throw();
~allocator() throw();
//return maximum number of elements that can be allocated
size_type max_size() const throw();
// allocate but don't initialize num elements of type T
pointer allocate(size_type num,
allocator<void>::const_pointer hint = 0);
// initialize elements of allocated storage p with value value
void construct(pointer p, const T& value);
// delete elements of initialized storage p
void destroy(pointer p);
// deallocate storage p of deleted elements
void deallocate(pointer p, size_type num);
};
}The default allocator uses the global operators new and delete to allocate and deallocate memory. Thus, allocate() may throw a bad_alloc exception. However, the default allocator may be optimized by reusing deallocated memory or by allocating more memory than needed to save time in additional allocations. So, the exact moments when operator new and operator delete are called are unspecified. See page 735 for a possible implementation of the default allocator.
There is a strange definition of a template structure inside the allocator, called rebind. This template structure provides the ability that any allocator may allocate storage of another type indirectly. For example, if Allocator is an allocator type, then
Allocator::rebind<T2>::other
is the type of the same allocator specialized for elements of type T2.
rebind<> is useful if you implement a container and you have to allocate memory for a type that differs from the element's type. For example, to implement a deque you typically need memory for arrays that manage blocks of elements (see the typical implementation of a deque on page 160). Thus, you need an allocator to allocate arrays of pointers to elements:
namespace std {
template <class T,
class Allocator = allocator<T> >
class deque {
...
private:
//rebind allocator for type T*
typedef typename Allocator::rebind<T*>::other PtrAllocator;
Allocator alloc; //allocator for values of type T
PtrAllocator block_alloc; //allocator for values of type T*
T** elems; //array of blocks of elements
...
};
}To manage the elements of a deque you have to have one allocator to handle arrays/blocks of elements and another allocator to handle the array of element blocks. The latter has type PtrAllocator, which is the same allocator as for the elements. By using rebind<> the Allocator for the elements (Allocator) is bound to the type of an array of elements (T*).
The default allocator has the following specialization for type void:
namespace std {
template <>
class allocator<void> {
public:
typedef void* pointer;
typedef const void* const_pointer;
typedef void value_type;
template <class U>
struct rebind {
typedef allocator<U> other;
};
};
}Writing your own allocator is not very hard. The most important issue is how you allocate or deallocate the storage. The rest is more or less obvious. As an example, let's look at a naive implementation of the default allocator:
//util/defalloc.hpp namespace std { template <class T> class allocator { public: //type definitions typedef size_t size_type; typedef ptrdiff_t difference_type; typedef T* pointer; typedef const T* const_pointer; typedef T& reference; typedef const T& const_reference; typedef T value_type; //rebind allocator to type U template <class U> struct rebind { typedef allocator<U> other; }; //return address of values pointer address (reference value) const { return &value; } const_pointer address (const_reference value) const { return &value; } /*constructors and destructor *-nothing to do because the allocator has no state */ allocator() throw() { } allocator(const allocator&) throw() { } template <class U> allocator (const allocator<U>&) throw() { } ~allocator() throw() { } //return maximum number of elements that can be allocated size_type max_size () const throw() { //for numeric_limits see Section 4.3, page 59 return numeric_limits<size_t>::max() / sizeof(T); } //allocate but don't initialize num elements of type T pointer allocate (size_type num, allocator<void>::const_pointer hint = 0) { //allocate memory with global new return (pointer) (::operator new(num*sizeof(T))); } //initialize elements of allocated storage p with value value void construct (pointer p, const T& value) { //initialize memory with placement new new((void*)p)T(value); } //destroy elements of initialized storage p void destroy (pointer p) { // destroy objects by calling their destructor p->~T(); } //deallocate storage p of deleted elements void deallocate (pointer p, size_type num) { //deallocate memory with global delete ::operator delete((void*)p)); } }; //return that all specializations of this allocator are interchangeable template <class T1, class T2> bool operator== (const allocator<T1>&, const allocator<T2>&) throw() { return true; } template <class T1, class T2> bool operator!= (const allocator<T1>&, const allocator<T2>&) throw() { return false; } }
Using this base implementation you should find it no problem to implement your own allocator. Typically, the only things that differ from this implementation are max_size(), allocate(), and deallocate(). In these three functions, you program your own policy of memory allocation, such as reusing memory instead of freeing it immediately, using shared memory, or mapping the memory to a segment of an object-oriented database.
See http://www. josuttis.com/libbook/examples.html for additional examples.
According to the specified requirements, allocators have to provide the following types and operations. There are special requirements for allocators that can be used by the standard containers. Allocators that are not provided for the standard containers may have less requirements.
allocator::value_type
The type of the elements.
It is equivalent to
Tforallocator<T>.
allocator::size_type
The type for unsigned integral values that can represent the size of the largest object in the allocation model.
To be usable by the standard containers, this type must be equivalent to
size_t.
allocator::difference_type
The type for signed integral values that can represent the difference between any two pointers in the allocation model.
To be usable by the standard containers, this type must be equivalent to
ptrdiff_t.
allocator::pointer
The type of a pointer to the element type.
To be usable by the standard containers, this type must be equivalent to
T*forallocator<T>.
allocator::const_pointer
The type of a constant pointer to the element type.
To be usable by the standard containers, this type must be equivalent to const
T*forallocator<T>.
allocator::reference
The type of a reference to the element type.
It is equivalent to
T&forallocator<T>.
allocator::const_reference
The type of a constant reference to the element type.
It is equivalent to
const T&forallocator<T>.
allocator::rebind
A template structure that provides the ability that any allocator may allocate storage of another type indirectly.
It has to be declared as follows:
template <class T> class allocator { public: template <class U> struct rebind { typedef allocator<U> other; }; ... }See page 734 for an explanation of the purpose of
rebind.
allocator::allocator ()
The default constructor.
Creates an allocator object.
allocator::allocator
(const allocator& a)
The copy constructor.
Copies an allocator object so that storage allocated from the original and from the copy can be deallocated via the other.
allocator::~allocator ()
The destructor.
Destroys an allocator object.
pointer
allocator::address (reference
value)
const_pointer
allocator::address (const_reference
value)
The first form returns a nonconstant pointer to the nonconstant value.
The second form returns a constant pointer to the constant value.
size_type
allocator::max_size ()
Returns the largest value that can be passed meaningfully to
allocate()to allocate storage.
pointer
allocator::allocate (size_type
num)
pointer
allocator::allocate (size_type num,
allocator<void>::const_pointer
hint)
Both forms return storage for num elements of type
T.The elements are not constructed/initialized (no constructors are called).
The optional second argument has an implementation-specific meaning. For example, it may be used by an implementation to help improve performance.
void
allocator::deallocate (pointer
p,
size_type
num)
Frees the storage to which p refers.
The storage of p has to be allocated by
allocate()of the same or an equal allocator.p must not be
NULLor0.The elements have to have been destroyed already.
void
allocator::construct (pointer
p,
const T&
value)
Initializes the storage of one element to which p refers with value.
It is equivalent to
new((void*)p)T(value).
void
allocator::destroy
(pointer
p)
Destroys the object to which p refers without deallocating the storage.
Simply calls the destructor for the object.
It is equivalent to
((T*)p)->T().
bool
operator ==
(const
allocator& a1,
const
allocator& a2)
Returns
trueif allocators a1 and a2 are interchangeable.Two allocators are interchangeable if storage allocated from each can be deallocated via the other.
To be usable by the standard containers, allocators of the same type are required to be interchangeable. So, this function should always return
true.
bool
operator !=
(const
allocator& a1,
const
allocator& a2)
Returns
trueif two allocators are not interchangeable.It is equivalent to ! (a1 == a2).
To be usable by the standard containers, allocators of the same type are required to be interchangeable. So, this function should always return
false.
This section describes the auxiliary functions for uninitialized memory in detail. The exemplary exception safe implementation of these functions is based with permission on code by Greg Colvin.
void uninitialized_fill (ForwardIterator beg, ForwardIterator end, const T& value)
Initializes the elements in the range [beg,end) with value.
This function either succeeds or has no effect.
This function usually is implemented as follows:
namespace std {
template <class ForwIter, class T>
void uninitialized_fill(ForwIter beg, ForwIter end,
const T& value)
{
typedef typename iterator_traits<ForwIter>::value_type VT;
ForwIter save(beg);
try {
for (; beg!=end; ++beg) {
new (static_cast<void*>(&*beg))VT(value);
}
}
catch (...) {
for (; save!=beg; ++save) {
save->~VT();
}
throw;
}
}
}void
uninitialized_fill_n (ForwardIterator
beg,
Size
num,
const T&
value)
initializes num elements starting from beg with value.
This function either succeeds or has no effect.
This function usually is implemented as follows:
namespace std { template <class ForwIter, class Size, class T> void uninitialized_fill_n (ForwIter beg, Size num, const T& value) { typedef typename iterator_traits<ForwIter>::value_type VT; ForwIter save(beg); try { for (; num--; ++beg) { new (static_cast<void*>(&*beg))VT(value); } } catch (...) { for (; save!=beg; ++save) { save->~VT(); } throw; } } }See page 730 for an example of the use of
uninitialized_fill_n().
ForwardIterator uninitialized_copy (InputIterator sourceBeg, InputIterator sourceEnd, ForwardIterator destBeg)
Initializes the memory starting at destBeg with the elements in the range [sourceBeg,sourceEnd).
The function either succeeds or has no effect.
The function usually is implemented as follows:
namespace std { template <class InputIter, class ForwIter> ForwIter uninitialized_copy(lnputIter beg, InputIter end, ForwIter dest) { typedef typename iterator_traits<ForwIter>::value_type VT; ForwIter save(dest); try { for (; beg!=end; ++beg,++dest) { new (static_cast<void*>(&*dest))VT(*beg); } return dest; } catch (...) { for (; save!=dest; ++save) { save->~VT(); } throw; } } }See page 730 for an example of the use of
uninitialized_copy().