38

As far as I can tell, the requirements on an allocator to be used with STL containers are laid out in Table 28 of section 17.6.3.5 of the C++11 standard.

I'm a bit confused about the interaction between some of these requirements. Given a type X that is an allocator for type T, a type Y that is "the corresponding allocator class" for type U, instances a, a1, and a2 of X, and an instance b of Y, the table says:

  1. The expression a1 == a2 evaluates to true only if storage allocated from a1 can be deallocated by a2, and vice versa.

  2. The expression X a1(a); is well-formed, doesn't exit via an exception, and afterward a1 == a is true.

  3. The expression X a(b) is well-formed, doesn't exit via an exception, and afterward a == b.

I read this as saying that all allocators must be copy-constructible in such a way that the copies are interchangeable with the originals. Worse, the same true across type boundaries. This seems to be a pretty onerous requirement; as far as I can tell, it makes impossible a large number of types of allocators.

For example, say I had a freelist class that I wanted to use in my allocator, in order to cache freed objects. Unless I'm missing something, I couldn't include an instance of that class in the allocator, because the sizes or alignments of T and U might differ and therefore the freelist entries are not compatible.

My questions:

  1. Are my interpretations above correct?

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

  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?

  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?

jacobsa
  • 5,719
  • 1
  • 28
  • 60
  • 3
    Note: the difficulty of allocators is `rebind`, when you instantiate a `std::list>` it will not use a `std::allocator` directly, but instead use `std::allocator<__list_node>` internally. Thus the requirements of equivalence across type boundaries: it's necessary to insulate the user of a container from the internal way memory is managed. – Matthieu M. Jun 18 '14 at 07:03
  • Right, but what's the point of allowing allocators to compare not equal, if every way that a container could construct one creates a new one that's equal to the old one? In my particular case, I would be fine if the container default constructed the type provided by `rebind`, yielding an instance that's not equal. But the standard doesn't allow for that, as far as I can tell. – jacobsa Jun 18 '14 at 07:08
  • 1
    It's not about one container but about two. If you have two containers, each with its own allocator, then you may or may not be able to *swap* their content depending on whether the instances can (or not) deallocate each other's content. The archetype is the *stack allocator*; ie an allocator that uses a block of memory stored on the stack. This poses specific challenges since the allocator cannot *move* its storage, and thus cannot swap it. – Matthieu M. Jun 18 '14 at 07:14
  • related: http://stackoverflow.com/questions/21975695/copy-stateful-allocator-standard-library-allocator-semantics-and-internal-memor – Ryan Haining Jun 18 '14 at 16:59
  • Note that you can restrict the types your allocator can be rebound to (via [allocator.requirements]/5). This can disallow their usage in specific implementations of the Standard Library for some containers, though, especially with debug implementations that use a rebound allocator e.g. for checked iterators (I'm looking at you, MSVC). – dyp Jun 18 '14 at 16:59

3 Answers3

29

Equality of allocators does not imply that they must have exactly the same internal state, only that they must both be able to deallocate memory that was allocated with either allocator. Cross-type equality of allocators a == b for an allocator a of type X and allocator b of type Y is defined in table 28 as "same as a == Y::template rebind<T>::other(b)". In other words, a == b if memory allocated by a can be deallocated by an allocator instantiated by rebinding b to a's value_type.

Your freelist allocators need not be able to deallocate nodes of arbitrary type, you only need to ensure that memory allocated by FreelistAllocator<T> can be deallocated by FreelistAllocator<U>::template rebind<T>::other. Given that FreelistAllocator<U>::template rebind<T>::other is the same type as FreelistAllocator<T> in most sane implementations, this is fairly easy to achieve.

Simple example (Live demo at Coliru):

template <typename T>
class FreelistAllocator {
    union node {
        node* next;
        typename std::aligned_storage<sizeof(T), alignof(T)>::type storage;
    };

    node* list = nullptr;

    void clear() noexcept {
        auto p = list;
        while (p) {
            auto tmp = p;
            p = p->next;
            delete tmp;
        }
        list = nullptr;
    }

public:
    using value_type = T;
    using size_type = std::size_t;
    using propagate_on_container_move_assignment = std::true_type;

    FreelistAllocator() noexcept = default;
    FreelistAllocator(const FreelistAllocator&) noexcept {}
    template <typename U>
    FreelistAllocator(const FreelistAllocator<U>&) noexcept {}
    FreelistAllocator(FreelistAllocator&& other) noexcept :  list(other.list) {
        other.list = nullptr;
    }

    FreelistAllocator& operator = (const FreelistAllocator&) noexcept {
        // noop
        return *this;
    }

    FreelistAllocator& operator = (FreelistAllocator&& other) noexcept {
        clear();
        list = other.list;
        other.list = nullptr;
        return *this;
    }

    ~FreelistAllocator() noexcept { clear(); }

    T* allocate(size_type n) {
        std::cout << "Allocate(" << n << ") from ";
        if (n == 1) {
            auto ptr = list;
            if (ptr) {
                std::cout << "freelist\n";
                list = list->next;
            } else {
                std::cout << "new node\n";
                ptr = new node;
            }
            return reinterpret_cast<T*>(ptr);
        }

        std::cout << "::operator new\n";
        return static_cast<T*>(::operator new(n * sizeof(T)));
    }

    void deallocate(T* ptr, size_type n) noexcept {
        std::cout << "Deallocate(" << static_cast<void*>(ptr) << ", " << n << ") to ";
        if (n == 1) {
            std::cout << "freelist\n";
            auto node_ptr = reinterpret_cast<node*>(ptr);
            node_ptr->next = list;
            list = node_ptr;
        } else {
            std::cout << "::operator delete\n";
            ::operator delete(ptr);
        }
    }
};

template <typename T, typename U>
inline bool operator == (const FreelistAllocator<T>&, const FreelistAllocator<U>&) {
    return true;
}

template <typename T, typename U>
inline bool operator != (const FreelistAllocator<T>&, const FreelistAllocator<U>&) {
    return false;
}
Casey
  • 41,449
  • 7
  • 95
  • 125
  • This answer is much more informative than the accepted one, but I have one question: why not make the data member `list` a `static` one? After all, the fact that they all compare equal (justly) indicates that allocators objects of the same template instance (i.e., of the same type) can recycle each other's produce. But then there seems to be no good reason why they should hold separate free lists; they could all share the same. (There would still be separate lists for different T's.) Since every constructor creates a fresh one, you may end up with many small free lists. – Marc van Leeuwen Aug 31 '18 at 07:08
  • @MarcvanLeeuwen That would be a simple optimization to make in a single-threaded program, and slightly more challenging in a multi-threaded program. But yes, that's a perfectly valid approach. – Casey Sep 01 '18 at 01:16
