Custom allocators

Hi everybody,

I was looking through custom allocators. For example std::set is defined as follows:

Code:

---

template < class Key, class Compare = less<Key>,
          class Allocator = allocator<Key> > class set;

---

What I find odd about this is that the allocator here apparently only allocates integer. A set will use an AVL tree or red-black tree internally, however, and each element inside a set will need more information than just the stored value. For example, each node in the tree will at least contain two child nodes.
Imagine a set of integers: the allocator will only be able to allocate integers. So how does it work internally? Does it allocate the tree's nodes simply by using "new", bypassing the allocator, and store a pointer to the allocated integer in the node?
That sounds to me as though it kind of defeats the purpose of the allocator, especially if it's used as optimization, for example using memory pools. Or am I missing something here?

Thanks in advance,
Evoex

O_o

The `std::set' class doesn't only allocate integers; it allocates whatever it wants by rebinding--with `allocator<???>::rebind'--the allocator to fit the purpose.

There are esoteric data structures that also match the standard requirements; they simply don't perform as well in the real world.

The containers can, basically, do whatever they want so long as the implementation matches the requirements.

However, in practice most implementations will inherit the mutated allocator by virtue of a proxy for the sake of simplicity. (Yes, that's actually one of the simpler ways.)

So then, if we pretend to expand the template inline we might have something like the following code.

Code:

---

set<int> a;
// ...
set<int, less<int>, allocator<int>> a;
// ...
set<int, less<int>, allocator<int>>: private set_base<int, less<int>, allocator<int>> a;
// ...
set<int, less<int>, allocator<int>>: private set_base<int, less<int>, allocator<int>>: public allocator<int>::rebind<set_base<int, less<int>, allocator<int>::node_type>::type a;

---

With such a mechanism we can see how the allocation works where facilities need to add a new node.

Code:

---

pair<iterator, bool> set<???>::insert(const value_type & f)
{
// ...
set<???>::node_type * loc(this->allocate(1));
this->construct(loc, f); // `loc' is now a constructed node type of `node_type' which is an unspecified structure or class
// ...
}

---

Soma

Ahh, that makes sense, thanks!

The reference I was looking at (allocator - C++ Reference) completely ignores rebind...


Thanks!

O_o

It's just as well. Many sources explain the concept incorrectly.

I think it is "The C++ Standard Library" by Nicolai M. Josuttis that you will want to read.

Soma

You're assuming that an allocator<Key> simply allocates Keys.

allocator<T> defines a templated rebind type. allocator<T>::rebind<U> is a struct type that contains a typedef named other. allocator<T>::rebind<U>::other is effectively a typedef for a SomeAllocator<U> (which is either an allocator<U> or some user supplied myallocator<U>). This means that, if the set is given a allocator<Key>, it can get any other allocator<U> to provide it services - such as memory allocation and deallocation - via rebind<U>::other.

Since the substitution happens at compile time (when templates are expanded) there should (depending on quality of compiler implementation) be no undue runtime overhead of an allocator<int> getting (say) an allocator<something_else> to provide it memory.

I'm not sure specifically about set, but this rebinding is critical to the working of std::list (which is typically akin to a single linked list). std::list<T> receives an allocator<T>, but is able to get an allocator<some_node<int> > to allocate memory for each node. I assume set does something along the same lines.