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:
The expression a1 == a2
evaluates to true
only if storage allocated
from a1
can be deallocated by a2
, and vice versa.
The expression X a1(a);
is well-formed, doesn't exit via an exception,
and afterward a1 == a
is true.
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:
Are my interpretations above correct?
I've read in a few places that C++11 improved support for "stateful allocators". How is that the case, given these restrictions?
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?
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?
Allocators were invented by Alexander Stepanov as part of the Standard Template Library (STL). They were originally intended as a means to make the library more flexible and independent of the underlying memory model, allowing programmers to utilize custom pointer and reference types with the library.
Member functions associated with std::allocator() : address: It is used for obtaining the address of an object although it is removed in C++20. construct: It is used to construct an object.It is also removed in C++20. destroy: It is used to destruct an object in allocated storage.It is also removed in C++20.
Allocators represent a special memory model and are an abstraction used to translate the need to use memory into a raw call for memory. They provide an interface to allocate, create, destroy, and deallocate objects. With allocators, containers and algorithms can be parameterized by the way the elements are stored.
Allocators are used by the C++ Standard Library to handle the allocation and deallocation of elements stored in containers. All C++ Standard Library containers except std::array have a template parameter of type allocator<Type> , where Type represents the type of the container element.
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;
}
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With