How to Write a Stateful Allocator in C++11, Given Requirements on Copy Construction

How can I write a stateful allocator in C++11, given requirements on copy construction?

1) Are my interpretations above correct?

You are right that your free-list might not be a good fit for allocators, it need be able to handle multiple sizes (and alignments) to fit. That's a problem for the free-list to solve.

2) I've read in a few places that C++11 improved support for "stateful allocators". How is that the case, given these restrictions?

It is not so much improved, than born. In C++03 the standard only nudged implementers toward providing allocators which could support non-equal instances and implementers, effectively making stateful allocators non-portable.

3) Do you have any suggestions for how to do the sort of thing I'm trying to do? That is, how do I include allocated-type-specific state in my allocator?

Your allocator may have to be flexible, because you are not supposed to know exactly what memory (and what types) it is supposed to allocate. This requirement is necessary to insulate you (the user) from the internals of some of the container that uses the allocator such as std::list, std::set or std::map.

You can still use such allocators with simple containers such as std::vector or std::deque.

Yes, it is a costly requirement.

4) In general, the language around allocators seems sloppy. (For example, the prologue to Table 28 says to assume that a is of type X&, but some of the expressions redefine a.) Also, at least GCC's support is non-conformant. What accounts for this weirdness around allocators? Is it just an infrequently used feature?

The Standard in general is not exactly easy to read, not only allocators. You do have to be careful.

To be pedant, gcc does not support allocators (it's a compiler). I surmise that you are speaking about libstdc++ (the Standard Library implementation shipped with gcc). libstdc++ is old, and thus it was tailored to C++03. It has been adapted toward C++11, but is not fully conformant yet (still uses Copy-On-Write for strings, for example). The reason is that libstdc++ has a huge focus on binary compatibility, and a number of changes required by C++11 would break this compatibility; they must therefore be introduced carefully.

Copy stateful allocator: standard library allocator semantics and internal memory

The allocator requirements say that copies of an allocator must be able to free each others' memory, so it is not generally possible to store the memory inside the allocator object.

This must be valid:

using IAllocChar = internal_allocator<char, 1024>;
IAllocChar::pointer p
IAllocChar a1;
{
  IAllocChar a2(a1);
  p = std::allocator_traits<IAllocChar>::allocate(a2, 1);
}
std::allocator_traits<IAllocChar>::deallocate(a1, p, 1)

So you need to store the actual memory outside the allocator object (or only use it in very restricted ways that ensure the object doesn't go out of scope while anything is referring to memory it owns).

You're also going to struggle with rebinding your internal_allocator, what should the following do?

using IAllocChar = internal_allocator<char, 1024>;
using IAllocInt = std::allocator_traits<IAllocChar>::rebind_alloc<int>;
IAllocChar ac;
auto pc = ac.allocate(1);  // got bored typing allocator_traits ;-)
IAllocInt  ai(ac);
auto pi = ai.allocate(1);
IAllocChar(ai).deallocate(pc, 1);
IAllocInt(ac).deallocate(pi, 1);

Are C++11 stateful allocators interchangeable across type boundaries?

The last line that you quote:

X a(b); Shall not exit via an exception. post: Y(a) == b, a == X(b)

Conflicts with your conclusion.

using X = Allocator<T>;
using Y = Allocator<U>;
Y b;
X a(b);
assert(Y(a) == b);
assert(a == X(b));
// therefore
assert(a == b);

compiler support for stateful allocators in STL containers

Looks like the feature of stateful allocators in STL containers is widely supported already. In most cases statefullness of the allocator does not cause trouble. What is not widely supported yet is the new standard's way of handling the problematic situations (swap of a container(whether to swap the allocator too), splice of lists).

This thread says:

in code for most current standard libraries (including Dinkumware's as used by MS), stateful allocators are supported

This tread (libstdc++, 2004) says (if i understood correctly):

We already support allocators where l1.get_allocator() != l2.get_allocator(). What we don't do is make any special provisions to detect those allocators in splice() and swap().

This blog entry (libstdc++, 2009) says:

Existing containers in C++0x mode are now more efficient together with stateful allocators (i.e., no allocators are created on the fly at element construction time).

This document says about the new libc++ library:

All containers meet all of the latest allocator requirements
which fully support stateful allocators.
– Space for stateless allocators optimized away.

EASTL supports statefull allocators.

This thread contains an interesting dispute about how portable this feature is.

So most STL implementations support statefull allocators, which means that they do not create additional instances of the allocator type under the hood, but store the client-supplied allocator instance and all allocations/deallocations are done via that. However the way that they handle swapping and list::splice is undocumented, non-portable.

UPDATE: VS2008's STL requires the allocators to have the templated copy constructor, which IMO makes the most important use of custom allocators impossible: simple segregated storage.

For whoever is not satisfied with the current state of stateful allocators in STL, I recommend to consider Boost.Intrusive and Boost.Container.

stl allocator, copy constructor of other type, rebind

To allow construction from other allocators, as containers need to use a different allocator type than you specify. Lists and maps, for example, allocate their internal node type rather than the value_type they expose.

The code looks similar to:

template<class T, class Alloc=std::allocator<T> >
struct Container {
  typedef T value_type;
  typedef Alloc allocator_type;

private:
  struct Node {/*...*/};
  typedef typename Alloc::template rebind<Node>::other RealAllocatorType;
  RealAllocatorType allocator;
};

How to use basic_ostringstream with stateful custom allocator?? (C++11)

It is possible that the resolution to the LWG defect #2210, which added allocator instances to the constructors of many standard library containers, was not sufficiently thorough and the streams were overlooked. Or perhaps it wasn't clear enough how to approach them. I would suggest filing a new library defect report (or perhaps asking first in std-discussion)

Is it possible to write a custom STL allocator that uses pointers to allocation functions provided by the user?

I looked at allocator classes but it seems STL containers must be able to use the default constructors to create the allocator

That's not true, all containers can be constructed with an allocator explicitly, so you can create your allocator object and then pass it to the container.

extern "C"
{
  typedef void* (*allocation_function)(size_t);
  typedef void (*deallocation_function)(void*);
}

template<typename T>
class Allocator
{
public:
  typedef T value_type;

  Allocator(allocation_function alloc, deallocation_function dealloc)
  : m_allocate(alloc), m_deallocate(dealloc)
  { }

  template<typename U>
    Allocator(const Allocator<U>& a)
    : m_allocate(a.m_allocate), m_deallocate(a.m_deallocate)
    { }

  T* allocate(size_t n)
  { return static_cast<T*>(m_allocate(n * sizeof(T))); }

  void deallocate(T* p, size_t)
  { m_deallocate(p); }

private:
  template<typename U>
    friend class Allocator<U>;

  template<typename U>
    friend bool operator==(const Allocator<U>&, const Allocator<U>&);

  allocation_function   m_allocate;
  deallocation_function m_deallocate;
};

template<typename T>
bool operator==(const Allocator<T>& l, const Allocator<T>& r)
{ return l.m_allocate == r.m_allocate; }

template<typename T>
bool operator!=(const Allocator<T>& l, const Allocator<T>& r)
{ return !(l == r); }

Allocator<int> a(custom_malloc, custom_free);
std::vector<int, Allocator<int>> v(a);

If you're using not using C++11 yet then you need to provide a lot more members for your allocator to meet the old requirements, but the one above is OK for C++11. Using custom allocators in C++03 is difficult and not portable anyway, so you should aim to use a C++11 compiler if you need to do this.

---

Related Topics