15

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.

Matthieu M.
  • 287,565
  • 48
  • 449
  • 722
  • Thanks for addressing all points. I have read lots of the standard in the past, and am used to reading through the standardese. This part in particular seems far less precisely worded, but maybe it's just me. And yes, I meant libstdc++ of course. – jacobsa Jun 18 '14 at 08:47
  • @jacobsa: I agree that not all parts are equal, if you have specific complaints do not hesitate to open an issue on the [Github repository](https://github.com/cplusplus/draft) (or even fix them yourself). – Matthieu M. Jun 18 '14 at 09:00
  • Thanks, I didn't realize that was possible. I've sent pull request #334. – jacobsa Jun 20 '14 at 01:27
  • 1
    You said _"In C++03 any instance of an allocator was supposed to be equivalent to another instance of the same type, effectively making stateful allocators impossible."_ That's not quite right. C++03 said "Implementors are encouraged to supply libraries that can accept allocators that encapsulate more general memory models and that support non-equal instances." So non-equal instances of stateful allocators were _supposed_ to work, but weren't _required_ to, making stateful allocators non-portable, because it was implementation-defined whether they worked. And in practice they didn't work. – Jonathan Wakely Aug 31 '18 at 13:09
  • Also "Your allocator _has to be flexible_," is not true. A fully general purpose allocator needs to be, but it's perfectly fine to have an allocator that only supports certain value types and so can only be used in limited ways. My answer goes into more detail on this part. – Jonathan Wakely Aug 31 '18 at 13:11
  • @JonathanWakely: I'll fix the C++03 comment; as for flexible, I am afraid there's no way around it. The allocator does not have to handle *everything*, but you just cannot know which type `std::list` will allocate, because it allocates a private "node" struct. – Matthieu M. Aug 31 '18 at 13:13
  • 1
    Yeah, I know how `std::list` works, I've implemented it multiple times :) As my answer says, an allocator that only supports some types can't be used with containers like `std::list`, but it can still be used with `std::vector`. So "there's no way around it" is wrong as long as you only use the allocator in limited ways. – Jonathan Wakely Aug 31 '18 at 13:16
  • @JonathanWakely: Amended to note that this applies only to a subset of the containers and the allocator can still be used with simpler ones. – Matthieu M. Aug 31 '18 at 14:44
  • @JonathanWakely Being the one who seems to have stirred up things here lately, let me use this occasion to remark the following. I just cannot understand why the standard defines nothing in the way of distinguishing allocator categories, in the same way it distinguishes iterator categories. Clearly something could be gained by acknowledging that not all iterators are created equal. Damn, I want to be able to write an iterator that will _only_ be used to allocate nodes of a fixed size, but the standard forces me to handle requests for n>1 items, though many containers never ever do that. – Marc van Leeuwen Sep 01 '18 at 09:27
  • This is the wrong place to discuss that. There are proposals for exactly that, but I'm not going to discuss them here. I'll just say that nothing prevents your allocator from throwing `bad_alloc` when n!=1, so it doesn't "force" you at all. – Jonathan Wakely Sep 01 '18 at 09:42
10

I read this as saying that all allocators must be copy-constructible in such a way that the copies are interchangeable with the originals. Worse, the same true across type boundaries. This seems to be a pretty onerous requirement; as far as I can tell, it makes impossible a large number of types of allocators.

It is trivial to meet the requirements if allocators are a lightweight handle onto some memory resource. Just don't try to embed the resource inside individual allocator objects.

For example, say I had a freelist class that I wanted to use in my allocator, in order to cache freed objects. Unless I'm missing something, I couldn't include an instance of that class in the allocator, because the sizes or alignments of T and U might differ and therefore the freelist entries are not compatible.

[allocator.requirements] paragraph 9:

An allocator may constrain the types on which it can be instantiated and the arguments for which its construct member may be called. If a type cannot be used with a particular allocator, the allocator class or the call to construct may fail to instantiate.

It's OK for your allocator to refuse to allocate memory for anything except a given type T. That will prevent it being used in node-based containers such as std::list which need to allocate their own internal node types (not just the container's value_type) but it will work fine for std::vector.

