STL Allocator: What is the meaning of the 'Alloc' template parameter in 'vector'?

[Yves M]

Q: What is the meaning of the 'Alloc' template parameter in 'vector'?
Q: How do I define my own allocator for use in STL containers?

A: The whole concept is very well explained in Gabriel and Andreas' article about Allocators.

The template parameter 'Alloc' specifies the type of allocator that the container should use to manage its memory. Every time the container needs a bit of memory, it will ask the allocator to retrieve it for him. The allocator usually just calls 'new' (and 'delete' when it has to free memory), but there can be more sophisticated strategies for allocators.

Usually, you are fine with the standard allocator provided by your STL. However, at times you may need to specify the allocation strategy explicitly. In theory, writing a custom allocator is not very difficult, but the task is complicated by the fact that the standard C++ design relies on template member functions which quite a few compilers don't support (e.g. Visual C++ 6).

A simple example for an allocator which never frees memory is this code (note that you need a recent compiler to get this to work):

#include <limits>

const size_t TEST_SIZE = 10000;
const double TIME_MULTIPLIER = 100.0;

const size_t MAX_SIZE = (TEST_SIZE + 1) * 12;

class MemoryPool
{
  unsigned char  *m_data;
  size_t      m_top;
  int        m_refcount;
public:
  MemoryPool()
  {
    m_data = new unsigned char[MAX_SIZE];
    m_top = 0;
    m_refcount = 0;
  }
  ~MemoryPool()
  {
    delete [] m_data;
  }
  void AddRef()
  {
    ++m_refcount;
  }
  void *alloc_mem(size_t n)
  {
    if ((MAX_SIZE - m_top) >= n) {
      size_t old_top = m_top;
      m_top += n;
      return m_data + old_top;
    } else {
      return 0;
    }
  }
  void Release()
  {
    if (--m_refcount == 0) {
      delete this;
    }
  }
};

template <class T>
class MyAlloc {
public:
  // type definitions
  typedef T        value_type;
  typedef T*       pointer;
  typedef const T* const_pointer;
  typedef T&       reference;
  typedef const T& const_reference;
  typedef std::size_t    size_type;
  typedef std::ptrdiff_t difference_type;

  // rebind allocator to type U
  template <class U >
  struct rebind {
    typedef MyAlloc< 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
  */
  MyAlloc() throw() {
    m_pPool = new MemoryPool;
    m_pPool->AddRef();
  }
  MyAlloc(const MyAlloc& src) throw() {
    m_pPool = src.m_pPool;
    m_pPool->AddRef();
  }
  template <class U >
  MyAlloc (const MyAlloc< U > &src) throw() {
    m_pPool = src.m_pPool;
    m_pPool->AddRef();
  }
  ~MyAlloc() throw() {
    m_pPool->Release();
  }

  // return maximum number of elements that can be allocated
  size_type max_size () const throw() {
    return MAX_SIZE / sizeof(T);
  }

  // allocate but don't initialize num elements of type T
  pointer allocate (size_type num, const void* = 0) {
    // print message and allocate memory with global new
    pointer ret = (pointer) m_pPool->alloc_mem(num * sizeof(T));
    return ret;
  }

  // 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) {
    // do not deallocate memory
  }

  MemoryPool  *m_pPool;
};

// return that all specializations of this allocator are interchangeable
template <class T1, class T2>
bool operator== (const MyAlloc<T1>&, const MyAlloc<T2>&) throw() {
  return true;
}
template <class T1, class T2>
bool operator!= (const MyAlloc<T1>&, const MyAlloc<T2>&) throw() {
  return false;
}