“An Allocator is a handle to a heap”.
Alexander Stepanov (the father of STL) came up with the idea of Allocator and the motivation was to make the containers completely independent of the underlying memory model. He intended to make allocators completely encapsulate the memory model, but the standards committee found it dangerous, as this approach would lead to unacceptable efficiency degradations. As a result, the current purpose of allocators is to give the programmer control over memory allocation within containers, rather than to adopt the address model of the underlying hardware. Not what Stepanov had in mind but still helpful in some scenarios. Unfortunately, these scenarios are super rare, and the Allocator just became “that last template parameter”.
Each container instance has a single instance of Allocator in it. It’s asking the allocator for storage to store the elements. The basic functionality the allocator is expected to have is the following:
T* allocate(size_t n); allocates enough storage to store n instances of T and returns a pointer to it
void deallocate(T* p, size_t n); releases the storage
void construct(T* p, Args ... args); constructs an object with args parameters where p points to
void destroy(T* p); calls the destructor of the object where p points to
Actually, the best practice for containers is not to call this functions directly, and STL containers don’t do it either. Instead, they call static functions of std::allocator_traits<AllocT>. When writing your own allocator you have to make it acceptable for allocator_traits , so that it will work for STL containers. It also will take care of a huge part of requirements, easing up your job. An important thing to note is that the last two functions ( construct and destroy ) are deprecated in C++17 and will be removed in C++20, instead the allocator_traits will simply do a placement new and call destructor respectively. So, if you’ll be writing your own container, use allocator_traits interface.
Another thing you may notice about std::allocator is that it’s stateless. Is it how allocators are supposed to be? Not necessarily, but as mentioned, an allocator is a handle to a heap, so surely it’s not supposed to be something big. std::allocator is empty because it’s a handle to the one and only, ultimate memory resource the OS is providing, you don’t need any fields to help you find it, it’s right there. Your custom Allocator should need enough members to stay in touch with the memory resource provider (heap), which roughly is a pointer. So, if you’re writing a custom allocator and it ends up big, probably something is wrong.
Let’s implement our own allocator, something meaningful. A good scenario would be if we had a custom memory resource or a memory pool, and then we implemented an Allocator for it. As mentioned above, an Allocator is just a handle, so it wouldn’t be a big deal.
Moreover, STL provides an abstract interface std::pmr::memory_resource, which you should extend if you’re implementing your own memory resource, and it has allocate and deallocate functions, so the allocator HAS ONE JOB, call them.
But I don’t have my own memory resource implemented, so I suggest implementing an allocator which will log the memory usage. We want it to behave exactly like std::allocator, only it has an extra step before allocating and deallocating. Instead of reinventing the whole wheel, we can simply derive from it and use shadowing for two functions:
The using declarations in private section help us to get the same signature for allocate and deallocate functions, thus shadowing the ones in the base. Now we add a global counter and modify it before allocating and deallocating.
That’s it, the Allocator is ready (hopefully). Now let’s test it. As a test, we’ll create three different containers with my::Allocator, insert 1000 elements in it and see how much memory was used.
I’ve chosen vector, list and set, and I’ve made the test function template not to write the same thing 3 times. So the test is a template function with one template template parameter.
Line 7: test has a single template parameter, ContainerT, which itself is a template type. Note that in function main non-specified template types are provided ( std::vector, not std::vector<int> ). And so our test function is expecting this parameter to be a template class with 2 parameters, value type and allocator type.
Line 10: The macro __PRETTY_FUCNTION__ is available in GCC and CLang. It gives us the name of the function in a pretty pretty format, including the template parameters, which we especially want.
Line 12: Here we create a container of int-s with our my::Allocator.
Line 14: This is the generic, container independent way of adding an element into an STL container. But there is a problem, and this code won’t compile. As stated above, our test function is expecting the ContainerT template parameter to be a template class with 2 parameters. The vector and list are such types, whereas the set is not. It has 3 parameters:
template <typename T,
typename CompareT = std::less<T>,
typename AllocatorT = std::allocator<T> >
class set;As a workaround, we can define a type alias:
Line 19–20: This type alias has only two template parameters, just like vector and list.
Finally, it compiles. And prints this:
It didn’t work. After debugging it’s easy to see that our shadowing functions are never being called. In fact, after a little more debugging it turns out that containers carry an instance of std::allocator instead of my::Allocator.
This happens because allocators are supposed to be so-called rebindable family types. This means, that even though std::allocator<T> and std::allocator<U> are completely different types, one is representable in
the other. That’s why std::allocator has such a constructor:
template <typename U>
allocator(const allocator<U>& other);But why is there such a heavy requirement on such a “useful” type? That’s because most of the STL containers force us to provide a specialized allocator type, like my::Allocator<int>, whereas they really need the first my::Allocator part only. We create an object, let’s say, of type std::vector<int, std::allocator<int> >, and we think the allocator instance in it is of type std::allocator<int>, whereas it is std::allocator<WHATEVER_I_WANT___TRUST_ME__I_KNOW_BETTER>. And he really does. In case of list it changes to std::allocator<LIST_NODE>, which (the LIST_NODE) is an internal class, inaccessible to us. Of course, it needs allocator to allocate memory for nodes, not only values. Same way, set's allocator is of some TREE_NODE type.
Back to our problem. We need to add so-called rebindability to our Allocator (lines 20–31).
This will compile and print this:
Perfect. The numbers are interestingly different, but every number has its explanation. We’ve inserted exactly 1000 elements into each container.
The vector has used 4096 bytes or 1024 int storage. That’s because the gcc vector has a growth factor of 2. Inserting 1000 elements in vector increased its capacity as such: 1 -> 2 -> 4 -> 8 -> ... -> 512 -> 1024. For msvc it’s different.
The list has used 24000 bytes or 24 bytes for each list node. It’s layout is roughly something like this:
struct list_node
{
list_node* m_previous;
list_node* m_next;
int m_value;
};The first two pointers are 8 bytes each, and even though int is only 4 bytes, struct padding makes it all 24. The same way, the set has used 40 bytes for each tree node. Keep in mind, this is a red-black tree node.
enum Color { RED, BLACK };struct rb_tree_node
{
Color m_color;
rb_tree_node* m_parent;
rb_tree_node* m_leftChild;
rb_tree_node* m_rightChild;
int m_value;
};Again, because of the padding, 5 8-bytes makes 40 bytes. Hopefully, this was helpful.
Source: Medium
The Tech Platform