That can be done by preventing the allocator being rebound to other types:

class T;

template<typename ValueType>
class Alloc {
  static_assert(std::is_same<ValueType, T>::value,
    "this allocator can only be used for type T");
  // ...
};

std::vector<T, Alloc<T>> v; // OK
std::list<T, Alloc<T>> l;   // Fails

Or you could only support types that can fit in sizeof(T):

template<typename ValueType>
class Alloc {
  static_assert(sizeof(ValueType) <= sizeof(T),
    "this allocator can only be used for types not larger than sizeof(T)");
  static_assert(alignof(ValueType) <= alignof(T),
    "this allocator can only be used for types with alignment not larger than alignof(T)");

  // ...
};
  1. Are my interpretations above correct?

Not entirely.

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

The restrictions before C++11 were even worse!

It is now clearly specified how allocators propagate between containers when copied and moved, and how various container operations behave when their allocator instance is replaced by a different instance that might not compare equal to the original. Without those clarifications it was not clear what was supposed to happen if e.g. you swapped two containers with stateful allocators.

  1. 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?

Don't embed it directly in the allocator, store it separately and have the allocator refer to it by a pointer (possibly smart pointer, depending on how you design the lifetime management of the resource). The actual allocator object should be a lightweight handle on to some external source of memory (e.g. an arena, or pool, or something managing a freelist). Allocator objects that share the same source should compare equal, this is true even for allocators with different value types (see below).

I also suggest that you don't try to support allocation for all types if you only need to support it for one.

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

Yes, as you reported at https://github.com/cplusplus/draft/pull/334 (thanks).

Also, at least GCC's support is non-conformant.

It's not 100%, but will be in the next release.

What accounts for this weirdness around allocators? Is it just an infrequently used feature?

Yes. And there's a lot of historical baggage, and it's difficult to specify to be widely useful. My ACCU 2012 presentation has some details, I'll be very surprised if after reading that you think you can make it simpler ;-)

Regarding when allocators compare equal, consider:

MemoryArena m;
Alloc<T> t_alloc(&m);
Alloc<T> t_alloc_copy(t_alloc);
assert( t_alloc_copy == t_alloc ); // share same arena
Alloc<U> u_alloc(t_alloc);
assert( t_alloc == u_alloc ); // share same arena
MemoryArena m2
Alloc<T> a2(&m2);
assert( a2 != t_alloc ); // using different arenas

The meaning of allocator equality is that the objects can free each other's memory, so if you allocate some memory from t_alloc and (t_alloc == u_alloc) is true, then it means you can deallocate that memory using u_alloc. If they're not equal, u_alloc can't deallocate memory that came from t_alloc.

If you just have a freelist where any memory can get added to any other freelist then maybe all your allocator objects would compare equal to each other.

Jonathan Wakely
  • 166,810
  • 27
  • 341
  • 521
  • I think this answer is somewhat confusing. An allocator with `value_type` T cannot be asked to allocate for another type than T (though it might be asked to allocate for an array of a given number of T), so saying it is OK to refuse to do so is missing a point. Also you aren't very clear about how a pointer to proper resources should be managed; it must notably be possible to copy-construct a "rebound" version of the allocator (which has a different type) then copy-construct a version back of the original type, and have it test equal (and presumable share resource) with the original allocator. – Marc van Leeuwen Aug 31 '18 at 07:50
  • By "your allocator" I meant the family of types defined by the class template. It can refuse to allocate memory for anything except a type `T` by not allowing rebinding to other types, or by allowing rebinding but always throwing `bad_alloc` when `value_type` isn't `T`, so that `Alloc` works but `Alloc` doesn't. That is what "An allocator may constrain the types on which it can be instantiated" means. I'll try to clarify the answer to address your concerns. – Jonathan Wakely Aug 31 '18 at 12:28