CONTENTS

Chapter 15. Allocators

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.

15.1 Using Allocators as an Application Programmer

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 SpecialAlloc:

   // a vector with special allocator
   vector<int,SpecialAlloc> v;


   // an int/float map with special allocator
   map<int,float,less<int>,SpecialAlloc> m;


   // a string with special allocator
   basic_string<char,char_traits<char>,SpecialAlloc> 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 basic_string<char,char_traits<char>,SpecialAlloc> xstring;


   // special string/string map type that uses special allocator
   typedef map<xstring,xstring,less<xstring>,SpecialAlloc> 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
       ...
   }

15.2 Using Allocators as a Library Programmer

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;
       }
   }

Raw Storage Iterators

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.

Temporary Buffers

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*,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.

15.3 The Default Allocator

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;
           };
       };
   }

15.4 A User-Defined Allocator

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.

15.5 Allocators in Detail

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.

15.5.1 Type Definitions

allocator::value_type

allocator::size_type

allocator::difference_type

allocator::pointer

allocator::const_pointer

allocator::reference

allocator::const_reference

allocator::rebind

15.5.2 Operations

allocator::allocator ()

allocator::allocator (const allocator& a)

allocator::~allocator ()

pointer allocator::address (reference value)

const_pointer allocator::address (const_reference value)

size_type allocator::max_size ()

pointer allocator::allocate (size_type num)

pointer allocator::allocate (size_type num, allocator<void>::const_pointer hint)

void allocator::deallocate (pointer p, size_type num)

void allocator::construct (pointer p, const T& value)

void allocator::destroy (pointer p)

bool operator == (const allocator& a1, const allocator& a2)

bool operator != (const allocator& a1, const allocator& a2)

15.6 Utilities for Uninitialized Memory in Detail

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)
   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)

   ForwardIterator uninitialized_copy (InputIterator sourceBeg,
                                    InputIterator sourceEnd,
                                    ForwardIterator destBeg)
CONTENTS
Browser Based Help. Published by chm2web software.