A working stack allocator

Question

Here's an absolutely essential piece of C++ lore, a stack allocator, that will allow you to, say, allocate strings and vectors on the stack. There are 2 stack allocators I know of, here and here.

The trouble was, neither of them were working with gcc-4.8, and both needed fixing. Here's a fixed version of Hinant's allocator. Could there some improvement or fix to still be made?

#pragma once
#ifndef STACKALLOCATOR_HPP
# define STACKALLOCATOR_HPP

#include <cassert>

#include <cstddef>

#include <functional>

#include <new>

#include <utility>

template <std::size_t N>
class stack_store
{
public:
  stack_store() = default;

  stack_store(stack_store const&) = delete;

  stack_store& operator=(stack_store const&) = delete;

  char* allocate(std::size_t n)
  {
    assert(pointer_in_buffer(ptr_) &&
      "stack_allocator has outlived stack_store");

    n = align(n);

    if (buf_ + N >= ptr_ + n)
    {
      auto r(ptr_);

      ptr_ += n;

      return r;
    }
    else
    {
      return static_cast<char*>(::operator new(n));
    }
  }

  void deallocate(char* const p, std::size_t n) noexcept
  {
    assert(pointer_in_buffer(ptr_) &&
      "stack_allocator has outlived stack_store");

    if (pointer_in_buffer(p))
    {
      n = align(n);

      if (p + n == ptr_)
      {
        ptr_ = p;
      }
      // else do nothing
    }
    else
    {
      ::operator delete(p);
    }
  }

  void reset() noexcept { ptr_ = buf_; }

  static constexpr ::std::size_t size() noexcept { return N; }

  ::std::size_t used() const { return ::std::size_t(ptr_ - buf_); }

private:
  static constexpr ::std::size_t align(::std::size_t const n) noexcept
  {
    return (n + (alignment - 1)) & -alignment;
  }

  bool pointer_in_buffer(char* const p) noexcept
  {
    return (buf_ <= p) && (p <= buf_ + N);
  }

private:
  static constexpr auto const alignment = alignof(::max_align_t);

  char* ptr_{buf_};

  alignas(::max_align_t) char buf_[N];
};

template <class T, std::size_t N>
class stack_allocator
{
public:
  using store_type = stack_store<N>;

  using size_type = ::std::size_t;

  using difference_type = ::std::ptrdiff_t;

  using pointer = T*;
  using const_pointer = T const*;

  using reference = T&;
  using const_reference = T const&;

  using value_type = T;

  template <class U> struct rebind { using other = stack_allocator<U, N>; };

  stack_allocator() = default;

  stack_allocator(stack_store<N>& s) noexcept : store_(&s) { }

  template <class U>
  stack_allocator(stack_allocator<U, N> const& other) noexcept :
    store_(other.store_)
  {
  }

  stack_allocator& operator=(stack_allocator const&) = delete;

  T* allocate(::std::size_t const n)
  {
    return static_cast<T*>(static_cast<void*>(
      store_->allocate(n * sizeof(T))));
  }

  void deallocate(T* const p, ::std::size_t const n) noexcept
  {
    store_->deallocate(static_cast<char*>(static_cast<void*>(p)),
      n * sizeof(T));
  }

  template <class U, class ...A>
  void construct(U* const p, A&& ...args)
  {
    new (p) U(::std::forward<A>(args)...);
  }

  template <class U>
  void destroy(U* const p)
  {
    p->~U();
  }

  template <class U, std::size_t M>
  inline bool operator==(stack_allocator<U, M> const& rhs) const noexcept
  {
    return store_ == rhs.store_;
  }

  template <class U, std::size_t M>
  inline bool operator!=(stack_allocator<U, M> const& rhs) const noexcept
  {
    return !(*this == rhs);
  }

private:
  template <class U, std::size_t M> friend class stack_allocator;

  store_type* store_{};
};

namespace std
{
  // string
  template<class CharT> class char_traits;

  template<class CharT, class Traits, class Allocator> class basic_string;

  // unordered_map
  template<class Key, class T, class Hash, class Pred, class Alloc>
    class unordered_map;

  // vector
  template <class T, class Alloc> class vector;
}

using stack_string = ::std::basic_string<char, ::std::char_traits<char>,
  stack_allocator<char, 128> >;

template <class Key, class T, class Hash = ::std::hash<Key>,
  class Pred = ::std::equal_to<Key> >
using stack_unordered_map = ::std::unordered_map<Key, T, Hash, Pred,
  stack_allocator<::std::pair<Key const, T>, 256> >;

template <typename T>
using stack_vector = ::std::vector<T, stack_allocator<T, 256> >;

#endif // STACKALLOCATOR_HPP

Example usage:

#include <iostream>

#include "stackallocator.hpp"

int main()
{
  ::stack_string::allocator_type::store_type s;

  ::std::cout << ::stack_string("blabla", s).c_str() << std::endl;

  return 0;
}

After running the above example under valgrind, it will report:

==25600== HEAP SUMMARY:
==25600==     in use at exit: 0 bytes in 0 blocks
==25600==   total heap usage: 0 allocs, 0 frees, 0 bytes allocated
==25600== 
==25600== All heap blocks were freed -- no leaks are possible
==25600== 
==25600== For counts of detected and suppressed errors, rerun with: -v
==25600== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 2 from 2)

Answer 1

Fixes required for a conforming Standard Library

There is one big issue that will make custom allocators fragile to work with: incomplete C++11 library support. Since C++11, containers are required to go through std::allocator_traits<Allocator> to access construct() and destroy() allocator member functions, as well as to access nested typedefs such as pointer and reference. Furthermore, all containers have a constructor with a single allocator argument. Not every Standard Library implements this for every container.

With the Coliru online compiler, I can get Hinnant's stack allocator working with libstdc++ for a std::vector with only 2 minor modifications running

g++ -std=c++11 -O1 -pedantic -Wall -Wconversion -Wsign-conversion -Wsign-promo

The first is to put parenthesis around the n + (alignment - 1) operand in the align_up()

std::size_t 
    align_up(std::size_t n) noexcept
        {return (n + (alignment-1)) & ~(alignment-1);}
                ^                 ^

The second is to remove the exception specification from the overloaded operator new

void* operator new(std::size_t s) // throw(std::bad_alloc)

Live Example exactly reproducing Hinnant's first test case.

Note that these 2 warnings are rather innocent and do not affect correctness of the program.

Fixes required for a non-conforming Standard Library

Since libstdc++ works fine with all containers if a std::allocator is provided (even when the container implementation directly accesses the allocator, rather than through std::allocator_traits) the safest bet is to provide all the nested typedefs and member functions of std::allocator_traits in your own allocator as well. This includes the various pointer and reference types, as well as the rebind templates. You appear to have done so, and this should resolve at least of all those issues. I still would leave the original naming of Hinnant's version in tact, though.

That leaves the issues of constructors taking a single allocator argument. At least for libstdc++ for g++ 4.8.1, this constructor is missing for std:unordered_map. Apart from patching the standard library headers yourself (possible, but if you have an automatic package updater, that will require constant monitoring) or submit a bug report. Microsoft did have many such issues in Visual C++ 2012 November CTP, which have all been fixed in Visual C++ 2013.