How are allocator in C++ implemented?

Question

I was trying to understand a bit better std::allocator in C++, I came across this question, and it seems to me there's actually only one allocator class typically used by containers (like std::vector) my question is how is such allocator implemented? Is it like a stack which is periodically re-allocated? If not how is it actually implemented?

Answer 1

The default allocator is std::allocator, and just uses ::operator new as and when required, so nothing special. It's more or less the same as doing new and delete yourself for each object needed. You can read more about it under [default.allocator] in the standard.

The allocator "interface" (really just a set of requirements, enforced during template instantiation) is a wrapper around this process, allowing alternative memory provisioning approaches to be employed.

For example, alternative allocators that you may provide could implement a memory pool or something else that's specific to your needs, cutting down on honest-to-goodness dynamic allocations.

Standard containers have, as well as their element type, an allocator type as template argument (you usually don't notice this!) and this is how you select alternative implementations for use with that container.

In these cases you'll generally be pre-allocating some big chunk of memory then dishing out little chunks as and when. In that sense, such an implementation could be considered a sort of "heap within a heap", but really there's no reason you need to give it heap semantics at all. It only needs to abide by the requirements of the concept Allocator.

Mr Josuttis has put a (boring) example up at http://www.josuttis.com/cppcode/allocator.html; I reproduce it here:

/* The following code example is taken from the book
 * "The C++ Standard Library - A Tutorial and Reference"
 * by Nicolai M. Josuttis, Addison-Wesley, 1999
 *
 * (C) Copyright Nicolai M. Josuttis 1999.
 * Permission to copy, use, modify, sell and distribute this software
 * is granted provided this copyright notice appears in all copies.
 * This software is provided "as is" without express or implied
 * warranty, and with no claim as to its suitability for any purpose.
 */
#include <limits>
#include <iostream>

namespace MyLib {
   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() {
       }
       MyAlloc(const MyAlloc&) throw() {
       }
       template <class U>
         MyAlloc (const MyAlloc<U>&) throw() {
       }
       ~MyAlloc() throw() {
       }

       // return maximum number of elements that can be allocated
       size_type max_size () const throw() {
           return std::numeric_limits<std::size_t>::max() / 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
           std::cerr << "allocate " << num << " element(s)"
                     << " of size " << sizeof(T) << std::endl;
           pointer ret = (pointer)(::operator new(num*sizeof(T)));
           std::cerr << " allocated at: " << (void*)ret << std::endl;
           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) {
           // print message and deallocate memory with global delete
           std::cerr << "deallocate " << num << " element(s)"
                     << " of size " << sizeof(T)
                     << " at: " << (void*)p << std::endl;
           ::operator delete((void*)p);
       }
   };

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

And usage:

#include <vector>
#include "myalloc.hpp"

int main()
{
    // create a vector, using MyAlloc<> as allocator
    std::vector<int,MyLib::MyAlloc<int> > v;

    // insert elements
    // - causes reallocations
    v.push_back(42);
    v.push_back(56);
    v.push_back(11);
    v.push_back(22);
    v.push_back(33);
    v.push_back(44);
}